Dana Vrajitoru
B424 Parallel and Distributed Programming

Program Decomposition

General Ideas

Code Decomposition

Decomposition Techniques

Characteristics of Tasks

Task generation:

Task size:

Task Interaction

Recursive Decomposition

Examples: QuickSort or MergeSort.

The MergeSort

Sequential MergeSort

void merge_sort(int a[], int first, int last, int aux[])
   if (last <= first)
   int mid = (first+last)/2;
   merge_sort(a, first, mid, aux);
   merge_sort(a, mid+1, last, aux);
   merge_arrays(a, first, mid, a, mid+1, last, aux, first, last);
   for (int i=first; i<=last; i++)
      a[i] = aux[i];

void merge_arrays(int a[], int afirst, int alast, int b[], int
bfirst, int blast, int c[], int cfirst, int clast)
{ // skip verification of size of c.
   int i=afirst, j=bfirst, k=cfirst;
   while (i<=alast && j<=blast) {
      if (a[i] < b[j])
         c[k++] = a[i++];
         c[k++] = b[j++];
   while (i<=alast)
      c[k++] = a[i++];
   while (j<=blast) 
      c[k++] = b[j++];

Parallel MergeSort

void parallel_merge_sort() 
   if (proc_id > 0) {
      Recv(size, parent);
      Recv(a, size, parent);
   mid = size/2;
   if (both children) {
      Send(mid, child1);
      Send(size-mid, child2);
      Send(a, mid, child1);
      Send(a+mid, size-mid, child2);
      Recv(a, mid, child1);
      Recv(a+mid, size-mid, child2);
      merge_arrays(a, 0, mid, a, mid+1, size, aux, 0, size);
      // declare aux local
      for (int i=first; i<=last; i++)
         a[i] = aux[i];
      merge_sort(a, 0, size);
   if (proc_id > 0)
      Send(a, size, parent); 

Data Decomposition