Mapping of algorithms onto programmable data-driven arrays
Bilha Mendelson, Israel Koren · Scholarworks (University of Massachusetts Amherst) · 1991
Control-driven arrays (e.g., systolic arrays) provide high levels of parallelism and pipelining for inherently regular computations. Data-driven arrays can provide the same for algorithms with no internal regularity. The purpose of this research is to establish a method for speeding up an algorithm by mapping and executing it on a data driven array. The array being used is an homogeneous, hexagonal, data driven processor array. Mapping a general algorithm, given in the data flow language SISAL, consists of translating the algorithm to a data flow graph (DFG) and assigning every node in the DFG to a processing element (PE) in the array. This research aims to find an efficient mapping that minimizes the area, and maximizes the performance of the given algorithm or find a tradeoff between the two.