A space-time representation method of iterative algorithms for the design of processor arrays

A novel Space-Time Representation (STR) of iterative algorithms for their s ystematic mapping onto regular processor arrays is proposed. Timing informa tion is introduced in the Dependence Graph (DG) by the definition and the c onstruction of the Space-Time DG (STDG). Any variable instance of the loop body, independently of the number of the loop indices, is characterized by an integer vector composed by its indices, as space part, and an additional time index, representing its execution time according to a preliminary tim ing. The main advantage of the STR is that the need for the uniformization of the algorithm is avoided. Moreover, it is proven that in the STDG depend ence vectors having opposite directions do not exist and therefore a linear mapping of the STDG onto the desired processor array can always be derived . Efficient 2D and 1D regular architectures are produced by applying the ST R to the original description of the Warshall-Floyd algorithm for the Algeb raic Path Problem.