Optimization of Vector Instructions in Divergent Control Flow on Long-Vector Architectures using Active-Lane Consolidation

  • Author / Creator
    Wyatt Praharenka
  • IF-conversion is a classic Control-Flow Graph (CFG) transformation that linearizes the basic blocks in a loop and assigns a predicate to them to enable or disable execution. IF-conversion is performed before vectorization where scalar statements are translated into vector statements to enable the vectorization of code with control flow constructs such as if-then-else statements. Divergent control flow contributes to the under-utilization of vector instructions where a low ratio of vector lanes produce a useful result. Traditional methods, such as the insertion of Branch on Super-Word Condition-Codes (BOSCCs), attempt to elide the execution of vector code with no active-lanes, however, with the increasing vector-lengths (VLs) appearing in vector Instruction-Set Architecture (ISA) extensions, BOSCCs lose their effectiveness.
    This thesis presents Active-Lane Consolidation (ALC), a variable vector permutation that re-organizes the lanes between two vector registers to consolidate those that are active into a single vector, increasing utilization; details the implementation of ALC in a modern vector ISA using only the current permutations available; presents two loop-transformations for loops with divergent control flow to utilize ALC and presents case studies for four benchmarks from the SPEC 2017 benchmark suite. The case studies show that ALC can substantially increase vector utilization in certain loops with divergent control flow, especially where IF-conversion and BOSCCs struggle. The increase in vector utilization translates to a large reduction in the dynamic instruction
    count giving evidence to the profitability of using ALC.

  • Subjects / Keywords
  • Graduation date
    Fall 2021
  • Type of Item
  • Degree
    Master of Science
  • DOI
  • 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.