The Leading Source for Global News and Information Covering the Ecosystem of High Productivity Computing
February 24, 2005
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(Digg, Technorati, more)
PGI Accelerator™ Fortran 95/03 and C99 compilers for x64+NVIDIA
Accelerate applications on x64+GPU platforms by adding OpenMP-like compiler directives to existing Fortran and C programs. Available now for Linux, MacOS and Windows. Download a free 15 day trial.
Platform HPC Workgroup Manager
Platform HPC Workgroup Manager integrates all the cluster productivity tools you need to deploy, run and manage your HPC environment.
Mar 18 | ChannelWeb | Westmere parts already showing up in HPC machines. Read more...
Mar 17 | The Register | But what about the tier ones? Read more...
Mar 17 | Cadalyst Magazine | A new generation of workstations is changing the nature of technical computing. Read more...
Mar 17 | Linux Magazine | Latest iteration of Sun Grid Engine able to tap into Cloud. Read more...
Mar 16 | Bio-IT World | Biotech firm builds genetic models from patient data. Read more...
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.
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.
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.
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.
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