Efficient Execution of Recursive Programs on Commodity Vector Hardware

Bin Ren, Youngjoon Jo, Sriram Krishnamoorthy, Kunal Agrawal, and Milind Kulkarni

PLDI 2015 · Programming Language Design and Implementation · June 2015 · pp. 509-520

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}
}

Group members