Abstract

The advance of multi-core processors has led to renewed interest in extracting parallelism from programs, with many different algorithms being proposed and evaluated. It is sometimes useful to know how much parallelism is exploitable in the limit, to put into perspective the speedups of various parallelisation techniques. Wall’s study (“Limits of instruction-level parallelism”, 1991) was one of the first to examine limits of parallelism in detail. In a similar vein we present an analysis of limits of parallelism in a number of benchmark programs, obtained by constructing Dynamic Dependency Graphs from execution traces, allowing us better visualisation of dependencies which limit parallelism, as well as flexibility in transforming graphs when exploring possible optimisations. Some of the results of Wall and subsequent studies are confirmed, including the fact that average available parallelism is often above 100, but requires effective measures to resolve control dependencies, as well as memory renaming. We also study the limits of parallelism when the effects of certain compiler artifacts are disregarded. In particular we show that the use of a Spaghetti stack, as a technique to implicitly rename stack memory and break chains on true dependencies on the stack pointer, can lead to a doubling of parallelism.