Simdization transformation strategies

Simdization transformation strategies

Westen, H.P.

Bertels, K.L.M. (mentor)

Electrical Engineering, Mathematics and Computer Science

Microelectronics & Computer Engineering

Computer Engineering

2012-09-26

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.

SIMD
simdization
loop-nest transformations

http://resolver.tudelft.nl/uuid:6d524027-0abc-46ec-a710-dc958062a38d

Student theses

master thesis

(c) 2012 Westen, H.P.