An Efficient Algorithm for Delay Buffer Minimization

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