MATCHING ALGORITHMS TO ARRAY PROCESSORS.

A methodology for mapping regular computations onto VLSI array processors is reviewed in which algorithms are described by dependence graphs (DGs). The objective of the mapping is to design an array to directly support the requirements of an algorithm. Several algorithm matching techniques are then proposed to ensure the efficient execution of algorithms on a given array. The matching can be achieved through different modifications of the mapping methodology. To reduce I/O lines, the DG is extended so that I/O are handled by boundary processing elements (PEs) only. Time-sharing schemes are devised to match algorithms to mesh and hypercube arrays. To meet the array size constraints, partitioning, which decomposes large problems into several smaller subproblems, and multiprojection, which applies the mapping method multiple times, are also addressed.