2008 (for 1998): The Implementation of the Cilk-5 Multithreaded Language, Matteo Frigo, Charles E. Leiserson, and Keith H. Randall
“The 1998 PLDI paper “Implementation of the Cilk-5 Multithreaded
Language” by Matteo Frigo, Charles E. Leiserson, and Keith H. Randall
introduced an efficient form of thread-local deques to control
scheduling of multithreaded programs. This innovation not only opened
the way to faster and simpler runtimes for fine-grained parallelism,
but also provided a basis for simpler parallel recursive programming
techniques that elegantly extend those of sequential programming. The
stack-like side of a deque acts just like a standard procedure stack,
while the queue side enables breadth-first work-stealing by other
threads. The work-stealing techniques introduced in this paper are
beginning to influence common practice, such as the Intel Threading
Building Blocks project, an upcoming standardized fork-join framework
for Java, and a variety of projects at Microsoft.”
2007 (for 1997): Exploiting Hardware Performance Counters with Flow and
Context Sensitive Profiling, Glenn Ammons, Thomas Ball, and James R.
2006 (for 1996): TIL: A Type-Directed Optimizing Compiler for ML,
David Tarditi, Greg Morrisett, Perry Cheng, Christopher Stone, Robert
Harper, and Peter Lee
2005 (for 1995): Selective Specialization for Object-Oriented Languages, Jeffrey Dean, Craig Chambers, and David Grove
2004 (for 1994): ATOM: a system for building customized program analysis tools, Amitabh Srivastava and Alan Eustace
2003 (for 1993): Space Efficient Conservative Garbage Collection, Hans Boehm
2002 (for 1992): Lazy Code Motion, Jens Knoop, Oliver Rüthing, Bernhard Steffen.
2001 (for 1991): A data locality optimizing algorithm, Michael E. Wolf and Monica S. Lam.
2000 (for 1990): Profile guided code positioning, Karl Pettis and Robert C. Hansen.