[Threads] Solution 7 : Reduction

This material is part of the course Practical Introduction to Parallel Programming and meant for educational purposes only.

Task

Implement a struct reductiont that can be used to perform a global reduction operation – like a global sum – across multiple threads.

That is, this data type should enable multiple threads to provide a local value (of type double) and obtain the global reduction of all local values.

You must implement the following functions: reduction_init, reduction_destroy`, ``reduction_sum.

/* red INOUT A pointer to the reduction variable to be initialised.                */
/* nt  IN    The number of threads that will participate in a reduction operation. */

void reduction_init ( reduction_t* red, int nt );

The function reduction_init` initialises a reduction variable. That is, it initialises the members of the struct reduction_t; more about this later.

It must be called before a reduction operation can be performed.

The parameter nt specifies the number of threads that will participate in a reduction operation. This will be the number of threads calling the function reduction_sum.

/* red INOUT A pointer to the reduction variable to be destroyed.                  */

void reduction_destroy ( reduction_t* red );

The function reduction_destroy destroys a reduction variable.

It must be called when a reduction variable is no longer needed. Each call to reduction_init must be paired with a call to reduction_destroy.

/* red IN A pointer to a reduction variable.                                       */
/* val IN The local value to be summed.                                            */

double reduction_sum ( reduction_t* red, double val );

The function reduction_sum performs a global sum across all threads.

The parameter val is the local value to be added to the global sum. The return value is the global sum.

This function waits until it has been called by the number of threads indicated by the nt parameter of the reduction_init function.

The struct reduction_t must contain at least a mutex, a condition variable and a double storing the result of the reduction operation (global sum in this case).

You need more members; that is for you to figure out.

Test the program by spawning multiple threads and by performing at least four global reduction operations in succession. Check whether the computed results are correct.

Paste this command into your terminal:

The password to connect is

Question 1: Reduction

#include <stdio.h>
#include <assert.h>
#include <pthread.h>

/* ---------------------------------------------------------------------
 * types & constants
 * ------------------------------------------------------------------ */

#define                   NTHREADS  9

/* Note that the member "cycle" flip flops between 0 to 1. It is
 * there to ensure that two successive reduction operations do not
 * interfere with each other. The last thread joining a reduction
 * operation is the one that flips the "cycle" member. */

struct                    reduction
{
  pthread_mutex_t           mutex;
  pthread_cond_t            cond;
  int                       nthreads;
  int                       cycle;
  int                       tcount[2];
  double                    result[2];
};

/* The struct "data" is used to pass data from the main thread to
 * each child thread. */

struct                    data
{
  int                       rank;
  struct reduction*         red;
};

typedef struct reduction  reduction_t;
typedef struct data       data_t;

/* ---------------------------------------------------------------------
 * reduction_init()
 *
 *   Initialises a reduction variable. The parameter "nt" specifies
 *   the number of threads that will participate in a reduction
 *   operation.
 * ------------------------------------------------------------------ */

void                      reduction_init

  ( reduction_t*            red,
    int                     nt )

{
  assert ( red && (nt > 0) );

  pthread_mutex_init ( &red->mutex, NULL );
  pthread_cond_init  ( &red->cond,  NULL );

  red->nthreads  = nt;
  red->cycle     = 0;
  red->tcount[0] = 0;
  red->tcount[1] = 0;
  red->result[0] = 0.0;
  red->result[1] = 0.0;
}

/* ---------------------------------------------------------------------
 * reduction_destroy()
 *
 *   Destroys a reduction variable.
 * ------------------------------------------------------------------ */

void                      reduction_destroy

  ( reduction_t*            red )

{
  assert ( red );

  pthread_mutex_destroy ( &red->mutex );
  pthread_cond_destroy  ( &red->cond );

  red->nthreads = 0;
}

/* ---------------------------------------------------------------------
 * reduction_sum()
 *
 *   Calculates a global sum across multiple threads. The number
 *   of threads calling this function must be equal to the
 *   parameter "nt" specified in the call to the reduction_init()
 *   function.
 * ------------------------------------------------------------------ */

double                    reduction_sum

  ( reduction_t*            red,
    double                  val )

{
  assert ( red && (red->nthreads > 0) );

  /* Store the current cycle in a local variable. This is essential
   * as the last thread will change the cycle. */

  int     cycle = red->cycle;
  double  result;

  pthread_mutex_lock ( &red->mutex );

  if ( red->tcount[cycle] == 0 )
  {
    /* This is the first thread. */

    red->result[cycle]  = val;
  }
  else
  {
    red->result[cycle] += val;
  }

  red->tcount[cycle]++;

  if ( red->tcount[cycle] < red->nthreads )
  {
    /* Wait for the last thread. */

    while ( red->tcount[cycle] < red->nthreads )
    {
      pthread_cond_wait ( &red->cond, &red->mutex );
    }
  }
  else
  {
    /* This is the last thread. Prepare the next cycle and wake the
     * other threads. */

    red->cycle              = (red->cycle + 1) % 2;
    red->tcount[red->cycle] = 0;

    pthread_cond_broadcast ( &red->cond );
  }

  result = red->result[cycle];

  pthread_mutex_unlock ( &red->mutex );

  return result;
}

/* ---------------------------------------------------------------------
 * thread_func()
 *
 *   The thread entry point. This function performs a number of
 *   reduction operations.
 * ------------------------------------------------------------------ */

void*                     thread_func

  ( void*                   arg )

{
  data_t*       data = (data_t*) arg;
  reduction_t*  red  = data->red;
  int           rank = data->rank;

  double        result[4];
  double        value [4];
  double        answer[4];
  int           i;

  for ( i = 0; i < 4; i++ )
  {
    value [i]  = (double) (i + rank);
    answer[i]  = (double) (i * NTHREADS +
                           (NTHREADS * (NTHREADS - 1) / 2));
    result[i] = reduction_sum ( red, value[i] );
  }

  for ( i = 0; i < 4; i++ )
  {
    printf ( "thread %d: value[%d] = %g, result[%d] = %g, "
             "answer[%d] = %g\n",
             rank, i, value[i], i, result[i], i, answer[i] );
  }

  return NULL;
}

/* ---------------------------------------------------------------------
 * main()
 * ------------------------------------------------------------------ */

int                       main

  ( int                     argc,
    char**                  argv )

{
  pthread_t    threads[NTHREADS];
  data_t       data   [NTHREADS];
  reduction_t  red;
  int          i;

  reduction_init ( &red, NTHREADS );

  for ( i = 0; i < NTHREADS; i++ )
  {
    data[i].rank = i;
    data[i].red  = &red;

    pthread_create ( &threads[i], NULL, thread_func, &data[i] );
  }

  for ( i = 0; i < NTHREADS; i++ )
  {
    pthread_join ( threads[i], NULL );
  }

  reduction_destroy ( &red );

  return 0;
}

Question 2: Command Line Argument

Specify the command line arguments that should be passed to your program when it is run. Arguments must be given in quotes and separated by commas. Leave this filed empty if you do not want to specify command line arguments.

Example: "1","int","arg=2" is interpreted as three arguments 1, int, and arg=2.

Author(s)	Erik-Jan Lingen, Matthias Möller
Deadline	Καμία προθεσμία
Submission limit	No limitation

Information

Συνδεθείτε