Concurrency and Load Balance

The Splash-2 paper suggests that one of the first steps in studying an application is to analyze its available concurrency and load-balance. In particular, algorithms that do not have enough concurrency are not useful for studying the scalability characteristics of a parallel machine.

In this section of the paper, the Splash-2 developers provide two different kinds of numbers. The first characteristic they measure is the speedup of programs assuming a unit cycle memory access. The second characteristic that they measure is the amount of time spent in synchronization. Based on these numbers, they draw certain conclusions on the inherent concurrency and load-balance of the program. The approach definitely provides an upper-bound to the speedup that can be obtained for these programs, and therefore provides a truthful indicator of the available concurrency in the program. However, since load balance is more of a machine dependent parameter whose value depends on a lot of different factors, the numbers do not capture the potential load-balance of the applications. We now discuss the important deficiencies in the proposed methodology.

Inverse Amdahl's Law
Effect of Single Cycle Memory Access Assumption
Synchronization Costs