The Multi-core Problem as an Algorithmic Problem
Leslie Valiant
Harvard University

Wednesday 9/28, 1pm to 2pm
LCPC/CnC Workshops @ Hilton Garden Inn Rochester/University

This keynote is free and open to the public but requires registration

Abstract

The writing of efficient parallel programs has always been difficult, and is currently compounded by the increasing complexity of architectures. We suggest that these difficulties need to be addressed already at the algorithm design level. Resources such as books for relevant efficient algorithms are currently lacking.

In sequential computing programmers have enjoyed efficiently universal algorithms, which have permitted them to write programs independent of machines. We suggest that for parallel or multi-core computers this will no longer be generally possible. Algorithms that run efficiently will need to be aware of the resource parameters of the machines on which they run. The main promise is that of portable algorithms, those that contain efficient designs for all reasonable ranges of the basic resource parameters and input sizes.

Such portable algorithms need to be designed just once, but, once designed, they can be compiled to run efficiently on any machine. In this way the intellectual effort that goes into parallel algorithms design becomes reusable. To permit such portable algorithms some standard bridging model is needed – a common understanding between hardware and algorithm designers of what the costs of a computation are. We shall describe the Multi-BSP model as a candidate for this role. We show that for several basic problems, namely matrix multiplication, fast Fourier transform, and sorting, portable algorithms do exist that are optimal in a defined sense, for all combinations of input size and parameter values.

Biography

Leslie Valiant was educated at King’s College, Cambridge; Imperial College, London; and at Warwick University where he received his Ph.D. in computer science in 1974. He is currently T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics in the School of Engineering and Applied Sciences at Harvard University, where he has taught since 1982. Before coming to Harvard he had taught at Carnegie Mellon University, Leeds University, and the University of Edinburgh.

His work has ranged over several areas of theoretical computer science, particularly complexity theory, computational learning, and parallel computation. He also has interests in computational neuroscience, evolution and artificial intelligence.

He received the Nevanlinna Prize at the International Congress of Mathematicians in 1986, the Knuth Award in 1997, the European Association for Theoretical Computer Science EATCS Award in 2008, and the 2010 A. M. Turing Award. He is a Fellow of the Royal Society (London) and a member of the National Academy of Sciences (USA).