邮箱登录 | 所务办公 | 收藏本站 | English | 中国科学院
 
首页 计算所概况 新闻动态 科研成果 研究队伍 国际交流 技术转移 研究生教育 学术出版物 党群园地 科学传播 信息公开
国际交流
交流动态
学术活动
学术交流
现在位置:首页 > 国际交流 > 学术活动
Some Sequential Algorithms are Almost Always Parallel
2017-07-14 | 【 【打印】【关闭】

  主讲人: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.

 
网站地图 | 联系我们 | 意见反馈 | 所长信箱
 
京ICP备05002829号 京公网安备1101080060号