| Provably Good Global Buffering by Generalized Multiterminal Multicommodity Flow Approximation (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract—To implement high-performance global interconnect without impacting the placement and per-formance of existing blocks, the use of buffer blocks is becoming increasingly popular in structured-custom and block-based ASIC methodologies. Recent works by Cong, Kong, and Pan [5] and Tang and Wong [21] give algorithms to solve the buffer block planning problem. In this paper, we address the problem of how to perform buffering of global multiterminal nets given an existing buffer block plan. We give provably good and heuristic algorithms for this problem based on a recent approach of Garg and Könemann [9] and Fleischer [8] (see also Albrecht [1]). Our method routes connections using available buffer blocks, such that required upper and lower bounds on buffer intervals are satisfied. In addition, our algorithms allow more than one buffer to be inserted into any given connection and observe upper bounds and parity constraints on the number of buffers per connection. Most importantly, and unlike previous works on the problem [5], [21], we take into account (i) multiterminal nets, (ii) multiple routing layers, (iii) simultaneous buffered routing and compaction, and (iv) buffer libraries. Our method outperforms existing algorithms for the problem [5], which are based on 2-pin decompositions of the nets, and has been validated on top-level layouts extracted from a recent high-end | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||