Buffer assignment algorithms on data driven ASICs

Data driven architectures have significant potential in the design of high performance ASICs. By exploiting the inherent parallelism in the applicatio n, these architectures can maximize pipelining. The key consideration invol ved with the design of a data driven ASIC is ensuring that throughput is ma ximized while a relatively low area is maintained. Optimal throughput can b e realized by ensuring that all operands arrive simultaneously at their cor responding operator node, if this condition is achieved, the underlying dat a flow graph is said to be balanced. If the initial data flow graph is unba lanced, buffers must be inserted td prevent the clogging of the pipeline al ong 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 wav e-pipelining in digital systems under certain restrictions. The algorithm u ses 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 whic h can further reduce the number of buffers by altering the DFO without affe cting functionality or performance. The time complexities of the proposed a lgorithms are O(V x E) and O(V-2 x logV), respectively, a considerable impr ovement over the existing strategies. Also proposed is a novel buffer distr ibution algorithm that exploits a unique feature of data driven operation. This procedure maximizes throughput by inserting substantially fewer buffer s than other techniques. Experimental results show that the proposed algori thms outperform the existing methods.