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 agam_shah@idg.com

Join the newsletter!

Or

Sign up to gain exclusive access to email subscriptions, event invitations, competitions, giveaways, and much more.

Membership is free, and your security and privacy remain protected. View our privacy policy before signing up.

Error: Please check your email address.

Tags processorshardware systemsComponentsAdvanced Micro DevicesUniversity of Alberta

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

Toys for Boys

Family Friendly

Stocking Stuffer

SmartLens - Clip on Phone Camera Lens Set of 3

Learn more >

Christmas Gift Guide

Click for more ›

Brand Post

Most Popular Reviews

Latest Articles

Resources

PCW Evaluation Team

Aysha Strobbe

Microsoft Office 365/HP Spectre x360

Microsoft Office continues to make a student’s life that little bit easier by offering reliable, easy to use, time-saving functionality, while continuing to develop new features that further enhance what is already a formidable collection of applications

Michael Hargreaves

Microsoft Office 365/Dell XPS 15 2-in-1

I’d recommend a Dell XPS 15 2-in-1 and the new Windows 10 to anyone who needs to get serious work done (before you kick back on your couch with your favourite Netflix show.)

Maryellen Rose George

Brother PT-P750W

It’s useful for office tasks as well as pragmatic labelling of equipment and storage – just don’t get too excited and label everything in sight!

Cathy Giles

Brother MFC-L8900CDW

The Brother MFC-L8900CDW is an absolute stand out. I struggle to fault it.

Luke Hill

MSI GT75 TITAN

I need power and lots of it. As a Front End Web developer anything less just won’t cut it which is why the MSI GT75 is an outstanding laptop for me. It’s a sleek and futuristic looking, high quality, beast that has a touch of sci-fi flare about it.

Emily Tyson

MSI GE63 Raider

If you’re looking to invest in your next work horse laptop for work or home use, you can’t go wrong with the MSI GE63.

Featured Content

Product Launch Showcase

Don’t have an account? Sign up here

Don't have an account? Sign up now

Forgot password?