GraphBolt：流图的依赖驱动同步处理

GraphBolt是一种高效的流图处理系统，可提供批量同步并行（BSP）保证。 GraphBolt执行依赖项驱动的增量处理，该处理可快速响应图形更改，并提供低延迟和高吞吐量的处理。 [阅读更多]

core / graphBolt /文件夹包含GraphBolt引擎，KickStarter引擎和我们的Stream Ingestor模块。可以在apps /目录中找到应用程序/基准代码（例如，PageRank，SSSP等）。有用的帮助程序文件，用于生成更改流（tools / generators / streamGenerator.C），以正确格式创建图形输入（tools / converters / SNAPtoAdjConverter.C-来自ligra的代码库）以及比较算法的输出（tools / output_comparators /）。

注意：默认情况下，gcc-5和gcc-7带有cilk支持。您可以使用update-alternatives工具轻松维护多个版本的gcc。如果您当前拥有gcc-9，则可以轻松安装gcc-5并按以下步骤切换到它：

$＃安装gcc-5 $ sudo apt安装gcc-5 $＃设置所有gcc版本的路径$ sudo update-alternatives --install / usr / bin / gcc gcc / usr / bin / gcc-5 50 $＃gcc- 9 version $ sudo update-alternatives --install / usr / bin / gcc gcc / usr / bin / gcc-9 60 $＃配置gcc以使用gcc-5 $ sudo update-alternatives --config gcc $＃验证gcc version $ gcc --version

-streamPath：输入流文件或管道的路径（有关输入格式的更多信息，请参见第2.4节）。

-numberOfUpdateBatches：可选参数，用于指定要进行的边缘更新的数量。默认值为1。

输入图文件路径（有关输入格式的更多信息，请参见第2.4节）。

$＃确保按照install_mimalloc.sh $的设置设置LD_PRELOAD。/ PageRank -numberOfUpdateBatches 2 -nEdges 1000 -streamPath ../inputs/sample_edge_operations.txt -outputFile / tmp / output / pr_output ../inputs/sample_graph.adj $ ./LabelPropagation -numberOfUpdateBatches 3 -nEdges 2000 -streamPath ../inputs/sample_edge_operations.pipe -seedsFile ../inputs/sample_seeds_file -outputFile / tmp / output / lp_output ../inputs/sample_graph.adj$ ./CF -s -numberOfUpdateBatches 2 -nEdges 10000 -streamPath ../inputs/sample_edge_operations.txt -partitionsFile ../inputs/sample_partitions_file -outputFile / tmp / output / cf_output ../inputs/sample_graph.adj.un$ ./SSSP -source 0- numberOfUpdateBatches 1 -nEdges 500 -streamPath ../inputs/sample_edge_operations.pipe -outputFile / tmp / output / sssp_output ../inputs/sample_graph.adj$ ./BFS -source 0 -numberOfUpdateBatches 1 -nEdges 50000 -streamPath ../inputs /sample_edge_operations.pipe -outputFile / tmp / output / bfs_output ../inputs/sample_graph.adj

根据算法，可能需要其他附加参数。有关受支持的参数，请参考应用程序代码（apps / PageRank.C，apps / SSSP.C等）中的Compute（）函数。图摄取器和图的其他配置可以在第5节中找到。

初始输入图应采用邻接图格式，例如，样本图的SNAP格式（边缘列表）和邻接图格式如下所示。

您可以使用工具/转换器/ SNAPtoAdjConverter将Edgelist格式（SNAP格式）的输入图转换为邻接图格式，如下所示：

$ ./SNAPtoAdjConverter inputGraph.snap inputGraph.adj $＃对于无向（对称）图，请使用-s标志$ ./SNAPtoAdjConverter -s inputGraph.snap inputGraphUndirected.adj

流输入文件应在单独的行上具有边缘操作（添加/删除）。边缘操作的格式应为[d / a]源目标，其中d表示边缘删除，a表示边缘添加。流输入文件示例：

可以使用工具/生成器/streamGenerator.C通过管道流化边缘操作。它采用以下命令行参数：

有关摄入器的更多详细信息，请参见第5节。有关加权图的信息，请参见第6节。

GraphBolt框架的一项关键设计决定是确保应用程序代码在不影响GraphBolt内部细微变化的同时仍提供快速性能。

因此，应用程序代码仅需要使用以下功能来表达其计算结果。有关这些功能的更多详细信息，请参见GraphBoltEngine.h的内联注释。

GraphBolt以聚合值的形式存储每个顶点的信息。因此，首先，用户应为算法识别聚合值和顶点值。例如，在PageRank中，顶点值是其页面等级（PR），聚合值是其所有inNeighbors中（PR [u] / out_Degree [u]）个值的总和。

在迭代图算法中，在给定的迭代i中，一组顶点会将一些值推入其outNeighbors。这些是该迭代的活动顶点。接收这些值的outNeighbors随后将计算其更新值。提供以下功能以强制顶点在给定迭代中处于活动状态/计算状态。例如，在“标签传播”中，所有顶点都应在每次迭代时计算其值，而不管它们在该迭代时是否从其inNeighbors接收到任何新更改（请参阅apps / LabelPropagation.C）。

这些是用于向聚合值添加值或从聚合值中删除值的函数。总而言之，它只是从传递的聚合值中减去值。请注意，多个线程将在同一聚合值上调用addToAggregationAtomic（）和removeFromAggregationAtomic（）。因此，应使用CAS自动执行更新。

确定源贡献-在此执行仅取决于源值的给定顶点的计算。例如，在PageRank中，顶点u将值PR [u] / out_degree [u]添加到其所有outNeighbors的聚合值中。由于PR [u] / out_degree [u]的这种计算对于处理u的所有outEdges是通用的，因此我们只能计算一次该值（源顶点的贡献），并对所有outEdges执行加法运算。

根据边数据转换贡献-在此步骤中，通过边属性来转换源顶点贡献。例如，在加权页面排名中，贡献将乘以边缘权重。

请注意，这些功能不需要CAS或锁定。对于复杂的聚合，必须定义一个额外的edgeFunctionDelta（）。有关这些功能的更多详细信息，请参考apps / GraphBoltEngine.h，apps / GraphBoltEngine_complex.h。

给定一个聚合值，computeFunction（）计算与该聚合值相对应的顶点值。为了确定收敛条件，使用isChanged（）确定顶点值与先前值相比是否发生了显着变化。函数不需要CAS或锁，因为它们将以顶点并行方式调用。

如果边缘操作的源或目标顶点在第一次迭代中处于活动状态，则应返回true。例如，在PageRank中，如果顶点的out_degree发生变化，则它将在第一次迭代中处于活动状态。

这是应用程序的起点。 GraphBolt引擎在此处使用所需的配置进行初始化并启动。

除了这些功能之外，算法还需要定义一个Info类，其中包含该应用程序所需的所有全局变量/常量。它应该实现以下功能：

与GraphBolt引擎类似，KickStarter引擎还提供了表示算法的功能。

与GraphBolt引擎不同，我们只需要知道在第一次迭代中哪些顶点是活动的。

对于边（u，v），根据u的值计算v的值。如果不应使用来自u的值更新v的值，则返回false。否则返回true。

应该传播的条件，用于确定顶点的单调性是否保持给定的2个值，具体取决于算法。

应用程序的起点。 KickStarter引擎在此处使用所需的配置进行了初始化并启动。

流摄取器FIFO由-streamPath指定。边缘操作可以写入此FIFO。 -nEdges指定可以单批传递给GraphBolt引擎的最大边缘操作数。 GraphBolt引擎将继续从流摄取器接收一批边缘，直到关闭流（当不再有FIFO写入器时）或超过-numberOfBatches为止。如果未打开FIFO的写入端，则GraphBolt引擎（即读取端）将阻塞并等待直到打开。

有一些可选标志可以影响行为并确定传递给命令行参数-streamPath的边缘操作的有效性：

-fixedBatchSize：可选标志，以确保严格遵守批次大小。如果FIFO没有足够的边沿，则摄取器将阻塞，直到接收到-nEdges指定的足够的边沿或流关闭为止。

-enforceEdgeValidity：可选标志，以确保批处理中的所有边缘操作均有效。例如，仅当图形中存在要删除的边时，边删除操作才有效。对于简单图形（如下所述），仅当图形中当前不存在边时，边加法运算才有效。计数批次中的边缘数量时，无效边缘将被丢弃并且不包括在内。

-simple：可选标志，用于确保输入图保持简单图（即，没有重复的边）。检查输入图以删除所有重复的边。批处理中不允许重复的边，并且检查边添加以确保图形中尚不存在要添加的边。

对于加权图，输入图应采用加权邻接图格式。它与邻接图格式相似，但边缘权重紧随边缘。

例如，下面显示了SNAP格式（加权边列表）和加权邻接图格式的样本图。

您可以使用tools / converter / SNAPtoAdjConverter.C将加权边列表转换为加权邻接图格式，如下所示：

$ ./SNAPtoAdjConverter -w inputGraphWeighted.snap inputGraphWeighted.adj $＃对于无向（对称）图，请使用-s标志$ ./SNAPtoAdjConverter -s -w inputGraphWeighted.snap inputGraphWeightedUndirected.adj

流加权输入文件中的每个条目都应采用[d / a]源目的地edge_data的格式，其中d表示删除，a表示添加。

$ make WEIGHTED = 1 SSSP $ ./SSSP -source 0 -numberOfUpdateBatches 1 -nEdges 1000 -streamPath ../inputs/sample_edge_operations.pipe -outputFile / tmp / output / sssp_output ../inputs/sample_graph.adj.weighted

应通过扩展在core / graph / edgeDataType.h下定义的EdgeDataType结构来定义边缘权重数据类型，类似于apps / SSSP_edgeData.h。以下功能确定系统如何转换和使用输入文件中的边缘权重：

createEdgeData（const char * edgeDataString）-根据图形输入或流输入中提供的字符串创建边缘数据。例如，在SSSP中，字符串“ 10”被转换为整数10，并存储为边缘权重。

如果复杂边缘数据表示为没有空格的单个字符串，则也支持具有复杂边缘数据的图。例如，如果每个边都有{edge_id，distance，max_speed}，则可以按加权SNAP格式表示，如下所示：

可以使用tools / converter / SNAPtoAdjConverter.C将具有复杂边缘数据的该图转换为加权邻接图格式，如下所示。

$ ./SNAPtoAdjConverter -w inputGraphWeighted.snap inputGraphWeighted.adj $＃对于无向（对称）图，请使用-s标志$ ./SNAPtoAdjConverter -s -w inputGraphWeighted.snap inputGraphWeightedUndirected.adj

然后可以通过定义相应的EdgeDataType结构，在用户程序中使用加权邻接图，如上所述。在createEdgeData（const char * edgeDataString）函数中，可以将字符串解析为{edge_id，distance，max_speed}的相应数据类型{long，double，double}。

该项目使用了Ligra和基于问题的基准套件的一些实用程序功能。我们感谢他们发布了源代码。

Mugilan Mariappan和Keval Vora。 GraphBolt：流图的依赖关系驱动的同步处理。欧洲计算机系统会议（EuroSys'19）。德国德累斯顿，2019年3月。

Keval Vora，Rajiv Gupta和Guoqing Xu KickStarter：通过修整逼近对流图进行快速准确的计算。编程语言和操作系统的体系结构支持（ASPLOS'17）。中国西安，2017年4月。

@inproceedings {Mariappan：2019：GDS：3302424.3303974，作者= {Mariappan，Mugilan和Vora，Keval}，标题= {GraphBolt：流图的依赖驱动同步处理}，书名= {2019年第十四届EuroSys会议论文集}，系列= {EuroSys '19}，年份= {2019}，isbn = {978-1-4503-6281-8}，位置= {德国德累斯顿}，页= {25：1--25：16}，商品编号= {25}，页数= {16}，URL = {http://doi.acm.org/10.1145/3302424.3303974}，doi = {10.1145 / 3302424.3303974}，acmid = {3303974}，发布商= {ACM}，地址= {{New York，NY，USA}，关键字= {Incremental Processing，Streaming Graphs}，} @inproceedings {Vora：2017：KFA：3037697.3037748，author = {Vora，Keval and Gupta，Rajiv and Xu，Guoqing}，标题= {KickStarter：通过修整近似对流图进行快速而精确的计算}，书名= {第二十二届国际编程语言和操作系统支持大会论文集}，系列= {ASPLOS '17}，年份= {20 17}，isbn = {978-1-4503-4465-4}，位置= {西安，中国}，页= {237--251}，页数= {15}，网址= {http：// doi .acm.org / 10.1145 / 3037697.3037748}，doi = {10.1145 / 3037697.3037748}，acmid = {3037748}，发布商= {ACM}，地址= {New York，NY，USA}，关键字= {图形处理，流图，价值依赖性}，}