針對高頻率的設計，為了最佳化連線延遲，緩衝器和正反器安插已成為不可避免的方法。在我們所知道相關研究中，所有的研究都將緩衝器和正反器安插執行在給定的繞線樹雛型 (routing tree topology) 上。然而，一個給定的繞線樹雛型可能會大大地限制緩衝器和正反器安插的效能。在本篇論文中，我們提出一個同時考慮緩衝器、正反器安插且受限於latency限制下建構一個繞線樹的方法。我們同時也提出了四種加速的方法來幫助減少程式的執行時間。實驗結果顯示，和一個將建樹與緩衝器、正反器安插區分成二個步驟的連續方法 (sequential method)比較，此連續方法在所有的測試資料中只能達到最多56% 的成功率，但我們的方法一定能夠找到一個合理的解答。針對那些用連續方法和我們的方法都能產生出答案的測試資料，我們的方法有高達94% 的機率找到在源頭 (source) 較大的鬆弛時間 (slack)。

For high-frequency design, buffer and flip flop insertion become inevitable for interconnect delay optimization. To the best of our knowledge, all existing works perform buffer and flip flop insertion on a given routing tree topology. However, the given topology may greatly limit the effectiveness of buffer and flip flop insertion. In this thesis, we present a method which simultaneously constructs a routing tree and performs buffer and flip flop insertion subject to latency constraints. We also propose four speed-up techniques to further reduce the computation time. Experimental results show that as compared to a sequential method which separates the tree construction and buffer/flip flop insertion into 2 steps, our method can always find a feasible solution for each test case while the sequential method can do so with only up to 56% probability. For those test cases in which both the sequential method and our method can generate feasible solutions, our method has up to 94% chances to bring out solutions of larger slacks at source pins.

ABSTRAC...........I
CONTENTS..........II
LIST OF FIGURES...III
LIST OF TABLES.... IV
Chapter 1 Introduction..... 1
Chapter 2 Preliminaries.... 5
2.1 Notation...... 5
2.2 Problem Formulation.....6
Chapter 3 Algorithm........ 7
3.1 Modified Hanan Graph.. 9
3.2 Modified Escape Node.. 11
3.3 Registered Routing Tree Construction..... 14
3.3.1 Edge Growing............. 15
3.3.2 Buffer/FF Insertion...... 15
3.3.3 Merging.................. 15
3.3.4 Pruning ..................16
Chapter 4 Speed-up Techniques....... 17
4.1 Hanan Graph and Escape Node Reduction.... 17
4.2 Pre-buffer/Pre-FF Slack Pruning.......... 20
4.3 Sampling................................. 20
4.4 Clustering............................... 23
Chapter 5 Experimental Results...... 26
Chapter 6 Conclusions...... 36
REFERENCES........ 37

[1] L. P. P. P. van Ginneken, “Buffer Placement in Distributed RC-Tree Networks for Minimal Elmore Delay,” Proc. International Symposium on Circuits and Systems, pp. 865-868, 1990.
[2] C. J. Alpert, G. Gandham, M. Hrkic, J. Hu, A. Kahng, J. Lillis, B. Liu, S. Sapatnekar, A. Sullivan, and P. Villarubia, “Buffered Steiner Trees for Difficult Instances,” Proc. International Symposium on Physical Design, pp. 4-9, 2001.
[3] J. Hu, C. J. Alpert, S. T. Quay, and G. Gandham, “Buffer Insertion with Adaptive Blockage Avoidance,” Proc. International Symposium on Physical Design, pp. 92-97, 2002.
[4] T. Okamoto and J. Cong, “Buffered Steiner Tree Construction with Wire Sizing for Interconnect Layout Optimization,” Proc. International Conf. on Computer-Aided Design, pp. 44-49, 1996.
[5] J. Lillis, C. K. Cheng, and T. T. Y. Lin, “Simultaneous Routing and Buffer Insertion for High Performance Interconnect,” Proc. Great Lakes Symposium on VLSI, pp. 148-153, 1996.
[6] J. Cong, and X. Yuan, “Routing Tree Construction under Fixed Buffer Locations,” Proc. Design Automation Conf., pp. 379-384, 2000.
[7] W. Chen, M. Pedram and P. Buch, “Buffered Routing Tree Construction under Buffer Placement Blockages,” Proc. Conf. on VLSI DESIGN, pp. 381-386, 2002.
[8] P. Cocchini, “Concurrent Flip Flop and Buffer Insertion for High Performance Integrated Circuits,” Proc. International Conf. on Computer-Aided Design, pp. 268-273, 2002.
[9] Z. C. Lu and T. C. Wang, “Concurrent Flip Flop and Buffer Insertion with Adaptive Blockage Avoidance,” Proc. Asia and South Pacific Design Automation Conf., pp. 19-22, 2005.
[10] R. Lu, G. Zhong, C. K. Koh and K. Y. Chao, “Flip-Flop and Repeater Insertion for Earl Interconnect Planning,” Proc. Design Automation and Test Europe Conf., pp. 690-695, 2002.
[11] Z. Li, C. N. Sze, C. J. Alpert, J. Hu and W. Shi, “Making Fast Buffer Insertion Even Faster Via Approximation Techniques,” Proc. Asia and South Pacific Design Automation Conf., pp. 13-16, 2005.
[12] K. H. Tam and L. He, “Power Optimal Dual-Vdd Buffered Tree Considering Buffer Stations and Blockages,” Proc. Design Automation Conf., pp. 497-502, 2005.
[13] C. J. Alpert, J. Hu, S. S. Sapatnekar, and C. N. Sze, “Accurate Estimation of Global Buffer Delay within A Floorplan,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 1140-1146, 2006.