Buffer Insertion with Adaptive Blockage Aoidance自适应阻塞避免缓冲器插入.pptVIP

Jiang Hu, et al., IBM Buffer Insertion with Adaptive Blockage Avoidance J. Hu C. J. Alpert S. T. Quay G. Gandham IBM Corporation Buffer Insertion Improve timing Drive long wire Shield load from critical path Van Ginneken’s Algorithm Given tree topology fixed Find optimal solution at fast speed Buffer Blockage Path vs. Branch Node Previous Work on 2-pin Nets Dynamic programming Zhou, et al., DAC 99 Graph based algorithm Jagannathan, et al., DAC 00 Lai and Wong, DAC 00 Minimum delay buffered path is found in polynomial time Previous Work on Multi-pin Nets RMP (Recursively Merging and Pruning), simultaneous tree construction and buffer insertion, Cong and Yuan, DAC 00 For buffer block planning Limited buffer sites, small nets High quality solution High complexity Tang, et al., ICCAD 01 Faster, Optimize delay Other Simultaneous Approaches Lillis, et al., GLSV 96 Integrate P-Tree with van Ginneken’s algorithms Salek, et al., DAC 98, 99 Combine P-Tree with fanout optimization Search solution over the entire Extended Hanan Grid Design Request Medium size modern chip design RMP run for at least one week Tree + van Ginneken’s algorithm run for 1-2 hours Simultaneous approach: Good at optimizing a few critical nets, or small nets Cannot afford for many medium/large nets Any Fast Approach? Sequential approach, TCAD 4/01 Steiner tree + make wires to avoid blockages + buffer insertion Fast Wire detour may be unnecessary, timing may become poor Challenge Good solution quality Fast speed Close to van Ginneken’s algorithm Handle large nets and large number of blockages Our Strategy Any technique somewhere between simultaneous and sequential methods? Construct Steiner tree as a guide Refine buffer solution search to limited region Allow flexibility to adjust tree topology Extend van Ginneken’s algorithm to incorporate tree adjustment with buffer insertion RIATA Algorithm Repeater Insertion with Adaptive Tree Adjustment Almost same as van Ginneken’s algorithm Ext