Buffer assignment algorithms on data driven ASICs

M. Chatterjee

doi:10.1109/12.822561

2000-01-01

PRE

M. Chatterjee *

Serene Banerjee

Dhiraj K. Pradhan

DOI：10.1109/12.822561

原文链接

原文求助

摘要

En 中文

Data driven architectures have significant potential in the design of high performance ASICs. By exploiting the inherent parallelism in the application, these architectures can maximize pipelining. The key consideration involved with the design of a data driven ASIC is ensuring that throughput is maximized while a relatively low area is maintained. Optimal throughput can be realized by ensuring that all operands arrive simultaneously at their corresponding operator node, if this condition is achieved, the underlying data flow graph is said to be balanced. If the initial data flow graph is unbalanced, buffers must be inserted td prevent the clogging of the pipeline along the shorter paths. A novel algorithm for the assignment of buffers in a data flow graph is proposed. The method can also be applied to achieve wave-pipelining in digital systems under certain restrictions. The algorithm uses a new application of the retiming technique; the number of buffers here is shown to be equal to the minimum number of buffers achieved by integer programming techniques. We also discuss an extension of this algorithm which can further reduce the number of buffers by altering the DFO without affecting functionality or performance. The time complexities of the proposed algorithms are O(V x E) and O(V-2 x logV), respectively, a considerable improvement over the existing strategies. Also proposed is a novel buffer distribution algorithm that exploits a unique feature of data driven operation. This procedure maximizes throughput by inserting substantially fewer buffers than other techniques. Experimental results show that the proposed algorithms outperform the existing methods.

Keyword:

application specific integrated circuits

data driven architecture

data flow graph

throughput

buffers

wave-pipelining