ACM通信
中国地区专区:热点话题
在中国超级计算机上处理极尺度图
来源:新华社
许多应用程序，例如Web搜索、社会网络分析和电网管理，都需要超大规模的图处理。然而，由于图处理具有负载不平衡、缺乏局部性、访问不规则等独特特点，因此具有很大的挑战性。极端的图表规模使情况更加糟糕。
超级计算机的计算量大，内存大，互连速度快。它们似乎非常适合超大规模的图形处理。中国已经建造了几台世界领先的超级计算机。例如，从2013年6月到2018年5月，天河二号和神威太湖之光超级计算机10次位列Top500榜单第一名。与许多其他超级计算机一样，它们使用异构加速器来实现常规工作负载(如基于模板和基于结构化网格的计算)的高性能。它们是否也能够处理极端规模的图?
太湖之光的独特功能之一是异构片上SW26010 CPU。
在本文中，我们将讨论我们在两个领先的超级计算机架构中实现极端规模图处理的努力。
天河五金特色。天河超级计算机在其多核CPU架构和高性能互连网络方面有着独特的设计，为图形处理提供了机遇和挑战。
数字位于中国江苏省国家超级计算机中心的太湖之光超级计算机。
天河的计算节点(CN)使用专有的Matrix-2000+ cpu(参见图1)．一个CN有3个Matrix-2000+处理器，每个处理器有128个2GHz核。每个核心都有一个顺序的8到12级管道，通过可伸缩矢量扩展(SVE)进行扩展。Matrix-2000+ CPU采用区域自治并行架构，一个CPU由四个区域组成，通过可扩展的片上通信网络连接。每个区域都是一个功能独立的超级节点(SN)，四个面板通过区域内接口进行通信。每个面板有8个缓存相干计算核。SVE使Matrix-2000+通过两种使用模式选择最合适的矢量长度:自动矢量长度不可知(AVLA)模式和装配矢量长度指定(AVLS)模式。AVLA模式可以自动将子向量打包成向量，但需要两个向量处理之间的同步，而AVLS模式允许程序员指定用户自定义的子向量长度。
图1。Matrix-2000+ CPU架构。
天河的网络子系统采用了光电混合互联的多维树形拓扑结构，结合了树形拓扑结构和n-D-Torus拓扑结构的优点。网络逻辑集成到网络接口芯片(HFI-E)和网络路由器芯片(HFR-E)中。HFI-E实现了专有的MP/RDMA(迷你包/远程直接内存访问)通信和集体卸载机制。连接到HFR-E的中枢神经网络处于同一通讯域。天河集团高度优化了域内通信，比跨多个hfr - e的域间通信速度快了一个数量级。
利用硬件特性进行图形处理。与传统的SIMD(单指令多数据)技术不同，Matrix2000+ cpu支持向量化来加速图的计算。我们利用SVE实现了高效的图遍历。
传统的向量化导致处理连续向量之间的同步(通过插入档位)，从而降低了整体性能。幸运的是，我们发现图遍历(如BFS)只是扫描一个顶点范围，以确定下一层要遍历的顶点，如果没有一个顶点属于一个以上的层，则允许避免同步。这种情况的存在可能仅仅是因为图中存在循环。为了解决循环问题，如果一个顶点存在于两个连续的关卡中并导致了循环，我们将其分割为两个虚拟点。此外，如果我们在预处理过程中发现一个顶点属于多个级别，我们在每个级别上使用一个虚拟顶点来参与该级别的向量化处理。
采用AVLA和AVLS算法，实现了高效的图遍历。如果遍历很可能会遇到循环(例如，在自顶向下的BFS中)，那么我们采用AVLA自动将未访问的相邻顶点(子向量)打包到向量中，同时避免顶点分裂(在开销显式同步时)。否则，它不太可能遇到循环(例如，在自底向上的BFS中)，因此我们通过AVLS将邻居打包到向量中，并在循环发生时分割顶点。AVLA和AVLS加速了每个线程(核心)处理不同顶点范围的过程，并检查连接到未访问顶点的边，以确定是否应该在下一层访问相邻顶点。
为了使图处理适应天河的多维树形网络拓扑结构，我们用融合而且裂变3.当存储图顶点和边时。具体来说，融合将一组相邻的低度顶点组织成一个超级顶点(用于处理局部性)，裂变将一个高度顶点分解为一组兄弟子顶点(用于负载平衡)。重构由中枢神经网络上的所有工作人员并行执行，我们通过对顶点状态的双重检查来解决潜在的冲突。工作人员在将顶点移到处理队列和执行融合/裂变之前检查顶点是否已被处理。如果发生冲突，将跳过进一步的处理。
天河超级计算机在其多核CPU架构和高性能互连网络方面有着独特的设计，为图形处理提供了机遇和挑战。
重构图的顶点和边根据多维树拓扑的接近性分配给网络中的cnn。相邻顶点被分配到同一个通信域。图重构可以用赋值流水线化，因此只会产生少量额外开销。3.注意，分区结果是可重用的。因此，在大多数情况下，为额外的重构开销买单是值得的。
我们进一步利用拓扑信息来执行积极的消息聚合。消息被收集到源域中的负责节点(称为监视器)，在监视器之间传输，并分散到目标域中的目标节点。采用自适应缓冲区切换和动态缓冲区扩展，有效地降低了通信成本。
图处理在天河上的应用。天河图处理系统在中国的工业领域中得到了广泛的应用，如计算生物学、工业仿真和可视化。
北京华大基因研究院(BGI)与上海药物研究所(SIMM)共同构建了基于天河图处理系统的高通量药物虚拟筛选平台。该平台每天筛选超过4000万个抗埃博拉病毒药物分子化合物，实现了历史上最快的高通量虚拟药物筛选，在抗埃博拉药物研发中发挥了重要作用。核心算法拉马克遗传算法(LGA)2在512 ~ 8192个CNs(最高19.7K CPU核)的天河图处理系统上进行深度加速，形成全局-局部混合搜索问题。我们的图形处理系统的效率高达60%。
陕西省大规模电磁计算重点实验室(LEC)开发了应用于海量并行矩量法(MoM)的复矩阵局部块旋转LU (LBPLU)分解软件。LEC实验室在天河上运行局部旋转LBPLU，求解由MoM生成的矩阵方程。具体来说，为了模拟飞机的电磁散射，LBPLU将飞机表面划分为网格结构，其中每个网格节点是图的顶点，网格节点之间的影响建模为边。LBPLU在网格上进行三角剖分，实现流动可视化。在LBPLU运行时，当并行规模为8192CNs (19.7K核)时，系统的并行效率高达50.16%。
为了最大限度地利用超级节点内的全等分带宽，我们使用超级节点边界组成目标组。
我们还在下一代百亿亿级天河超级计算机的一个子集上部署了图形处理系统，天河超级计算机由512cn和96608核组成。性能评估表明，该512节点子系统在Graph500的BFS测试中达到2131.98 Giga TEPS(每秒遍历边数)，优于节点数增加16倍的天河2号超级计算机。
神威太湖之光图形处理
太湖之光的建筑是在图2．太湖之光的一个独特的特点是异质片上SW26010 CPU(见右图)图2)．每个SW26010 CPU由4个核心组(cg)组成，通过低时延片上网络(NoC)连接。每个CG由一个MPE (management processing element)、一个64核CPE (computing processing element)集群和一个内存控制器(memory controller)组成，每个CPU (node)共260核。每个CPE都附带一个64KB的无缓存的临时存储器(SPM)，这需要显式的程序员控制。该体系结构要求手动协调所有数据移动，这对于不规则的随机访问来说是一项特别具有挑战性的任务。
图2。太湖之光的建筑。
太湖之光的中枢网络通过2级ib网络连接。一个具有全等分带宽的单交换机连接一个超级节点内的所有256个节点，而一个具有全等分带宽1/4的胖树连接所有超级节点图2)．
将图形处理模块映射到异构处理器。在每个SW26010 CPU中，四个CPU被分配有不同的功能图3:(A)生成，(B)中继，(C1)粗排序，(C2)更新。这个函数映射是静态的，每个函数只由一个CG执行。此映射的目标是实现平衡的CG利用率。这种流水线架构允许我们以流的方式处理批处理数据，降低了对主存储器的I/O复杂度，并提高了片上带宽的利用率。
图3。cpe中的超级节点路由和模块映射。
在第二级专门化中，我们利用每个CG中的特定硬件特性。MPE非常适合进行任务管理以及网络和磁盘I/O，而cpe通过2D快速通信特性紧密相连，自然会导致我们在MPE上分配通信任务，在cpe上分配数据排序任务。
Supernode路由。该技术的目标是高效的节点间通信，从而在整个系统上实现异构处理管道。
分布式图应用程序的性能通常会被图拓扑发送的大量小消息所破坏。由于每个消息的开销(路由信息、连接状态等)，10,000个节点之间的all-to-all风格的小消息效率很低。我们提出了一种超级节点路由技术，通过根据它们的超级节点从属关系将所有计算节点分解成组来缓解这一问题。每个节点将发送到同一目标组内节点的所有消息组合为发送到该组内指定节点的单个消息。这个所谓的中继节点将接收到的消息进行解包，将来自不同源组的消息进行梳理，将发送到每个组内目标节点的消息重新打包为一个消息，并将它们分发给相应的对等点。
为了最大限度地利用超级节点内的全等分带宽，我们使用超级节点边界组成目标组。每个源节点都尽量减少发送到目标组中的中继节点数量(通常每个目标组一个中继节点)，以有效地执行消息聚合。为了实现负载均衡，目标组中的每个节点都充当中继节点。如果超级节点中存在故障节点，情况就更加复杂，我们使用随机重放分配来保持负载平衡。
数字申屠数据集和性能。
申图图处理框架。除了硬件专门化和超级节点路由之外，我们还有其他创新，如片上CPU排序和程度感知消息传递。由于篇幅有限，这里省略了它们。对更多细节感兴趣的读者可以参考林等人。1
最后，我们设计并实现了一个以顶点为中心的图形处理框架——Shentu。它可以支持PageRank、WCC和BFS等图形算法，只需大约30行代码就可以在TaighuLight的整个系统上运行。
需要注意的是，搜狗图是文献中处理过的最大的实图，它有12万亿个边，对于小规模系统来说是不允许的。申图在完整规模的神威TaighuLight中，每次PageRank迭代仅需8.5秒(见附表)。42克朗(70万亿个边)也是迄今为止文献中处理过的最大的合成图。
结论
在本文中，我们展示了具有不同异构架构特征的超级计算机如何有效地支持图形处理:带有SPMs和宽向量单元的片上处理单元阵列。我们还展示了如何使用向量化和超级节点路由等技术来优化图计算的所有对所有消息。我们期望这一结果不仅能够实现极端规模的图形处理，而且还暗示了超级计算和大数据架构的可能融合。
参考文献
1.林，H.，等。申图:在数秒内处理数百万核上的上万亿条边图。在2018 ACM实习生论文集。讨论超级计算。
2.G. Morris, Goodsell, D. Halliday, r.s.， Huey, R. Hart, W. Belew, R.和Olson, a .使用拉马克遗传算法和经验绑定自由能函数的自动对接。j .第一版。化学19(1998), 1639 - 1662。
3.张颖，王慧慧，贾明，王俊，李德生。TopoX:在图计算中最小化网络通信的拓扑重构。IEEE / ACM反式。网络28(2020), 2768 - 2782。
数字图书馆是由计算机协会出版的。版权所有©2021 ACM, Inc.
没有找到条目