Consider the following binary search algorithm ( a classic divided and conquer a
ID: 3685088 • Letter: C
Question
Consider the following binary search algorithm ( a classic divided and conquer algorithm ) taht searches for a value X in a sorted N-element array A and returns the index of matched entry: BinarySearch ( A[0...N1], 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 } 1. 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 2.Next, assume that Y is equal to N. How would this affect your conclusions your previous answer? If you were tasked without obtaining the best speedup factor possible ( i.e. Strong scaling ), explain how you might change this code to obtain it.Explanation / Answer
>A binary search actually has very good serial performance and it is difficult to parallelize without modifying the code
>Increasing Y beyond 2 or 3 would have no benefits
>At best we could…
1.On core 1: perform the comparison between low and high
2.On core 2: perform the computation for mid
3.On core 3: perform the comparison for A[mid]
>Without additional restructuring, no speedup would occur o …and communication between cores is not “free”
>compare low=core 1
>Calculate mid =Core 2 Core 1 = CompareA[mid]=Core 3
>Compare high=core1
2)
>question suggest that the number of cores can be made equal to the number of array elements
>With current code, this will do no good
>Alternative approach is to:
1.Create threads to compare the N elements to the value X and perform these in parallel
2.Then, we can get ideal speed-up (Y)
3.Entire comparison can be completed in the amount of time to perform a single computation
>Probably not a great idea to design a processor architecture for just this problem o Especially as a binary search should take just log2N operations anyhow
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.