Browse Definitions :
Definition

Amdahl's law

What is Amdahl's law?

Amdahl's law -- also known as Amdahl's argument -- is an intuitive observation and an associated formula. Named after computer scientist Gene Amdahl, the observation is that the performance improvement that can be gained through parallel processing is limited by the part of a system that's inherently sequential -- that is, the set of operations that must be run in series.

The formula, which makes a prediction about the maximum performance improvement that can be expected from parallel computing, is shown in the following:

Smax = 1 / ((1-p) + p/s)

Where the following applies:

  • Smax is the theoretical maximum improvement in execution time of the entire task. If Smax is 2, that means the task can be done twice as fast.
  • p is the proportion of overall execution time spent by the part of the task that benefits from parallel processing.
  • 1-p is the portion of the overall execution time spent by the part of the task that must be run sequentially.
  • s is the performance improvement, or speedup, of the part of the task that benefits from parallel processing.

Amdahl's law is attributed to Amdahl, an American computer scientist and high-tech entrepreneur, who worked first on mainframe computers at IBM and then founded his own companies, including Amdahl Corp. Much of his work involved improving computer performance using a variety of techniques, including parallel processing.

In 1967, Amdahl gave a presentation at the American Federation of Information Processing Societies (AFIPS) Spring Joint Computer Conference describing ways of predicting the limits of parallel processing. The ideas outlined in his presentation later became known as Amdahl's law.

The formula can be applied in a broader sense to other techniques that improve latency, not just parallel computing. If the overall task consists of a part that can benefit from an improvement and another part that can't benefit from the same improvement, Amdahl's law can make a prediction about the maximum savings in execution time of the overall task.

What is an example of how Amdahl's law can be applied?

Amdahl's law can be illustrated with a simple example. If a program is composed of a set of instructions that take 10 hours to run in series, and a one-hour portion of that program can't be parallelized, the absolute best you can expect is to approach the limit of 10x improvement in execution time. That's because no matter how much you parallelize the nine hours that can run in parallel, you will never be able to do away with the one hour that must be run in sequence.

How is Amdahl's law different from Gustafson's law?

Gustafson's law -- also called Gustafson-Barsis' law -- doesn't overturn Amdahl's law. Instead, it adds predictions about the improvement in execution time as more cores are added to execute a task that benefits from parallel computing. The formula starts with the theoretical performance of the task on a single processor as the baseline and makes predictions about system performance as processors are added.

The formula and associate ideas were described by John L. Gustafson and his colleague Edwin H. Barsis, in their article "Reevaluating Amdahl's Law," which was published in May 1988 in Communications of the ACM.

Amdahl's law assumes the problem size is fixed. But in practice, as more resources become available, programmers solve more complex problems to fully exploit the improvements in computing power. So, in reality, the time spent in the part of the task that can benefit from parallel computing often grows much faster than the time spent in the sequential part.

Gustafson's law, on the other hand, assumes that even though the overall execution time is limited -- as predicted by Amdahl -- larger problems can be solved in the same amount of time by increasing the number of processors.

Learn how software testing can be used to push software to its breaking point, identifying points of failure that can be fixed before the software is rolled out to users.

This was last updated in April 2023

Continue Reading About Amdahl's law

Networking
  • firewall as a service (FWaaS)

    Firewall as a service (FWaaS), also known as a cloud firewall, is a service that provides cloud-based network traffic analysis ...

  • private 5G

    Private 5G is a wireless network technology that delivers 5G cellular connectivity for private network use cases.

  • NFVi (network functions virtualization infrastructure)

    NFVi (network functions virtualization infrastructure) encompasses all of the networking hardware and software needed to support ...

Security
  • virus (computer virus)

    A computer virus is a type of malware that attaches itself to a program or file. A virus can replicate and spread across an ...

  • Certified Information Security Manager (CISM)

    Certified Information Security Manager (CISM) is an advanced certification that indicates that an individual possesses the ...

  • cryptography

    Cryptography is a method of protecting information and communications using codes, so that only those for whom the information is...

CIO
  • B2B (business to business)

    B2B (business-to-business) is a type of commerce involving the exchange of products, services or information between businesses, ...

  • return on investment (ROI)

    Return on investment (ROI) is a crucial financial metric investors and businesses use to evaluate an investment's efficiency or ...

  • big data as a service (BDaaS)

    Big data as a service (BDaS) is the delivery of data platforms and tools by a cloud provider to help organizations process, ...

HRSoftware
  • talent acquisition

    Talent acquisition is the strategic process an organization uses to identify, recruit and hire the people it needs to achieve its...

  • human capital management (HCM)

    Human capital management (HCM) is a comprehensive set of practices and tools used for recruiting, managing and developing ...

  • Betterworks

    Betterworks is performance management software that helps workforces and organizations to improve manager effectiveness and ...

Customer Experience
  • martech (marketing technology)

    Martech (marketing technology) refers to the integration of software tools, platforms, and applications designed to streamline ...

  • transactional marketing

    Transactional marketing is a business strategy that focuses on single, point-of-sale transactions.

  • customer profiling

    Customer profiling is the detailed and systematic process of constructing a clear portrait of a company's ideal customer by ...

Close