3
$\begingroup$

I would like to learn more about Amdahl's Law and other similar topics. In what branch of computer science would one place Amdahl's law? Could someone point me to a textbook or further reading (aside from Wikipedia or other sites that are found on the first page of a Google search) that discusses it?

$\endgroup$
  • $\begingroup$ I get it, sort of. The OP might start with F. Tom Leighton's textbooks (both the VLSI complexity one and the parallel algorithms and architectures book.) If I remember correctly the back chapters of Cormen, Leiserson and Rivest also touch on some of Leiserson's VLSI complexity research (fat trees and systolic array computation). There's also Gustafson's law (CACM 31(5):532-533, 1988). Finally, there's Bennett's work on the physical limits of computation. $\endgroup$ – Wandering Logic May 8 '13 at 12:18
3
$\begingroup$

Amdahl's Law is perhaps most associated with computer architecture (Gene Amdahl was a computer architect). Although initially applied to the potential speedup from partial parallelization of a task, the formula applies to the benefit from any partial improvement.

In its general form, it can be applied to many different types of problems. E.g., the improvement in voter turn out by getting a fraction of potential voters to always vote.

Since it is a rule of thumb intended to compensate for excessive expectations from dramatic improvements in part of a system, it is most useful when the improvement factor is large and is intended more for quick estimation (and generally the best case--though sometimes an improvement can unexpectedly benefit other aspects) than an exact measurement (as systems tend to have complex and subtle interactions). (Quick estimation facilitates quick pruning of paths of exploration.)

As a mathematically based rule of thumb, it is not an especially deep topic (rules of thumb based on history, economics, etc. are generally more susceptible to discussion), though Gustafson's Law points out that context is important. However, Amdahl's Law is an important corrective to optimism with respect to dramatic (but partial) improvements.

$\endgroup$
  • $\begingroup$ It may be originally intended as a rule of thumb, but I as computer systems become more vast and complex, I wonder if the implications may become deeper. In my original post, I tried to get across the idea that a computer system may be characterized like the physical environment (e.g. by a physicist). This law is the first one of its kind that seems like a step in that direction and I would like to learn more about similar approaches to computer systems. $\endgroup$ – vrume21 May 10 '13 at 14:19
  • $\begingroup$ @bam54 This page on Andy Glew's computer architecture wiki mentions Pollack's Law which as mentioned there might have some physical justification. Computer architects are generally less interested in "spherical cows" than physicists. :-) With the increase in complexity and more common requirements of statistical (more economic than abstract) truth, biological systems might be a better analogy. $\endgroup$ – Paul A. Clayton May 10 '13 at 14:32
  • $\begingroup$ Your comment about biological systems rings true, but biological research (along with finance) seems to have become the newest frontier for many physicists (at least the ones in my course on parallelism). But as this field develops more quantitatively significant information (traditionally a bastion of qualitative work), I wonder if my point wouldn't still hold if biological systems were used as an analogy? $\endgroup$ – vrume21 May 10 '13 at 15:20
  • $\begingroup$ Your other comments include many practical considerations and while they're well received, I am young and idealistic and so, I hear them and then quickly ignore them. $\endgroup$ – vrume21 May 10 '13 at 15:21

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.