# A Lightweight Infrastructure for Graph Analytics sosp13，比ligra晚一点 20240223 4：50——6：00 20240224 3：33——5：00 TL;DR：高性能轻量级的图计算基础设施 图分析基础设施：像ligra和powergraph都是特定的DSL：vertex program，activity是节点，邻域只能是节点在图上的直接邻居，而galois作为一种基础设施可以实现多种DSL 作为一个图分析基础设施，为了保证在不同DSL下都能实现高性能，采用精心设计的优先级调度和重新实现的内存管理 ![image.png](https://might-image-bed.oss-cn-hangzhou.aliyuncs.com/imgbed/20240226164653.png)

针对图的特定领域语言DSL可以在通用基础设施之上完成，基础设施需要支持

  1. 细粒度的任务
  2. 任务的自主推测执行
  3. 允许应用程序对任务调度策略进行应用程序特定的控制
    该基础设施的优势
  4. 针对以前 DSL 解决的一些图形分析问题实现了更复杂的算法，并表明即使在幂律图上，端到端性能也可以提高几个数量级
  5. 即使一个算法可以用现有的 DSL 来表达，当输入图是道路网络和具有高直径的类似图时，该算法在更通用的系统中的实现速度也可以快几个数量级，这要归功于更多复杂的调度
  6. 几百行代码在公共基础设施之上实现了三个现有图 DSL 的 API，并表明即使对于幂律图，最终实现的性能也常常超过原始 DSL 系统的性能

Introduction

autonomous scheduling：当数据可用时，操作被调度执行
主要改进：

  1. 拓扑感知的工作窃取调度
  2. 优先级调度
  3. 可拓展数据结构

Programming models

amorphous data parallelism (ADP)
image.png
活动节点是图中必须执行计算的节点，活动节点上的计算称为活动，活动读取或者写入的图元素是其邻域，可能横跨多个数据结构也可能重叠，邻域不等于节点的邻居。

operator：算子表达了对邻域元素的一些计算，并且允许通过添加或删除节点和边来改变邻域的图结构，图分析通常需要更简单的算子，即不需要改变图的结构
算子有pull和push两种形式
怎样确定活动顶点：

  • 结构驱动：对于某些算法（Bellman-Ford），需要执行算子的顶点是确定的，可以直接设置为活动顶点进行并行
  • 数据驱动：某些算法活动顶点是动态产生的，根据pull或者push的邻居获得活动顶点。工作只在系统需要的地方执行，但是负载均衡成为问题
    活动什么时候执行？

当活动节点多于线程时，实现必须决定哪些活动节点优先执行，有两种流行的模型，我们称之为自主调度(autonomous scheduling)和协调调度(coordinated scheduling)。

在自主调度中，活动以事务语义执行，因此它们的执行看起来是原子的和隔离的。并行活动是可串行化的.线程从工作列表中获取活动节点并执行相应的活动，只在需要确保事务语义的情况下与其他线程进行同步。这种细粒度的同步可以使用带有逻辑锁的推测执行或图元素上的无锁操作来实现。活动的副作用在活动提交时对外部变得可见。

协同调度将活动调度限制为迭代执行，在BSP中，程序被分为一系列超步，每个超步包括根据前一个超步更新，执行计算，向下一个超步发送信息。多次更新可以不同的方式解决，比如使用规约操作。

数据驱动、自主调度的算法很难高效实现，但是可以收敛的更快
此外，对于道路网络等高直径图，数据驱动的自主调度算法可能能够比其他类别的算法利用更多的并行性，例如，BFS，如果图又长又瘦，则每一级的节点数会非常少，如果使用协调调度，就会限制并行性。

一个例子是增量步进SSSP(delta-stepping SSSP)，SSSP 最常用的并行实现。

自主调度、数据驱动的图形分析算法需要特定于应用程序的优先级和优先级调度来平衡工作效率和并行性。良好 DSL 必须允许应用程序程序员为任务指定此类应用程序和输入特定的优先级，并且运行时系统必须以最小的开销来调度这些细粒度任务并最小化优先级反转

Graph analytics DSLs

graphlab

  • 共享内存编程模型
  • 拓扑或数据驱动
  • 自主或协同调度
  • 顶点编程
    PowerGraph
  • 分布式编程模型
  • 拓扑或数据驱动
  • 自主或协同驱动
  • GAS模型
  • 图按边划分，边的端点可以由多台机器共享
    GraphChi
  • 共享内存，支持核外
  • 对边排序实现高效的IO
  • 只提供协同调度
    Ligra
  • 共享内存
  • 顶点编程
  • 协同调度
  • pull和push自动转换

Applications

Single-source shortest-paths
SSSP 的最佳顺序和并行算法使用优先级调度。Galois SSSP 应用程序使用数据驱动的自主调度增量步进算法 (§2)，通过自动调整来查找给定输入的最佳 Δ 值。
Breadth-first search
两个重要优化

  • 对于小直径：pull和push之间切换可以减少内存访问
  • 对于高直径：使用自主调度
    galois BFS 应用程序融合了协调调度和自主调度。最初，应用程序使用基于推和拉的运算符的协调调度。经过一定轮次的基于推送的遍历后，应用程序切换到优先自主调度。优先级函数有利于执行具有较小 BFS 数量的节点。
    Approximate diameter
    近似直径是指图中所有顶点对之间的最短距离中最大的那个。其计算成本极高但是应用广泛，因此需要近似值。

galois基于在图中查找伪外围节点实现。首先从任意节点开始计算一次广度优先搜索（BFS）。然后，它从第一次BFS发现的距离最远的节点开始计算另一次BFS。如果存在多个节点具有相同的最大距离，算法选择度数最小的节点。它重复这个过程，直到最大距离不再增加。
Betweenness centrality
介数中心性，衡量节点重要性，算法使用前向和后向的BFS
Galois 应用程序基于优先级调度、基于pull的算法来计算介数中心性。优先级函数基于节点的 BFS 编号
ligra 应用程序通过协调执行在基于拉式和推式的运算符之间切换，这在大直径图上可能会产生巨大的开销
Connected components
连通分量
galois使用并行并查集
PowerGraph、GraphChi 和 Ligra 包括基于迭代标签传播的应用程序。图的每个节点最初都被赋予一个唯一的 id。然后，每个节点将其标签更新为其自身及其邻居中的最小值 id。这个过程一直持续到没有节点更新其标签为止；如果图的直径很大，它会慢慢收敛。
PageRank
GraphLab、GraphChi、PowerGraph 和 Ligra 有两个协调的基于推送的应用程序，它们要么是拓扑驱动的，要么是数据驱动的。们在所有情况下都使用拓扑驱动的应用程序。
Galois 提供了基于拉式的 PageRank 应用程序，与基于推式的应用程序相比，它减少了内存开销和同步。

The Galois system

基础：amorphous data-parallelism (ADP)

  • 程序员通过使用无序集合迭代器隐式指定并行
  • 迭代器的主体是操作符的实现，它是一个读写全局数据结构的命令式动作。迭代需要谨慎：迭代必须在写入任何元素之前读取其邻域中的所有元素
  • 应用程序代码中未指定执行迭代的相对顺序；唯一的要求是最终结果应该与按某种顺序顺序执行迭代所获得的结果相同。
  • 系统通过并行执行迭代来利用并行性，程序员必须使用系统定义的内置并发数据结构库，这些库实现轻量级同步来确保迭代的可串行性（其实就是正确性）。
    关于同步，并行执行修改操作需要获得节点和边上的逻辑锁，直观上，迭代的谨慎性将同步问题简化为哲学家就餐问题 [7]，从而消除了对事务内存等更复杂解决方案的需要。
    另一个有用的优化是当操作员仅对机器字执行简单更新或根本不需要事务执行时，使用原子指令代替锁。
    累积集合是支持并发插入新元素但不需要支持并发读取集合的元素集合。协调调度策略可以从多个自主调度循环和累积集合数据结构构建，该数据结构由 Galois 库提供。

    有点像polymer的负载均衡，分区内自主调度，分区间协调调度，但是没有累积集合

Scheduler

Topology-aware bags of tasks

当没有特定于应用程序的优先级时，galois调度程序使用并发包来保存一组挂起的任务（活动节点），）允许并发插入和检索无序任务，并以分布式、机器拓扑感知的方式实现
image.png

  1. 每个核心有一个叫chunk的数据结构，大小8-64（编译时决定），组织为stack形式
  2. 每个package有chunk list，同样组织为stack形式
  3. 当核心的chunk满了，将其移动到package的chunk list中
  4. 当核心的chunk空了，从package的chunk lists中获取chunk，如果package的chunk lists也空了，就去其他package中寻找任务。为了减少包间连接网络上的流量，只有一个饥饿核心代表包中的所有饥饿核心在其他包中寻找工作。

Priority scheduling

操作系统上下文中优先级调度的开销被任务的执行时间所掩盖，而图分析中的情况并非如此，因此这里不能使用操作系统领域的解决方案。

另一种可能性是使用并发优先级队列，但我们无法通过无锁跳表 [29] 和文献中的其他方法获得可接受的性能水平。
我们描述了一种称为 obim 的机器拓扑感知、物理分布式数据结构，它利用了优先级是“软”的事实，因此调度程序不需要完全遵循它们。

obim调度相比前面提到的简单版调度器，使用了sequence of bags，每个bag和一个优先级关联，同一bag中的任务具有相同的优先级，因此可以按任何顺序执行，但是，序列中较早的包中的任务会优先于较晚的包中的任务进行调度。如图四所示，该映射很稀疏，因为它仅包含条目 1、3 和 7 处的包。线程首先处理包 1 中的任务。仅当线程在包 1 中没有找到任务时，它才会在下一个包（包 3）中查找工作。如果线程创建具有某种优先级的任务，并且全局映射中不存在相应的包，则该线程会分配一个新包，更新全局映射，并将任务插入到该包中。
全局映射是所有线程都可以读写的中央数据结构。为了防止它成为瓶颈并减少一致性流量，每个线程都维护一个由软件控制的全局映射延迟缓存，如图 4b 所示。每个本地映射都包含该线程已知的全局映射的某些部分，但线程可以在不通知其他线程的情况下更新全局映射。
obim的主要挑战：如何在分布式，懒缓存的设计下让线程处理早期优先级工作。

Implementation of global/local maps
线程局部映射是通过排序的、动态调整大小的数组来实现的。在线程本地映射中查找优先级是使用二分搜索完成的。线程还维护一个版本号，表示它们同步的全局映射的最后一个版本。
全局映射被表示为基于日志的结构，该结构存储表示逻辑全局映射上的插入操作的包优先级对。每个逻辑插入操作都会更新全局版本号。
Updating the map: 当线程在本地映射中找不到某个优先级的包时，必须和全局映射同步，并可能在那里创建一个新映射。本地线程从自己的最后一个同步版本开始重播全局日志，直到当前全局日志的末尾 。这会将所有新创建的映射插入到线程的本地映射中。如果仍然找不到正确的映射，线程将获取写锁，再次重播日志，并将新映射附加到全局日志及其本地映射。全局日志的实现必须要小心，以确保可以在存在并发读取者的情况下追加日志而不需要锁。
Pushing a task: 推送任务的线程使用本地映射来查找要插入的包，如果失败，就按照上面的流程，更新本地，有可能创建新映射。结束后执行推送操作。
Retrieving a task: 为接近理想的调度，所有的线程都必须处理最早优先级的工作，当执行一项任务时，它可能会创建一个或多个优先级比其自身更早的新任务，因为优先级是任意特定于应用程序的函数。如果是，则线程执行具有最早优先级的任务，并将所有其他任务添加到本地映射中。仅当线程所在的包变空时，线程才会搜索具有不同优先级的任务；然后线程扫描全局地图寻找重要的工作。此过程称为反向扫描
由于扫描整个全局地图的成本可能很高，尤其是在有很多包的情况下（这通常发生在高直径图上），因此使用近似共识启发式来本地估计可用的最早优先级工作并防止冗余反向扫描，这我们称之为反向扫描预防。每个线程通过将其写入共享内存来发布其正在工作的优先级。当线程需要扫描工作时，它会查看共享同一包的所有线程的该值，并使用找到的最早优先级开始扫描工作。为了在包之间传播信息，除了扫描其包中的所有线程之外，每个包的一个领导线程还将扫描其他包领导者。此限制允许大多数线程仅进行少量本地通信。一旦线程有了扫描的起点，它就会尝试从扫描点开始的每个包中弹出工作。

Evaluation of design choices
image.png
不启用反向扫描预防，分布式包在此输入上的效率低于集中式包，这是因为检查（单个）集中式袋子是否为空比检查它是否为空更有效。

Related work
并发优先级队列进行任务调度
最常见的实现：并发跳表，其性能不佳
有界优先级可以提高性能，但是拓展性欠缺
另一种可能性是为每个线程使用并发优先级队列，如果本地优先级队列变空，则从其他优先级队列窃取工作。然而，最终实现的工作效率通常很差，因为一​​个线程生成的早期优先级工作不能足够快地扩散到其他线程。
另一种可能性是为每个线程使用并发优先级队列，并使用逻辑分区图和所有者计算规则 [27] 进行任务分配。该策略非常适合分布式系统，并已用于分布式图遍历算法 [25]，但当工作负载局部化时，其性能会很差

Scalable library and runtime

Memory allocation：现有的内存分配器法扩展到分配非常密集的大规模多线程工作负载，也不能直接解决非均匀内存访问（NUMA）问题。
对于图形分析应用程序，内存分配通常仅限于两种情况：运行时（包括库数据结构）中的分配和活动中用于跟踪活动状态的分配。
对于前者，galois使用slab分配器，分配内存大小固定，对于后者使用bump-pointer region allocator.

bump-pointer region allocator（碰撞指针区域分配器）是一种简单而高效的内存分配算法，维护一个指向当前可用内存位置的指针（称为碰撞指针），并按需分配连续的内存块。当应用程序请求分配内存时，分配器会将碰撞指针向后移动，分配一段连续的内存作为结果，并更新碰撞指针的位置。因此，每次分配都会在前一个分配的内存块之后产生一个新的内存块。
优点：简单高效，连续内存，无碎片
缺点：不支持释放，无法内存回收

slab分配器对于每个块大小有一个单独的分配器和一个中央页池，中央页池包含从操作系统分配的大页。每个线程维护一个空闲块列表。首先从空闲列表中分配块。如果列表为空，则线程从页面池获取页面，并使用碰撞指针分配将页面划分为块

页池是NUMA-aware的，释放的页面重新回到池中原来分配他们的地方
从操作系统分配页面可能是一个重要的可扩展性瓶颈 [9, 34]，因此为了初始化页面池，每个应用程序在并行执行之前预分配一定数量的页面；确切的金额因应用程序而异。

bump-pointer allocator后端是页面池，如果大小超过页大小2MB，分配器回退再malloc。bump-pointer allocator用于分配临时活动状态，其生命周期与活动绑定，因此可以在活动结束后立即回收所有内存。

Topology-aware synchronization：
通信模式是拓扑感知的，因此最常见的同步仅发生在同一package上的核心之间并共享相同的 L3 缓存。这些核心之间的通信成本低廉。例如，运行时不使用标准 Pthread 屏障，而是使用混合屏障，其中跨package构建树拓扑，但​​package中的线程通过共享计数器进行通信。这大约是经典 MCS 树屏障 [20] 速度的两倍。类似的技术，信号树，可以应用于信号线程执行，它用于开始并行执行。
Code size optimizations：
一般来说，由于任务可以创建新任务，因此操作员的支持代码必须检查是否创建了新任务，如果是，则将它们交给调度程序。然而，许多算法的运算符并不创建新任务；而是创建新任务。尽管此检查仅需要大约 4 条指令（其中至少一条是加载指令，其中一条是分支指令），但这几乎相当于平均 SSSP 任务中指令数量的 2%。对于具有细粒度任务的应用程序，通用性会很快影响性能。
为了减少这种开销，Galois 不会为运算符不使用的功能生成代码。它使用一组类型特征来静态地传达。在编译时，会为每个运算符生成专门的实现，仅支持所需的功能。运行时代码的这种简化对性能具有重要的次要影响：紧密循环更有可能适合跟踪缓存或 L1 指令缓存。对于非常短的算子，例如 BFS 或 SSSP 中的算子，这可以带来相当大的性能改进。

Other DSLs in Galois

通过使用上述功能，图形分析 DSL（例如 GraphLab、GraphChi 和 Ligra）可以简单地分层在 Galois 之上