HOME UP PREV NEXT (Kiwi : Compiling Concurrent Programs to Hardware)

Polyhedral Address Mapping

Not examinable Q. Does the following have loop interference ?

  for (i=0; i<N; i++)  A[i] := (A[i] + A[N-1-i])/2

A. Yes, at first glance, but we can recode it as two independent loops. ('Loop Splitting for Efficient Pipelining in High-Level Synthesis' by J Liu, J Wickerson, G Constantinides.) "In reality, there are only dependencies from the first N/2 iterations into the last N/2, so we can execute this loop as a sequence of two fully parallel loops (from 0...N/2 and from N/2+1...N). The characterization of this dependence, the analysis of parallelism, and the transformation of the code can be done in terms of the instance-wise information provided by any polyhedral framework."

Q. Does the following have loop body inter-dependencies ?

  for (i=0; i<N; i++)  A[2*i] = A[i] + 0.5f;

A. Yes, but can we transform it somehow?

Affine transformations (Zuo, Liang et al). »Improving High Level Synthesis Optimization Opportunity Through Polyhedral Transformations

The skewing of block 1 enables it to be parallelised without data dependence. The following block can be run in parallel after an appropriately delayed start ...

»Wikipedia:Polyhedral