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.Scroll Up
Robert D. Blumofe and Charles E. Leiserson, recipients of the 2013 Paris Kanellakis Theory and Practice Award
Robert D. Blumofe and Charles E. Leiserson, recipients of the Paris Kanellakis Theory and Practice Award for contributions to robust parallel and distributed computing. They developed provably efficient randomized “work-stealing” scheduling algorithms, and Cilk, a small set of linguistic primitives (the simplest elements in a programming language) for programming multithreaded computations. Their conceptual framework for work stealing is ubiquitous on scores of millions of multicore platforms and underpins many parallel-programming platforms. Cilk simplifies multiprocessor programming and guarantees mathematically that multithreaded programs with sufficient parallelism run with near-perfect speed. Blumofe is an Executive Vice President at Akamai Technologies, where he is responsible for the Platform Division, which includes the core distributed systems and network technology that underlie all of Akamai’s products and services. Leiserson, Professor of Computer Science and Engineering at the Massachusetts Institute of Technology, is co-author of Introduction to Algorithms, won the ACM Doctoral Dissertation Award, and is an ACM Fellow.