Dana Vrajitoru
B424/B524 Parallel and Distributed Programming

B424/B524 Class Exercise 2

Date: Thursday, October 8, 2020.

Ex. 1 Applying divide and conquer

Here is the function bucket sort that you may have seen in C243.

const unsigned int m = largest(array) + 1;
void bucketSort(unsigned int a[], unsigned int n)
{
    int buckets[m], i, j, k;
    for (j = 0; j < m; j++)
        buckets[j] = 0;
    for (i = 0; i < n; i++)
        buckets[a[i]]++;
    for (i = 0, j = 0; j < m; j++)
        for (k=0; k < buckets[j]; k++)
            a[i++] = j;
} // bucketSort()
The bucket sort works with the idea of counting how many times each value occurs in the array, and storing that information in the buckets. Then it reconstructs the original array from the buckets. Here is an illustration of this operation:

a. Examine each of the 3 for loops and decide whether they can be done in parallel and how you would divide them between processes or threads.

b. Is there a need for any barriers between them?

a. What difference would it make if this was implemented with pthreads or with MPI (shared memory or distributed)?

Upload to Canvas:

Upload a file with the answers to points a, b, and c to Canvas, Assignments, Exercise 2, or type it directly in the submission input box.