Liberating Threads from Sequential Programs

Tuesday April 26, 2005
Hamerschlag Hall D-210
4:00 pm

David August
Princeton University

For years, a steadily growing clock speed could be relied upon to consistently deliver increasing performance for a wide range of applications. Recently, however, this approach has faltered. Meanwhile, the exponential growth in per-chip transistor count remains strong, leading major microprocessor companies to add value by producing chips incorporating multiple processors. Unfortunately, since decades of compiler research have not succeeded in delivering automatic threading for sequential codes, current chip multiprocessors demonstrate no improvement for most applications.

We propose a new approach to thread extraction, called Decoupled Software Pipelining (DSWP), that leverages various successes of compiler research not previously applied to automatic threading. DSWP exploits the fine-grained pipeline parallelism lurking in most applications to extract long-running, concurrently executing threads. Use of the non-speculative, streaming threads produced by DSWP can increase execution efficiency, reduce design complexity, and provide latency tolerance, suggesting simpler inter-core communication mechanisms. Using our compiler implementation and a validated processor model, we prove the concept by demonstrating significant gains for a dual core chip multiprocessor running a variety of codes. Then, we highlight opportunities missed by our initial compiler implementation which suggest that much higher degrees of automatic threading are finally within our reach.

Prof. David August is an Assistant Professor in the Department of Computer Science at Princeton University. His research interests lie in computer architecture and back-end compilation. At Princeton, he directs the Liberty Research Group. The Liberty Research Group is studying next generation architectures, code analyses, and code transformations to enhance performance, reliability, and security. To support this work and to advance computer architecture research in general, the group develops powerful open-source compiler and modeling tools. David's work has been recognized by an NSF CAREER Award, an Emerson Electric Company - E. Lawrence Keyes '51 Award, an IBM Faculty Partnership Award, three best paper awards, and The Chronicle of Higher Education's annual list of "New Ph.D.'s to Watch". David earned his Ph.D. in Electrical Engineering from the University of Illinois at Urbana-Champaign in 2000 while working as a member of the IMPACT research compiler group.