英伟达要“甩开”CPU

作者：智通编选 2022-03-22 09:59:19

BaM：一种能达到细粒度，高吞吐率的GPU编排的内存访问方法

摘要

加速器类似于图像处理单元(GPU)已经越来越多地用在现代的数据中心，因为他们拥有高计算能力和高带宽。传统来说这些加速器依赖于“主应用代码”和运行在CPU上的操作系统来控制他们对存储设备的访问。CPU控制GPU对存储设备的访问在典型的GPU应用上都有比较出色的表现，比如稠密的神经网络训练，其中数据访问的模板预定义的很好，有规律的，而且稠密，独立于数据值，能使CPU把存储数据粗粒化，并且能使存储数据访问和与加速器的数据交互有效协同。不幸的是，这种以CPU为中心的策略导致了CPU-GPU过度的同步，并且IO阻塞恶化，减少了需要细粒度的存储访问模板的新兴中的访存带宽，例如图和数据分析，推荐系统，图神经网络。在我们的工作中，我们提出了一种能达到细粒度，高吞吐率的GPU内存访问方法来访问NVMe固态存储硬盘(SSDs)通过一个新的叫BaM的系统结构。BaM缓和了IO阻塞恶化通过使用GPU线程来读或者写少量的需要计算的数据。

我们展示了(1)运行在GPU上的BaM基础软件可以识别并细粒度，高效率地对底层存储设备进行访问。(2)即使是消费级地SSD，BaM系统和贵很多的只用DRAM地方案相比也可以支持应用性能。(3)减少的IO阻塞可以带来更大的性能收益。这些结果是通过引入高吞吐率的GPU数据结构类似碎裂和软件缓存来实现GPU中大量的进程级并行来解决SSDs访问的长延迟。我们已经简历了一个BaM系统原型并且在一些应用和数据集上面使用不同的SSD类型估算了它的性能。和最先进的解决方案相比，BaM原型提供了平均的0.92x和1.72x端到端加速倍数，载荷为BFS和CC图分析，使用了4个Intel Optane SSD硬盘和高达4.9倍的数据分析负载，使用了一个Optane SSD。

简介

近年来GPU的计算吞吐率快速增长，举个例子，如表1中所示，GPU的计算吞吐量从G80到A100在13年的跨度中增长了452倍。可以看到的是，A100的吞吐量已经比它的暂存CPU高出了1~2个数量级。尽管GPU内存带宽的增长没有如此引人注目，表1中提出的18倍，但A100的内存带宽也比它的暂存CPU高出一个数量级。一个相同趋势也趁现在AMD的各代GPU上。因为拥有这种级别的计算吞吐量和内存带宽，GPU已经变成了流行的高性能计算应用设备，占据了神经网络训练计算设备的主要位置。

表1.从NVIDIA G80到A100的性能进步

新兴的高价值的数据中心负载比如图和数据分析，图神经网络，还有推荐系统，能潜在地受益于GPU的高计算吞吐量和高内存带宽。然而，这些工作负载必须涉及到大量的典型的数十GB到数十TB的数据结构，在预测中，未来将增长迅速。如表1中所示，A1000的内存容量，虽然和G80相比增加了53倍，但是也仅有80GB，和这些工作负载所要求的容量相比相差甚远。

对于存储这些大容量数据结构而GPU内存容量不足的问题，一个可行的解决方案是把多个GPU的内存容量合并来满足存储需求，并使用快速的共享内存互联类似NVLink来连接多个GPU，使得他们能访问每一块的内存。整个数据结构首先会被分片存到GPU的内存中，之后算法会识别并且访问他们实际使用的部分。这个方法有两个缺点。首先，整个数据结构需要从存储空间移动到GPU的内存中，即使仅有一块被访问到，这会显著增加应用的启动延迟。其次，数据大小取决于应用所需求的GPU格式，它会导致需要储备的计算资源严重超出当前的工作负载。

使用主存，目前典型的范围在128GB~2TB大小，来帮助存储分片后的数据结构可以减少所使用的总GPU数。我们把这种使用主存来扩展GPU内存的方式称之为DRAM-only解决方案。因为多个GPU可能倾向于使用相同的CPU和主存在数据中心的服务器中，对于每个GPU的内存容量来说，这些DRAM-only解决方案仅仅增加了主存的几分之一的内存。举个例子，在英伟达DGX A100系统中，每个主存被8个GPU共享，因此，使用主存仅仅把每个GPU的内存扩展了主存大小的1/8。

对于它们最近的在延迟，吞吐率，花费，密度和耐久度上的提升，SSDs有理由成为实现另一种内存层次的候选方案。在这篇文章中，我们提出了使用GPU来使用本地的或者远端的SSD来扩展GPU的内存作为一种更低成本和更加具有可伸缩性的方案。我们将比较该方案和目前最好的解决方案的性能。

方案：我们提出了一种新的系统接口叫做BaM(大型加速器内存)。BaM的目标是来扩展GPU的内存容量，并有效地增加存储器访问带宽，同时提供高层次的GPU进程抽象，使得GPU线程能完成按需的，细粒化的访存请求，来扩展内存层次。在这篇paper中，我们提出并且估计了一些关键点，并且整个BaM的设计提出了三个重要的技术挑战来有效地支持这些加速应用的按需访存请求。

首先，对于按需的访存请求来说，传统的内存映射的文件抽象方式以来虚拟地址转换来计算当前待访存数据的位置。然而，应用稀疏地访问大型数据结构会导致过度地TLB缺失，而且串行化并行访问请求会导致大量的GPU线程。BaM提出了一种高并发，高吞吐量的软件缓存来对它进行替代。这个缓存是高度参数化的，可以让开发者根据他们应用的需求进行设置。有了软件缓存，BaM不依赖于虚拟地址转换，因此就不会被出串行化的事件影响比如TLB缺失。

其次，基于内存映射的文件抽象使用缺页处理进行维护，并且运行在传统的CPU上的文件系统服务有数据搬运的需求。以CPU为中心的模型，这里指通过CPU来处理缺页时的数据搬运，对于OS的缺页处理函数来说受制于底层的CPU进程级并行性是否可行。为了解决这个问题，BaM提供了一个用户级的库用于在GPU内存中实现高并发的NVMe提交/完成队列，这使得按需访问的GPU线程在软件缓存未命中的情况下仍然能高吞吐量地完成访存。这种用户级别的方式使得软件每次访存的开销较小，并且支持高级别的进程级并行。

第三，为了避免虚拟地址转换和缺页处理的高开销，应用程序员采取了对数据进行分块并且根据每种计算方式控制数据搬运的方式。传统文件系统服务中这样的CPU-GPU同步带来的高代价迫使开发者粗粒度地搬运数据。不幸地是，由于对我们目标程序的数据访问倾向于无规律和稀少的。这些粗粒度的数据搬运导致SSD和CPU/GPU的内存中很多有无用的字节，一个现象是I/O扩大。如参考文献中所述的工作，I/O扩大减少了关键资源的有效带宽例如PCIe链路。

表1中，对于A100，访存带宽受限于PCIe Gen4的x16带宽，它是32GB/s，仅仅约为A100内存带宽的2%。更严重的访存由于I/O扩大引起的访存带宽的丢失可以认为是应用性能丢失的一个重要信号。在BaM中SSD使用并行队列和多个SSD，我们实现的系统中GPU可以足够快速地进行细粒度的I/O请求，来完全使用SSD的设备并且明显地减少I/O扩大地级别。

在我们已经拥有的认知中，BaM是第一个加速器中心的模型，GPU可以独立地识别和完成数据访存请求不管它是储存在内存或者存储设备中，不依赖于CPU的控制。当传统的庞大而单调的服务器架构在用户级别对于存储设备队列的实现出现安全问题时，最近数据中心开始转向零新人的安全模型，并且NiC/DPU进行的安全相关性检查也为加速器为中心的访存模型，比如BaM，提供了新的框架。

我们已经通过现成的硬件组件简历了一个BaM原型系统。采用多种不同类型的工作负载，多种数据集对BaM原型系统进行评价，展示了BaM能与最优秀的解决方案达到相同水平，或是略慢一点，甚至是更加出色。

总结一下，我们主要做出了以下这几点贡献:

1.提出了BaM，一个以加速器为中心的架构，GPU线程能细粒度，按需访存，不管它是存储在内存或者其他存储设备中。2.允许按需的，高吞吐量的细粒度访存请求，通过高并行的I/O队列实现3.为程序员提供高吞吐量，低延迟的缓存和软件API，来利用局部性并且控制它们应用中的数据搬运。4.对于成本敏感性的内存容量可变的加速器，提出和评估了一种经过概念验证的设计。

我们计划开源硬件和软件优化的细节，来使任何人都能建立BaM系统。

背景和动机

A.CPU为中心的访存途径中的软件开销

这个部分展示了对于BaM模型背景信息的重要评估数据，来使得读者更好地理解BaM系统中的关键点。

按需的访存请求可以分为两种类型a)隐式和间接的 b)显式和直接的。隐式和间接的访存途径在CPU为中心的模型中可以采用扩展CPU内存映射的文件抽象到GPU线程中的方式实现。NVIDIA Pascal架构中，GPU驱动和编程模型允许GPU线程来隐式地访问大型的虚拟内存对象，这些可能会部分分布于主存中，采用了通用虚拟内存抽象(UVM)。之前的工作展示了UVM驱动可以被扩展成连接文件系统的接口来访问存储，当一个页面是一个内存映射的文件中的一部分，并且它在GPU内存和主存中缺失。

这个方法的主要优点是所有的访存操作都是简单的访存操作，可以在GPU的内存带宽上进行访问只要页和待访问的数据存储在GPU的内存。然而，这个反应的途径在虚拟地址转换和缺页处理时，当待访问的数据不在GPU内存中并且它需要被从外部存储调入GPU内存中时会引起软件开销。因此，我们可以看到对于UVM实现来说最大化的页传输吞吐量会成为基于虚拟地址转换和缺页处理的按需访存请求的上界。

图1.跨不同数据集的 BFS 图遍历应用程序的 UVM 页面错误开销

图1中的每一条都展示了完成的主存到GPU内存的数据传输带宽对于UVM缺页请求在英伟达A100 GPU，PCIe Gen4系统中执行BFS图遍历在5个不同的数据集上(参见表4)，边列表在UVM地址空间中，初始化在主存中，根据图1，UVM缺页机制完成的PCIe带宽约为14.52GBps，它只有测量的PCIe Gen4带宽26.3GBps的55.2%。从资料手机的数据来看，在我们的实验中最大的缺页处理速率达到了约500K IOP。从表3中可以看出，500K IOP只有Samsung 980proSSD的一半完全吞吐量，并且比Intel Optane SSD的完全吞吐量少10%。再则，UVM缺页处理器的IOP由于几种因素被限制，其中包括有限数量的可使用资源来处理TLB确实以及串行驱动器的实现。在我们的实验中，我们发现主CPU上的UVM缺页处理在进行图遍历性能测试的时候100%执行了。

由于存在这些限制，即使我们通过集成系统层到UVM驱动的方式构建了一个假定的系统，并且假设它没有附加的开销，对于当前的UVM实现来在一个相当的高速率来做到对SSD的细粒度的完全使用依旧是不可能的。因此，BaM采用了软件缓存和高吞吐率的用户级别的NVMe队列来避免TLB和缺页处理的性能瓶颈，并且提供显式和直接的存储访问方式。

B.一个具体的I/O扩大的例子

一个以CPU为中心的处理缺页请求的途径要求程序员来对数据进行分块并且编写CPU的代码来根据各个计算的阶段来控制数据搬运。尽管这种以CPU为中心的模型在一些经典的具有很好的预定义，有规律和稠密的访存模板的GPU应用中有较好的工作情况，但当它被应用到我们的目标程序例如数据分析上面时就会出现问题。用于同步的执行时间开销和CPU的控制迫使开发者采用粗粒度的数据传输，它会加剧I/O扩大的恶化。

把在纽约出租车数据集上执行分析问题作为一个例子。假设我们进行提问：问题1：从Williamsburg开始的平均旅行距离是多少?这个问题要求扫描整个数据集中的pickup_gid列来找到符合从Williamsburg出发的条件的项目。然后那些旅程中的trip_dist值需要被加起来来产生问题的答案。然而，由于对trip_dist列的访问和pickup_gid列的访问是独立的，在CPU为中心的模型中，CPU不能决定哪个trip_dist值是被要求的。所以，为了增强存储带宽，目前最优秀的GPU加速数据分析的框架，文献中的RAPIDS，会从GPU的存储中抓取这两列中的所有的行。因为只有901k从Williamburg出发的旅途和因此只有0.05%的第二列数据会被使用。上述问题导致RAPIDS在这个问题上引起了6.34倍的I/O扩大。

如果把问题改成：问题1：从Williamsburg开始的旅行的平均总花费是多少?那么有三列会被访问到：pickup_id,trip_dist和total_amt。为了这个提问，RAPIDS导致了10.36倍的I/O扩大由于它传输了两个完全数据独立的列，trip_dist和total_amt到GPU的内存中。这个提问可以扩展为回答一些更加感兴趣的问题通过增加数据独立的指标，比如附加费(问题3)，打车费(问题4)，通行费(问题5)和税费(问题6)，但是完成这些会导致CPU为中心的模型中的严重的I/O扩大，如图2中所示，在BaM的这些细粒度的，按需的访存能力能缓解这些I/O扩大的问题。

图2.使用最先进的 RAPIDS系统对 GPU 加速的数据分析应用程序中的I/O扩大现象

C.延迟，吞吐率，队列深度和并发性

高吞吐量的访存系统的设计都要基本地遵循Little定律:。T是目标地吞吐量，例如期望的每秒的访存数，L是平均延迟，例如从开始到完成每个访存的秒数，Qd是需要在一段时间内支撑目标吞吐量的最小队列深度。

如果一个系统可以可以产生访存请求在不超过T的平均速率下，那么T会被访存数据中的大部分关键资源瓶颈限制。在我们的BaM原型系统的情况中，我们想完成对关键资源的最大化利用。PCIe x16第四代连接拥有512B和4KB的访存粒度。因此考虑估计的最大的PCIe x16第四代带宽大概是26GBps，对于512B访问中的T值是26GHps/512B=51M/sec，4KB的访问中是26GBps/4KB=6.35M/sec。

L的值依赖于使用的SSD设备和互联的延迟，访问一块Intel Optane SSD通过x4 PCIe第四代互联具有11us的平均延迟，访问Samsung 980pro小飞机SSD通过PCIe x4第四代互联具有324us的平均延迟。根据Little定律，要支持期望的51M的每次512B的访问，对于Optane SSD来说，系统需要容纳一个具有51M/s*11us=561的请求项的队列(对于每次4KB的方式来说是70项)。对于Samsung 980pro SSD，需要的能支持相同目标吞吐量的Qd是51M*324us=16524(对于4KB来说是2057)。

注意上述队列深度可以通过多个队列被传播，只要这些队列被SSD设备积极地使用。因此，在任意时刻，这个系统都必须有至少有561项并行请求存在于提交队列中来支持目标吞吐量T。很明显，它必须有很多倍这个数目的并行可使用请求中来支撑队列深度，从而达到T的一段时间内的吞吐量。

假定对于应用的一个阶段，我们有X个并行的可使用访问请求。假定这些请求可以被入队在吞吐量至少达到T的情况下，我们可以期望为了支撑服务所有请求的投递速率是投递总时间除以投递请求X/(L+X/51M)。当X远大于51M乘以L时，被支撑的投递速率会很接近51M。对于Intel Optane SSD来说，应用需要有约8K的并行可使用的访问在每个执行阶段中，而消费级的Samsung 980pro SSD 约需要256K并行访问来建立可支撑的访问速率在51M，512B的粒度(2K和64K并行访问，4KB的粒度对于Intel Optane和Samsung 980pro SSD来说)。这意思是，拥有足够的并行可使用的访问，消费级的SSD可以达到服务器级的SSD的吞吐量水平。

因此，一个系统需要有至少10个Intel Optane SSD或者多达50个Samsung SSD，所以SSD不是访存的瓶颈。更进一步说，由于所有的SSD在写时候的吞吐量都远远低于读时候的吞吐量，所以一个具有大量写请求的应用更容易会导致SSD引起性能瓶颈。

D.NVMe队列

NVMe协议时工业级最新的定义的标准协议来完成高吞吐量的访存给服务器级和消费级的SSD提供虚拟化支持。NVMe协议最大支持64K的并行提交(SQ)和完成(CQ)队列，每个设备都具有64K的表项。NVMe设备驱动在内存中分配了一个缓存池供SSD设备中的DMA引擎进行使用来完成读和写请求。在传统的CPU为中心的模型中这些队列和缓存存在于系统内存中。

一个应用程序进行访存请求会导致驱动从I/O缓存池中该请求分配一块缓存并且在SQ的尾部一个NVMe I/O命令入队，并给它一个独立的命令标记。

之后该驱动程序写入一个新的尾值到指定的SQ的只写寄存器，在NVMe SSD的BAR空间中，举个例子，它产生了该队列的doorbell。为了提高效率，一个驱动在多次将请求入队SQ时产生一次doorbell。

对于读请求来说，SSD设备控制器通过它的DMA引擎访问它的存储介质并且传输数据到链接好的缓存。对于一个写请求，SSD设备控制器通过DMA把数据从它的缓存中搬到它的存储介质中。一旦一个请求被服务，SSD控制器就会在CQ中插入一个表项。当主控制器检测到CQ中有一个包含命令标记的表项，它会完成这个请求并且释放队列中的空间和请求的缓存。完成表项也会告知驱动SQ中有多少表项被NVMe控制器处理掉了。驱动使用这个信息来释放SQ中的空间。为了和之前的进度通信，驱动之后会产生CQ队列的带有新的CQ头的doorbell，为了效率，一个SSD设备在一次传输中的多个请求中都可以插入CQ表项。

因为SSD设备的延迟已经被减少通过先进的技术例如似乎用Optane或者ZNAND存储媒介，软件开销变成了整个I/O访问延迟的重要部分。事实上，我们的测量数据展示了对于Intel Optane SSD，软件延迟占到36.4%的比重。BaM设计软件缓存和高吞吐量的NVMe队列就是用来减少或者避免这些软件开销。

BaM系统和结构

BaM设计的目标是设法解决GPU的不足的内存容量并且增强有效的访存带宽，同时为加速器提供高层次的抽象，来完成按需的，细粒度的，高吞吐量的存储设备访问。BaM提出了一种以加速器为中心的模型，GPU线程可以在数据存储的位置直接访问数据，在内存或者在外部存储中，不需要CPU来控制数据搬运。为了达到这个目的，BaM在GPU的内存中提供了NVMe的I/O队列和缓存并且映射UVMe的doorbell寄存器到GPU的地址空间。由于这样做会使得GPU线程去访问TB级别的NVMe SSD的数据，BaM必须提出三个关键的挑战来提供一个高效的解决方案。

1)由于NVMe协议和设备会引起重要的要吃，BaM需要增强GPU的并行性来保持多个请求在运行中并且有效地来遏制这些延迟(详见III-C部分)2)因为NVMe设备的带宽非常有限并且GPU的内存容量也优先，BaM必须为应用程序优化这些资源(详见III-D部分)3)因为我们的目标是通过已存在的硬件来评估BaM，BaM硬件和软件必须克服这些现成的组件的挑战(详见III-F部分)

这个部分讨论了BaM怎么设法解决这些挑战。

A.BaM系统概览

图3中展示了BaM系统概览。BaM提供了高层次的编程抽象，例如N维数组和键值对的储存方式，使得程序员能很容易地将BaM集成到它们目前已有地GPU应用中。一个应用程序可以调用BaM API来建立一个从抽象地数据结构到NVMe驱动上的数据块范围的映射。之后程序员可以例化这些抽象通过把映射传递给一个该抽象数据结构的一个构造函数。这个映射的元数据已经足够在SSD中找到需要的数据块。

图3.BaM中GPU线程的生命周期

每一个GPU线程使用这种抽象来计算待访问的数据块的偏移。之后这个线程把这个偏移作为键值在BaM软件缓存(III-D)中进行索引，如图3所示。这个抽象也会有wrap-level 的coalescer来增加访问的效率。如果一个访问请求命中了cache，线程会直接访问GPU内存中的数据，如果Cache未命中，线程会从后端存储中调取数据。BaM软件缓存在设置集中对后端存储的带宽优化采用了两个方式：(1)通过消灭冗余的后端内存的访问请求。(2)通过允许用户来对它们的数据进行细粒度的cache驻留控制。

如果一个NVMe SSD正在备份数据，GPU线程会进入BaM IO栈(详见III-C)来入队一个NVMe请求，并且等待NVMe SSD来提交一个响应完成表项。BaM IO栈的目的是分割和NVMe协议相关的软件开销通过增强GPU的巨大的线程并行性和启动低延迟对多个提交/完成队列的请求表项的批处理来最小化UVMe协议中doorbell寄存器更新的昂贵代价，并减少NVMe协议中的关键区。当接收到一个doorbell更新请求时，NVMe SSD会抓取相关的提交队列表项，处理在SSD和GPU内存中进行数据传输的命令。在传输的最后，NVMe SSD会在完成队列中提交一个完成表项。在完成表项提交以后，这个线程会更新对应键值的cache的状态并在之后访问从GPU内存中调取的数据。

B.和以CPU为中心的设计的比较

当和传统的如图4a中所示的以CPU为中心的模型比较时，BaM有三个主要优势。首先，在以CPU为中心的模型中，由于CPU管理存储数据的传输和GPU计算，它会导致在存储和GPU内存间的数据拷贝并且多次启动计算内核来覆盖一个巨大的数据集。每个核的启动和终结都会引起CPU和GPU间的同步开销。由于BaM允许GPU线程来同时完成计算和从存储中抓取数据如图4b所示，GPU不需要和CPU经常同步，并且更多的工作可以通过单个GPU核完成。更进一步说，一些线程的访存延迟也可以通过计算其他线程而得到同时，因而提高了整体的性能。第二，因为在以CPU为中心的设计中计算负载加在GPU上而数据搬运控制由CPU完成，对于CPU来说，决定哪个部分的数据在什么时候需要十分困难，因此它会导致调取很多不需要的字节。有了BaM，一个GPU线程只在它需要的时候抓取特定的数据，减少了CPU为中心的模型中饱受困扰的I/O扩大开销。第三，在以CPU为中心的模型中，程序员耗费精力去分割应用程序的数据并且重叠计算任务和数据传输来减少访问存储设备的延迟。BaM使得程序员能自然地在大型的数据集上利用GPU的线程并行性来减少访存延迟。

图4.传统的以 CPU 为中心的计算模型与 BaM 计算模型的比较如(a)和(b)所示。BaM 使 GPU 线程能够直接访问存储，从而实现细粒度的计算和 I/O 重叠。BaM 的关键组件的逻辑视图如 (c) 所示。

C.I/O栈

BaM的I/O栈出于两个目的，第一，它使得GPU线程使用NVMe队列和NVMe SSD进行通信。第二，它建立了高吞吐率的队列，利用了GPU强大的并行性来克服NVMe软件栈的挑战。在这里，我们描述一下BaM的I/O栈时如何达到这些目标的。

1)启用直接的从GPU线程访问NVMe的机制

为了启动GPU线程来直接地访问NVMe SSD中的数据，我们需要：1)从CPU内存中移动NVMe队列和I/O缓存到GPU内存中2)在NVMe SSD的BAR空间中启动GPU线程来写队列的doorbell寄存器。为了达到这个目的，我们建立了一个自定义的Linux驱动，它在系统中对于每一块NVMe SSD会创建一个字符设备。使用BaM API的应用程序可以打开这个字符设备来使用他们想使用的SSD。

在自定义的Linux设备驱动中，BaM使用了GPUDirect的RDMA特性来分配和管理GPU内存中的NVMe队列和I/O缓存。BaM使用nvidia_p2p_get_pages 内核API来固定NVMe队列中的页和GPU内存中预分配的I/O缓存，之后映射这些页作为DMA请求来自于另一个PCIe设备，类似NVMe SSD，使用nvidia_p2p_map_pages内核API，它使得SSD能完成对GPU内存的对等数据读写。

我们使用了异步的GPUDirect来映射NVMe SSD的doorbell到CUDA地址空间，所以GPU线程可以按需地产生doorbell。这会要求SSD的BAR空间首先映射到应用的地址空间，之后BAR空间会被映射到CUDA的地址空间使用拥有cudaHostRegisterIoMemory flag的cudaHostRegister API。使用cudaHostGetDevicePointer，应用能获取虚拟地址，GPU线程可以使用它来访问NVMe doorbell寄存器从而产生doorbell。

2)高吞吐量的I/O队列

既然GPU线程可以直接和NVMe设备通信，我们需要优化数千的GPU线程的同步，当它们使用共享队列时。如II-D中描述的，NVMe协议要求驱动来写SSD的BAR空间中的doorbell寄存器值。由于这些doorbell寄存器是只写的，当一个线程产生doorbell，也就是入队一个I/O请求，他必须保证没有其他的线程正在写相同的寄存器并且它在写的值有效的，和之前写的其他值相比，它是一个全新的值。一个不成熟的解决方案可能会是在入队一个命令到提交队列和产生doorbell时上锁，然而，对于GPU中数以千计的并行线程来说，这样的设计方案可能会导致严重的延迟，因为所有的I/O请求都必须串行化。

相反地，BaM使用了细粒度的内存同步来允许多个线程来并行的入队I/O请求并且仅仅进入一个临界区来产生doorbell。为了达到这个目的，我们对于GPU内存中的每一个提交队列维护了下面的队列：1)队列头的本地拷贝，2)队列尾的本地拷贝，3)原子标签计数器，4)turn_counter数组，一个和队列由相同长度的整形数组，5)一个mark位向量，总位数和队列长度相同。当一个线程需要一个入队请求时，它首先原子地增加标签计数器，返回的标签值除以队列的大小的商来关联一个队列中的entry，而余数turn代表它的位置。线程使用它的entry来在turn_counter数组中进行索引，并且在这个位置中进行计数直到它的计数值和线程的turn值相同。当它的计数值达到线程的turn值时，线程可以复制它的NVMe命令到它关联的队列中的位置。在复制以后，这个线程会设置这个位置的mark标记位，这个线程之后会快速地复位这个位作为比特向量中当前的尾部。如果它是成功的，它会进入临界区来移除尾部并且它会重复地去顺序地复位比特向量中的比特，直到它命中一个未设置的比特或者队列已满。在这个时候，线程知道了新的尾值并且可以用它来进行doorbell。这个线程之后会更新GPU 内存中的尾部的备份，之后离开临界区。

如果线程没法进入临界区，它会不断尝试知道它在mark比特向量中的位被复位。这个方法的主要优点是多个线程可以找到它们在队列中的位置，并且把它们的命令写到相关的队列中而不去请求任意的锁，事实上，大部分要入队一个命令到提交队列的线程都不曾进入临界区，因为一个要进入临界区的单进程可以尽可能地移除尾部。

在一个线程的命令提交以后，这个线程可以对完成队列进行无锁轮询，来找到对于已提交请求的完成项。这个方法的主要优点是很多线程都能在队列中找到它们的位置并且在不获取任何锁的情况下把他们的命令写到他们相关的队列表项中。当它找到这个完成表项，它必须标记这个完成表项已经被NVMe控制器之前的通信过程所消费。移除完成队列的头并且使用新的头部产生doorbell请求也可以通过和线程移除提交队列的头相同的方式完成。线程竞相地去复位当前头的标记并且进入临界区的线程重复地复位标记知道它不能做为止。

然而，在线程能离开完成队列地临界区之前，它必须也更新提交队列的头部来释放空间确保下一轮命令能入队。每个完成队列的表项都有一个字段，他使得NVMe控制器和驱动通信告知它这个位置可以移除提交队列的头部。线程从它可以重置标记的最后一个完成队列表项中读取此字段。然后它从当前提交队列头开始迭代，直到完成条目中指定的头值，将每个位置的 turn_counter 值加一。线程之后通过更新在GPU内存中的本地完成队列头的备份来更新提交队列头并且离开临界区。如果一个线程注意到提交队列头已经移除过它的表项，它不会再进入临界区。

D.BaM软件缓存

BaM 软件缓存旨在允许优化使用有限的GPU内存和GPU外带宽。传统的内核模式的内存管理(分配和翻译)的必须支持多种多样的，已停产的应用/硬件的需求。这样会导致他们包含了大量的临界区，限制了多线程实现的效率。BaM采用在每个应用启动时预分配所有的软件需要的虚拟和物理内存的方法来设法解决这个瓶颈。这个方法允许BaM软件缓存管理来减少临界区，尽在插入或者收回一个缓存行的过程中去请求锁。继而，BaM缓存支持更多的并行访问，特别是数据在GPU内存中的时候。

当一个线程通过一个偏移量来询问缓存的时候，它会直接地检查相关缓存行地原子状态。如果它是有效的，线程会增加该缓存行的引用技术。如果被访问的缓存行不在缓存种，线程会锁住缓存行，并且找到一个非法的行腾出来，然后从后端内存中调取缓存行。当请求完成以后，发起请求的线程会通过把它的状态置为合法和增加它的引用计数的方法来解锁缓存行。这样上锁的方式防止了对同一高速缓存行的后端内存的多个请求，利用数据中的空间局部性并最大限度地减少对后端内存的请求数量。当一个线程结束使用某一个缓存行时，它的引用计数会被减少。

BaM缓存使用了一个时钟替换算法。这个缓存有一个全局计数器，当一个线程需要找到一个缓存槽时它会增加。这个计数器的返回值告诉线程哪一个缓存槽是尝试要使用的。如果被选中的缓存槽目前已经被映射到一个由非0引用值的缓存行，线程会继续并且再次增加全局计数器来尝试替换下一个缓存槽。当线程发现一个指向一个缓存行的缓存槽拥有非0的引用计数值，线程会尝试通过将缓存行的状态设置为临时状态来回收它。如果成功了，线程会标记这个缓存行无效并且改变缓存槽到线程想要带入的缓存行的映射。否则，它会再次增加计数器并且尝试使用下一个缓存槽。

Warp 合并：虽然BaM的软件缓存最小化了到后端内存的请求数量，但它增加了每次访问缓存行时的管理开销。同一个warp中的线程经常相互竞争，尤其是当连续线程尝试访问内存中的连续字节时。为了克服这个，BaM的缓存使用wrap级的原语在软件层面实现了wrap合并。当线程去访问cache时，__match_any_sync wrap原语被用来来同步其他在wrap中的线程，并且一个淹没被计算出来使得每个线程都知道其它某个wrap中的线程在访问相同的偏移量。在该组中，线程决定一个领导者，并且只有领导者可以操纵被请求的缓存行的状态。这组中的线程使用__shfl_sync原语进行同步，并且领导者将GPU内存中被请求的偏移量的地址广播给这个组。当数据已经在GPU内存中时，这个合并对于减少访问开销极其有效，因为那是每次访问增加的开销最明显的时候。

E.BaM抽象和软件API

列表1.具有 BamArray 抽象的 GPU 内核示例

BaM软件栈给程序员提供了一个基于数组的高层次API(BamArray)，由使用新的编程语言定义的接口组成(比如C++，Python或者Rush)。因为GPU内核操作类似的数组，BaM 的抽象简化了程序员调整内核以便对整个数据集进行操作的工作，如列表1所示。

相比之下，以 CPU 为中心的模型需要将完整的、重要的应用程序重写，以优化地将计算和数据传输分块来适应GPU 有限的内存。

BamArray 的重载下标运算符对程序员隐藏了BaM的所有复杂性。运算符通过选择一个查询 BaM 缓存并在未命中时发出 I/O 请求的领导线程，使访问线程能够合并它们的访问。当请求完成，领导线程会和其他在同个wrap中的线程分享缓存行的引用。每个线程使用这个引用来返回合适的类型为T元素到调用函数。

Bam的初始化啊需要分配一些内部的数据结构，他们会在应用程序的生命周期中重复使用。如果没有自定义，初始化会隐式地在一个库的构造函数中发生。否则，应用程序需要通过BaM初始化调用中的模板参数来专业化内存，一个C++中的标准例子。我们也提供了BaMArray的四种内存实现方式(1)SSD和BaM缓存(缺省值)(2)固定的CPU内存和BaM缓存(3)固定的CPU(4)GPU内存。然而，在大部分情况中，专业化和微调不是严格必须的，就像我们之后再IV部分中介绍的仅有BaM的缺省参数使用的情况。

F.BaM原型系统的设计

使用数据中心级 4U 服务器中可用的 PCIe 插槽的 BaM 设计面临几个挑战。这些机器中可以使用的PCIe槽是悠闲地。举个例子，例如，Supermicro AS-4124 系统每个socket有五个 PCIe Gen4 ×16 插槽，如果一个GPU占据了一个插槽，它啊在不适用socket间的互联组件的情况下只能访问4x16的PCIe设备。进一步说，由于现在的多核CPU的chiplet设计，即使每个socket中的5个PCIe可以互相访问，他们也必须穿过CPU内部的互联组件。

穿过这些不同的互联组件进行访问会导致严重的性能损失因为每个互联中都存在包的转换，增加了延迟并限制了吞吐量。然而，如我们再II-C中讨论的，BaM 硬件应支持扩展到大量 NVMe 设备，以提供使 ×16 PCIe Gen4 GPU 带宽饱和所需的吞吐量，而无需太多开销。

表2.BaM原型系统的规格

为了解决这个问题，我们为BaM架构构建了一台自定义的BaM原型机器，使用了如图5中所示的大量已有的组件。表2中展示了使用在原型系统中主要组件的规格。BaM 原型使用具有定制PCIe拓扑的PCIe扩展机箱来扩展SSD的数量。PCI交换机支持低延迟和高吞吐量的PCIe设备之间的对等访问。扩展机箱有两个相同的抽屉，目前都独立连接到主机。每个抽屉支持8个x16 PCI而插槽(如图5a中所示)，我们在每个抽屉中为一个NVIDIA A100 GPU使用一个x16插槽，并且其余插槽装有不同类型的SSD。目前，每个抽屉只能支持 7 个U.2(Optane或Z-NAND)SSD，因为U.2外形占用了大量空间。由于PCIe交换机支持PCIe分叉，一个PCIe多SSD转接卡支持每个抽屉超过16个M.2 NAND闪存SSD。

图5.使用现成组件实现的BaM原型

表3.不同类型 SSD 与 DRAM DIMM 的比较

SSD 技术的折中：表III列出了对三种类型的现成 SSD的BaM系统的设计、成本和效率有显着影响的指标。RD IOPS (512B, 4KB) 和 WR IOPS (512B, 4KB) 列分别显示了在512B 和4K粒度下测量的每种SSD的随机读写吞吐量。$/GB 列显示了每种 SSD 类型的每 GB 成本，基于为构建系统的每个设备、扩展机箱和转接卡当前的当前报价。Latency 列显示测量的平均设备延迟(以 µs 为单位)。对 SSD 类型的这些指标进行比较表明，消费级 NAND 闪存 SSD 价格便宜，具有更具挑战性的特性，而低延迟驱动器(如 Intel Optane SSD 和 Samsung Z- NAND更昂贵，具有更理想的特性。例如，对于使用 BaM 的写入密集型应用程序，Intel Optane驱动器提供最佳的写入 IOP 和耐久性。

不考虑底层 SSD 技术，如表 III 所示，BaM和DRAM-only解决方案先比在每GB成本方面有4.4-21.8倍的优势，即使在使用扩展机箱和转接板的情况下。此外，这一优势随着每台设备增加的额外容量而增长，这使得 BaM 在SSD容量和应用程序数据大小的增加的情况下具有高度可扩展性。

评估

这个部分进行了对BaM原型软硬件系统的评估并且展示了：

BaM 可以生成足够的 I/O 请求以使底层存储系统饱和(详见IV-A)。

即使仅有一个SSD，BaM的性能也可以达到活超越最优秀的解决方案(详见IV-B和IV-C)。

BaM 设计与所使用的 SSD 存储介质无关，可实现特定于应用的经济高效的解决方案。

BaM 显着降低了数据分析工作负载的I/O扩大和CPU控制开销(详见IV-C)。

BaM 性能随着 SSD 的添加而扩展。

综上，我们展示了和最优秀的解决方案相比，带有4个Optane SSD的BaM在BFS和CC图分析数据负载上达到了平均0.92倍和1.72倍的加速性能，并且单个Optane SSD在数据分析负载上达到了4.9倍的加速性能。在不同的存储媒介上观察到了和SSD类似的性能。

A.使用微基准测量的BaM的原始吞吐量

设置：我们首先评估了BaM在使用Intel Optane SSD的合成随机访问微基准上可实现的原始吞吐量。我们把整个SSD的容量映射到III中描述的GPU的地址空间。我们分配所有的可用的SSD的SQ/CQ队列对到GPU的内存中，队列深度为1024。我们之后启动一个CUDA内核，它的每个线程都从SSD中请求一个独立的512字节的块。每个线程提交一个NVMe请求到一个指定的队列中。队列以循环方式供给GPU线程使用。然后，我们改变映射到单个 NVIDIA A100 GPU 的线程和 SSD 的数量。对于多个 SSD，请求以循环方式进一步分布在 SSD 之间。我们将每秒 I/O 操作 (IOP) 衡量为一个指标，该指标定义为GPU提交的请求和内核执行时间。

图6.在 Intel Optane P5800X SSD 上使用 BaM 进行 512B 随机读写基准扩展。BaM 的 I/O 堆栈可以达到每个 SSD 的峰值 IOP，并针对随机读取和写入访问进行线性扩展

结果：图 6 显示了 512B 随机读写访问基准的测量 IOP，BaM的每个SSD可以达到IOPs的峰值并且可以根据附加的SSD线性增加，对于读和写都适用。使用单个Optane SSD，BaM仅仅需要大约16K-64K的GPU线程来达到接近峰值的IOP。使用7个Optane SSD，BaM能达到35M随机的读IOP和7.4M的随机写IOP，是Intel Optane SSD的512B访问粒度可达到的最大峰值。扩容实验中SSD的最大数量目前受限于扩展机箱的抽屉容量。一旦我们完成抽屉级联的开发，可以进行额外的扩容。相似的性能和扩展性可以在Samsung SSD中看到，并且也可以使用4KB的访问大小，但是限于篇幅并没有在此处列出。这些结果验证了 BaM 的基础架构软件可以匹配底层存储系统的峰值性能。我们下一步会使用应用程序基准来对BaM进行评估。

B.图分析中的性能收益

表4.图分析数据集

设置：首先，我们评估BaM在图分析应用中的性能收益。我们使用表4列出的图来进行评估。K，U，F，M是SuiteSparse 矩阵集合中四个最大的图，而 UK 和 Sk 取自 LAW。这些图数据集涵盖了不同的领域，包括社交网络、网络爬虫、生物医学，甚至合成图。

BaM的一个目标就是提供比DRAM-only图分析解决方案更有竞争力的性能。为此，目标基线系统 T 允许 GPU 线程在图形分析执行期间直接对存储在主机内存中的数据执行合并细粒度访问。由于输入图都可以放入主机内存中，因此我们可以直接比较 BaM 和 T 之间的性能。

我们在目标系统和构建于表3中列出的不同SSD上的BaM分别运行两种图分析算法，广度优先搜索 (BFS) 和连接组件 (CC)。在 BFS 中，每个 GPU warp 被分配给当前迭代中正在访问的节点，其中 warp 中的所有线程协作遍历节点的邻居列表。CC 实现遵循与 BFS 类似的分配，只是应用程序首先检查图中的所有节点，因此呈现出比 BFS 更突发的访问模式。对于 BFS，我们统计了运行至少 32 个具有两个以上邻居的源节点后的平均运行时间。

我们不对 UK 和 Sk 数据集执行 CC，因为 CC 仅在无向图上运行。最后，我们将 BaM 软件缓存大小固定为 8GB，缓存行大小为 4KB。

图7.使用单个Intel Optane SSD 的 BaM 和目标系统(T)的图形分析性能。平均而言，BaM 的端到端时间比目标快 1.1 倍(BFS)和 1.29 倍(CC)。

一个SSD的整体性能：图7个展示了目标系统(T)和使用单个Intel Optane SSD的BaM(B_I)，Samsaung DC 1735(B_S)和消费级的Samsung grade 980 Pro SSD(B_SC)。回想一下，目标系统 T 受益于主机和 GPU 之间的完整 ×16 Gen4 PCIe 带宽，而 BaM 仅限于单个 SSD 的 ×4 Gen4 PCIe 接口。

然而，在所有图和算法中，在不考虑 T 系统的初始文件加载时间的情况下，采用英特尔傲腾 SSD (B_I) 的 BaM 的性能从略快到比目标 T 系统慢 4.4 倍的现象都存在。这是因为由于只有一个SSD，BaM的性能被SSD的x4 Gen4 PCIe接口的吞吐量限制。如果我们考虑T系统的初始文件加载时间，BaM平均比T系统在BFS和CC这两个算法上分别要快1.1和1.29倍。在这两种情况下，GPU 计算内核通过 BaM 1D 数组抽象执行按需图的边数据访问。这允许 BaM 将来自 SSD 的某些线程的数据传输与其他线程的计算重叠。相反，目标系统 T 需要等到文件加载到内存中才能将计算任务卸载到 GPU。T系统的监管者的主存带宽不能克服加载初始文件的延迟。这会导致BaM获得了更高的端对端延迟。

Samsung DC 1735和Intel Optane SSD对于所有的负载几乎有着相同的新能。因为这两个驱动器的4KB随机读IOP峰值都被PCIe x4 接口限制了。然而对于CC工作负载中的两个数据集(U和M)，Sansung DC 1735的性能比较差，并且我们初始的分析指出了这是因为SSD控制器在处理CC使用突发随机访问模板访问这两个图时的长尾部延迟。将重点转移到成本效益上，BaM 原型使用一个三星 980 Pro SSD，与目标系统(包括文件加载时间)相比，BFS和CC工作负载平均慢1.97倍和1.85倍。这些对于消费级 SSD 来说是非常令人鼓舞的结果，因为它们提供了迄今为止所有 SSD 技术中的最佳价值。

图8.缓存行大小对使用一块Intel Optane SSD 进行图形分析的 BaM 性能的影响

缓存行大小的重要性：我们尝试调整 BaM 软件缓存的缓存行大小从 512B 到 8KB，以了解访问粒度对图形分析工作负载的影响。回想一下，BaM 缓存行大小决定了对存储的访问粒度。由于其高IOP率因此使用单个 Intel Optane SSD 完成了评估(详见表 III)。从图8中可以看到，由于我们把缓存行大小从4KB减少到512B，BFS和CC工作负载分别慢了1.41倍和2.31倍。这是因为图工作负载在其邻接列表中表现出空间局部性，并且可以从更大的访问中受益。此外，我们的分析数据显示，对于512B访问粒度，BFS 和 CC 应用程序可以达到 4.76M IOPs 和 4.97M IOPs。对于4KB访问粒度，分别可以达到 1.37M IOPs 和 1.52M IOPs。这意味着 512B 和 4KB 存储访问的带宽约为 2.5GBps 和 6GBps，接近一个 Optane SSD 的峰值可实现带宽。

出现了三个主要发现：

在 BaM 中运行的工作负载可以生成足够的 I/O 请求以使驱动器的吞吐量饱和.

4K 的粒度在某些图中利用了大型邻接列表的空间局部性，并且为较小的邻接列表传输的额外字节不会降低性能，因为 PCIe 带宽没有过饱和。

BaM 的细粒度访问减少了 I/O 放大，从而提高了有效带宽。

否则，在将缓存行大小从 4KB 减少到 512B 时，应用程序的速度会降低 8 倍。将缓存行大小从 4KB 增加到 8KB 几乎不会影响整体性能。这是因为在 4KB 时，应用程序接近 SSD PCIe 带宽限制，并且进一步增加缓存行大小不会提高带宽。在Samsung设备中观察到类似的性能变化和趋势，限于篇幅不讨论。

图9.扩展Optane SSD的数量

扩展到多个SSD：我们扩展 SSD 的数量并跨 SSD 复制数据以增加 BaM 的聚合带宽。图9展示了具有4KB缓存行的Optane SSD的扩展结果。使用 BaM 原型的图形分析工作负载可以很好地扩展到两个 Optane SSD，但若数量超过两个，收益开始递减。如果使用超过两个SSD，使用BaM原型的图分析应用就不能以足够的速度产生I/O请求来有效地满足附加设备。即使应用程序具有足够的 I/O 并行度，当前的 GPU 内核实现和数据布局都针对利用局部性和减少 I/O 请求的数量进行了优化，而不是最大化生成 I/O 请求的速率以隐藏长延迟。这些相互冲突的目标需要通过扫描每个线程的工作分配或增加每个线程的工作量来探索设计空间，以便 GPU 线程可以以更高的速率生成 I/O 请求以充分利用超过 2 个 Optane SSD。此外，BaM 软件栈中的一些优化，例如自动改变 I/O 请求的大小和预取，尚未实现。我们将在未来解决这些问题。目前，使用四个Intel Optane SSD的系统和考虑文件加载时间的目标系统T相比已经可以在BFS和CC应用上提供平均0.92和1.72倍的加速比。BaM在所有数据集上对于BFS和CC负载达到了平均0.72 和1.51倍的加速比。三星 SSD 也出现了类似的趋势，但三星 980 Pro SSD 可以很好地扩展到 4-10 个 SSD，然后再扩展SSD才会在图形工作负载上出现收益递减。

C.数据分析中的I/O扩大收益

除了图形分析之外，我们还评估了 BaM 原型对企业数据分析工作负载的性能优势。这些新兴的数据分析被广泛用于解释、发现或推荐随时间推移或从非结构化数据湖收集的数据中的有意义的模式。数据分析实验旨在说明 BaM 设计在处理大型结构化数据集时减少 I/O 扩大和软件开销的好处。

设置：II-B中讨论了在NYC出租车数据集上的I/O扩大问题。该数据集由 200GB 编码数据组成，以优化行列 (ORC) 格式组织为 1.7B 行和 49 列。我们使用了II-B部分中描述的6个数据相关的提问来和最优秀的GPU加速数据分析框架RAPIDS进行比较。基线和BaM都使用一块Intel Optane P5800X SSD。我们使用两种配置来评估基线：a)SSD 中所有数据的冷情况和 b)数据已被提取到 Linux CPU 页面缓存的暖情况。

图10.使用一个 Optane SSD的前提下，在NYC出租车数据集的数据分析查询中BaM 和 RAPIDS 的性能。BaM 比以 CPU 为中心的 RAPIDS 框架快 4.9 倍。

结果：在大多数情况下，采用单个英特尔傲腾 SSD 的 BaM 在冷配置和暖配置中均优于 RAPIDS 性能，如图 10 所示。对于 Q1，暖配置的基线比 BaM 略有优势，因为它可以利用整个 CPU DRAM 带宽和 PCIe ×16 Gen4 带宽在主机和 GPU 之间传输数据，而 BaM 则受到 SSD 带宽的限制。随着数据相关指标的添加，BaM 性能提高，如图 10 所示。性能提高的原因是 BaM 由于按需数据提取而减少了 I/O 放大，但基线必须将整个列传输到 GPU 内存。如图 2 所示，通过额外的数据相关指标，基线(包括暖和冷)会引起更多的I/O扩大和CPU上用于查找和移动数据以及管理GPU内存的软件开销。但是，BaM 能够按需访问数据以及重叠计算、缓存管理和许多 I/O 请求，这使得它处理多个数据相关列的效率几乎与处理单个数据相关列一样高。