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.

Labro Dimitriou
HPC Product and Marketing specialist
ASPEED Software
[email protected]

REFERENCES:
[1] D. Parkinson, Parallel efficiency can be greater than unity, Parallel Computing 3 (1989)
[2] A. T. Phillips and J.B. Rosen, Anomalies acceleration in parallel multiple cost row linear programming, ORSA Journal on Computing (1989(.

---

Labro Dimitriou is a High Performance Computing product and marketing specialist. He has been in the field of distributed computing, applied mathematics, and operations research for over 20 years, and has developed commercial software for trading, engineering, and geosciences. Labro has spent the last five years designing and implementing HPC and BPM business solutions. Currently employed by ASPEED Software.