Challenging Sequential Bitstream Processing via Principled Bitwise Speculation
Challenging Sequential Bitstream Processing via Principled Bitwise Speculation
复制标题
通过有原则的按位推测挑战顺序比特流处理
DOI：
10.1145/3373376.3378461
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zhao, Zhijia
中科院分区：
文献类型：
--
作者：
Qiu, Junqiao;Jiang, Lin;Zhao, Zhijia
许多性能关键型应用程序通过按位计算遍历比特流，以获得更好的性能或更高的空间效率，例如多媒体处理和位图索引。然而，当这些按位计算带有依赖性时，整个比特流遍历变得串行，从根本上限制了可扩展性。在这项工作中，我们表明，通过采用系统化处理——有原则的按位推测（PBS），比特流携带的依赖性在许多情况下实际上是“可打破的”。 PBS 的核心思想源于比特流程序和时序电路之间的类比，两者都转换二进制序列。在这个新的视角中，使用有限状态机（FSM）（时序电路的基本模型）对比特流程序中的依赖性进行建模变得很自然。为了实现这一目标，PBS 提供了一组静态分析，这些分析将比特流程序推理到比特级别，以识别导致相关性的比特，然后将相关比特的值组合视为构造 FSM 的状态。该建模首次支持使用 FSM 推测技术来并行化比特流程序。基本上，通过利用 FSM 的状态收敛，可以以更高的精度预测相关位的值。如果预测失败，PBS 会尝试根据按位逻辑直接“纠正”错误的输出，从而最大限度地减少错误推测成本。此外，FSM在某些情况下表现出比原始程序更高的执行效率，使其成为加速串行比特流处理的优化版本。我们使用 LLVM 制作了 PBS 原型。对实际比特流程序的评估证实了 PBS 的有效性，在多核/众核机器上显示出接近线性的加速。
Many performance-critical applications traverse bitstreams with bitwise computations for better performance or higher space efficiency, such as multimedia processing and bitmap indexing. However, when these bitwise computations carry dependences, the entire bitstream traversal becomes serial, fundamentally limiting the scalability. In this work, we show that bitstream-carried dependences are actually "breakable" in many cases, with the adoption of a systematic treatment - principled bitwise speculation (PBS). The core idea of PBS stems from an analogy drawn between bitstream programs and sequential circuits, both of which transform binary sequences. In this new perspective, it becomes natural to model the dependences in bitstream programs with finite-state machines (FSM), a basic model for sequential circuits. To achieve this, PBS features an assembly of static analyses that reason about bitstream programs down to the bit level to identify the bits causing dependences, then it treats the value combinations of dependent bits as states to construct FSMs. The modeling, for the first time, enables the use of FSM speculation techniques to parallelize bitstream programs. Basically, by leveraging the state convergence of FSMs, the values of dependent bits can be predicted with much higher accuracies. In cases the prediction fails, PBS tries to directly "rectify" the wrong outputs based on bitwise logic, minimizing the mis-speculation costs. In addition, FSM shows even higher execution efficiency than the original program in some cases, making itself an optimized version to accelerate serial bitstream processing. We prototyped PBS using LLVM. Evaluation with real-world bitstream programs confirms the effectiveness of PBS, showing up to near-linear speedup on multicore/manycore machines.
登录
查看更多内容
为 FSM 计算启用可扩展性敏感的推测并行化
DOI：
10.1145/3079079.3079082
发表时间：
2017
期刊：
Proceedings of the International Conference on Supercomputing
影响因子：
--
作者：
Junqiao Qiu;Zhijia Zhao;Bo Wu;Abhinav Vishnu;S. Song
通讯作者：
S. Song
16 位指令的动态合并
DOI：
--
发表时间：
2005
期刊：
TECS
影响因子：
--
作者：
A. Krishnaswamy;Rajiv Gupta
通讯作者：
Rajiv Gupta
影响因子：
1.5
作者：
Jimborean, Alexandra;Clauss, Philippe;Caamano, Juan Manuel Martinez
通讯作者：
Caamano, Juan Manuel Martinez
商品并行处理器上当代半结构化数据的可扩展处理 - 基于编译的方法
DOI：
10.1145/3297858.3304008
发表时间：
2019
期刊：
Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS '19
影响因子：
--
作者：
Jiang, Lin;Sun, Xiaofan;Farooq, Umar;Zhao, Zhijia
通讯作者：
Zhao, Zhijia
MicroSpec：用于 FSM 计算的以推测为中心的细粒度并行化
DOI：
10.1145/2967938.2967965
发表时间：
2016
期刊：
2016 International Conference on Parallel Architecture and Compilation Techniques (PACT)
影响因子：
--
作者：
Junqiao Qiu;Zhijia Zhao;Bin Ren
通讯作者：
Bin Ren