Question

Question: Many computer applications involve searching through a set of data and sorting the data. A number of efficient searching and sorting algorithms have been devised in order to reduce the runtime of these tedious tasks. In this problem we will consider how best to parallelize these tasks.

(6.3.1) Consider the following binary search algorithm (a classic divide and conquer algorithm) that searches for a value X in a sorted N-element array A and returns the index of matched entry:

BinarySearch(A[0..N-1], X) {

low=0

high=N-1

while(low<high) {

mid=(low<=high). {

mid = (low+high)/2

if (A[mid]>X)

high = mid -1

else if (A[mid]<X)

low=mid+1

else

return mid //found

}

return -1 //not found

}

Assume that you have Y cores on a multi-core processor to run BinarySearch. Assuming that Y is much smaller than N, express the speedup factor you might expect to obtain for values of Y and N. Plot these on a graph.

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

Short answer

(6.3.1)

No speedup will occur with Y much smaller than N.

(6.3.2)

The speedup can be achieved if the value of Y is equal to N. The best speedup equal to Y can be obtained by creating N threads.

Step-by-step solution

Analyzing Binary Search Algorithm

The binary search algorithm takes an array of size N and targets element X. The algorithm is only applicable tothe sorted list. The algorithm finds the mid of the array. It compares the element at the mid of the array with X. If the value of X is equal to the mid element, then X is found. If the value of X is less than the mid element, then the algorithm is applied only to the first half of the elements. Otherwise, on the second of the program.

Impact of executing a binary search on Y cores on a multi-core processor

It is given that the value of Y is much smaller than N, that is, the number of cores is comparatively much lesser than the total number of elements on which the search is to be performed. With very less cores, no speedup can be obtained. These multicores can be used to perform different operations like performing comparison on low and high, performing comparison on mid, etc. But this will not improve the speed of the algorithm because communication between cores also takes some time. So, no speedup will occur.

Impact of executing a binary search on Y cores equal to N

(6.3.2)

If the number of cores is equal to the number of elements in the array, the speedup can be achieved. But using the algorithm given in the question will not give the speedup. A different algorithm should be used to achieve speedup if the number of cores is the same as the elements.

Algorithm for binary search with N cores

The following code should be used to perform a binary search:

• Create N threads.

• Assign each thread an element from the array.

• Each thread compares the element with X.

The process is performed in parallel. Thus, it will take constant time to search the element X. The speedup of Y can be obtained.