FibonacciNumbers

In this section, we will construct a parallel version of a program that calculates the nth Fibonacci number using what we have learned in the previous sections. To save space, the example is constructed in C.

Parallelizing Fibonacci

Consider the serial version of fibonacci numbers shown below:

int serial_fib (int n) {
  if (0 == n || 1 == n) return n;
  else {
    int x, y;
    x = serial_fib (n-1);
    y = serial_fib (n-2);

    return x+y;
  }
}

The function serial_fib recursively divides the task of calculating the Nth Fibonacci number (for N >= 2), into the tasks of calculating the N-1st and the N-2nd Fibonacci numbers. As the tasks of calculating the N-1st and the N-2nd Fibonacci numbers are independent of one another, they can be executed in parallel. To parallelize the execution of this function using PFunc, we have to first change serial_fib's signature to match PFunc's accepted void ()(void) prototype. This transformation can be achieved by means of a C-struct. This is demonstrated below:

typedef struct { int n; int fib_n; } fib_t;

void serial_fib (void* arg) {
  fib_t* fib_arg = (fib_t*) arg;

  if (0 == fib_arg->n || 1 == fib_arg->n) fib_arg->fib_n = fib_arg->n;
  else {
    fib_t x = {fib_arg->n-1, 0};
    fib_t y = {fib_arg->n-2, 0};

    serial_fib (&x);
    serial_fib (&y);

    fib_arg->fib_n = x->fib_n + y->fib_n;
  }
}

The above version of serial_fib is now ready to be parallelized using PFunc. First, we note the following properties about serial_fib. First, as it does not require setting of any special attributes, we can use the default value of NULL. Second, serial_fib is not a SPMD-style program, groups are not needed (i.e., NULL can be used). With the following in mind, we arrive at the new definition, which we now call parallel_fib.

void parallel_fib (void* arg) {
  fib_t* fib_arg = (fib_t*) arg;

  if (0 == fib_arg->n || 1 == fib_arg->n) fib_arg->fib_n = fib_arg->n;
  else {
    pfunc_cilk_task_t fib_task_1;
    pfunc_cilk_task_t fib_task_2;
    fib_t x = {fib_arg->n-1, 0};
    fib_t y = {fib_arg->n-2, 0};

    pfunc_cilk_task_init (&fib_task_1);
    pfunc_cilk_task_init (&fib_task_2);

    pfunc_cilk_spawn_c_gbl (fib_task_1, NULL, NULL, parallel_fib, &x);
    pfunc_cilk_spawn_c_gbl (fib_task_2, NULL, NULL, parallel_fib, &x);

    pfunc_cilk_wait_gbl (fib_task_1);
    pfunc_cilk_wait_gbl (fib_task_2);

    pfunc_cilk_task_clear (&fib_task_1);
    pfunc_cilk_task_clear (&fib_task_2);

    fib_arg->fib_n = x->fib_n + y->fib_n;
  }
}

In this version, we have parallelized the execution of parallel_fib for the non-base cases using PFunc. In our case, we have used Cilk-style scheduling. Queue-based or Stack-based scheduling could very well have been used instead. Although the current version of parallel_fib has been parallelized, it is sub-optimal. When a thread is executing a non-base case of parallel_fib, it is not necessary to spawn two tasks; it is sufficient to spawn one of the tasks and execute the other serially. In effect, this will result in the same degree of parallelization without the cost of an additional task spawn. This version of parallel_fib is given below:

void parallel_fib (void* arg) {
  fib_t* fib_arg = (fib_t*) arg;

  if (0 == fib_arg->n || 1 == fib_arg->n) fib_arg->fib_n = fib_arg->n;
  else {
    pfunc_cilk_task_t fib_task;
    fib_t x = {fib_arg->n-1, 0};
    fib_t y = {fib_arg->n-2, 0};

    pfunc_cilk_task_init (&fib_task);

    pfunc_cilk_spawn_c_gbl (fib_task, NULL, NULL, parallel_fib, &x);
    parallel_fib (&y);

    pfunc_cilk_wait_gbl (fib_task);
    pfunc_cilk_task_clear (&fib_task);

    fib_arg->fib_n = x->fib_n + y->fib_n;
  }
}

Setting up the rest of the program

Once the final version of parallel_fib is ready, we proceed to setting up the rest of the program. This consists of initializing PFunc and spawning the first parallel_fib. The code for this is given below:

int main (int argc, char** argv) {
  pfunc_cilk_task_t root_task;
  unsigned int num_queues = 4;
  const unsigned int num_threads_per_queue[] = {1,1,1,1};
  pfunc_cilk_taskmgr_t cilk_tmanager;
  fib_t fib = {35, 0};

  /* Initialize the cilk run time */
  pfunc_cilk_taskmgr_init (&cilk_tmanager, num_queues, num_threads_per_queue, NULL);

  /* Make this instance global */
  pfunc_cilk_init (&cilk_tmanager);

  /* Spawn the first task */
  pfunc_cilk_task_init (&root_task);
  pfunc_cilk_spawn_c_gbl (root_task, NULL, NULL, parallel_fib, &fib);

  /* Wait for the tasks and clear the task handle */
  pfunc_cilk_wait_gbl (root_task);
  pfunc_cilk_task_clear (&root_task);
  
  /* Clear the global runtime */  
  pfunc_cilk_clear ();  
  
  /* Clear the Cilk runtime */  
  pfunc_cilk_taskmgr_clear (&cilk_tmanager);

  return 0;
}

In the above example, we have set up Cilk-style Pfunc runtime with 4 task queues and 1 thread per task queue. In essence, each threads owns its own task queue. Giving each thread its own queue is typical of Cilk-style scheduling and is highly recommended. Such a setup minimizes the contention on the task queues when the programs being parallelized are deeply nested (for example, the fibonacci program). Furthermore, in deeply nested parallel programs, Cilk-style work-stealing setup with one task queue per thread minimizes the chances of thread stack space explosion. Finally, we initialize the root task and launch it to calculate the 35th Fibonacci number. At the end of the wait (pfunc_cilk_wait_gbl), fib->fib_n contains the 35th Fibonacci number.

Runtime details

In the Fibonacci example, the root task is launched from the main thread of execution. This thread is not a part of PFunc's runtime and therefore is not used to execute the spawned task. The call to pfunc_cilk_wait_gbl from the main thread turns into a sleep until the task is completed. When the main thread spawns a task (eg., the root task), it is put on the task queue numbered 0. Since there has to be at least one task queue in every PFunc runtime, queue number 0 always exists. Alternately, the task attributes can be used to directly specify the queue on which the task needs to be enqueued. From here, the task is picked up and executed by thread 0, which is assigned to queue 0. At this point, the other threads (1,2 and 3) have no tasks enqueued on their task queues and consequently, are looking to steal tasks from one another. The main task (parallel_fib with N = 35) gives rise to more tasks. By default, these new tasks are spawned on the queue of the owning thread (task queue 0). At this point, threads 1, 2 and 3 bootstrap by stealing their first task from queue 0. As execution of parallel_fib is deeply nested, stealing one task gives rise to many other tasks that keep each thread busy. Therefore, very few steals are necessary.