Porosity Aware Buffered Steiner Tree Constrction孔隙度感知的缓冲Steiner树构造.pptVIP

Porosity Aware Buffered Steiner Tree Construction C. Alpert G. Gandham S. Quay IBM Corp Outline Introduction and Previous work Problem formulation Algorithm Experimental results Conclusion 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 If There Are Big Blockages Previous Works Simultaneous tree construction and buffer insertion Buffer blockage driven Recursively Merging and Embedding [Cong and Yuan, DAC 00] Graph-based[Tang, et al., ICCAD 01] General purpose SP-Tree [Hrkic and Lillis, ISPD 02] Excellent solution quality High complexity Sequential tree construction + buffer insertion Adaptive blockage avoidance [Hu, et al., ISPD 02] Very good solution quality Practical computation speed If There Are Many Small Blockages Porosity Has to Be Considered Handling small blockages will slow down computation Buffers in dense region may be spiraled away No previous work handles porosity directly Express Porosity through Tile Graph For a tile g A(g): tile area a(g): usage area d(g) = a(g)/A(g) Porosity cost is d2(g), if a buffer is placed in g Problem Formulation Porosity-aware Buffered Steiner Tree Problem: Given A net N = {v0, v1, …, vn} Load capacitance c(vi) and required arrival time q(vi) Tile graph G(VG, EG) Construct a Steiner tree T(V,E), such that Required arrival time q(vi) are satisfied Total porosity cost is minimized Observation Easy to deal with node-to-node path Congestion can be avoided by rerouting without affecting timing Hard to deal with Steiner nodes Moving Steiner nodes may degrade timing Basic Strategy Construct a timing driven Steiner tree regardless porosity Adjust Steiner nodes simultaneously with length-based buffer insertion Adjustment range need to be restrained A Steiner node is moved only when buffer is needed there Length-based Buffer Insertion Simple buffering following rule of thumb Capacitance load of driver/buff