Efficient execution of recursive programs on commodity vector hardware
Authors:
Open Access
- 3 June 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 509-520
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.Keywords
Funding Information
- National Science Foundation (CCF-1150013,CCF-1439126,CCF-1439062)
- U.S. Department of Energy (63823,DE-SC0010295)
This publication has 30 references indexed in Scilit:
- Fine-grain task aggregation and coordination on GPUsACM SIGARCH Computer Architecture News, 2014
- From relational verification to SIMD loop synthesisACM SIGPLAN Notices, 2013
- Efficient SIMD code generation for irregular kernels2012
- Enhancing locality for recursive traversals of recursive structures2011
- Shallow Bounding Volume Hierarchies for Fast SIMD Ray Tracing of Incoherent RaysComputer Graphics Forum, 2008
- UTS: An Unbalanced Tree Search Benchmark2007
- Programming with exceptions in JCilkScience of Computer Programming, 2006
- Efficient parallel out-of-core matrix transpositionInternational Journal of High Performance Computing and Networking, 2004
- CilkACM SIGPLAN Notices, 1995
- Vectorization of tree traversalsJournal of Computational Physics, 1990