Question

Consider the following recursive mergesort algorithm (another classic divide and conquer algorithm). Mergesort was first described by John Von Neumann in 1945. The basic idea is to divide an unsorted list x of m elements into two sublists of about half the size of the original list. Repeat this operation on each sublist, and continue until we have lists of size 1 in length. Then starting with sublists of length 1, “merge” the two sublists into a single sorted list.

Mergesort(m)

var list left, right, result

if length(m) <= 1

return m

else

var middle = length(m) / 2

for each x in m up to middle

add x to left

for each x in m after middle

add x to right

left = Mergesort(left)

2

right = Mergesort(right)

result = Merge(left, right)

return result

}

The merge step is carried out by the following pesudocode:

Merge(left, right)

var list result

while length(left) > 0 and length(right) > 0

if first(left) <= first(right)

append first(left) to result

left = rest(left)

else

append first(right) to result

right = rest(right)

if length(left) > 0

append rest(left) to result

if length(right) > 0

append rest(right) to result

return result

}

6.5.1 [10] Assume that you have Y cores on a multi-core processor to run MergeSort. Assuming that Y is much smaller than length(m), express the speedup factor you might expect to obtain for values of Y and length(m). Plot these on a graph.

6.5.2 [10] Next, assume that Y is equal to length (m). How would this affect your conclusions in your previous answer? If you were asked with obtaining the best speedup factor possible (i.e., strong scaling), explain how you might change this code to obtain it.

Short answer

1. To obtain the speedup factor, 1+2+4+8+16+......+LOG₂(m) processors can be used.
2. If the length(m) is equal to the Y, then the speedup can be obtained without restructuring the code. To obtain the best speed-up factors for m cores, we can use other algorithms like parallel comparison sort,odd-even sort and cocktail sort.

Step-by-step solution

Merge Sort Algorithm

Merge sort is a recursive sorting algorithm used for sorting the elements in the list of arrays. The merge sort algorithm is a Divide and conquers algorithm. The divide and conquer algorithms divide the problem into two halves and solve the problem individually. In the merge sort algorithm, the given data is divided into two until the elements in the data became individual. After dividing the elements individually, using the merge algorithm the elements are bound back, and the resulting data will be sorted. If the data contains n elements then the time complexity of the algorithm will be O(n*Log n).

(6.5.1)Step 2: Speed factor if the Y is so much smaller than length(m)

As Merger sort is a divides and conquer algorithm. If there are Y cores on the processor and the data set is the length of m. As the merge sort divides the data into two halves and two threads were assigned to them. The algorithm further divides both halves into four halves and the process continues until it reaches the single element. Due to this process threads will be assigned exponentially.

If the Y is the core required for the data of the length of m. Then the Y can be written as below:

Y = 1+2+4+8+16+......+LOG₂(m)

The graph shows the relation between the number of cores required for the merge sort and the length of the data. The graph has no cores on the Y-axis and the length of the data on the X-axis.

(6.5.2)Step 3: Speed factor if the Y is equal to the length(m)

In, this scenario log₂(m) is the largest value of Y, so we can obtain any speedup without restructuring the code.

If m cores are considered, then the sorting can be done by the different algorithm.

For example, if we have greater than m/2 cores, then we can compare all pairs of data elements, swap the elements if the left element is greater than the right element and this will be repeated to m times. This is known as parallel comparison sort , that can be used.

Prallel Comparison sort:

function ParalleComparisonSort(left, right)

if List.core > 1 then

for(m > m/2; left >right;m++)

ParallelComparisonSort(Left,Right)

end if

end Procedure