背景

随着计算机架构的发展，即使是嵌入式系统，也可以集成GPU设备，提供卓越的性能和能效，满足不同行业、应用和部署环境的需求。数据分析是嵌入式系统的重要应用场景。遗憾的是，由于嵌入式设备容量的限制，嵌入式系统处理的问题规模有限。

中国人民大学数据工程与知识工程教育部重点实验室张峰、杜小勇老师课题组提出了一种新的数据分析方法，称为 G-TADOC，用于直接对嵌入式 GPU 系统上的压缩进行有效的文本分析。嵌入式系统可以对大量数据进行压缩存储，在压缩状态下可以直接进行处理，大大增强了系统的处理能力。

直接基于压缩的文本分析 (TADOC)

在日常生活中，越来越需要轻巧方便的嵌入式设备来促进数据分析任务，而嵌入式系统，例如 NVIDIA Jetson XAV IER NX ，在同一芯片上集成了 GPU 和 CPU，将超级性能达到边缘。

研究团队以 Jetson XAVIER NX 平台为例，它包含整个计算机系统组件，包括一个 GPU。重要的是，它的长度小于钢笔的长度，而且价格低廉。然而，目前的嵌入式 GPU 与服务器用 GPU 相比仍然不那么强大，并且存储空间有限。幸运的是，最近的一项技术，即直接基于压缩的文本分析 (TADOC, Text Analytics Directly On Compression) 已被证明是一种很有前途的大数据分析技术。由于TADOC无需解压即可处理压缩数据，因此可以节省大量空间。同时，TADOC 复用数据和中间计算结果，使得原始文件不同部分的相同内容只能处理一次，从而节省了大量的计算时间。因此，在嵌入式 GPU 系统上应用TADOC 是非常有益的。

挑战

尽管在嵌入式 GPU 上启用 TADOC 会带来显着的好处，但开发高效的启用GPU的TADOC极具挑战性。首先，TADOC 将数据转化为规则，规则可以进一步表示为DAG。

不幸的是，TADOC 的规则结构的 DAG 之间的依赖量非常大，这对 GPU 并行性不友好，表现在：

1. 在研究团队的实验中，为每个文件生成的 DAG 平均有 450,704 个独立的中间层节点，这极大地限制了其并行性。更糟糕的是，TADOC 的 DAG 中的一个节点可以有多个父节点，这使得这个问题更加 复杂的。

2. 大量 GPU 线程写入同一个结果缓冲区，不可避免地会造成巨大的写入冲突。一个直接的解决方案是锁定线程的缓冲区，但这种原子性会失去部分性能。在最坏的情况下，并行性能低于 CPU 顺序TADOC。

3. 维护和利用 GPU 上的序列信息是另一个难点：原来的 TADOC 采用递归调用 对压缩数据进行完整的顺序遍历，这类似于深度优先搜索 (DFS)，并且极难并行求解。此外，需要设计特殊优化，例如针对嵌入式GPU使用CPU-GPU共享统一内存。

有大量关于TADOC的文献，但不幸的是，目前的 TADOC 解决方案都没有解决在上述 GPU 上启用 TADOC 的挑战。

细节

为了解决上述挑战，研究团队开发了 G-TADOC，这是第一个直接在压缩时提供基于 GPU 的文本分析的框架，有效地在 GPU 上实现高效的文本分析，而无需解压输入数据。G-TADOC 涉及三个新颖的功能，可以解决上述三个挑战。

1. 为了利用 GPU 并行性，团队在 GPU 上开发了一种细粒度的线程级工作负载调度策略，它根据不同规则的负载自适应地分配线程资源，并使用掩码来描述规则之间的关系。

2. 为了解决多线程写冲突的挑战，他们启用 G-TADOC 来维护自己的内存池并设计线程安全的数据结构。当多个线程同时更新全局结果时，他们使用锁缓冲区。

3. 为了支持 G-TADOC 中的序列敏感应用，他们在每个规则中开发了头尾数据结构来存储规则开始和结束的内容，这需要一个轻量级的 DAG 遍历。

此外，团队添加了额外的新基准和数据集实验。在目前最强大的嵌入式 GPU 平台、Nvidia JETSON AGX XAVIER 和三个独立 GPU 平台评估 G-TADOC，涵盖了三代 Nvidia GPU（Pascal、Volta 和 Turing 微架构）。

创新点

G-TADOC 有三项创新。

1. 首先，开发了一种新的GPU线程细粒度线程级工作负载调度策略，它以细粒度的方式自适应地划分高度依赖的负载。

2. 开发了一个GPU线程安全内存池来处理低同步开销的不一致问题。

3. 一种序列支持策略，以保持高GPU并行性，同时确保无损压缩的序列信息。

此外，G-TADOC涉及对嵌入式GPU的特殊优化，例如利用CPU-GPU共享统一内存。

实验表明，与最先进的TADOC工作相比，G-TADOC提供了 13.2 倍的平均加速。G-TADOC 还比 TADOC 提高了 2.6 倍的单位成本性能和 32.5 倍的能源效率。

----------------

论文作者：

潘再峰、张峰、周炎亮、翟季冬（清华大学）、慎熙鹏（NCSU）、Onur Mutlu（ETH Zürich）、杜小勇

论文信息：

Z. Pan, F. Zhang, et al., "Exploring Data Analytics Without Decompression on Embedded GPU Systems," in IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 7, pp. 1553-1568, 1 July 2022, doi: 10.1109/TPDS.2021.3119402.