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

被引：0
作者：
E.D. Kyriakis-Bitzaros
C.E. Goutis
机构：
[1] NCSR “DEMOKRITOS,Institute of Microelectronics
[2] ”,VLSI Design Laboratory, Department of Electrical Engineering
[3] University of Patras,undefined
来源：
Journal of VLSI signal processing systems for signal, image and video technology | 1999年 / 22卷
关键词：
Dependence Graph; Systolic Array; Index Point; Total Execution Time; Processor Array;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：151 / 162
页数：11
相关论文
共 40 条
  • [1] Cappello P.R.(1984)Unifying VLSI array design with linear transformations of space-time Advances in Computer Research 2 23-65
  • [2] Steiglitz K.(1992)An efficient decomposition technique for mapping nested loops with constant dependencies into regular processor arrays J. of Parallel and Distributed Computing 16 258-264
  • [3] Kyriakis-Bitzaros E.D.(1988)Synthesizing linear array algorithms from nested for loop algorithms IEEE Trans. on Computers 37 1578-1598
  • [4] Goutis C.E.(1990)Mapping nested loop algorithms into multidimensional systolic arrays IEEE Trans. on Parallel and Distributed Systems 1 64-76
  • [5] Lee P.(1986)Partitioning and mapping algorithms into fixed size systolic arrays IEEE Trans. on Computers C-35 1-12
  • [6] Kedem Z.M.(1990)Matrix computations on systolic type meshes IEEE Computer 23 32-51
  • [7] Lee P.(1989)The mapping of linear recurrence equations on regular arrays Journal of VLSI Signal Processing 1 95-113
  • [8] Kedem Z.M.(1989)Synthesizing systolic arrays with control signals from recurrence equations Distributed Computing 3 88-105
  • [9] Moldovan D.I.(1988)Regular iterative algorithms and their implementation on processor arrays Proc. of the IEEE 76 259-269
  • [10] Fortes J.A.B.(1994)Constructive methods for scheduling uniform loop nests IEEE Trans. on Parallel and Distributed Systems 5 814-822
1234