Skip navigation

At this year’s DAC, Bill Dally, Stanford professor and Chief Scientist at Nvidia, gave a keynote speech in which he claimed that Amdahl’s law is not a law, but an observation. This uses the popular interpretation of law to mean “proven correct”. However, in scientific terms, stating something is a law has nothing to do with whether it is correct or not.

In scientific terms, a law is a relationship between two or more entities. Some well know laws are:

  • Newton’s second law of motion
    • F = mA
  • Ohm’s law
    • E = Ir
  • Newton’s law of universal gravitation
    • F = G*m1*m2/r^2

Newton’s second law relates force, mass, and acceleration. Ohm’s law relates voltage, current and resistance. Newton’s law of universl gravitation relates gravitation force to the mass and distance of two bodies.

A law allows us to derive the value of an unknown quantity from other known quantities. Knowing voltage and resistance, Ohm’s law gives us current.

What quantities does Amdahl’s law relate? Amdahl’s law is a relationship between parallelism, number of processors, and speedup. It is usually used to compute the maximum speedup that can be obtained for an application given an infinite number of processors. Parallel speedup is limited by the portion of the application that is sequential (cannot be parallelized). For example, if 10% of the execution time cannot be parallelized, the maximum speedup obtainable through parallelism is 10X.

So, Amdahl’s law does meet the requirements for being a scientific law. Then, what do we make of Dally’s statement? Other than trying to be provocative, I think the point he was trying to make is that, in the applications he is addressing, the sequential portion is essentially zero. In this case speedup is equal to the number of processors. But, this still follows Amdahl’s law.

Advertisements

2 Comments

  1. Interesting – in electronics engineering we call things laws that may be better described as “Observations” (I think of Moore’s “Law” here) and “Formulae” (perhaps Amdahl’s Law would be better as Amdahl’s Forumula). Even if meeting the requirement of being a scientific Law, I think the colloquial interpretation of a Law may constrain people’s thinking. For example: in decoding a video stream using a portable device, there is a more or less sequential portion (using the user interface to select the video stream) followed by a parallelisable portion (decoding the stream). In terms of overall elapsed time, the sequential portion cannot be sped up using parallel resources – but since it is controlled by the user reaction time much more than the sequential computation time, speeding it up may be irrelevant to the overall perception of speed. And interestingly, use of parallel resources in the video decode may be not so much to speed it up (since a certain rate of processing is required) but to reduce overall energy consumption by running each resource at a lower frequency and hopefully requiring a lower supply voltage. I think it may be fruitful for people to worry less about the sequential portion in many applications and start looking at them from different perspectives – irrespective of Laws or Formulae.

    Grant Martin

    • Grant,

      The association of the word “law” with scientific laws is not very scientific (irony intended). For example, we call them Maxwell’s equations, not Maxwell’s laws, the simple reason being that each individual law was already named after someone else.

      You may have heard of certain laws being called a “square law” or “inverse law”. Newton’s universal law of gravitation is an example of an inverse square law. Put this way, interpreting “law” to mean proven or “assumed to be true” doesn’t make sense. Interpreting “law” to mean “relationship” makes a lot more sense. Amdahl’s law describes a relationship, so it makes sense to call it a law.

      It’s interesting to think of why a relationship of quantities is called a law. We usually think of laws as governing behavior – you can’t commit murder or run red lights, for example. Well, scientific laws also govern behavior. Newton’s laws of motion govern how things move, for example.

      Moore’s law is an interesting case. It does state a relationship between two quantities, namely chip density and time. However, it doesn’t actually allow you to make compute one quantity from another. The fact that this year is 2009 does not automatically mean you can calculate chip density. Moore’s law says density doubles every 1.5 years, therefore you would need to know what the density was 1.5 years ago in order to predict the density today. Maybe Moore’s rule-of-thumb is more appropriate.

      –chris


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: