Description
Amdahl's law is a model for the relationship between the expected speedup of parallelized implementations of an algorithm relative to the serial algorithm, under the assumption that the problem size remains the same when parallelized. For example, if for a given problem size a parallelized implementation of an algorithm can run 12% of the algorithm's operations arbitrarily quickly (while the remaining 88% of the operations are not parallelizable), Amdahl's law states that the maximum speedup of the parallelized version is 1/(1 – 0.12) = 1.136 times as fast as the non-parallelized implementation.
More technically, the law is concerned with the speedup achievable from an improvement to a computation that affects a proportion P of that computation where the improvement has a speedup of S. (For example, if 30% of the computation may be the subject of a speed up, P will be 0.3; if the improvement makes the portion affected twice as fast, S will be 2.) Amdahl's law states that the overall speedup of applying the improvement will be:
To see how this formula was derived, assume that the running time of the old computation was 1, for some unit of time. The running time of the new computation will be the length of time the unimproved fraction takes (which is 1 − P), plus the length of time the improved fraction takes. The length of time for the improved part of the computation is the length of the improved part's former running time divided by the speedup, making the length of time of the improved part P/S. The final speedup is computed by dividing the old running time by the new running time, which is what the above formula does.
Here's another example. We are given a sequential task which is split into four consecutive parts: P1, P2, P3 and P4 with the percentages of runtime being 11%, 18%, 23% and 48% respectively. Then we are told that P1 is not sped up, so S1 = 1, while P2 is sped up 5×, P3 is sped up 20×, and P4 is sped up 1.6×. By using the formula P1/S1 + P2/S2 + P3/S3 + P4/S4, we find the new sequential running time is:
or a little less than 1⁄2 the original running time. Using the formula (P1/S1 + P2/S2 + P3/S3 + P4/S4)−1, the overall speed boost is 1 / 0.4575 = 2.186, or a little more than double the original speed. Notice how the 20× and 5× speedup don't have much effect on the overall speed when P1 (11%) is not sped up, and P4 (48%) is sped up only 1.6 times.
Read more about this topic: Amdahl's Law
Famous quotes containing the word description:
“I was here first introduced to Joe.... He was a good-looking Indian, twenty-four years old, apparently of unmixed blood, short and stout, with a broad face and reddish complexion, and eyes, methinks, narrower and more turned up at the outer corners than ours, answering to the description of his race. Besides his underclothing, he wore a red flannel shirt, woolen pants, and a black Kossuth hat, the ordinary dress of the lumberman, and, to a considerable extent, of the Penobscot Indian.”
—Henry David Thoreau (1817–1862)
“Once a child has demonstrated his capacity for independent functioning in any area, his lapses into dependent behavior, even though temporary, make the mother feel that she is being taken advantage of....What only yesterday was a description of the child’s stage in life has become an indictment, a judgment.”
—Elaine Heffner (20th century)
“Whose are the truly labored sentences? From the weak and flimsy periods of the politician and literary man, we are glad to turn even to the description of work, the simple record of the month’s labor in the farmer’s almanac, to restore our tone and spirits.”
—Henry David Thoreau (1817–1862)