CSC 334 – Parallel and Distributed Computing

Instructor: Dr. M. Hasan Jamal

Lecture# 05: Parallel Algorithms

1
Problem
• Assume we have a 100-inch sandwich to feed 8 people.

• We know how many inches each person wants.

• [6 4 16 10 16 14 2 8]

• How do we cut the sandwich quickly? How much will be left?

• Method 1: cut the sections sequentially: 6 inches first, 4 inches second, 16

inches third, etc.

• Method 2: calculate Prefix sum and cut in parallel

2
• [6, 10, 26, 36, 52, 66, 68, 76] (24 inches left)
Prefix Sum (Scan)
• Given an array X, compute output array Y as follows:
𝑌 𝑖 = σ 𝑋 𝑗 for 0 ≤ 𝑗 ≤ 𝑖
𝑌0 = 𝑋0
𝑌1 = 𝑋0 + 𝑋1
𝑌2 = 𝑋0 + 𝑋1 + 𝑋2

Using recursive definition

𝑌𝑖 = 𝑌𝑖−1 + 𝑋𝑖

• Implementation: Y[0] = X[0];

for (i = 1; i < N; i++)
Y[i] = Y[i-1] + X[i];

• The above is an inclusive prefix sum since 𝑌 𝑖 includes X 𝑖 .

• Fo an exclusive prefix sum perform the summation for 0 ≤ 𝑗 < 𝑖 3

• It is easy to see that prefix sums can be computed sequentially in O(N) time
Naïve Inclusive Parallel Prefix Sum
• Assign one thread to calculate each 𝑌 element that adds up all X elements
needed for that Y element.
• 𝑌0 = 𝑋0
• 𝑌1 = 𝑋0 + 𝑋1
• 𝑌2 = 𝑋0 + 𝑋1 + 𝑋2

• Implementation:
#pragma omp parallel for
for (i = 0; i < N; i++){
Y[i] = 0;
for (j = 0; j <= i; j++)
Y[i] += X[j];
}
4
Naïve Inclusive Parallel Prefix Sum
10 26 36 52 66 68 76
6 4
10 16 26 10 36 16 52 14 66 2 68 8
6 4 52 14 66 2
10 16 26 10 36 16
6 4 36 16 52 14
10 16 26 10
6 4 26 10 36 16
10 16
6 4 10 26 10
16
• Observations: 6 4
10 16
• Total Work T1 (number of operations) = O(N2)
• Critical Path Length (CPL) = O(N) 6 4
• With P = O(N) processors, best achievable execution time is T1 = max(CPL, WORK/P) = O(N) 5

• Parallel programming is easy as long as you don’t care about performance.

Parallel Prefix Sum
• How to improve efficiency?
• Build a balanced binary tree on the input data and sweep it to and from the root
• Traverse up from leaves to root building partial sums at internal nodes in the tree
• Root holds sum of all leaves
• Traverse back down the tree building the scan from the partial sums

6
Parallel Prefix Sum: Upward Sweep
76
for (i = 0; i < n - 1; i++)
Y[i] = X[i]; 36 40
for (d = 1; d < n; d *= 2) {
#pragma omp parallel for 10 26 30 10
for (int i = 0; i < n; i += 2 * d) {
Y[i + 2 * d - 1] += Y[i + d - 1];
} 6 4 16 10 16 14 2 8
}

Step 6 4 16 10 16 14 2 8
d =1 6 10 16 26 16 30 2 10
d=2 6 10 16 36 16 30 2 40
7
d=4 6 10 16 36 16 30 2 76
Parallel Prefix Sum: Downward Sweep
0
Y[n-1] = 0;
for (d = n / 2; d >= 1; d /= 2) {
#pragma omp parallel for 0 36
for (int i = 0; i < n; i += 2 * d) {
int left = i + d - 1;
int right = i + 2 * d - 1; 0 10 36 66
temp = Y[left];
Y[left] = Y[right];
Y[right] += temp; 0 6 10 26 36 52 66 68
}
}

Step 6 10 16 36 16 30 2 76
0
d=4 6 10 16 0 16 30 2 36
d=2 6 0 16 10 16 36 2 66 8

d=1 0 6 10 26 36 52 66 68
Parallel Prefix Sum: Inclusive
for (i = 0; i < n; i++) {
Y[i] += X[i]; X 6 4 16 10 16 14 2 8
}

Y 0 6 10 26 36 52 66 68
Updated Y 6 10 26 36 52 66 68 76

• Observations:
• Critical Path Length (CPL) = O(log n)
• Total Work T1 (number of add operations) = O(N)
• Optimal algorithm for P = O(n / log n) processors
• Adding more processors does not help
• The total number of adds is no more than twice that done in the efficient sequential algorithm
• The benefit of parallelism can easily overcome the 2X work when there is sufficient hardware 9
Applications of Prefix Sum
• Parallel Prefix Sum has several applications that go way beyond computing the
• sum of array elements. A key primitive in many parallel algorithms to convert
serial computation into parallel computation
• Radix Sort
• String Comparison
• Lexical Analysis
• Stream Compaction
• Polynomial Evaluation
• Solving Recurrences
• Tree Operations
• Histograms
• Assigning space in farmers market
• Allocating memory to parallel threads
10
• Allocating memory buffer for communication channels
• Frequently used for parallel work assignment and resource allocation
Sorting in Parallel
• Why?
• It is a frequent operation in many applications

• Goal?
• Sorting a sequence of values in increasing order using n processors

11
Bubble Sort
• Idea: Given a list of n elements, repeat the following steps n -1 times:
• For each pair of adjacent numbers, if number on the left is greater than the number
on the right, swap them.
• “Bubble” the largest element to the end of the array using pair-wise comparisons
and swapping.

BUBBLE-SORT(A)
n ← length[A]
for i ← 0 to n – 2
for j ← 0 to n – i – 2
if A[ j ] > A[ j+1 ]
A[ j ] ↔ A[ j+1 ]

12
• Time complexity is O(N2) independent of the order of the elements.
Parallel Bubble Sort: Odd-Even Sort
• Idea: Rearrange the comparisons in as many independent comparisons as
possible!

• Observation: Comparisons can be carried out in parallel if every processor is

involved in at most one compare-and-exchange.

• This can be achieved if the processors are grouped into even/odd pairs or
odd/even pairs
• Odd–Even Phase: The odd processes p compare and exchange their elements
with the even processors p + 1
• Even–Odd Phase: The even processes compare and exchange their elements with
the odd processors p + 1
13
Odd-Even Sort

4 2 7 8 5 1 3 6

2 4 7 8 1 5 3 6

2 4 7 1 8 3 5 6

2 4 1 7 3 8 5 6

2 1 4 3 7 5 8 6

1 2 3 4 5 7 6 8
14

1 2 3 4 5 6 7 8
Odd-Even Sort
OddEvenSort(A)
n = length[A]
for (i = 0; i <= n - 1; i++)
if( i%2 == 0)
#pragma omp parallel for
for (j = 0; j <= n - 2; i+=2)
if A[j] > A[j+1]
A[j] ↔ A[j+1]
else
#pragma omp parallel for
for (j = 1; j <= n - 2; i+=2)
if A[j] > A[j+1]
15
A[j] ↔ A[j+1]
barrier();
Odd-Even Sort
• Assuming array size n and p threads
• (assuming p ≤ n/2, i.e., each processor handles multiple comparisons)

• For each phase (odd and even)

• Comparisons  n/2
• Comparisons per thread  n/(2p)

• Time per phase = O(n/p)

• Number of phases = O(n)
• Total time = O(n2/p)

• Theoretical speedup  O(p) linear with p for small p

16
• But due to synchronization overhead (barriers), actual speedup is less than ideal.
Merge Sort
• Idea: Recursively divide a given unsorted list of n elements until each sublist
contains one element. Then these sublists are repeatedly merged to form a
sorted list.
9 3 17 11 6 2 1 10

9 3 17 11 6 2 1 10
divide

9 3 17 11 6 2 1 10

9 3 17 11 6 2 1 10

3 9 11 17 2 6 1 10
merge

3 9 11 17 1 2 6 10 17

1 2 3 6 9 10 11 17
Merge Sort
• Idea: Recursively divide a given unsorted list of n elements until each sublist
contains one element. Then these sublists are repeatedly merged to form a
sorted list.
MERGE-SORT(A, left, right) MERGE (A, left, mid, right)
if left < right i = left, j = mid+1, k=0
mid = (𝑙𝑒𝑓𝑡 + 𝑟𝑖𝑔ℎ𝑡)/2 while (i ≤ 𝑚𝑖𝑑 && 𝑗 ≤ right)
MERGE-SORT(A, left, mid) if (A[i] ≤ A[j])
MERGE-SORT(A, mid+1, right) B[k++] = A[i++]
MERGE (A, left, mid, right) else
B[k++] = A[j++]
A[ ] = B[ ]

• Time complexity is O(N lg N) independent of the order of the elements. 18

Parallel Merge Sort
• Idea: A new worker thread is created to execute the left sub-array and the right
sub-array will be executed by the calling thread.

MERGE-SORT(A, left, right) MERGE (A, left, mid, right)

if left < right i = left, j = mid+1, k=0
mid = (𝑙𝑒𝑓𝑡 + 𝑟𝑖𝑔ℎ𝑡)/2 while (i ≤ 𝑚𝑖𝑑 && 𝑗 ≤ right)
if (A[i] ≤ A[j])
Spawn MERGE-SORT(A, left, mid) B[k++] = A[i++]
MERGE-SORT(A, mid+1, right) else
B[k++] = A[j++]
Sync A[ ] = B[ ]
MERGE (A, left, mid, right)
19
 Parallel Merge Sort
P0

9 3 17 11 6 2 1 10
P1 P0
9 3 17 11 6 2 1 10
P2 P1 P3 P0
9 3 17 11 6 2 1 10

9 3 17 11 6 2 1 10 P4 P2 P5 P1 P6 P3 P7 P0

3 9 11 17 2 6 1 10
P2 P1 P3 P0
3 9 11 17 1 2 6 10
P1 P0
1 2 3 6 9 10 11 17
20
P0
Odd-Even Merge Sort
• A parallel approach to sorting based on the recursive application of the odd-
even merge algorithm, to speed up the merge process.

• The odd-even merge algorithm merges sorted sub-lists in a bottom-up manner

starting with sublists of size 2 and merging them into larger lists until the final
sorted list is obtained.

• The odd-even-merge operates on two alternating phases

• Even phase - Even-numbered processes exchange values with their right neighbor.
• Odd phase - Odd-numbered processes exchange numbers with their right neighbor.

21
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 9 3 17 11 6 2 1 10

22
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

23
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 11 9 17 2 1 6 10

24
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 11 9 17 2 1 6 10

25
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 9 11 17 2 1 6 10

26
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 9 11 17 2 1 6 10

27
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 9 11 17 1 2 6 10

28
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 9 11 17 1 2 6 10

29
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 9 11 17 1 2 6 10

3 1 9 2 11 6 17 10

30
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 9 11 17 1 2 6 10

3 1 9 2 11 6 17 10

31
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 9 11 17 1 2 6 10

1 3 2 9 6 11 10 17

32
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 9 11 17 1 2 6 10

1 3 2 9 6 11 10 17

33
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 9 11 17 1 2 6 10

1 2 3 6 9 10 11 17

34
Odd-Even Merge Sort
• Step 1: Recursive Division 9 3 17 11 6 2 1 10

• Step 2: Odd-Even Merge 9 3 17 11 6 2 1 10

• Interleave
• Compare and Swap 3 9 11 17 2 6 1 10

3 9 11 17 1 2 6 10

1 2 3 6 9 10 11 17

Total Work: O(n log2 n)

Parallel Time (Depth): O(log2 n) 35

Quick Sort
• Idea: Use a pivot and partition the array into two parts. Sort each of them
recursively.

QUICK-SORT(A, left, right) PARTITION (A, left, right)

if left < right pivot = A[low]
mid = PARTITION(A, left, right) i = low +1
QUICK-SORT(A, left, mid-1) for (j = low + 1 ; j ≤ high; j++) {
QUICK-SORT(A, mid+1, right) if (A[j] < pivot) {
A[i] ⟺ A[j]
i++;
}
}
A[low] ⟺ A[i – 1]
return i – 1
36

• Time complexity is O(N lg N) and O(N2) in average and worst case, respectively.
Parallel Quick Sort
• Idea: Use a pivot and partition the array into two parts. Sort each of them
recursively, in parallel.

QUICK-SORT(A, left, right) PARTITION (A, left, right)

if left < right pivot = A[low]
mid = PARTITION(A, left, right) i = low +1
Spawn QUICK-SORT(A, left, mid-1) for (j = low + 1 ; j ≤ high; j++) {
QUICK-SORT(A, mid+1, right) if (A[j] < pivot) {
Sync A[i] ⟺ A[j]
i++;
}
}
A[low] ⟺ A[i – 1]
return i – 1
37
Parallel Quick Sort
• Step 1: Choose a Pivot 9 3 17 11 6 2 1 10 pivot = 9

38
Parallel Quick Sort
• Step 1: Choose a Pivot 9 3 17 11 6 2 1 10 pivot = 9

• Step 2: Create Boolean Masks Is_less

0 1 0 0 1 1 1 0
in Parallel
1 0 1 1 0 0 0 1 Is_more

39
Parallel Quick Sort
• Step 1: Choose a Pivot 9 3 17 11 6 2 1 10 pivot = 9

• Step 2: Create Boolean Masks Is_less

0 1 0 0 1 1 1 0
in Parallel
1 0 1 1 0 0 0 1 Is_more
• Step 3: Compute Prefix Sums
(exclusive)

0 0 1 1 1 2 3 4 prefix_less

0 1 1 2 3 3 3 3 prefix_more

total_less = 4
40
Parallel Quick Sort
• Step 1: Choose a Pivot 9 3 17 11 6 2 1 10 pivot = 9

• Step 2: Create Boolean Masks Is_less

0 1 0 0 1 1 1 0
in Parallel
1 0 1 1 0 0 0 1 Is_more
• Step 3: Compute Prefix Sums
(exclusive)

• Step 4: Scatter Values to 0 0 1 1 1 2 3 4 prefix_less

Output Array
0 1 1 2 3 3 3 3 prefix_more
if A[i] < pivot
output[prefix_less[i]] = A[i]; total_less = 4
else 41
output[total_less + prefix_more[i]] = A[i];
Parallel Quick Sort
• Step 1: Choose a Pivot 9 3 17 11 6 2 1 10 pivot = 9

• Step 2: Create Boolean Masks Is_less

0 1 0 0 1 1 1 0
in Parallel
1 0 1 1 0 0 0 1 Is_more
• Step 3: Compute Prefix Sums
(exclusive)

• Step 4: Scatter Values to 0 0 1 1 1 2 3 4 prefix_less

Output Array
0 1 1 2 3 3 3 3 prefix_more
if A[i] < pivot
output[prefix_less[i]] = A[i]; 9 total_less = 4
else 42
output[total_less + prefix_more[i]] = A[i];
Parallel Quick Sort
• Step 1: Choose a Pivot 9 3 17 11 6 2 1 10 pivot = 9

• Step 2: Create Boolean Masks Is_less

0 1 0 0 1 1 1 0
in Parallel
1 0 1 1 0 0 0 1 Is_more
• Step 3: Compute Prefix Sums
(exclusive)

• Step 4: Scatter Values to 0 0 1 1 1 2 3 4 prefix_less

Output Array
0 1 1 2 3 3 3 3 prefix_more
if A[i] < pivot
output[prefix_less[i]] = A[i]; 3 9 total_less = 4
else 43
output[total_less + prefix_more[i]] = A[i];
Parallel Quick Sort
• Step 1: Choose a Pivot 9 3 17 11 6 2 1 10 pivot = 9

• Step 2: Create Boolean Masks Is_less

0 1 0 0 1 1 1 0
in Parallel
1 0 1 1 0 0 0 1 Is_more
• Step 3: Compute Prefix Sums
(exclusive)

• Step 4: Scatter Values to 0 0 1 1 1 2 3 4 prefix_less

Output Array
0 1 1 2 3 3 3 3 prefix_more
if A[i] < pivot
output[prefix_less[i]] = A[i]; 3 6 9 17 11 total_less = 4
else 44
output[total_less + prefix_more[i]] = A[i];
Parallel Quick Sort
• Step 1: Choose a Pivot 9 3 17 11 6 2 1 10 pivot = 9

• Step 2: Create Boolean Masks Is_less

0 1 0 0 1 1 1 0
in Parallel
1 0 1 1 0 0 0 1 Is_more
• Step 3: Compute Prefix Sums
(exclusive)

• Step 4: Scatter Values to 0 0 1 1 1 2 3 4 prefix_less

Output Array
0 1 1 2 3 3 3 3 prefix_more
if A[i] < pivot
output[prefix_less[i]] = A[i]; 3 6 2 1 9 17 11 10 total_less = 4
else 45
output[total_less + prefix_more[i]] = A[i];
Parallel Quick Sort
• Step 1: Choose a Pivot 9 3 17 11 6 2 1 10

• Step 2: Create Boolean Masks

3 6 2 1 9 17 11 10
in Parallel
pivot = 3 pivot = 17
• Step 3: Compute Prefix Sums
(exclusive) 2 1 3 6 9 11 10 17

⋮
• Step 4: Scatter Values to
Output Array 1 2 3 6 9 10 11 17

Total Work: O(n log n)

Partition Step (Parallel Prefix Scan): O(log n) 46

Parallel Time (Depth): O(log2 n)

Shell Sort
• Idea: Generalization of insertion sort by allowing exchanges of far-apart
elements. It works by:
• Starting with a large gap (interval between elements being compared),
• Sorting elements at that gap using insertion sort,
• Gradually reducing the gap until it becomes 1 (normal insertion sort).

47
Shell Sort
ShellSort(A)
n = length[A];
for (gap = n/2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
key = A[i];
j = i;
while(j > gap – 1 && A[j – gap] > key)
A[j] = A[j – gap];
j = j – H;
A[j] = key;

Gap Sequence: {n/2, n/4, … 1}

9
6
1 3
2 17 11
1 10
6
3 3
6 6
9 2
10 1 10
3 17
11 11
17
11 1
Gap = 4
2 48
Parallel Shell Sort
ShellSort(A)
n = length[A];
for (gap = n/2; gap > 0; gap /= 2)
#pragma omp parallel for shared(A, n, gap)
for (i = gap; i < n; i++)
key = A[i];
j = i;
while(j > gap – 1 && A[j – gap] > key)
A[j] = A[j – gap];
Total Work: O(n log2 n)
j = j – H;
Best Case: O((n/p) log n)
A[j] = key;
Worst Case: O(n2/p)

Gap Sequence: {n/2, n/4, … 1}

49
9
6
1 3
2 17 11
1 10
6
3 3
6 6
9 2
10 1 10
3 17
11 11
17
11 1
Gap = 4
2