Matching algorithms to array processors
Sun‐Yuan Kung, S. N. Jean, S. C. Lo · Fall joint computer conference · 1987
This paper first reviews a methodology of mapping regular computations onto VLSI array processors. In this mapping methodology, 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. Since the communication links of a given array may not meet the requirements of an algorithm or the size of a given array may be too small for some algorithms (from the mapping point of view), algorithm matching can be viewed as constrained mapping. The matching can be achieved through different modifications of the mapping methodology. To reduce I/O lines, the DG is extended such 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.