Simdization transformation strategies

The Single Instruction Multiple Data (SIMD) paradigm promises speedup at relatively low silicon area cost for software that exposes a large amount of loop level parallelism. Automatic simdization–the act of exploiting loop level parallelism by issueing SIMD instructions that operate on multiple data elements at once– remains a daunting task for compilers, especially because SIMD instructions impose restrictions on the organization of the data elements. The CoSy simdization flow is able to effectively transform and simdize a program such that parallelism that is directly exposed in the inner loop is exploited, but it may not be able to exploit parallelism that is exposed at higher levels of a loop. This thesis proposes a new pass in the simdization flow that exposes such parallelism in a form in which it can be exploited. To achieve such transformations and determine which transformation should be applied, the polyhedral approach has been used. A polyhedral representation of loop nests allows for precise dependence analysis and application of transformations. To find the best transformation, we have proposed a cost estimation model that estimates the simdizability and cost of a transformation based on the polyhedral representation of the original loop nest. A prototype of this pass has been implemented, and using a number of tests the new flow has been shown to allow simdization in the CoSy flow where previously no simdization could take place.Computer EngineeringMicroelectronics & Computer EngineeringElectrical Engineering, Mathematics and Computer Scienc