OSDI 2022 论文评述-0xB：Recommenders and Pattern Mining

Ekko: A Large-Scale Deep Learning Recommender System with Low-Latency Model Update

Chijun Sima,Tencent;Yao Fu and Man-Kit Sit,The University of Edinburgh;Liyi Guo, Xuri Gong, Feng Lin, Junyu Wu, Yongsheng Li, and Haidong Rong,Tencent;Pierre-Louis Aublin,IIJ research laboratory;Luo Mai,The University of Edinburgh

深度学习在推荐系统中应用广泛。本文指出基于深度学习的推荐系统需要支持低延迟地更新模型从而达到服务新用户的需求，然而在此之前的推荐系统都不符合低时延的要求。来自腾讯、爱丁堡大学等等机构的研究人员提出了一套系统Ekko，用于支持低时延的模型更新。整个系统设计的出发点是允许模型更新操作立即传播到集群内的所有机器，避免时延较长的模型检查点拖慢整体的运行时间。

传统的一个深度学习推荐系统DLRS常常会服务于全球各个终端，因此为了最小化服务的延迟，DLRS常常会在处于多个地方的集群上保存若干份复制。在用户请求到达的时候，推理服务器会从本地获取参数并且回答请求。假设集群之间的网络带宽很大并且时延较低。DLRS整体有不少的服务目标，例如短视频的推荐中DLRS的模型准确性决定了服务质量这个目标。在现实世界中，这些目标经常取决于模型的更新延迟，尤其是在面对现实世界中短时间内创建的大量数据时，模型是否能及时更新适配这些数据成为了关注焦点。目前的挑战主要有几个方面，一是缺乏传播大模型更新的有效算法，二是缺少对服务目标的保护。第二点的例子是各个目标有相对的重要性排序，在发生更新的时候应该优先保证高优先级的目标先完成。

Ekko是一个分布式的DLRS，允许其中的服务器出现在地理上的多个位置。Ekko表述模型的方法是通过Key-Value对的方法进行表达。Ekko在设计上使得参数服务器之间支持点对点的模型更新，从而避免中心化的广播以达到减少时间开销的目的。由于没有中心节点，因此每个数据中心可以独立地选择自己的时间间隔进行模型更新。而在解决服务级别目标方面，Ekko依靠一个目标感知的模型更新器感知各个更新的优先级别之后进行更新。此外，Ekko可以保护用于推理的服务器不受detrimental模型更新的影响。P2P更新的细节在论文中有更加完整的介绍。

测试方面，作者将该方法同Adam进行对比，采用了一个有30个服务器的集群，每个服务器拥有一个24核的CPU、64GB内存和5Gbps的网络连接来模拟现实的情况。结果显示相比于传统的Adam方法在随着数据中心数量上升的情况下，本方法的时间延迟很低，并且具有较好的可扩展性。

FAERY: An FPGA-accelerated Embedding-based Retrieval System

Chaoliang Zeng (Hong Kong University of Science and Technology), Layong Luo (ByteDance), Qingsong Ning (ByteDance), Yaodong Han (ByteDance), Yuhang Jiang (ByteDance), Ding Tang (Hong Kong University of Science and Technology), Zilong Wang (Hong Kong University of Science and Technology), Kai Chen (Hong Kong University of Science and Technology), Chuanxiong Guo (ByteDance)

基于嵌入的检索（Embedding-based retrieval, EBR）被广泛应用于推荐系统中，用于从一个包含数百万或更多条目的大型语料库中检索候选条目。本文设计了一个FPGA加速的EBR系统FAERY，与基于GPU的EBR相比，FAERY拥有更低的延迟和更高的吞吐。

EBR利用语义嵌入向量（或称embedding）表示用户查询和候选条目，将条目检索问题转化为嵌入空间中的相似度搜索问题。下图是一个典型的EBR算法，首先将扫描语料库以获得所有条目，并计算每个条目的embedding与给定查询embedding之间的相似度得分（通过内积等方式），然后进行K-selection，根据相似度得分返回Top-K条目，EBR返回的Top-K条目通常是有序的，以便于后续算法的合并和过滤。

该算法中，第3行的语料库扫描是内存密集型操作，一个工业语料库的大小达若干GB，将产生数百万次内存访问，需要较大的外部存储器和较高的内存带宽。第4行的相似度计算是计算密集型操作，该操作计算用户查询和所有条目embedding之间的相似度得分，由于不同条目embedding的计算是相互独立的，该操作可以采用数据并行的方式。第6行的K-selection也是计算密集型操作，该操作在现有工作中已有多种实现方式，常见方式是将其划分为多个子步骤，并按照流水线的方式进行组织。

现有的EBR实现方式中，基于CPU的方案内存带宽太小，并行度有限；基于GPU的方案中，根据实验，如果将所有操作集成为一个kernel，则难以利用pipeline，且线程同步、结果合并操作开销较大，而如果将操作拆分为多个kernel，则需要externel memory进行通信，同样有性能问题。而FPGA拥有大带宽的HBM 以及大量片上RAM，并可以通过自定义逻辑实现流水线，很适合EBR。

下图为基于FPGA的FAERY加速器的主要架构：

FAERY将条目embedding存储在HBM中，语料库管理器（Corpus Manager）进行语料库扫描和更新，相似性计算（Similarity Calculation）操作采用数据并行，K-Selection操作采用流水线结构，过滤器位于K-Selection和Similarity Calculation两个操作之间，用于解决两者吞吐量不匹配的问题，并降低资源需求。

经过测试，对于HBM，为了达到90%以上的带宽利用率，一次内存访问大小应不小于64字节，因为embedding大小可能小于64字节，FAERY 将一个或多个embedding压缩到一次内存请求中。

相似度计算（Similarity Calculation）同时接收来自多个HBM通道的多个embedding，为了匹配HBM的带宽，FAERY的多个评分单元（Score Unit）并行工作，每个单元独立进行条目embedding的相似度计算。

FAERY 采用了一种基于现有工作的硬件开销较小的流水线 K-selection 方案，每个时钟周期处理一个score，但相似度计算操作采用数据并行，吞吐更高。为了解决吞吐不匹配的问题，FAERY引入了过滤器，如果K-selection的输入分数不大于现有的Top-K的最小分数，则输入不会改变内部正在运行的Top-K，因此过滤器可以直接删除该输入，从而大大减少发送到K-selection的score的数量，过滤器示意图如下：

根据分析，过滤器的输出仍然不能被K-Selection操作在一个周期内处理的概率极小，但过滤器中仍然设有一个缓冲区存储暂时无法被处理的输出，以应对该小概率事件。

多个FAERY加速器可以一起以复制或分片的模式工作，在复制模式下，不同加速器存储相同语料库的独立副本，并同时服务不同的查询，以提高查询吞吐量；在分片模式下，多个加速器存储同一个语料库的不同分片，同时服务一个查询，以增加支持的语料库大小。

在测试部分，本文基于Xilinx VU35P FPGA 进行了系统实现，并与可以支持CPU/GPU的系统 Faiss 在不同的语料库上进行延迟和吞吐的对比，结果表明FAERY降低1.21×-12.27×的延迟并提高4.29×的吞吐。

Efficient and Scalable Graph Pattern Mining on GPUs

Xuhao Chen and Arvind,MIT CSAIL

图模式挖掘(GPM)在给定的数据图中找到与给定模式相匹配的子图（如上图）。GPM在许多领域都是一个关键的构建模块，例如，蛋白质功能预测，网络对齐，垃圾邮件检测，化学信息学，社会计量学研究，图像分割。图机器学习任务也可以受益于GPM，包括异常检测、实体解析、社区检测、角色发现和关系分类。GPM的计算量非常大，因为它的搜索空间与模式大小呈指数级关系。例如，Peregrine，CPU上最先进的GPM系统，在一个56核CPU机器上，在Friendster图中挖掘4个圆形的模式（下图）需要9个小时。gpu提供了比cpu更高的计算吞吐量和内存带宽，因此对GPM加速非常友好。

然而，在GPU上高效地实现GPM是一个挑战。这是因为它需要通过利用GPU硬件架构中的信息、感兴趣的模式和输入数据图来进行复杂的优化。

本工作提出了 G2Miner，这是第一个在多gpu上高效运行的GPM框架。G2Miner采用架构感知、模式感知和输入感知的搜索策略，在gpu上实现高效的图模式搜索。

架构感知：GPU的内存容量通常比CPU小，需要更细粒度的数据并行才能充分利用GPU的算力。然而，更多的线程需要更多的内存来容纳中间数据。因此，GPU上的GPM需要仔细地编排并行度和内存使用，以最大限度地提高效率。GPU对 thread divergence和工作负载不平衡也比cpu敏感得多。这就使得GPU需要比CPU更复杂的 task-to-hardware映射。

模式感知：CPU上最先进的GPM系统使用模式感知的搜索计划，使用模式信息对搜索空间进行剪枝。这已经被证明比模式无关搜索快了几个数量级。这种模式感知方法在CPU上工作得很好，但在GPU上还没有得到很好的探索。例如，许多模式感知的剪枝方案只在DFS探索下有效，但现有的基于gpu的系统使用BFS，因此失去了这些剪枝的机会。

输入感知：动态内存分配在GPU中是非常昂贵的，如果我们可以估计最坏情况下的内存使用情况，那么我们可以避免动态内存分配。这可以通过使用一些元信息来实现，比如输入图的最大度等信息。对于有标记的图，我们可以利用输入图的顶点标签分布来获得可能的模式的最大数量，这有助于节省内存空间。通常，输入信息有助于更好地权衡工作效率、并行性和内存消耗。

上表将G2Miner与最先进的系统进行了比较，包括那些只解决子图匹配问题的系统（子图匹配问题是GPM问题的一个子集）。在上表中，子图匹配系统包括emptyheaded、Graphflow、GraphZero、GraphPi和PBE, Peregrine、Pangolin和G2Miner是通用的GPM系统。之前的大部分工作都集中在CPU上，并使用DFS来减少内存占用。另一方面，基于GPU的系统(Pangolin和PBE)使用BFS，因为直接在GPU上实现DFS会遇到thread divergence和负载不平衡的问题。无论如何，这限制了他们的效率和/或他们可以解决的问题的规模。此外，G2Miner通过自动生成CUDA代码简化了GPU编程，而Pangolin则需要用户手工编写CUDA代码，而PBE则完全不能编程。同时，G2Miner是唯一一个可以扩展到多个gpu的系统。

上图是G2Miner的overview。G2Miner由图形加载器、模式分析器、运行时系统、CUDA原语库和代码生成器组成。用户只负责使用G2Miner的API指定感兴趣的模式。模式分析器对模式进行分析，并生成一个特定于模式的搜索计划，基于此，代码生成器自动为GPU生成特定于模式的CUDA内核。内核包含对GPU原语库中定义的设备函数的调用，其中包括了高效实现的集合操作。NVCC编译器将生成的内核、GPU原语库和运行时一起编译，以生成在多GPU上运行的可执行文件。

在V100 GPU上的实验表明，G2Miner比目前最先进的两种单GPU系统Pangolin和PBE分别快5.4×和7.2×。在多gpu设置中，G2Miner实现了从1到8个gpu的线性加速，用于各种模式和数据图。作者还将G2Miner同最先进的基于CPU的系统Peregrine和GraphZero做了对比。G2Miner运行在V100 GPU上，而Peregrine和GraphZero运行在56核CPU机器上，G2Miner的速度比后两者分别快48.3和15.2倍。