Efficient Execution of Recursive Programs on Commodity Vector Hardware
Acceptance rate 19%
Abstract
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 efficiently execute data-parallel computations in a vectorized manner. 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 paper 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.
BibTeX
@inproceedings{ren15pldi,
author = {Bin Ren and Youngjoon Jo and Sriram Krishnamoorthy and Kunal Agrawal and Milind Kulkarni},
title = {Efficient Execution of Recursive Programs on Commodity Vector Hardware},
booktitle = {Proceedings of the Programming Language Design and Implementation (PLDI)},
pages = {509--520},
publisher = {ACM},
address = {Portland, OR, USA},
year = {2015},
month = jun,
doi = {10.1145/2737924.2738004}
}