An Efficient Algorithm for Delay Buffer Minimization

Guoliang Xue (), Shangzhi Sun (), David H.C. Du () and Lojun Shi
Additional contact information
Guoliang Xue: The University of Vermont
Shangzhi Sun: Synplicity Inc.
David H.C. Du: University of Minnesota
Lojun Shi: Jiao Wu Chu, Yantai Jiaoyu Xueyuan

Journal of Combinatorial Optimization, 2000, vol. 4, issue 2, No 5, 217-233

Abstract: Abstract 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.

Keywords: VLSI technology; data flow machine; optimal delay buffer insertion (search for similar items in EconPapers)
Date: 2000
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009850721462 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:4:y:2000:i:2:d:10.1023_a:1009850721462

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009850721462

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().