论文部分内容阅读
A new methodology is proposed for mapping and partitioning arbitrary n-dimensional nested loopalgorithms into 2-dimensional fixed size systolic arrays.Since planar VLSI arrays are easy to im-plement,our approach has good feasibility and applicability.In the transformation process of analgorithm,we take into account not only data dependencies imposed by the original algorithm but alsospace dependencies dictated by the algorithm transformation.Thus,any VLSI algorithm generated byour methodology has optimal parallel execution time and yet remains space-time conflict free.Moreover,a theory of the least complete set of interconnection matrices is proposed to reduce thecomputational complexity for finding all possible space transformations for a given algorithm.
A new methodology is proposed for mapping and partitioning arbitrary n-dimensional nested loopalgorithms into 2-dimensional fixed size systolic arrays. Strong planar VLSI arrays are easy to im-plement, our approach has good feasibility and applicability. In the transformation process of analgorithm, we take into account not only data dependencies imposed by the original algorithm but alsospace dependencies dictated by the algorithm transformation.Thus, any VLSI algorithm generated byour methodology has optimal parallel execution time and yet remains space-time conflict free .Moreover, a theory of the least complete set of interconnection matrices is proposed to reduce thecomputational complexity for finding all possible space transformations for a given algorithm.