一句话：提出统一抽象 RZM 与可组合并行原语，以 O(V log V) 硬件代价支持多种归并类操作并获得显著加速。
排序键值数组上的归并类操作（MSO）在科学计算、深度学习、数据库和图分析中非常基础，但已有并行方案大多孤立处理不同 MSO，难以支持可变键/值大小与运行时值计算，且常需 O(V^2) 硬件代价。本文提出统一抽象模型“受限 zip 机器（RZM）”，并设计可组合并行原语以支持可变键/值大小和运行时值计算，给出仅需 O(V log V) 资源的硬件实现。该设计可作为加速器归并单元的替代或 CPU/GPU 的 SIMD ISA 扩展。在 CPU 上 V=16 时，集合运算、数据库连接、稀疏张量运算、归并排序和 SpGEMM 等获得 4.4×–8.4× 加速。
The processing of sorted key-value arrays using a “merge style operation (MSO)” is a very basic and important problem in domains like scientific computing, deep learning, database, graph analysis, sorting, set-operation etc. MSOs dominate the execution time in some important applications like SpGEMM and graph mining. For example, sparse vector addition as an MSO takes up to 98% execution time in SpGEMM in our experiment. For this reason, accelerating MSOs on CPU, GPU, and accelerators using parallel execution has been extensively studied but the solutions in prior work have three major limitations. (1) They treat different MSOs as isolated problems using incompatible methods and an unified solution is still lacking. (2) They do not have the flexibility to support variable key/value sizes and value calculations in the runtime given a fixed hardware design. (3) They require a quadratic hardware cost (O(V2)) for given parallelism V in most cases. To address above three limitations, we make the following efforts. (1) We present a one-for-all solution to support all interested MSOs based on a unified abstraction model “restricted zip machine (RZM)”. (2) We propose a set of composable and parallel primitives for RZM to provide the flexibility to support variable key/value sizes and value calculations. (3) We provide the hardware design to implement the proposed primitives using only O(Vlog(V)) resource. With the above techniques, a flexible and efficient solution for MSOs has been built. Our design can be used either as a drop-in replacement of the merge unit in prior accelerators to reduce the cost from O(V2) to O(Vlog(V)), or as an extension to the SIMD ISA of CPU and GPU. In our evaluation on CPU, when V=16 (512-bit SIMD, 32-bit element), we achieve significant speedup on a range of representative kernels including set operations (8.4×), database joins (7.3×), sparse vector/matrix/tensor addition/multiplication on real/complex numbers (6.5×), merge sort (8.0× over scalar, 3.4× over the state-of-the-art SIMD), and SpGEMM (4.4× over the best one in the baseline collection).
@inproceedings{WangDSDLWX22,
title = {A one-for-all and
<i>o</i>
(
<i>v</i>
log(
<i>v</i>
))-cost solution for parallel merge style operations on sorted key-value arrays},
author = {Bangyan Wang and Lei Deng and Fei Sun and Guohao Dai and Liu Liu and Yu Wang and Yuan Xie},
booktitle = {ASPLOS},
year = {2022},
doi = {10.1145/3503222.3507728}
}