Scalable Graph Traversal on Sunway TaihuLight with Ten Million Cores
Scalable Graph Traversal on Sunway TaihuLight with Ten Million Cores
复制标题
DOI：
10.1109/ipdps.2017.53
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Heng Lin;Xiongchao Tang;Bowen Yu;Youwei Zhuo;Wenguang Chen;Jidong Zhai;Wanwang Yin;Weimin Zheng
中科院分区：
文献类型：
--
作者：
Heng Lin;Xiongchao Tang;Bowen Yu;Youwei Zhuo;Wenguang Chen;Jidong Zhai;Wanwang Yin;Weimin Zheng
最近，人们对有效分析社交网络图和蛋白质结构等非结构化数据的兴趣日益浓厚。完成此类任务的基本图算法是广度优先搜索 (BFS) 算法，它是许多其他重要图算法的基础，例如计算最短路径或查找图中的最大流。在本文中，我们分享了在神威太湖之光（神威太湖之光）上设计和实现 BFS 算法的经验，神威太湖之光是一款新发布的机器，拥有 40,960 个节点和 1,060 万个加速器核心。它以 93.01 petaflops Linpack 性能位居 2016 年 6 月 Top500 排行榜榜首[1]。神威·太湖之光处理器专为超大规模计算和功效而设计，采用独特的异构众核架构和内存层次结构。该机器尺寸极大，为实现BFS等高性能不规则算法提供了机遇和挑战。我们提出了多种技术，包括流水线模块映射、无争用数据洗牌和基于组的消息批处理，以解决有效利用这种大规模异构机器的功能的挑战。我们最终实现了每秒 23755.7 千兆遍历边数 (GTEPS)，这是异构机器中最好的，也是 2016 年 6 月 Graph500 列表中的第二名 [2]。
Interest has recently grown in efficiently analyzing unstructured data such as social network graphs and protein structures. A fundamental graph algorithm for doing such task is the Breadth-First Search (BFS) algorithm, the foundation for many other important graph algorithms such as calculating the shortest path or finding the maximum flow in graphs. In this paper, we share our experience of designing and implementing the BFS algorithm on Sunway TaihuLight, a newly released machine with 40,960 nodes and 10.6 million accelerator cores. It tops the Top500 list of June 2016 with a 93.01 petaflops Linpack performance [1]. Designed for extremely large-scale computation and power efficiency, processors on Sunway TaihuLight employ a unique heterogeneous many-core architecture and memory hierarchy. With its extremely large size, the machine provides both opportunities and challenges for implementing high-performance irregular algorithms, such as BFS. We propose several techniques, including pipelined module mapping, contention-free data shuffling, and group-based message batching, to address the challenges of efficiently utilizing the features of this large scale heterogeneous machine. We ultimately achieved 23755.7 giga-traversed edges per second (GTEPS), which is the best among heterogeneous machines and the second overall in the Graph500s June 2016 list [2].