# Approaching DRAM performance by using microsecond-latency flash memory for small-sized random read accesses: a new access method and its graph applications TL;DR:通过新的硬件接口和无堆栈协程隐藏延迟来优化针对SSD的小尺寸随机读取，使其接近DRAM的性能

introduction

数据密集型应用，数据大小常常超出DRAM限制，需要放到SSD中。虽然SSD性能比DRAM差很多，但如果是顺序访问SSD，得益于预取和高带宽，其性能接近DRAM.
但是小尺寸的随机访问会严重的影响应用的性能，由于小尺寸的随机访问每次需要发出一个请求来读一小段数据，这个请求本身会带来CPU的开销。由于随机访问，预取也不是很有效。
上下文切换是传统的解决方案，但是操作系统进行上下文切换花费几毫秒

针对高速SSD，CPU处理IO请求是一种开销，为了减少开销

  1. 开发出新的硬件接口来减少CPU读请求发射和完成的开销
  2. 每个核心用数百个上下文来隐藏延迟

BFS-like算法：BFS BC SSSP
在XLFDDs：XL-FLASH™ Demo Drive上实验，使其接近DRAM
将只读数据放到XLFDD上。其性能可以达到DRAM的88%-141%，某些情况下比DRAM更好
此外，用无堆栈的协程隐藏延迟。

BACKGROUND

介绍了load和DMA的区别

  • load同步，DMA异步
  • load的延迟可以被cache、OOO、预取隐藏，但延迟很高的话无法完全隐藏
  • DMA需要发射和完成
  • 对于SCM和低延迟flash，具有深请求队列的 DMA 可以有效覆盖长延迟

介绍了CPU怎么从SSD中通过DMA读数据
image.png
(N1)CPU向提交队列(SQ)中的SSD写入读请求。 (N2) CPU向SSD上的SQ门铃寄存器写入一个值，以通知该请求已添加到SQ。 (N3)SSD读取SQ条目并且(N4)执行请求命令。读取闪存芯片中的指定页，并将读取的数据传输到请求中指定的位置。 (N5)SSD将请求的完成写入完成队列(CQ)。 (N6)CPU通过中断(或轮询CQ)检测到CQ中的条目已被添加，并读取CQ条目以获知哪个请求已完成。请注意，CPU 需要读取 CQ 条目，因为由于 SSD 的内部处理，SQ 和 CQ 中条目的顺序可能不同。 (N7)CPU向CQ门铃寄存器写入一个值，通知SSD该CQ条目已被消耗。 (N8)CPU使用读取的数据。
在此方法中，写入门铃是极大的开销，门铃通过MMIO映射，所以不会过cache。此外还要保证N2晚于N1，这需要插入memory fence

ROPOSED ACCESS METHOD

Lightweight interface

提出了轻量级的方法

  • 移除门铃
  • 提高缓存命中率
    在 SQ 一侧，闪存驱动器轮询 SQ 条目以消除对 N2 中门铃寄存器的写入
    在CQ侧，完全消除了队列结构本身。这不仅减少了门铃写入，而且通过消除对 CQ 条目的访问，有助于提高缓存命中率。通过将其写入每个SQ条目对应的指定位置来通知完成，而不是写入CQ。 CPU可以通过轮询（本文称为CN轮询）每个请求对应的内存位置来检测完成通知。 CPU 可以通过在请求发出后经过足够长的时间后执行 CN 轮询的次数来抑制 CN 轮询的数量。
    修改之后的流程如下
    (L1) CPU 将与从闪存驱动器传输的数据不同的数据写入数据缓冲区。 (L2) CPU向SQ中的驱动器写入请求。请注意，一旦驱动器在我们的评估中检索到 SQ 条目，它就可以重复使用。因此，如果 SQ 的深度大于未完成请求的数量，则新请求将不会覆盖驱动器尚未检索到的请求。 (L3)驱动器轮询SQ条目(SQ轮询)。轮询可能从 L1 之前就已经进行了。 (L4) 驱动器执行请求命令。读取闪存芯片中的指定页，并将读取的数据传输到请求指定的位置。 (L5) CPU 轮询数据缓冲区（CN 轮询）。

Hiding latency using stackless coroutines

因为这里是DMA，异步的，所以上下文切换到不是用来隐藏延迟，而是为了实现高 IOPS 性能，需要发出数千个未完成的请求并并行操作许多 die

数百个上下文并行运行并在一个 CPU 核心上切换，
image.png

过程如图所示，先执行A任务，需要读数据发送请求，上下文切换；到B任务，需要读数据发送请求，上下文切换；到C任务，一样的流程，再上下文切换回A，此时DMA完成，确认完成，继续执行A任务。
对于DRAM来说就是完全同步的过程。
可以想到继续优化的需要减少A2A3A4，A2A4可以通过上面提到的新硬件接口来减少。

减少A3，所谓无堆栈的上下文切换就是用户态的、不涉及操作系统的。或者准确的说是在同一个进程内的上下文切换

程分为栈式协程和栈式协程。在栈式协程中，每个执行上下文都有一个栈，当上下文切换时，CPU中的寄存器值会保存在栈中。另一方面，无堆栈协程并不为每个上下文都有堆栈。因此，用户需要编写程序，在执行暂停时保存稍后需要的数据。如果要保存的数据量较小，则可以进行快速上下文切换。在最好的情况下，只能更改程序计数器。无堆栈协程已在 C++20 中标准化，预计在不久的将来会得到广泛应用
image.png

4 APPLICATION : LARGE-SCALE GRAPH PROCESSING

CSR格式 offset_data 存放点 edge_data存放邻边
原始伪代码，非常简单，遍历点的邻边，执行计算
image.png
来看协程版本
image.png
般来说，每个顶点的大部分边数据都比闪存的页面大小小得多。此外，如上所述，可以将edge_data放置在非连续的物理存储器地址空间中。因此，通过排列每个顶点的边缘数据以便尽可能不跨越多个页面，对每个顶点的边缘数据的大部分访问可以通过从XLFDD读取一页来完成。如果每个顶点的边数据大小超过一页，则需要读取多页。当处理度分布遵循幂律的图时，如图 4 (b) 和 (c) 所示，很少有顶点具有非常大的边数据量。我们在多个协程上下文中处理大量边缘数据。清单 4 显示了代码片段的最终版本，该代码片段替换了清单 3 中的 Y6 到 Y18 部分。
image.png

评估执行时间image.png

CONCLUSION

在本文中，我们展示了微秒级延迟闪存可用​​于在某些读取密集型和小规模随机访问工作负载中实现接近内存的性能。
提出了一种新的轻量级接口来代替现有的 NVMe 接口，以减少 CPU 开销。处理读取请求的 CPU 开销为 6.7 ns。此外，为了隐藏闪存的延迟，我们通过使用无堆栈协程来操作每个 CPU 内核的数百个上下文。无堆栈协程之间的上下文切换成本可以忽略不计。将新接口和协程相结合，可实现每个 CPU 内核 99 MIOPS 的性能