Space-time representation of iterative algorithms and the design of regular processor arrays

Abstract

A novel space-time representation of iterative algorithms, which can be expressed in nested loop form and may include non-constant dependencies is proposed and a systematic methodology for their mapping onto regular processor arrays is presented. In contrast to previous design methodologies, the execution time of any variable instance is explicitly expressed in the Dependence Graph, by the construction of the Space-Time Dependence Graph (STDG). This approach avoids the uniformization step of the algorithm and the requirement for fully indexing the variables. Also in the STDG dependence vectors having opposite directions do not exist and therefore, a linear mapping of the STDG onto the processor array can alwys be derived. Efficient 2-D and 1-D regular processor arrays are produced by applying the method to the Warshall-Floyd algorithm.