University of Cambridge > > Computer Laboratory Programming Research Group Seminar > Limits of parallelism using Dynamic Dependency Graphs

Limits of parallelism using Dynamic Dependency Graphs

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Boris Feigin.

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.

This talk is part of the Computer Laboratory Programming Research Group Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity