Fixed Time, Tiered Memory, and Superlinear Speedup

In the problem size-ensemble size plane, fixed-sized and scaled-sized paradigms have been the subsets of primary interest to the parallel processing community. A problem with the newer scaled-sized model is that execution time increases for problems where operation complexity grows faster than storage complexity. The fixed time model is introduced, which, unlike the scaled model, implies the need to reduce problem size per processor. This reduction causes uniprocessor speed to vary. Historical ensemble models hold uniprocessor performance flat as problem size varies, even beyond physical memory size. However, tiered memory can make performance increase instead of decrease as problem size per processor shrinks, and workload can shift to routines with higher speed as the problem is scaled. Superlinear speedup results in such cases. Superlinear speedup, far from being an anomaly, becomes commonplace when the performance model makes realistic assumptions about memory speed and problem scaling. Historical Background: Superlinear Speedup Enough has been written on the subject of superlinear speedup to merit a survey article on the subject [5]. The initial counter-reaction to the notion of superlinear speedup goes something like this: “For a P-processor algorithm, simply execute the work of each processor on a single processor, and the time will obviously be no worse than P times greater. It will usually be less, because sources of parallel inefficiency are eliminated. ” Faber et al. [1] have used this argument as a “proof ” of the impossibility of superlinear speedup. (The proof assumes fixe