Systems Seminar: Rastislav Bodik, University of Wisconsin

BAFL: Bottleneck Analysis of Fine-Grain Parallelism

Abstract

Thanks to the RISC revolution, processors became easy to understand. Then, thanks to Moore's Law, they came to baffle their own creators all over again. The culprit, fed by the growing supply of transistors, is parallelism, introduced at many levels of the machine.

The effect of parallelism is that the linear performance models -- popularized on RISC pipelines, on which they were accurate -- break down on modern (out-of-order) processors, leaving architects with no good quantitative methods, and no qualitative intuition on what to do with future transistors.

A natural method for analyzing parallel performance is the critical path. If we could model the diverse constraints in a micro-execution uniformly, as a dependence graph, we could answer (open) questions such as in which cycle the bottleneck was a data dependence, and when it was the small instruction window.

This talk will show how to do exactly that. More importantly, I will present randomized graph algorithms that let us compute the critical path in hardware, without actually building a dependence graph, and without requiring any major changes to the existing processor designs.

Our result is a methodology, both quantitative and qualitative, thanks to which students can regain intuition; architects can design smart control policies that reduce circuit complexity; and processors can understand themselves, reconfiguring their bowels to save power.

Speaker Bio

Ras Bodik is an Assistant Professor at the University of Wisconsin. His current projects are exploring how run-time information can help program analysis solve problems in computer architecture, software engineering, and dynamic compilation. BAFL is joint work with Brian Fields, and in part with Shai Rubin, Mark Hill, and Mary Vernon. http://www.cs.wisc.edu/~bodik