Robert D. Blumofe and Charles E. Leiserson were announced today as the winners of the 2013 Association for Computing Machinery’s (ACM) Paris Kanellakis Theory and Practice Award for contributions to robust parallel and distributed computing. The ACM credits Blumofe and Leiserson for developing provably efficient randomized “work-stealing” scheduling algorithms and Cilk, a small but powerful programming-language extension for multithreaded computing. The Kanellakis Award honors specific theoretical accomplishments that significantly affect the practice of computing.
Charles Leiserson is a professor in the MIT Department of Electrical Engineering and Computer Science (EECS) and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL). Robert Blumofe was a Ph.D. student of Prof. Leiserson and is now Executive Vice President of the Akamai Platform Division of Akamai Technologies. In the early 1990’s, they set out to investigate why a dataflow computation system, developed by EECS/CSAIL Professor Arvind, consumed so much memory. They showed that ill-structured multithreaded programs could indeed consume large amounts of memory, but well-structured programs could be scheduled efficiently. This work formed the basis of Blumofe’s master’s thesis. The pair went on to develop randomized work-stealing scheduling algorithms — where processors “steal” computational threads from other processors — which guarantee mathematically that programs with sufficient parallelism run with near-perfect speed and without “blowing out” memory. This work lies at the foundation of Cilk, a multithreaded programming technology developed by Leiserson and his students, including Blumofe, to simplify multiprocessor programming.
The impact of these two contributions by Blumofe and Leiserson go far beyond esoteric scheduling theory as they are employed in every major concurrency platform for task scheduling today. For example, work-stealing schedulers can be found in the Java JDK 7, distributed over 10 million desktops, and in Microsoft Visual Studio, distributed to virtually all machines running Windows. In addition, algorithms based on Blumofe and Leiserson’s work-stealing approach have found extensive use in other applications such as Oracle’s state-of-the-art Garbage-First garbage collector for Java. The Blumofe-Leiserson work-stealing schedulers have demonstrated how pure theory can influence practice — where a clear model and strong guarantees of performance form a practical basis for protocol development.
On completing his Ph.D. in 1995, Robert Blumofe joined the faculty at the University of Texas, Austin. Blumofe joined the fledgling MIT spinoff Akamai Technologies in 1999 and was instrumental in the early design and development of the Akamai Platform. Serving in several positions since then, he has led all of Networks and Operations since 2004 and, as Executive Vice President of the Akamai Platform Division, is responsible for operating and evolving the distributed computer system underlying all Akamai products.
Charles Leiserson is Margaret MacVicar Faculty Fellow at MIT, a member of CSAIL’s Theory of Computation Group, and head of the Supertech Research Group, which investigates the technologies that support scalable computing, including hardware, software, and theory. He is coauthor of Introduction to Algorithms, the widely used algorithms textbook, and he has developed multiple courses on algorithms and parallel programming. Leiserson was recognized with the first ACM Doctoral Dissertation Award and was recently selected for the IEEE Computer Society’s 2014 Taylor L. Booth Award for his contributions to computer-science education. He is an ACM Fellow, an AAAS Fellow, and a senior member of both IEEE and SIAM.