- 50 views
- 46 downloads
Efficient Auto-Vectorization for Control-flow Dependent Loops through Data Permutation
-
- Author / Creator
- Paktinatkeleshteri, Rouzbeh
-
The presence of control-flow divergence in loops can either hinder or impede auto-vectorization as a compiler transformation to exploit parallelism enabled by Single-Instruction Multiple-Data (SIMD) instructions. A solution is to linearize control flow through the use of predicated execution. However, computation resources are wasted when predicated instructions are executed but not committed because of a false predicate. Alternative approaches optimisticallyavoid predicated instructions when all conditions in a vectorized loop iteration evaluate to the same value. However, dynamic uniformity is less frequent in long vectors. Active-Lane-Consolidation (ALC) was proposed to form uniformvectors dynamically by merging active elements from different iterations. In its seminal presentation, ALC was only evaluated in a simulated environment through hand-modified programs. This thesis presents the first performance evaluation of ALC on real hardware which reveals that the original design of ALC indeed reduces the number of executed instructions, but it fails to provide speedup over auto-vectorized code. It then presents a change to the design of ALC that results in it outperforming auto-vectorized code and describes the first compiler-enabled transformation that applies ALC as a compiler optimization pass. The experimental results show that compiler-generated ALC codeoutperforms auto-vectorized code, produced by state-of-the-art compilers, by up to 79%.
-
- Subjects / Keywords
-
- Graduation date
- Fall 2023
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.