Large-Scale Energy-Efficient Graph Traversal: A
Path to Efficient Data-Intensive Supercomputing
作者：
Nadathur Satish, Changkyu Kim, Jatin Chhugani, and Pradeep Dubey
Parallel Computing Lab, Intel Corporation
摘要
图遍历是一种在社交网络、商业分析等领域中广泛使用的算法，在高性能计算领域中更是如此。这使得对高性能计算机的评价不仅仅是千万亿次的规模，还需要有“GigaTEPS”（十亿次边访问每秒）的能力。因此一个新的对高性能计算机的评价标准Graph500产生了。
对于现在的CPU架构，在单个节点中的图遍历算法已经有了很深入的研究。然而，图遍历在当前的计算机集群实现过程中遇到了数据通信高延时和需要大量跨节点传输的问题，导致了性能的低下和能源的浪费。在这篇文章中将提到一种方法，这种方法结合了高效的低消耗数据压缩技术以及延迟隐藏技术以减少数据量的传输。文章中的方法对单节点的图遍历算法进行优化，达到了国家最先进水平性能的6.6倍，也有同样数量级的能源节省。实验结果表明，在2011年11月份的Graph500排名中，使用这种方法可以达到排名第二的机器的性能，而且比第二名的机器少用了5.6倍的节点，同时单节点的性能在Graph500的TOP10中排在首位。对比最优的单节点图遍历算法，这种方法仅有1.8倍的性能开销，并允许接近线性的扩大节点规模。
一．简介
手机通信、药物数据以及社交媒体交互在过去的十年中以一种爆炸式的速度产生了大量的数据，对这些大数据的分析是一个巨大的挑战。图作为一个模型已经被用在许多方面，例如像Google、Facebook还有Twitter的社交网络分析，生物数据系统，以及网页搜索等。由于在这些方面的大规模数据增长，在拥有兆兆字节以及更多数据的图中做遍历和分析显得越来越重要。
对于现今的数据规模，单个计算节点是不可能存得下整个图的，因此需要大规模的集群或者超级计算机。然而，将图遍历的算法分布在一个集群中实现已经被证明是一个很大的挑战。因为这个问题的重要性，图算法已经被用来作为对超级计算机性能评价的第二个准则，Graph500基准正是在这样的背景下被提出。Graph500是按照对图的广度优先搜索进行排序的。这个过程有一系列的步骤：在每一轮迭代中，一组边界顶点将与他们相邻的未访问的节点加入队列，用以下一深度的继续操作。这个算法产生整个图的最小的深度和对于每个节点的父节点。这个过程是图分析的基本构件，在其他图应用的数据访问方面也有着相同的特性。图分析已经被认为是百亿亿次级挑战的应用之一。
电力消耗相关的能源消耗在运行一个集群的总体消耗中占据着越来越大的比重。在以后这会变得更加昂贵。计算的供电还有运行时间需要消耗能源。一个重要的减少能源使用的方法是显示运行时间。整体的性能由两方面决定，一个是单节点的性能，另一个是在一个集群中节点级别的互访。文章中首先介绍单节点的优化遍历算法，接着扩展到多个节点。文章提到的算法使用了所有权的方法，即每个节点都拥有者一部分输入节点，以及对应的邻接节点信息。每一层的边界顶点都需要和拥有这些顶点的计算节点通信。在这个过程中，这些大量的还有高延迟的通信是一个最主要的性能瓶颈，也是这边文章重点关注的优化方向。
我们首先关注减少通信的数据量。典型的实现方法是对每一个访问的边传递可能的边界顶点以及父节点，依据Graph500每一个点需要16个字节表示。这就要占超过96%的整体运行时间。一个减少2倍数据量的方法可以很容易通过使用4字节的本地节点标志去对占8个字节的顶点和父节点标志进行编码。同时，有很多重复的边界顶点（有着不同的父节点）需要传输，我们可以通过传输独特的边界顶点与明确的父节点实施解重复。然而这样的方法没有足够的压缩。更进一步地，因为顶点和父节点标志随机的共性，结果数据的传输拥有着很高的随机性，数据传输只有很低的压缩率。
接着我们通过父节点和边界节点传输解耦合提出一种改变的算法。与先发送可能的父节点相比，我们仅仅传输一个节点第一次访问的父节点。因为这样对于每个节点只发生一次，这样就会很大程度地减少了整体的数据流量到1.8~1.9倍。另外，已经传输的边界节点现在可以以一种熵较少了的方法进行重新排列。我们使用了位矢量来编码这些重新排列的顶点，这样对于每一条边整体压缩率是以前发送8个字节的6.2~9倍。
为了减少数据通信延迟对于性能的影响，我们使用了两方面的优化。首先，我们使每个节点上的通讯以及计算同时进行。这样做的目的是在通讯发生时保持节点的忙碌。第二，由于父节点之间的通信会牵扯到小信息的传输导致高延迟的影响，我们尝试将这些传输与边界顶点通信结合。然后，在给定的深度中，这些通信是相互独立的，父节点的通信只能在边界顶点已经接受和处理之后开始。因此，我们使用管道技术将给定深度的边界顶点通信和现役深度的父节点传输相结合（使用软件流水线概念）。这两个技术使得整体性能有着2.1倍的提升。
相比最近发布的以集群实现的图遍历系统，使用了压缩和延迟隐藏技术后可以得到超过6倍的单节点的性能提升。对于使用每天边8个字节的基准性能，我们得到6.6倍性能上的提升。减少数据量的传输同时也降低了电源的消耗。基于基准的集群实施，电源的减少和性能上的提升的结合使得能源的消耗有8.1倍的改进。据我们所了解，这是首次文章中提及和测量Graph500中的能源消耗。文章实验中实现了Graph500基准中在2011年11月排名第二的拥有115GigaTEPS在320个节点（5120个Intel Xeon E5-2670处理器）的Intel Endeavor集群。在能量使用方面，我们使用Intel NodeManager API来测量能源，实现了1.5MTEPS/Watt的效果，这也可以用于最为将来的一个比较基准。文章中介绍的使用压缩和隐藏延迟的技术可以适用于广泛的图遍历算法，例如强连通分支，最短路劲以及中介中心。
二．问题描述
图问题是一个在无向图G = (V ,E)中广度优先搜索的问题。邻接矩阵使用Adj表示。给定一个开始的顶点s，这个算法产生输出对于每个顶点v∈V 有（a）从s到v的最少边数（b）v的父节点（定义为从s到v最短路径中v的前一个顶点）。
一个原始的BFS算法使用多步循环实现，每步循环对给定的一组边界顶点BVC进行迭代，寻找与每个顶点相邻的未访问的Adj结构并更新深度（Depth）（还有父节点（Parent）），和把他们加入到下一轮边界状态队列BVn中。在每次循环中有一个同步的点。建立一个高效的多节点BFS遍历挑战在于（1）减少每个节点中由于Adj，Depth，Parent等空间上不相关性造成的随机访问的影响（2）提供一种高效的分散式机制，以标志一个相邻顶点是否已经被访问过。这可以在延迟和带宽消耗方面带来低的开销。（3）不断增加的节点规模可以达到高的性能和能源效率。
Graph500 基准描述：Graph500基准制定了附加的条件要求。图G是特定的无尺度无向Kronecker图。对于每条边需要使用8个字节要存储，其中每个顶点需要至少48位。无向边的总数是顶点的16倍。性能的表示是以TEPS为单位，指的是遍历无向边的数目和所使用完成BFS时间的比例。所使用的BFS代码必须使用不同的初始顶点运行64次以得到统计上的平均运行时间。
在文章中，使图中的每条边变成不同方向两条，将无向图转换成有向图。对于每个方向，度数ρ乘以两倍达到32。因为遍历了Graph500标准输入中的两倍数量的边数目，因此在文章中得到的性能结果是实际结果中除以2的TEPS，以符合Graph500中指定的要求。
三．算法描述
在本节以及后续的章节中，文章使用如表一所示的符号表示优化的多节点BFS算法。在多节点的BFS遍历算法中使用了单节点的最优化算法作为子模块来扩展到多节点系统，同时对MPI通信做了优化以减少在每个每个节点中的计算量以及数据传输，以尽可能在效率上接近单节点性能中的最优效率。以下将简要介绍单节点算法来说明文章中的计划。
表一：在本文所用的符号
符号 |
表示 |
符号 |
表示 |
|V | |
图中顶点数 |
|E| |
图中边数 |
|V `| |
已经指定深度的顶点数 |
|E`| |
已经被访问的边数 |
|VS| |
节点S中的顶点数 |
|ES| |
节点S中的边数 |
ρ` |
已遍历顶点的平均度数 |
D |
图的深度 |
M |
计算节点数目 |
P |
每个节点中的核数 |
BM |
在每个节点主存上B/W（GB/秒） |
Freq |
核的频率（GHz） |
|VIS| |
VIS数组的大小，等于|V|/8字节 |
L |
高速缓存大小（字节） |
A.单节点BFS遍历：
这个算法维护了一个常驻内存的辅助位结构（表示为VIS），以检查一个顶点是否已经被赋值一个深度。VIS被分成NVIS个部分，使得每个部分都适合整个最后一级缓存的大小，以及可以使用一种原子性的方法来更新以减少延迟和开销对性能的影响。这个算法在不断的循环中迭代，每一步都包含了以下两段程序（如图一）：
在第一个程序片段：对于每个线程，平均分割边界顶点集（）。每个线程都被赋予一组的顶点以访问Adj。然而，因为不连续的顶点会指向空间上不邻近的内存区域，这种访问模式不可以通过硬件上的先获取来捕获。因此，当对一个顶点访问Adj时，发出预取邻域的指令将后续顶点存在第一级缓存中。对于每一个已经访问的邻域节点，计算他们的bin_id（根据vertex_id）并加到相关分区（PBVt）中。为了帮助邻域计算，需要数对（vertex_id,parent_id）。正如以上所述，NVIS分离部分被创建为缓存友好的VIS访问。在第一个程序片段的结尾有一个等待。
图一：单节点的BFS图搜索
在第二个程序片段：每个线程已经被平均地分到一部分顶点。当对一个给定的顶点分区进行操作时，对于每个顶点，执行UPDATE_BV_VSI（原子性地更新VIS数组），将一系列的顶点从VIS中更新到下一步边界状态（）。假设顶点没有被访问到，它的depth和parent都要更新。当没有新的节点添加到时，算法结束。
B.可扩展多节点算法：
一个重要的原因为什么图遍历是一个很难扩展的问题是遍历需要很多的节点间通讯，但是节点间的带宽却是受限的。举一个例子，在一个1GBps的无线宽带链接中（假设节点频率为2.6GHz）传输一条8字节的边需要20.8个时钟周期，这比单节点的性能要差10倍。另一个原因是节点间通信的高延迟。在节点间的像PBV数据结构传输的延迟比共享存储访问的延迟要高出一个数量级。正是因为这样的原因，多节点实施需要另外的优化。
在这篇文章中，提及到一种使用上述技术结合的图遍历方法。这种方法可以在Graph500列表的万亿字节或更大规模中最大程度地提升多节点实施的效率。
节点之间的数据分离：Adj数组在节点间是分布存在的。我们将顶点分布在不同的节点中，每个节点保持它拥有的顶点的邻接数据。因为每个顶点的度数有很大的区别，我们按照邻接结构的大小将顶点分离，使得每个节点都有差不多大小的邻域信息。每一个节点保持其他节点的顶点范围。对于一个节点m，我们用SVM来表示初始节点，因此节点m拥有的顶点范围是[SVM…SVM+|Vm|]。每一个节点负责在每一个深度中遍历一组子集拥有的BV顶点子集。这些数据结构都保存在每一个节点的非均匀存储访问感知方式中，就像在单节点算法的时候一样。
算法概要：图二展示了用于多节点遍历的整个图的算法。在某一个遍历的深度中，每个节点（m）都会根据一系列的BV去寻找他们的邻近顶点，像单节点算法一样，并生成PBV数组。然而在PBV中的顶点可能属于任何的节点。这就需要在PBV中的顶点与拥有这些信息的节点间进行交流。每一个节点都会从其他所有的节点中接收和收集一系列属于自己的PBV记录，接着继续更新DP数组并产生新的BV数据以用于下一个深度的遍历（像在但节点实施一样）。
图二：多节点的BFS图遍历算法
为了更高效地在不同节点间对PBV中的顶点进行通信，我们只发送一个拥有所有需要传播数据的一条信息。这需要我们将每一个节点PBV记录打包成M份（M代表了节点的总数），其中每一个包（PBVM）得到所有顶点在节点m中记录。这可以很容易地在保持VSI缓存的同时合并到NVIS中，这总共需要M*VIS个箱。对于小型或者中型的接近2000个节点的集群，我们发现这样附加的打包没有导致明显的性能退化.
由于节点间的带宽限制，主要的性能关键是在节点间的大量数据传输。当对每个节点拥有的顶点遍历其Adj时，一对（vertex_id,parent_id）将会被加入到PBVM中。当通过每一循环遍历后，这些数据会传播到相关的节点中。我们现在关注这些数据的通信，并提出一种算法减少需要传输的数据量的方法，以至于用在计算方面用最低的花销提高性能。保持整体花销的低水平是一件很困难的事情，因为这些步骤都要在遍历的算法过程中实施，为了减少传输数据量带来的花销会被加入到整体的BFS遍历花销之中。
C.通过压缩减少节点间的数据流量：
方案一，对（vertex_id,parent_id）使用四字节存储：每一个顶点都使用按顺序的64位id，这样原始的实现需要对每个vertex_id以及parent_id使用8个字节来，总共对于每一条边需要发送16个字节。
但是，对于现在给定的在每个节点的主存大小，||（在节点m中的顶点个数）小于，这在每个节点中需要大于1万亿字节的存储空间。由于每个节点都保存着一个范围的顶点，对于每个节点，可以转换为local_vertex_id（通过对每个节点减去最少的vertex_id），和相应的local_parent_id。这样对于每一条边可以减少8字节的传输，这也所谓后面更多的提升和改进的基础。
方案二，数据冗余清除：现在主要关注的是PBV中值对的数据在节点间的传输。很容易可以发现，在PBV中整体值对在节点间的传输数目和所有的高度结合起来接近图中所有已遍历边的数目。但是，所有的在PBV数组中不重复的记录数目只能是图中已经遍历的顶点数目，以一个因子ρ`（标准化的图度数）次小于边数。这一位这每一个在PVB中的记录都会重复大约ρ`次。还有，由于结果的输出是一个树，每个顶点实际只需存储一个父节点，因此有很多冗余的值对因为潜在的分布不共享的多节点部署被传输。
虽然因为这些重复的节点会在不同深度的不同节点出现，因而不能消除所有的这些重复，但是知我在每个节点的每一次特定深度的重复可以消除。对于Graph500中的Kronecker图，ρ`∼64，和大多数在一些深度中被遍历的边，会增加重复的可能性。
因此，在传递PBV对之前，所有拥有相同的local_vertex_id的值对都会合成一个相同的local_vertex_id，然后从所有值对中任意地选取一个local_parent_id。我们使用一种高效的低开销的位结构方法来达到这个目标。这个节点间通信减少的实现是基于图特性的一个函数，而且可以随着顶点的平均节点度增长而增长。在实际中，对于Graph500中的Kronecker图，对于不同图的大小，我们可以实现介于1.2~1.4倍之间的通信减少
方案三：可变长度压缩：作为一个极限研究，我们实施了在节点间的动态压缩。特别地，处于这样的目的我们使用了bzip2压缩和解压算法。在这样的极限研究中，我们同样使用了local_vertex_id去减少结果的熵和提高数据传输的压缩率。但是，最后实现的数据传输减少了1.05~1.15倍，却带来了很大的计算开销（节点11~23倍增加的计算时间）。因此我们使用了接下来的一种算法改变了将要被传输的PBV内容，如下面描述。
D.将Parent_Ids与Vertex_Ids分离：
正如上面提到的，对于每一个指定深度的顶点，只需要存储下一个父节点信息。但是我们预先地发送了parent_id连同vertex_id一起，即使仅仅需要传输一个可行的parent_id就可以了。因此我们修改了这种协议，取而代之每个节点只需传送相关的vertex_id作为PBVM的一部分。一旦节点（这里是m）从其他不同的节点中接收到了所有的PBVM包，它就会检查自己本地的VIS数组，如果一个顶点还没有被记录下深度，这个节点就会被添加到Parent_Query（PQ）包中，并发送回原来发送PBVM包的节点中。注意对于任何给定的顶点在这一步被更新的时候，这个父节点信息请求只需发送到任何一个源节点中，而不需要发送到所有来源节点。
在遍历了所有的顶点后，这些Parent_Qurey包就会传输回来，然后源节点计算相关的父节点并且送回Parent_Response（RR）包到目标节点（m）中，然后目标节点（m）就会利用这些信息设置节点中顶点的父节点。这带来了戏剧性的通信减少，因为相比之下，对于每个节点，原来平均ρ的通信降低到2。这带来了倍的通信量减少。
就节点间的通信量减少而言，到此为止我们实现了1.8~1.9倍的降低。另一个发送分离的vertex_ids的好处是现在这些ids可以以任何的方式被被重新排列——因为他们全部都便是这一系列的对应于某个深度的顶点集。这样我们就可以进一步地对他们进行排序并进一步地通过压缩来减少通信量，这将会在下面描述。
方案四：位向量表示：对于一个给定的拥有一系列顶点的PBVM包，我们可以通过维护一个位数组（BitArraym）来表示，其中每一个顶点用一位来表示，如果存1就说明顶点包含在PBVM中，如果不是则存0。对于一个节点m来说，BitArraym的全部大小等于字节。如果BitArraym的的大小比PBVM小的话，我们就会传输BitArraym。我们传输的BitArraym，与PBVM有着相同的表示，除非顶点集现在已经被表示为一种排好序的方式，这样的话使用位向量表达对BFS遍历的结果没有什么影响。主要到的是传输BitArraym。我们实际上已经自动执行了离散化，因为对于每个顶点只发送一次。对于一个很大通信量的深度中，这种方法可以导致将近每条边0.9~1.3字节传输，不同的性能依赖于节点M拥有的顶点数。
即使还有可以做更加深入压缩的可能（使用实时delta编码以及可变长度压缩），上面所说的方法在试验中证明对于多大上千的节点足够满足需求。主要到所有这些数据减少或者压缩的技术都需要在运行时实施，而且数据在每一次计算中都需要解压缩，这样耗费的时间都要在整体的时间消耗中被考虑。因此，在存储通信量减少方面需要权衡高代价的压缩技术对结果影响的代价。
四．实验评价
平台描述：我们在一个有320个节点的Intel Endeavor 集群中来检验我们的图遍历算法，每个节点有64GB的RAM和16个2.6GHz的基于E5-2670系统的双插槽Intel Xeon处理器。总共的核数为5120个。每一个核有64KB的一级L1缓存和256KB的二级L2缓存。在同一个插槽的核共享最后一级L3的20MB缓存（LLC）。所有的缓存都保持一致性。不同的节点间使用QDR Infinband 4X连接，峰值可达4GB/s的带宽，使用双向的14元胖树拓扑结构。我们也在基于Intel XeonX5670处理器以及Intel Xeon E5-2670节点系统的NASA的Pleiadas超级计算机运行我们的代码。实验中使用Intel Composer XE2011编译器以及Intel MPI 4.0.3内库。
算法的可扩展性：图三（a）显示了我们算法在320个节点中使用标量基准的2个线程的核可扩展性。这里从两个线程开始因为一个线程为了实现MPI操作而保留。图中显示可扩展性在2到8线程的时候呈现接近线性的趋势。这里的代码首先与存储访问的延迟。一旦我们使用SMT（同时多线程），延迟就被隐藏了并带来了性能1.4倍的提升。现在算法主要被存储的带宽所限制，因此我们得不到更高的可扩展性。最后，我们使用socket来扩展得到1.85倍的提升。单节点代码的NUMA感知带来了低的socket间通信。
图三（b）显示了从32到320个节点从到个顶点的一个弱可扩展的趋势。在小于32个节点时，算法得到的效果的是完全线性的。从32到320个节点，我们得到一个接近线性的可扩展性，9.6倍相对于10倍的峰值。注意到每个节点中的性能比单一节点的最优性能降低了1.8倍，原因是在压缩和解压的过程造成了开销。
图三：在Graph500中图遍历的扩展性使用输入（a）线程数目（b）节点数目
性能比较：图四中显示了不同优化方案对相对性能的影响。所有的在图四种的性能都和上述的方案相对应。第一栏显示了我们再单节点实施的最优性能，使用方案一中所说的每条边发送8个字节的策略。在这种实施对逆向算法的影响大概有1.7倍。这种影响随着后面我们对向前阶段使用MPI来优化消耗更少的时间而逐渐降低；而在逆向阶段基本保持不变。这样的实施在计算和通信之外还要多花58%的时间，这种低效是因为节点间的动态负载均衡带来了很大的影响，某些节点遍历更多的边和比其他节点传送更多的数据。
第二栏显示了方案二的实施，以1.6倍更多计算为代价，实现了减少冗余以及使用了每条边传送6个字节的方法。这样的方法比前一个有了1.33倍的性能提升，大概是整体带宽提升的比例，尽管增加的计算。我们注意到在负载均衡的过程中，那些比较低效的节点同时拥有了更多的冗余数据，因此减少冗余同时也带来了更好的负载均衡。
第三栏显示了分离父节点通信同时使用方案二的情况。这里性能进一步提到到1.4倍。这里由于需要查找父节点会带来了一些新增小计算。
接着我们显示了方案四种使用位矢量压缩技术的性能。是用这样的技术可以显著地减少把MPI带宽需求从4.13字节每条边降低到2.63字节每条边，就是大概1.6倍性能的提升。在这个方案中，我们注意到逆向算法只给出了1.4倍的性能提升，由于前面程序算法的更改已经对性能有显著的提升。相比前一个方案，整体性能1.75倍的提升比MPI带宽的降低要大。这个主要的原因是负载均衡在整体的运行时间中降低了20%~30%；发送的位矢量是一个固定长度不相关的PBV数组。压缩方法带来整体性有3.2倍的提升。
最后，两个将计算与通信重叠的改进方法还有管道技术将性能提升到方案四的2.1倍。这样我们最后的方案在整体的性能收益上是原始方案一的6.6倍。将计算和通信重叠带来了1.7倍的性能提升，而管道技术有1.2倍更进一步的提升。最后的这个方案中，花在计算和通信的时间是差不多的，整体计算所花的时间比通信花的时间只差5%。
图四：在多节点上不同优化方案得到的性能比较
能源比较：在图五中显示了使用优化的压缩技术延迟隐藏技术得到的能源高效的好处。这样的优势源于上面提到的性能上的提升以及压缩带来的节点间通信数据量的降低。虽然我们并不直接测量相互连接消耗的能源（只是测量每个计算节点的能源消耗），由于需要将包在用户可见的区域间拷贝，高的节点间通信也会带来在计算节点上更高的存储带宽消耗。在实际中，经过了算法的优化，我们可以看到有1.25倍的能源被节省下来（平均240Watts相比没有优化之前的300Watts）。另加上上面提到的6.6倍性能的提升，我们得到整体8.1倍能源效率提升。整体的能源效率为1.5MTEPS/Watt。
图五：不同优化方案得到的能源效率比较
五．结论
在这篇文章中，展示了通过结合低消耗的数据压缩技术降低通信数据量以及延迟隐藏技术，得到了在多节点集群上图遍历的高性能表现。结合这个算法的创新性以及实现最大限度地利用所有现代集群为基础的多核心处理器的微架构，我们得到了在图遍历中6.6倍性能以及同等数量级的能源效率的提升。文章中得到的结果可以达到2011年11月Graph500中排名第二的结果并且比原本的实现减少使用了5.6倍的节点，同时在排名的前十名中有着最高的单节点性能。
在以后的研究中有着两个方向。一个是可以将算法使用在更大的集群上并使用delta编码以及可变长压缩提升压缩率。另一个是需要加强能源消耗测量的方法以更好地解释由于降低通信带来的互连功耗的降低。
参考文献
[1] J. Chhugani, N. Satish, C. Kim, J. Sewall, and P. Dubey, “Fast and efficient graph
traversal algorithm for cpus : Maximizing single-node efficiency,” Parallel and
Distributed Processing Symposium, International, vol. 0, pp. 1–10, 2012.
[2] “The Graph 500 List (Nov 2011),” http://www.graph500.org.
[3] H. Kwak, C. Lee, H. Park, and S. B. Moon, “What is twitter, a social network or
a news media?” in WWW, 2010, pp. 591–600.
[4] A. Mislove, M. Marcon, P. K. Gummadi, P. Druschel, and B. Bhattacharjee,
“Measurement and analysis of online social networks,” in Internet Measurement
Conf., ’07, pp. 29–42.
[5] M. Fernandez, D. Florescu, A. Levy, and D. Suciu, “A query language for a Website
management system,” SIGMOD Rec., vol. 26, pp. 4–11, September 1997.
[6] U. Kang, C. E. Tsourakakis, A. P. Appel, C. Faloutsos, and J. Leskovec, “Radius
plots for mining tera-byte scale graphs: Algorithms, patterns, and observations,” in
SDM, 2010, pp. 548–558.
[7] D. Bader, “Exascale Analytics of Massive Social Networks,” 2010, AN09 Minisymposium
on High Performance Comp. on Massive Real-World Graphs.
[8] M. Anderson, “Better benchmarking for supercomputers,” IEEE Spectrum, vol. 48,
pp. 12–14, January 2011.
[9] R. C. Murphy, K. B. Wheeler, B. W. Barrett, and J. A. Ang, “Introducing the graph
500,” Cray User’s Group, May 2010.
[10] P. Kogge and K. B. et al., “ExaScale Computing Study: Technology Challenges in
Achieving Exascale Systems,” 2008.
[11] J. Dongarra, P.Beckman, et.al,, “The international exascale software project
roadmap,” International Journal of High Performance Computing, vol. 25, no. 1,
pp. 3–60, 2011.
[12] D. G. Andersen, J. Franklin, M. Kaminsky, A. Phanishayee, L. Tan, and V. Vasudevan,
“Fawn: a fast array of wimpy nodes,” in SOSP, 2009, pp. 1–14.
[13] J. G. Koomey, “Worldwide electricity used in data centers,” Environmental
Research Letters, vol. 3, no. 3, p. 034008, 2008. [Online]. Available:
http://stacks.iop.org/1748-9326/3/i=3/a=034008
[14] Julian Seward, “Bzip2: Program and Library for lossless, block-sorting data
compression. ,” 2012. [Online]. Available: bzip.org
[15] K. M. Wong and S. Chen, “The entropy of ordered sequences and order statistics.”
IEEE Transactions on Information Theory, vol. 36, no. 2, pp. 276–284, 1990.
[16] H. E. Williams and J. Zobel, “Compressing integers for fast file access,” Comput.
J., vol. 42, no. 3, pp. 193–201, 1999.
[17] Toyotaro Suzumura et al., “Performance characterization of the graph500 on largescale
distributed environment,” in IISWC, 2011.
[18] A. Buluc¸ and K. Madduri, “Parallel breadth-first search on distributed memory
systems,” in SC, 2011, p. 65.
[19] Intel, “Intel Data Center Manager,” http://software.intel.com/sites/datacentermanager/,
2012.
[20] D. Bader, G. Cong, and J. Feo, “On the architectural requirements for efficient execution
of graph algorithms,” in Parallel Processing, 2005. ICPP 2005. International
Conference on, june 2005, pp. 547 – 556.
[21] J. R. Crobak, J. W. Berry, K. Madduri, and D. A. Bader, “Advanced shortest paths
algorithms on a massively-multithreaded architecture,” in IPDPS, 2007, pp. 1–8.
[22] D. A. Bader, S. Kintali, K. Madduri, and M. Mihail, “Approximating betweenness
centrality,” in WAW, 2007, pp. 124–137.
[23] “Intel Advanced Vector Extensions Programming Reference,” 2008,
http://softwarecommunity.intel.com/isn/downloads/intelavx/Intel-AVXProgramming-
Reference-31943302.pdf.
[24] “The Message Passing Interface (MPI) standard,”
http://www.mcs.anl.gov/research/projects/mpi/.
[25] “Intel MPI Library,” http://software.intel.com/en-us/articles/intel-mpi-library/.
[26] T. Willhalm, N. Popovici, Y. Boshmaf, H. Plattner, A. Zeier, and J. Schaffner,
“Simd-scan: ultra fast in-memory table scan using on-chip vector processing units,”
Proc. VLDB Endow., vol. 2, no. 1, pp. 385–394, aug 2009.
[27] C. Kim, J. Chhugani, N. Satish, E. Sedlar, A. D. Nguyen, T. Kaldewey, V. W. Lee,
S. A. Brandt, and P. Dubey, “Fast: fast architecture sensitive tree search on modern
cpus and gpus,” in SIGMOD. ACM, 2010, pp. 339–350.
[28] R. Motwani and P. Raghvan, Randomized Algorithms. Cambridge University Press,
1995.
[29] S. Beamer, K. Asanovic, and D. A. Patterson, “Searching for a
parent instead of fighting over children: A fast breadth-first search
implementation for graph500,” EECS Department, University of California,
Berkeley, Tech. Rep. UCB/EECS-2011-117, Nov 2011. [Online]. Available:
http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-117.html
[30] C. E. Leiserson, “Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing,”
IEEE Transactions on Computers, vol. 34, no. 10, 1985.
[31] NASA, “Pleiadas supercomputer,” http://www.nas.nasa.gov/hecc/resources/pleiades.html.
[32] V. Agarwal, F. Petrini, D. Pasetto, and D. A. Bader, “Scalable graph exploration
on multicore processors,” in SC, ’10, pp. 1–11.
[33] C. E. Leiserson and T. B. Schardl, “A work-efficient parallel breadth-first search
algorithm (or how to cope with the nondeterminism of reducers),” in SPAA, 2010,
pp. 303–314.
[34] Y. Xia and V. K. Prasanna, “Topologically Adaptive Parallel Breadth-first Search
on Multicore-Processors,” in PDCS, 2009.
[35] S. Hong, S. K. Kim, T. Oguntebi, and K. Olukotun, “Acc. CUDA graph algorithms
at max. warp,” in PPOPP, ’11, pp. 267–276.
[36] D. P. Scarpazza, O. Villa, and F. Petrini, “Efficient breadth-first search on the
cell/be processor,” IEEE Trans. Parallel Distrib. Syst., vol. 19, no. 10, pp. 1381–
1395, 2008.
[37] A. Yoo, E. Chow, K. W. Henderson, W. M. III, B. Hendrickson, and U¨ . V.
C¸ ataly¨urek, “A scalable distributed parallel breadth-first search algorithm on
bluegene/l,” in SC, 2005, p. 25.
[38] J. Jose, S. Potluri, M. Luo et al., “Upc queues for scalable graph traversals: Design
and evaluation on infiniband clusters,” in PGAS, 2011.
[39] V. Marjanovi´c, J. Labarta, E. Ayguad´e, and M. Valero, “Overlapping
communication and computation by using a hybrid mpi/smpss approach,” in
Proceedings of the 24th ACM International Conference on Supercomputing, ser.
ICS ’10. New York, NY, USA: ACM, 2010, pp. 5–16. [Online]. Available:
http://doi.acm.org/10.1145/1810085.1810091
[40] B. V. Protopopov and A. Skjellum, “A multithreaded message passing
interface (mpi) architecture: performance and program issues,” J. Parallel
Distrib. Comput., vol. 61, no. 4, pp. 449–466, Apr. 2001. [Online]. Available:
http://dx.doi.org/10.1006/jpdc.2000.1674
[41] Mao Jiayin and Song Bo and Wu Yongwei and Yang Guangwen, “Overlapping
107 Communication and Computation in MPI by Multithreading,” 2006.
[42] V. H. Allan, R. B. Jones, R. M. Lee, and S. J. Allan, “Software pipelining,” ACM
Computing Surveys, vol. 27, no. 3, pp. 367–432, 1995.
[43] H. Simon, “Exascale computing: Applications performance and energy efficiency,”
Santa Barbara Summit on Energy Efficiency, April 2011.
原文链接：
http://delivery.acm.org/10.1145/2390000/2389015/a14-satish.pdf?ip=121.33.190.176&acc=ACTIVE%20SERVICE&CFID=157831126&CFTOKEN=45283573&__acm__=1355670401_366551a7ab8fdb95cde090cc1572da81