主讲人：Guy E. Blelloch Professor, and Associate Dean for Undergraduate Programs,Department of Computer Science,Carnegie Mellon University ?

报告时间：2017年7月18日（周二） 上午 10:00-11:30

报告地点：计算所601会议室

报告摘要：

Over the years many interesting and efficient parallel algorithms have been developed to solve a wide variety of problems, but not much attention has been paid to studying the inherent parallelism in sequential algorithms—i.e., understanding the depth of their dependence structure, and how shallow dependence structures might be used to develop efficient parallel implementations.

In this talk I will describe recent work on analyzing the dependence depth of iterative sequential algorithms—ones that loop over a collection of elements. Many of these algorithms have deep dependence chains in the worst case, but shallow chains (polylog w.h.p.) if the elements are randomly ordered. Examples include many fundamental algorithms: the Knuth shuffle for random permutations, sorting by insertion into a binary search tree, greedy maximal independent set (MIS), greedy maximal matching, greedy graph-coloring, counting cycles in a permutation, incremental k-dimensional linear programming, and incremental 2d Delaunay triangulation.

An advantage of the approach is that it can lead to very simple and efficient parallel algorithms. Our MIS algorithm, for example can be coded in a dozen or so lines, and is significantly faster than Luby’s algorithm on modern multicore machines. Also the approach encourages snapping the view that sequential and parallel algorithms are distinct, and instead thinking of algorithms, in general, as collections of instructions with dependences among them.

主讲人简介：

Guy Blelloch is a Professor of Computer Science at Carnegie Mellon University. His research interests are in algorithms and programming languages and how they interact, with an emphasis on parallel computation. He has worked on programming-language based cost models along with provable implementation bounds, on bounding costs in runtime scheduling and parallel garbage collection, and designed the Nesl programming language. He has developed a variety of parallel algorithms, including algorithms for graph connectivity, set cover, semi sorting, suffix trees, balanced trees, hashing, shortest paths, and Delaunay triangulation. He is an ACM Fellow for his contributions in parallel computation, and was general chair of the ACM Symposium on Parallelism in Algorithms and Architecture (SPAA) from 2011–2015.