Extracting SIMD Parallelism from Recursive Task-Parallel Programs
Extracting SIMD Parallelism from Recursive Task-Parallel Programs
复制标题
DOI：
10.1145/3365663
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Bin Ren;S. Balakrishna;Youngjoon Jo;S. Krishnamoorthy;Kunal Agrawal;Milind Kulkarni
中科院分区：
文献类型：
--
作者：
Bin Ren;S. Balakrishna;Youngjoon Jo;S. Krishnamoorthy;Kunal Agrawal;Milind Kulkarni
对计算效率的追求导致了面向吞吐量的硬件，从GPU到增加商品处理器和加速器上的较宽的向量单元。在没有数据并行性的情况下，更自然地表示为递归，递归，任务平行的计算。为了实现吞吐量的体系结构。在限制空间使用的同时，高利用矢量资源。使用Intel的SSE4.2矢量单元以及使用Intel的Avx512单元的加速器进行大量加速，我们通过严格的采样表明，实际上，我们的矢量化技术对更大的程序有效。
The pursuit of computational efficiency has led to the proliferation of throughput-oriented hardware, from GPUs to increasingly wide vector units on commodity processors and accelerators. This hardware is designed to execute data-parallel computations in a vectorized manner efficiently. However, many algorithms are more naturally expressed as divide-and-conquer, recursive, task-parallel computations. In the absence of data parallelism, it seems that such algorithms are not well suited to throughput-oriented architectures. This article presents a set of novel code transformations that expose the data parallelism latent in recursive, task-parallel programs. These transformations facilitate straightforward vectorization of task-parallel programs on commodity hardware. We also present scheduling policies that maintain high utilization of vector resources while limiting space usage. Across several task-parallel benchmarks, we demonstrate both efficient vector resource utilization and substantial speedup on chips using Intel’s SSE4.2 vector units, as well as accelerators using Intel’s AVX512 units. We then show through rigorous sampling that, in practice, our vectorization techniques are effective for a much larger class of programs.