臺灣博碩士論文加值系統

近來，由於導線延遲己凌駕於電晶體延遲的緣故，致使許多效能導向的繞線及插入緩衝器的演算法，相繼被提出，以降低導線的延遲。在我們的論文當中，我們提出了兩種有效率的方法，可以快速建構出效能導向的繞線及插入緩衝器，並考慮避開障礙物的限制。
第一個演算法，我們修改了[8]中使用的降溫演算法，以階層的方式建構繞線，並同時考量插入緩衝器的效應。第二個演算法，我們採用兩級最佳化的方式，來達成繞線和插入緩衝器的任務，首先建構出效能導向的繞線之後，再插入緩衝器，以降低導線的延遲效應。
最後，我們所提出的兩個方法，與過去所提出的演算法相比，能夠得到更好的效能，且所需要的運算時間大幅減少。

In recent years, many algorithms for buffered interconnect tree construction were proposed to minimize interconnect delay due to the interconnect delay becomes more critical than transistor delay. In this thesis, we proposed two efficient algorithms to construct buffered interconnect tree with blockages. Our first algorithm modifies the simulated annealing algorithm [8] to hierarchically construct buffered interconnect tree considering buffer insertion simultaneously. Our second algorithm adopts two-stage optimization techniques to construct buffered interconnect tree. First to construct a performance-driven routing and then insert buffers for it to minimize the interconnect delay. We will show our algorithms could obtain better performance and more efficient than pervious algorithms.

1 Introduction 1
1.1 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Techniques For Timing Optimization in Interconnect Tree Con-
struction 4
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Performance-Driven Interconnect Tree Synthesis . . . . . . . . . . . . 6
2.2.1 Geometric Approaches to Delay Minimization . . . . . . . . . 6
2.3 Van Ginneken's Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Buffered Interconnect Tree Construction with Simultaneous Topol-
ogy Generation and Buffer Insertion 12
3.1 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Simulated Annealing Method For Buffered Tree Construction . . . . . 14
3.2.1 Decomposition of Routing Tree . . . . . . . . . . . . . . . . . 15
3.2.2 Component Construction . . . . . . . . . . . . . . . . . . . . . 16
3.2.3 Routing Tree Perturbation . . . . . . . . . . . . . . . . . . . . 17
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 Buffered Interconnect Tree Construction via Two-Stage Optimiza-
tion 20
4.1 Performance-Driven Tree Construction . . . . . . . . . . . . . . . . . 20
4.1.1 Routing Grid Graph . . . . . . . . . . . . . . . . . . . . . . . 20
4.1.2 Iterated Dominance Algorithm (IDOM) [1] . . . . . . . . . . . 21
4.2 Buffer Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.1 Efficient Buffer Insertion . . . . . . . . . . . . . . . . . . . . . 23
4.2.2 Buffered Tree Transformation . . . . . . . . . . . . . . . . . . 25
4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5 Experimental Results 30
6 Conclusion and Future Work 34
Bibliography 36

[1] M. J. Alexander and G. Robins. "New Performance-driven FPGA Routing
Algorithms". IEEE Transactions on Computer-Aided Design of Integrated Cir-
cuits and Systems, 15(12):1505-1517, Dec. 1996.
[2] C. J. Alpert, A. Devgan, and S.T. Quay. "Buffer Insertion with Adaptive Block-
age Avoidance". IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, 18(11):1633-1645, Nov. 1999.
[3] C. J. Alpert, G. Gandham, M. Hrkic, J. Hu, A. B. Kahng, B. Liu J. Lillis, S. T.
Quay, S. S. Sapatnekar, and A. J. Sullivan. "Buffered Steiner Trees for Difficult
Instances". In Proceedings International Symposium on Physical Design, pages
4-9, 2001.
[4] C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, and D. Karger. "Prim-
Dijkstra Tradeoffs for Improved Performance-driven Routing Tree Design".
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Sys-
tems, 14(7):890-896, July 1995.
[5] J. P. Cohoon and L. J. Randall. "Critical Net Routing". In Proceedings IEEE
International Conference on Computer Design, pages 174-177, 1991.
[6] J. Cong. Challenges and Opportunities for Design Innovations in Nanometer
Technologies". In Semiconductor Research Corporation Design Sciences Con-
cept Paper, pages 1-15, 1998.
[7] J. Cong, A. B. Kahng, and K.-S. Leung. "Efficient Algorithms for The Mini-
mum Shortest Path Steiner Arborescence Problem with Applications to VLSI
Physical Designs". IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, 17(1):24-39, Jan. 1998.
[8] J. Cong and X. Yuan. "Routing Tree Construction Under Fixed Buffer Lo-
cations". In Proceedings IEEE/ACM Design Automation Conference, pages
379-384, 2000.
[9] S. Dechu, C. Shen, and C. Chu. "An Efficient Routing Tree Construction Algo-
rithm with Buffer Insertion, Wire Sizing and Obstacle Considerations". IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems,
24(4):600-608, April 2005.
[10] M. Hrkic and J. Lillis. "S-Tree: A Technique for Buffered Routing Tree Syn-
thesis". In Proceedings IEEE/ACM Design Automation Conference, pages 578-
583, 2002.
[11] M. Hrkic and J. Lillis. "Buffer Tree Synthesis with Consideration of Tempo-
ral Locality, Sink Polarity Reuirements, Solution Cost and Blockages". IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems,
22(4):481-491, April 2003.
[12] F. K. Hwang, D. S. Richards, and P. Winter. "The Steiner Tree Problem".
North-Holland Publisher, 1992.
[13] S. S. Sapatnekar J. Hu. "Algorithms for Non-Hanan-Based Optimization for
VLSI Interconnect under a Higher-Order AWE Model". IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems, 49(4):446-458,
April 2000.
[14] M.-H. Lai and D.F. Wong. "Maze Routing with Buffer Insertion and Wiresiz-
ing". IEEE Transactions on Computer-Aided Design of Integrated Circuits and
Systems, 21(10):1205-1209, Oct. 2002.
[15] J. Lillis, C.-K. Cheng, and T.-T. Lin. "Optimal Wire Sizing and BuRer In-
sertion for Low Power and a Generalized Delay Model". IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems, 31(3):437-447,
March 1996.
[16] J. Lillis, C.-K. Cheng, T.-T Lin, and C.-Y. Ho. "New Performance Driven
Routing Techniques with Explicit Area/Delay Tradeoff and Simultaneous Wire
Sizing". In Proceedings IEEE/ACM Design Automation Conference, pages 395-
400, 1996.
[17] T. Okamoto and J. Cong. "Buffered Steiner Tree Construction with Wire
Sizing for Interconnect Layout Optimization". In Proceedings IEEE/ACM In-
ternational Conference on Computer-Aided Design, pages 44-49, 1996.
[18] R. R. Rao, D. Blaauw, D. Sylvester, C. J. Alpert, and S. Nassif. "An Effi-
cient Surface-Based Low-Power Buffer Insertion Algorithm". In Proceedings
International Symposium on Physical Design, pages 86-93, 2005.
[19] X. Tang, R. Tian, H. Xiang, and D. F. Wong. "A New Algorithm for Routing
Tree Construction with Buffer Insertion and Wire Sizing under Obstacle Con-
straints". In Proceedings IEEE/ACM International Conference on Computer-
Aided Design, pages 49-56, 2001.
[20] L. P. P. P. van Ginneken. "Buffer Placement in Distributed RC-tree Network
for Minimal Elmore Delay". In Proceedings Internationl Symposium on Circuits
and Systems, pages 865-868, 1990.
38
[21] H. Zhou, D.F. Wong, I.-M. Liu, and A. Aziz. "Simultaneous Routing and
Buffer Insertion with Restrictions on Buffer Locations". IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems, 19(7):819-824,
July 2000.