A Portable Optimization Engine for Accelerating Irregular Data-Traversal Applications on SIMD Architectures
A Portable Optimization Engine for Accelerating Irregular Data-Traversal Applications on SIMD Architectures
复制标题
DOI：
10.1145/2632215
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Bin Ren;Todd Mytkowicz;G. Agrawal
中科院分区：
文献类型：
--
作者：
Bin Ren;Todd Mytkowicz;G. Agrawal
细颗粒数据并行性越来越普遍，以与主流处理器（SSE，AVX）和各种GPU架构集成的更长向量的形式。本文开发了为一类非数字的非数字应用程序利用此类数据并行性的支持，这些应用程序在遍历许多独立的，不规则的数据结构时进行了计算。我们通过开发多种新技术来解决这个问题。首先，对于代码生成，我们开发了一种用于指定此类遍历的中间语言，然后是一个运行时调度程序，将遍历遍历到各种SIMD单元。其次，我们观察到，良好的数据局部性对于SIMD架构的持续性能至关重要，而在不规则数据结构（例如，树木和图形）上运行的许多应用程序的数据局部性很差。为了应对这一挑战，我们开发了一组数据布局优化，以改善遍历许多不规则数据结构的应用程序。与先前的数据布局优化不同，我们的方法将线程相互和杂物的空间重复使用的概念纳入数据布局。最后，我们通过准确对Interrath Read Locality对程序性能的影响进行建模，启用性能可移植性（即，能够自动优化不同体系结构的应用程序的功能）。结果，我们的模型可以预测用于在各种SIMD体系结构上使用的数据布局优化。为了证明我们的方法和优化的功效，我们首先展示了它们如何在一组真实世界应用程序上启用一个SIMD架构上的12倍加速度。为了证明我们的方法可以实现性能可移植性，我们展示了我们的模型如何预测三种真实世界SIMD体系结构的各种应用程序的最佳布局，该架构在次优的解决方案上提供了多达45％的速度。
Fine-grained data parallelism is increasingly common in the form of longer vectors integrated with mainstream processors (SSE, AVX) and various GPU architectures. This article develops support for exploiting such data parallelism for a class of nonnumeric, nongraphic applications, which perform computations while traversing many independent, irregular data structures. We address this problem by developing several novel techniques. First, for code generation, we develop an intermediate language for specifying such traversals, followed by a runtime scheduler that maps traversals to various SIMD units. Second, we observe that good data locality is crucial to sustained performance from SIMD architectures, whereas many applications that operate on irregular data structures (e.g., trees and graphs) have poor data locality. To address this challenge, we develop a set of data layout optimizations that improve spatial locality for applications that traverse many irregular data structures. Unlike prior data layout optimizations, our approach incorporates a notion of both interthread and intrathread spatial reuse into data layout. Finally, we enable performance portability (i.e., the ability to automatically optimize applications for different architectures) by accurately modeling the impact of inter- and intrathread locality on program performance. As a consequence, our model can predict which data layout optimization to use on a wide variety of SIMD architectures. To demonstrate the efficacy of our approach and optimizations, we first show how they enable up to a 12X speedup on one SIMD architecture for a set of real-world applications. To demonstrate that our approach enables performance portability, we show how our model predicts the optimal layout for applications across a diverse set of three real-world SIMD architectures, which offers as much as 45% speedup over a suboptimal solution.