同時考慮緩衝器、正反器安插與具障礙物考量之繞線樹合成

Blockage-Aware Routing Tree Construction with Buffer and Flip Flop Insertion

陳淑雲(Shu-Yun Chen)

指導教授 ： 王廷基

國立清華大學/電機資訊學院/資訊工程學系/碩士(2006年)

摘要

針對高頻率的設計，為了最佳化連線延遲，緩衝器和正反器安插已成為不可避免的方法。在我們所知道相關研究中，所有的研究都將緩衝器和正反器安插執行在給定的繞線樹雛型 (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.

並列關鍵字

buffer ； flip flop ； routing tree construction

參考文獻

[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.

[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.