# Ligra：A Lightweight Graph Processing Framework for Shared Memory 阅读时长：20240223 2：00——4：26 ppopp13 TL;DR：适用于遍历应用的轻量级单机图处理 ## introduction Ligra支持两种数据类型，一种表示具有顶点V和边E的图G=(V, E)，另一种表示顶点 V 的子集，我们将其称为 vertexSubsets。除了构造函数和大小查询之外，该接口仅提供两个函数，一个用于顶点映射 (VERTEXMAP)，另一个用于边映射 (EDGEMAP)。

由于 vertexSubset 是 V 的子集，因此 VERTEXMAP 可用于映射原始顶点的任何子集，因此它在遍历算法中很有用，或者在其他每一轮只处理部分顶点子集的算法中有用。EDGEMAP 还处理边的子集，该子集使用 vertexSubset 来指定以指示有效源，并使用布尔函数来指示每个边的有效目标。
抽象的说，vertexSubset 只是包含顶点的一组整数标签，而 VERTEXMAP 只是将用户提供的函数应用于每个整数由。用户来维护任何基于顶点的数据。该实现根据 vertexSubset 的大小在整数的稀疏表示和稠密表示之间切换。在我们的接口中，可以维护多个vertexSubset，此外，一个vertexSubset可以用于具有不同边集的多个图，只要图中的顶点数量相同。

以BFS为例
image.png

  1. 使用parents数组记录BFS树中的父节点
  2. frontier是一系列当前正在探索的节点，在每次迭代算法都会拓展frotier来包含尚未访问的当前前沿节点的邻居。
  3. UPDATE 函数: 此函数检查节点是否已访问过。它使用比较和交换 (CAS) 操作来确保原子访问并避免竞争条件。
  4. 终止: 当前沿变为空时，算法终止，这意味着没有更多未访问的节点

ligra支持以多种顺序处理边：

  1. 在活动源顶点的稀疏表示中循环遍历每个顶点，将函数应用于每个出边
  2. 也可以使用源顶点集的密集表示，顺序或并行循环所有目标顶点，并且对于每个边内检查源是否在源顶点集中，如果是，则应用边函数

    关于稀疏表示和稠密表示

ligra处理的图应用（BFS,BC,GC,PR,BF）都有相同的特质：都是以迭代形式工作，每轮迭代处理点的子集

预备知识

通用的不说了
N +(v)：点v的出向邻居
N -(v)：点v的入向邻居
deg+(v)：点v的出度
deg-(v)：点v的入度
CAS：三个参数，内存位置，旧值，新值，如果内存位置的值等于旧值，将其赋予新值并返回true，反之不改变值并返回false

Framework

Interface

image.png
image.png
对于未加权图 G = (V, E) EDGEMAP 将函数 F 应用于源顶点位于 U 且目标顶点满足 C 的所有边，返回的vertexSubset是应用了F的边中F为true的边的目的顶点。
image.png
对所有属于U的顶点应用F，返回F为true的顶点

vertexSubset的表示方式：

  • 对于U含于V，稀疏表示，通过长度为U的整数来表示
  • 稠密表示，长度为V的boolean数组，如果i属于U，则为true

Implementation

根据U和U的出边数量，来决定调用EDGEMAPSPARSE还是EDGEMAPDENSE
EDGEMAPSPARSE算法并行地遍历顶点集合U中的所有顶点，并对每个顶点u ∈ U并行地应用函数F(u, ngh)到u的所有邻居ngh。它返回一个稀疏表示形式的顶点子集。EDGEMAPSPARSE算法的工作量与|U|以及U中顶点的出度之和成正比。在输出的顶点子集中，需要删除重复的顶点ID。

EDGEMAPDENSE算法并行地遍历图中的所有顶点V，并对每个顶点v ∈ V顺序地应用函数F(ngh, v)到v的属于U的每个邻居ngh，直到C(u)返回false。它返回一个稠密表示形式的顶点子集。

当顶点子集较小的时候，EDGEMAPSPARSE算法应该更高效，而对于较大的顶点子集，EDGEMAPDENSE算法应该更快。根据经验，我们将使用EDGEMAPSPARSE和EDGEMAPDENSE的阈值设置为|E|/20，在我们的所有应用中表现良好。

其实就是push和pull
image.png

Graph Representation

入边和出边用数组存储，按照目的顶点进行分区
每个顶点保存其入度和出度，指向其入边和出边分区的起点
权重保存在边数组中，为了缓存一致性

Optimizations

pull是并行的，ligra的push是串行的，没有使用原子操作，文中指出如果F能够保证不涉及竞争，可以并行会提高性能
提供了写版本的EDGEMAPDENSE ：EDGEMAPDENSEWRITE（更像现在通用的push）
image.png
我们发现，仅对于我们的两个应用程序 PageRank 和 Bellman-Ford 最短路径，EDGEMAPDENSE-WRITE 比 EDGEMAPDENSE 更有效。
其他的感觉是比较简单的优化，都是避免不必要的计算一类的

Applications

有空再看吧

Experiments

性能好