Consider the following binary search algorithm (a classic divide and conquer algorithm) that searches for a value
Question:
Consider the following binary search algorithm (a classic divide and conquer algorithm) that searches for a value X in an sorted N-element array A and returns the index of matched entry:
Assume that you have Y cores on a multi-core processor to run Binary Search. 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.
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.
Binary Search (A[0..N-1], X) { low = 0 high = N - 1 while (low <= high) { mid (low if (A[mid] > X) high else if (A[mid] < X) low = mid + 1 } else high) / 2 mid - 1 return mid // found } return -1 // not found
Step by Step Answer:
Heres a breakdown of the expected speedup factor and a plotted graph Speedup Factor Ideal Speedup In ...View the full answer
Computer Organization And Design The Hardware Software Interface
ISBN: 9780123747501
4th Revised Edition
Authors: David A. Patterson, John L. Hennessy
Students also viewed these Computer science questions
-
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...
-
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...
-
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...
-
A company estimates that the marginal cost (in dollar per item) of producing x items is 1.73 - 0.004x. if the cost of producing one item is $566, find the cost of producing 100 items. (Round your...
-
In 2003, Weyco, Inc., gave employees a 15-month advance warning of a new policy that went into effect on January 1, 2005. The policy prohibited employees from smoking, on or off the job. The company...
-
Addition and subtraction. Simplify. 3ax - 2x + 1 - 3 + 3x - 4ax
-
The ratio of indicated thermal efficiency to air standard efficiency is called (a) volumetric efficiency (b) thermal efficiency (c) mechanical efficiency (d) relative efficiency
-
The Huber Batting Company manufactures wood baseball bats. Hubers two primary products are a youth bat, designed for children and young teens, and an adult bat, designed for high school and...
-
ed k Lucido Products markets two computer games: Claimjumper and Makeover. A contribution format income statement for a recent month for the two games appears below: Sales Variable expenses...
-
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...
-
If on average we need to access memory once every 75 cycles, what is impact on our application? On a CC-NUMA system, the cost of accessing non-local memory can limit our ability to utilize...
-
Determine whether the statement is true or false. Rewrite each false statement to make it a true statement. A false statement can be modified in more than one way to be made a true statement. p is a...
-
Describe a Cyber Piracy case that you were not aware of. What was the outcome? Was the penalty fair in your opinion? Was there a cost to society for this crime?
-
Describe the main trade-off that must be made between distribution and other logistics activities?
-
Describe the relationship between law and ethics, and analyze how legal and ethical requirements influence the managers' activities including but not limited to the following.
-
Fill in the Table below (note: this is just for practice - you can copy this and try fill the values just for practice): # of Workers Total Product P of Output Wage Rate VMP 0 $5 $400 1 $5 $400 2 $5...
-
Describe how much money Bangladesh Bank supply in 2018, 2019, 2020, 2021, 2022 And what is their impact on Bangladesh economy such as : inflation, bank interest rate, Unemployment, forex Reserve etc...
-
A standard setter recently made a private remark that conservatism was a "barbaric relic" that violated the "neutrality" requirement of accounting information and that financial statements would be...
-
Explain the buyers position in a typical negotiation for a business. Explain the sellers position. What tips would you offer a buyer about to begin negotiating the purchase of a business?
-
In the previous problem, we used the Poisson distribution to find the probability of generating x number of frames, in a certain period of time, in a pure or slotted Aloha network as p[x] = (e x...
-
Which of the following is a channelization protocol? a. ALOHA b. Token-passing c. CDMA
-
In the previous problem, we found that the probability of a station (in a G-station network) successfully sending a frame in a vulnerable time is P = e 2G for a pure Aloha and P = e G for a slotted...
-
Review one of the clinical personality measures (i.e., Minnesota Multiphasic Personality Inventory-2, Millon Clinical Mutliaxial Inventory-III, Personality Assessment Inventory, Revised NEO...
-
the Jordan family has a health insurance policy with the following characteristics: a. Deductible: $1,000 b. Coinsurance Provision: 80%/20% c. Out of Pocket Maximum: $5,000 If total health expenses...
-
- Betty tried to find derivative of an exponential function f(x) = e2x+4. At first glance, she thoughtf'(x) = (2x + 4)e2x+3. Explain why this is not the derivative of the function and state the...
Study smarter with the SolutionInn App