|
|
|
“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.