What the $#@! Is Parallelism? (And Why Should Anyone Care?)

Many people bandy about the notion of "parallelism," saying such things as, "this optimization makes my application more parallel," with only a hazy intuition about what they're actually saying. Others cite Amdahl's Law, which provides bounds on speedup due to parallelism, but which does not actually quantify parallelism. In this talk, I'll review a general and precise quantification of parallelism provided by theoretical computer science, which every computer scientist and parallel programmer should know. I'll argue that parallel-programming models should eschew concurrency and encapsulate nondeterminism. Finally, I'll discuss why the impending end of Moore's Law "” the economic and technological trend that the number of transistors per semiconductor chip doubles every two years "” will bring new poignancy to these issues.
Charles E. Leiserson received his B.S. from Yale University in 1975 and his Ph.D. from Carnegie Mellon University in 1981. He is currently Professor of Computer Science and Engineering at MIT, where he holds the position of Edwin Sibley Webster Professor in MIT's Department of Electrical Engineering and Computer Science (EECS). He is a Margaret MacVicar Faculty Fellow, the highest recognition at MIT for undergraduate teaching. He is a member of MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL), a member of the Lab's Theory of Computation Group (TOC), and head of the Lab's Supertech Research Group. Professor Leiserson is an ACM Fellow, a AAAS Fellow, and a senior member of IEEE and SIAM. He is coauthor of Introduction to Algorithms (The MIT Press), one of the most cited publications in computer science. " He" " has received numerous awards, including the 2013 ACM Paris Kanellakis Theory and Practice Award, the 2014 IEEE Taylor L. Booth Education Award, and the 2014 ACM-IEEE Computer Society Ken Kennedy High-Performance Computing Award. Among his research contributions are the retiming method of digital-circuit optimization, the fat-tree interconnection network, the notion of cache-oblivious algorithms, and the Cilk multithreaded programming technology. His current research centers on software performance engineering: how to engineer code that runs fast" and consumes a small memory footprint."