An efficient algorithm for delay buffer minimization

Citation
Gl. Xue et al., An efficient algorithm for delay buffer minimization, J COMB OPTI, 4(2), 2000, pp. 217-233
Citations number
13
Categorie Soggetti
Mathematics,"Engineering Mathematics
Journal title
JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN journal
13826905 → ACNP
Volume
4
Issue
2
Year of publication
2000
Pages
217 - 233
Database
ISI
SICI code
1382-6905(200006)4:2<217:AEAFDB>2.0.ZU;2-Q
Abstract
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 .