Limits of parallelism using Dynamic Dependency Graphs

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

• Jonathan Mak (University of Cambridge)
• Friday 14 November 2008, 15:15-16:15
• GS15, Computer Laboratory.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory Programming Research Group Seminar
• Department of Computer Science and Technology talks and seminars
• GS15, Computer Laboratory
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.