94720, October 1997. Wavefront arrays use a dataflow method of execution, and hence, do not require global synchronization.
Array elements start computing whenever they have all of their inputs.
In a systolic implementation, the dependence graph cannot have any cycles since the existence of a schedule depends on the existence of a schedule vector that has non-negative dot product with each dependency edge. However, a graph implemented on a WA may have cycles provided that the cycles do not deadlock. While both of these problems are well known and well studied for ordinary static, homogeneous dataflow graphs, and can be solved with polynomial time algorithms, they have not been studied in the context of RDFGs. Since RDFGs have an exponentially more compact representation, we determine the complexity of these two problems in terms of this lower representation size. We show that the problems are NP-complete, and hence, no advantage can be theoretically gained from the smaller input size.