The USC Andrew and Erna Viterbi School of Engineering USC Signal and Image Processing Institute USC Ming Hsieh Department of Electrical Engineering University of Southern California

Technical Report USC-SIPI-142

“Mapping/Matching Algorithms to Reconfigurable Mesh Arrays”

by Shiann-Ning Jean

December 1988

Due to the fast progress of VLSI technology, algorithm-oriented array architectures appear to be effective, feasible, and economic. In particular, a large class of regular computations, especially those for signal and image processing can be efficiently implemented on arrays of processors. these trends have necessitated a systematic methodology of mapping computations onto processor arrays.

To facilitate the mapping, these regular computations can be represented in some computational graphs. In this dissertation (1) a canonical mapping methodology is introduced to map homogeneous computational graphs onto arrays; (2) a generalized mapping methodology is proposed to map heterogeneous computational graphs onto arrays; (3) algorithm matching techniques are developed to ensure the efficient execution of algorithms on a given array; and (4) a single-track switch model is proposed and a reconfiguration algorithm is developed for high yield implementation of mesh processor arrays.

To unify these techniques, a set of programs are developed on a Sun workstation (Sun 3/60) with a color monitor. The resulting software is intended to be used as a CAD tool for designing a processor array. The input to the system is a description of the computation to be parallelized and executed on a processor array. The system accepts high-level behavior inputs in terms of dependence graphs (DGs) and generates array structures. The system provides graphic interface, criteria evaluator, and simulation tools to facilitate the designer. A designer can see the DG graphically displayed, modify the DG, simulate the DG, evaluate different optimally criteria, select an "optimal" design, and then do simulation to verify the correctness.

To download the report in PDF format click here: USC-SIPI-142.pdf (41.9Mb)