USA - 2013
For contributions to efficient and robust parallel computation through both provably efficient randomized scheduling protocols and a set of parallel-language primitives constituting the Cilk framework. Implementations of these protocols and conceptual framework have been deployed on scores of millions of machines and therefore enjoy daily impact.
Before the two papers by Robert D. Blumofe and Charles E. Leiserson, distributed scheduling involved various promising but ultimately fragile heuristic techniques built on the ideas of work queues and dataflow computation. The fragility meant that some programs might run efficiently, but slight changes in code or the environment could make execution far less efficient. The theoretical framework offered by the two papers showed that under certain eminently achievable circumstances, a simple randomized "work-stealing" algorithm, in which idle processors takes work from busy processors, can achieve essentially perfect parallel speedup. The impact of this work has been both rapid and widespread. Work-stealing schedulers can be found in Java, Microsoft Visual Studio, and state-of-the-art garbage collectors. The Cilk parallel programming framework, developed by the authors, is now directly incorporated within the Intel C/C++ compiler, GCC, and other compilers, thus increasing the range of application of these ideas to nearly ubiquitous platforms.
Robert D. Blumofe is Executive Vice President of the Akamai Platform Division and is responsible for the deployment of Akamai networks, as well as for the distributed algorithms that run on them. Charles E. Leiserson is Professor of Computer Science and Engineering in MIT's Department of Electrical Engineering and Computer Science and Computer Science and Artificial Intelligence Laboratory, where he works on performance engineering and the theory and practice of multicore computing.