An efficient algorithm for delay buffer minimization

A data flow machine is said to be synchronized if for any vertex u in the u nderlying data flow graph, all inputs to vertex u arrive at the same time. An unsynchronized data flow machine with an acyclic underlying data flow gr aph can be transformed into a synchronized system by adding unit delay buff ers to the system. This synchronization process can increase pipelining and throughout. Since the addition of delay buffers introduces hardware and ar ea costs, it is desirable to insert the minimum number of delay buffers to synchronize a given data flow machine. Due to important applications in com puter design, various delay buffer minimization problems have been studied by many researchers. Several optimal algorithms and heuristic algorithms ha ve been proposed for slightly different models. In this paper, we introduce the concept of extensions of a directed acyclic graph to generalize and fo rmalize several delay buffer minimization problems studied in the literatur e and present a polynomial time algorithm for computing the minimum delay b uffer synchronization of a given data flow machine. Examples are provided t o illustrate our algorithm and to show that our algorithm requires fewer de lay buffers than previously published optimal algorithms for various models .