A Space-Time Representation Method of Iterative Algorithms for the Design of Processor Arrays

    loading  Checking for direct PDF access through Ovid


A novel Space-Time Representation (STR) of iterative algorithms for their systematic mapping onto regular processor arrays is proposed. Timing information is introduced in the Dependence Graph (DG) by the definition and the construction 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 timing. 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 dependence 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 STR to the original description of the Warshall-Floyd algorithm for the Algebraic Path Problem.

    loading  Loading Related Articles