HPCwire: Amdahls Law: 1+1

The Leading Source for Global News and Information Covering the Ecosystem of High Productivity Computing

HPCwire >> Features

February 24, 2005

Amdahls Law: 1+1 < 1?

by Labro Dimitriou

Page: 1 of 2
1 | 2 All »

In my last article (http://news.tgc.com/msgget.jsp?mid=339671), I demonstrated how 1 + 1 can be equal to 1 by using a simple program of two instructions: I1 and I2 executing on two processors at the same time and simultaneous completing in about 1 clock tick. I concluded by posing the question: "can we do better?" In order to explain this, I need to shed some light on algorithmic complexity and run time fabric.

For our purpose, algorithmic complexity is best viewed with Amdahl's law. So, it is helpful to prove it. Don't be alarmed, it only requires middle-school algebra! To compare the run time of a parallel execution with a serial execution, we need to have a measure of speedup. The standard approach is to define speedup as the ratio of Ts, serial time of execution, over time of execution of the same algorithm in parallel. So, if we have N processors and p, and s are the parts of the algorithm than can execute in parallel and serial respectively, using s + p = 1

Speedup = (s + p) Ts / ((s + p/N) Ts), applying middle school algebra

Speedup = 1 / (s + (1 - s) / N)

So this is the law that tells us that as s gets smaller and smaller, my speedup approaches N. Incidentally, for stage I or embarrassingly parallel problems, s approaches or is equal to zero. Of course, the key assumption is the amount of computation is exactly the same in serial or parallel execution on N processors. Plugging into the formula the numbers from MPT' claims -- 102 speedup on 127 processors -- we can conclude that the serial part of the problem they are solving must be equal to 0.001945.

Run time fabric consists of main shared memory, L1 and L2 cache, disk I/O, network bandwidth, speed of light, etc. And modeling a parallel or even serial execution very quickly gets very complex. There are a number of papers discussing performance engineering using queuing theory, but some simpler models exist for basic algebraic operations (see BLAST, NAS, etc.).

Putting one and one together now, we need to ask yet another key question: do I really solve the same problem parallel and serially? The answer -- not always! Algorithmic complexity changes from parallel to serial. This is well understood, for example, on the so called branch and bound algorithms, such as techniques for integer programming and global optimizations. See references D. Parkinson and Phillips et al. demonstrating arbitrary speedup gains. In these type of algorithms, you can find exactly the optimal number of processors that get you maximum speedup.

In terms of the run time fabric, consider a problem requiring very large data or large enough not to fit in the serial memory cache, where in parallel execution everything fits nicely in local memory. The penalty of memory paging and hit misses can be sufficiently big to demonstrate a speedup of greater than N. In fact, some of our benchmarks of Monte Carlo simulation of large portfolios, at ASPEED Software, have demonstrated speedup greater than N.

I conclude this article by saying that the underlying value of this conversation is not just an academic exercise but has a real business value: predictability in completing mission critical operations and knowing how exactly I can scale my operations in support of business growth.

Until next time: keep the GRIDS crunching.

Page: 1 of 2
1 | 2 All »

Article Tools

Share Options

(Digg, Technorati, more)

Subscribe

Subscribe to HPCwire

Discussion

There are 0 discussion items posted.

Join the Discussion

You must be a registered user in order to comment on HPCwire stories.

Members enjoy:

	Access to Special Content, including Podcasts, Webcasts, and Whitepapers and more!
	Ability to take an active role in the discussions that are shaping the HPC technology discipline!
	Special offers available only to HPCwire members!

Become a Registered User Today!

Registered Users Log in Here to Comment

Email Address:	Password (case sensitive)

Remember me	Forgot Password?

RSS Feeds

Feeds by Topic

Feeds by Industry

Feeds by Content Type

Top Headlines

Intel Partners See 'Easy' Upgrade Path With Xeon 5600 Chips

Mar 18 | ChannelWeb | Westmere parts already showing up in HPC machines. Read more...

AMD: OEMs primed for Opteron 6100s

Mar 17 | The Register | But what about the tier ones? Read more...

Arrival of the Desktop Supercomputer

Mar 17 | Cadalyst Magazine | A new generation of workstations is changing the nature of technical computing. Read more...

Scheduling HPC In The Cloud

Mar 17 | Linux Magazine | Latest iteration of Sun Grid Engine able to tap into Cloud. Read more...

Tailoring Medicine with Supercomputers

Mar 16 | Bio-IT World | Biotech firm builds genetic models from patient data. Read more...

Read more headlines...

Featured Whitepapers

Virtualization for Aggregation And The vSMP Architecture™

Jan 12 | | In-depth look at vSMP Foundation server virtualization technology, technical implementation, use cases and capabilities. The technical whitepaper provides an architectural overview and details on the three vSMP Foundation products: vSMP Foundation for SMP, vSMP Foundation for Cluster and vSMP Foundation for Cloud.

Copper Cable Technologies for High Performance Computing

Jan 18 | | This white paper discusses Gore’s copper cable assemblies, and how they continue to exceed the standards for providing reliable, cost-effective solutions for high-performance computer applications.

View the White Paper Library

Multimedia

Webcast: Virtualized Data Center Roundtable

Join this online panel discussion for live Q&A with leading industry experts, analysts, and end-users to discuss the latest innovations, best practices, barriers to implementation, and measurable benefits of server virtualization with a particular focus on today's real world solutions.

Webcast: Watch SC09 Birds of a Feather Video: Scalable Fault-Tolerant HPC Supercomputers

Learn about scalable fault-tolerant architectures and examples of energy efficient and scalable supercomputing clusters using dual QDR InfiniBand to combine capacity computing with network failover capabilities with the help of programming languages such as MPI and a robust Linux cluster management package.

Webcast: High Performance Computing for a Smarter Planet

LIVE@SCO9: The IBM team discusses new innovations in hardware, software and services that help clients better understand their workloads and get insight from their R&D efforts. Technology demonstrations include the soon-to-be-released Power7 HPC processor, the DCS990 system with 2.4 petabytes of storage, the xCAT management tool, secure HPC cloud computing and more. Winners of two HPCwire Readers' and Editors’ Choice Awards! Take the IBM virtual tour at SC09 or more information go online to: http://www-03.ibm.com/systems/deepcomputing/sc09.html