BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Limits of parallelism using Dynamic Dependency Graphs - Jonathan M
 ak (University of Cambridge)
DTSTART:20081114T151500Z
DTEND:20081114T161500Z
UID:TALK14622@talks.cam.ac.uk
CONTACT:Boris Feigin
DESCRIPTION:The advance of multi-core processors has led to renewed intere
 st in extracting parallelism from programs\, with many different algorithm
 s being proposed and evaluated. It is sometimes useful to know how much pa
 rallelism is exploitable in the limit\, to put into perspective the speedu
 ps of various parallelisation techniques. Wall's study ("Limits of instruc
 tion-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 constructin
 g Dynamic Dependency Graphs from execution traces\, allowing us better vis
 ualisation of dependencies which limit parallelism\, as well as flexibilit
 y in transforming graphs when exploring possible optimisations. Some of th
 e results of Wall and subsequent studies are confirmed\, including the fac
 t that average available parallelism is often above 100\, but requires eff
 ective measures to resolve control dependencies\, as well as memory renami
 ng. We also study the limits of parallelism when the effects of certain co
 mpiler artifacts are disregarded. In particular we show that the use of a 
 Spaghetti stack\, as a technique to implicitly rename stack memory and bre
 ak chains on true dependencies on the stack pointer\, can lead to a doubli
 ng of parallelism.
LOCATION:GS15\, Computer Laboratory
END:VEVENT
END:VCALENDAR