Scientist out to break Amdahl's law

The 46-year old Amdahl's law will be challenged during a presentation at the International Supercomputing Conference this week

Many attempts have been made over the last 46 years to rewrite Amdahl's law, a theory that focuses on performance relative to parallel and serial computing. One scientist hopes to prove that Amdahl's law can be surpassed, and that it doesn't apply in certain parallel computing models.

A presentation titled "Breaking the Law" at the International Supercomputing Conference this week in Leipzig, Germany, will show how "pitfalls of Amdahl's law can be avoided in specific situations," according to a blog entry that provides a teaser on the presentation.

The presentation will "challenge Amdahl's generalized law by exposing it to a new class of experiments in parallel computing," wrote Thomas Lippert, director of the Jülich Supercomputing Centre at Jülich, Germany, in the blog entry. Lippert will lead the presentation.

Amdahl's law, established in 1967 by noted computer scientist Gene Amdahl when he was with IBM, provides an understanding on scaling, limitations and economics of parallel computing based on certain models. The theory states that computational tasks can be decomposed into portions that are parallel, which helps execute tasks and solve problems quicker. However, the speed of task execution is limited by tasks -- in the case of computers it could be serial tasks -- that cannot be parallelized.

"If you throw enough hardware at parallel you can solve a problem; you still have to do some in serial, which is a limiting factor in speeding up tasks," said Nathan Brookwood, principal analyst at Insight 64.

The mathematics of Amdahl's law assume there is a limit to parallel speed-up, assuming some things are constant, such as the problem size and the nature of the processors doing the computation.

Amdahl's law has been challenged in the past. Amdahl's law was re-evaluated by John Gustafson, who provided an understanding of parallelism among processors in which the size of a problem can be meaningfully increased. The corollary, called Gustafson's law, assumes that problem size is not constant, and parallel computer speed can scale up accordingly. Gustafson now works at Advanced Micro Devices as senior fellow and chief graphics product architect.

The mathematic equations resulting from Amdahl's law and corollaries have become reference points as chip and software makers try to scale supercomputing performance. Such computing power is necessary to find scientific solutions in fields such as biotechnology and meteorology. Countries are also developing faster supercomputers for economic forecasting and national security reasons.

The ISC presentation has been triggered by a past history of optimizing simple and efficient systems for simulations in high-performance computing such as in Blue Gene/L, which took over as the world's fastest computer in 2004, said Lippert in an email. The systems are highly scalable and energy efficient, but have been restricted to problems that are not adapted to parallel processing.

The presentation, however, is based on experiments done as part of the DEEP Project, which investigates highly parallel computing models that help speed up supercomputers. In addition to investigating software development and programming tools, the project involves building high-performance systems called JUROPA (Jülich Research on Petaflop Architectures).

"My team was building the very effective JUROPA system together with Bull, Partec and Intel. This machine is ideal for highly complex problems that exhibit a lower concurrency, in general. Most codes live somewhere in between. I want to find out, if we can bring the concepts together. The different architectures can assign the ... different code parts according to the concurrency," Lippert said.

Performance in supercomputers has scaled thanks to new programming models and hardware such as accelerators and graphics cards. Code needs to be structured according to concurrency levels, such as in programming languages like the one provided by Barcelona Supercomputing Center's OmpSS, Lippert said.

Despite the title of the presentation, the aim is not to challenge Amdahl's law, Lippert said.

"On the contrary, I think, we are not taking [Amdahl's law] serious enough. It is simply obvious that we should adapt the right piece of hardware to the corresponding concurrency," Lippert said. "Only this approach has the potential to be most energy efficient and performance oriented at the same time."

While Lippert's blog entry did not provide much detail on how Amdahl's law is being challenged, academics said it is always interesting to see the law being revisited.

Unlike Moore's Law, which is an observation, Amdahl's law cannot be "broken" in any mathematical sense, and is still relevant, said Paul Lu, associate professor at University of Alberta's Department of Computing Science.

As with any mathematical theorem, if the assumptions are no longer true, the law is not relevant. "That is not to say that the law has been 'broken'; it just means that the law does not apply to that situation," Lu said.

While the size of a problem can be meaningfully increased, there are cases in which the size of a problem is fixed, and Amdahl's law is relevant.

"For fixed-sized problems, Amdahl's law is a sobering reminder of reality," Lu said.

Faster computers are designed to reduce execution time for fixed-size problems, but there are other metrics that need to be taken into account, said Xian-He Sun, chair and professor of the Department of Computer Science at the Illinois Institute of Technology.

"Amdahl's law is a law, which shows even when you have reduced your communication and other overhead -- such as memory access delay, software and hardware delay -- to zero, with the sequential portion of your program, your parallel processing gain is still very limited," Xian-He said.

"It gives the limitation of parallel processing, and does not matter how much you have improved your hardware," Xian-He said. "Gustafson's law says there is no limitation of parallel processing if you allow problem size increase."

Xian-He revisited Amdahl's law and established Sun-Ni's law, which introduces memory constraint as a limitation on problem execution.

"With the long-standing memory-wall problem and the newly emerged big data problem, the problem size increase, however, is limited by memory access delay," Xian-He said, adding that memory-bound speedup needs to be followed.

"That means software models and hardware need to be redesigned to reduce data access time in order to get better scalability," Xian-He said.

While new theories will provide new insights, Amdahl's law provides a base.

"As with all real laws and theorems, one must always revisit things like the main assumptions, just as Gustafson did. The original law still stands, but corollaries might be very interesting," said University of Alberta's Lu.

Agam Shah covers PCs, tablets, servers, chips and semiconductors for IDG News Service. Follow Agam on Twitter at @agamsh. Agam's e-mail address is

Join the PC World newsletter!

Error: Please check your email address.

Tags Advanced Micro Deviceshardware systemsComponentsprocessorsUniversity of Alberta

Our Back to Business guide highlights the best products for you to boost your productivity at home, on the road, at the office, or in the classroom.

Keep up with the latest tech news, reviews and previews by subscribing to the Good Gear Guide newsletter.

Agam Shah

IDG News Service
Show Comments

Cool Tech

Crucial Ballistix Elite 32GB Kit (4 x 8GB) DDR4-3000 UDIMM

Learn more >

Gadgets & Things

Lexar® Professional 1000x microSDHC™/microSDXC™ UHS-II cards

Learn more >

Family Friendly

Lexar® JumpDrive® S57 USB 3.0 flash drive 

Learn more >

Stocking Stuffer

Plox Star Wars Death Star Levitating Bluetooth Speaker

Learn more >

Christmas Gift Guide

Click for more ›

Most Popular Reviews

Latest News Articles


GGG Evaluation Team

Kathy Cassidy


First impression on unpacking the Q702 test unit was the solid feel and clean, minimalist styling.

Anthony Grifoni


For work use, Microsoft Word and Excel programs pre-installed on the device are adequate for preparing short documents.

Steph Mundell


The Fujitsu LifeBook UH574 allowed for great mobility without being obnoxiously heavy or clunky. Its twelve hours of battery life did not disappoint.

Andrew Mitsi


The screen was particularly good. It is bright and visible from most angles, however heat is an issue, particularly around the Windows button on the front, and on the back where the battery housing is located.

Simon Harriott


My first impression after unboxing the Q702 is that it is a nice looking unit. Styling is somewhat minimalist but very effective. The tablet part, once detached, has a nice weight, and no buttons or switches are located in awkward or intrusive positions.

Featured Content

Latest Jobs

Don’t have an account? Sign up here

Don't have an account? Sign up now

Forgot password?