Threads from Sequential Programs
Tuesday April 26, 2005
Hamerschlag Hall D-210
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.