Mapping/matching algorithms to reconfigurable mesh arrays
Shiann-Ning Jean · University of Southern California Digital Library · 2015
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 optimality criteria, select an optimal design, and then do simulation to verify the correctness. (Copies available exclusively from Micrographics Department, Doheny Library, USC, Los Angeles, CA 90089-0182.)