SIMD parallelization of applications that traverse irregular data structures
SIMD parallelization of applications that traverse irregular data structures
复制标题
DOI：
10.1109/cgo.2013.6494989
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
Bin Ren;G. Agrawal;J. Larus;Todd Mytkowicz;T. Poutanen;Wolfram Schulte
中科院分区：
文献类型：
--
作者：
Bin Ren;G. Agrawal;J. Larus;Todd Mytkowicz;T. Poutanen;Wolfram Schulte
细粒度数据并行性在主流处理器中越来越普遍，以较长的向量和片上GPU的形式。本文为一类非数字的非图形应用程序开发了利用此类数据并行性的支持，这些应用程序在遍历许多独立的，不规则的数据结构时进行了计算。尽管任何一个不规则的数据结构的遍历都没有给并行化的机会，而是遍历其中的一组。但是，将这种并行性映射到SIMD单位是不平凡的，在先前的工作中没有解决。我们通过开发一种用于指定此类遍历的中间语言来解决此问题，然后是将遍历遍历映射到SIMD单元的运行时间调度程序。我们运行时方案中的一个关键想法是将分支转换为算术操作，然后允许我们使用SIMD硬件。为了快速实现我们的方法，我们演示了几种优化，包括一种流动压实方法，该方法具有SIMD中控制流的辅助，这是一组降低内存延迟的布局，以及一种可以更有效的预拿的瓷砖方法。使用我们的方法，我们证明了单核性能的显着提高，而不是针对两种应用的优化基线。
Fine-grained data parallelism is increasingly common in mainstream processors in the form of longer vectors and on-chip GPUs. This paper develops support for exploiting such data parallelism for a class of non-numeric, non-graphic applications, which perform computations while traversing many independent, irregular data structures. While the traversal of any one irregular data structure does not give opportunity for parallelization, traversing a set of these does. However, mapping such parallelism to SIMD units is nontrivial and not addressed in prior work. We address this problem by developing an intermediate language for specifying such traversals, followed by a run-time scheduler that maps traversals to SIMD units. A key idea in our run-time scheme is converting branches to arithmetic operations, which then allows us to use SIMD hardware. In order to make our approach fast, we demonstrate several optimizations including a stream compaction method that aids with control flow in SIMD, a set of layouts that reduce memory latency, and a tiling approach that enables more effective prefetching. Using our approach, we demonstrate significant increases in single-core performance over optimized baselines for two applications.