0
$\begingroup$

There is an example problem from p506 of Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy enter image description here

I wonder how "potential speedup" is defined? The book doesn't give its definition.

In the example, since speedup with $10$ processors is $55\%$ of the potential speedup, the potential speedup should be $ 5.5 / 55\% = 10$. it is equal to the number of processors.

Since the execution time before improvement has a part $(10t)$ unaffectable by parallel computing on multiple processors, according to Amdahl's law (outlined in blue box), the potential speedup must be smaller than the number of processors.

So I am puzzled.

Google books has an earlier (4th) edition which has a similar example too.

$\endgroup$
  • 4
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Jan 29 '15 at 17:53
2
$\begingroup$

Potential speedup $\equiv$ number of processors. I agree that it is poorly chosen wording. A better term would be efficiency (the average amount of time that the processors are doing useful work.)

$\endgroup$
  • $\begingroup$ Thanks. The execution time before improvement has a nonzero part (10t) unaffectable by parallel computing on multiple processors, and according to Amdahl's law (outlined in blue box), the speedup must be smaller than the number of processors. So how does "efficiency (the average amount of time that the processors are doing useful work)" take that into account? $\endgroup$ – Tim Jan 29 '15 at 2:28
  • $\begingroup$ Efficiency runs from 0 to 1. 1 - efficiency is the percentage of available processor time that went unused because only one processor was working. $\endgroup$ – Wandering Logic Jan 29 '15 at 4:03
1
$\begingroup$

Since the execution time before improvement has a part (10t)(10t) unaffectable by parallel computing on multiple processors, according to Amdahl's law (outlined in blue box), the potential speedup must be smaller than the number of processors.

The potential speedup in the article means a number of processors, already answered. It means a speedup limit for a given PC for the case when the algorithm could be cut in parallel pieces unlimited.

For example, an algorithm has N independent parts for N processors. It never occurs in real life, but a theoretically example is - find N random numbers. Here our speedup is N, but the article's algorithm hasn't this property.

The Amdahl's law doesn't interfere directly with the potential speed term. It, in other words, states that when the task split, the summary execution time can't be less than the largest fragment. So, Amdahl's law uses only sequential computation time for program fragments as the statement objects, not a "potential speedup."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.