On Control Signals for Multidimensional Time
DaeGon Kim, Gautam Gupta and Sanjay Rajopadhye
The 19th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2006)
New Orleans, Louisiana, November 2-4, 2006
Abstract
Affine control loops (ACLs) comprise an important class of compute- and data-intensive computations. The theoretical framework for the automatic parallelization of ACLs is well established. However, the hardware compilation of arbitrary ACLs is still in its infancy. An important component for an efficient hardware implementation is a control mechanism that informs each processing element (PE) which computation needs to be performed and when. We formulate this control signal problem in the context of compiling arbitrary ACLs parallelized with a multi-dimensional schedule into hardware. We characterize the logical time instants when PEs need a control signal indicating which particular computations need to be performed. Finally, we present an algorithm to compute the minimal set of logical time instants for these control signals.