Many computer applications involve searching through a set of data and sorting the data. A number of effi cient 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.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 = 0high = N −1while (low <= high) {mid = (low + high) / 2if (A[mid] >X)high = mid −1else if (A[mid] <X)low = mid + 1elsereturn 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.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.
Many computer applications involve searching through a set of data and sorting the data. A number of effi cient 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.
Consider the following binary search
BinarySearch(A[0..N−1], X) {
low = 0
high = N −1
while (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.
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.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 3 images
