The Concept and Implementation of Data-Driven Processor Arrays

V arious topologies and architec-tural designs for processor arrays have recently been proposed. These designs include systolic arrays and globally asynchronous wavefront arrays. ' Both array types have a computation front that propagates according to a predeter-mined control sequence, and consequently these control-driven arrays have proven to be very effective for executing highly regu-lar algorithms like vector and matrix oper-ations. There are, however, many computationally demanding problems that do not exhibit high regularity and may therefore prove unsuitable for these control-driven arrays. Still, many ofthese problems have an inherent parallelism, and it should be possible to exploit this parallelism by means of processor arrays that can provide a high degree of pipelining. In Koren and Silberman,2 a new approach to array design was proposed-that of developing specialized array architectures that would be capable of executing any given algorithm. In this approach, the algorithm is first repre-sented in the form of a dataflow graph (DFG) and is then mapped onto the array. The processing elements (PEs) in the array execute the operations included in the cor-responding nodes (or subsets of nodes) of the DFG; regular interconnections ofthese PEs serve as edges of the graph. In general, when an arbitrary algorithm is executed on an array there is no regular propagation of computation fronts. Hence, to speed up the execution of arbi-trary algorithms, a more flexible array is needed. Such an array should make pos-sible the generation of new computation fronts and their cancellation at a later tim