晶元上佈線問題之演算法設計
No Thumbnail Available
Date
1993-08-01
Authors
張國恩
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
本報告提出一個線性時間之演算法以解決過晶元佈線之問題。該演算法嘗試將一些佈線配置到晶元上以儘可能地減少最大通道密度。方法中首先定義了通道表示的新方式,並依此而導出一個稱為「交叉圖」的模式,然後按照此模式定義出問題之數學型態。在此型態中此交叉圖之獨立集代表了可以佈線在晶元上之連線集合。文中所提出的啟發式演算法就是要找出交叉圖之獨立集。文中方法也被實際設計,並經實測評估後得到一些結果。這些結果和以前之研究結果比較顯示我們的方法除了可有效減少通道密度外,執行速度也較快。以Deutsch's difficult example為例,文中之方法僅需花費約5.6秒,此對以前之方法而言其平均花費時間為29.25秒。
A linear time algorithm for the problem of routing over the cells is presented. The algorithm tries to reduce significantly maximum channel density by routing some connections over the cells. The algorithm first defines a new scheme of channel representation and formulates the problem based on an intersection graph derived from the new scheme. Then, a feasible independent set of the intersection graph is found for efficiently routing some subnets over the cells. The algorithm is implemented and evaluated with several well known benchmarks. In comparison with previous research, our results are satisfactory, and the algorithm takes substantially less CPU time than those of previous work. For Deutsch's difficult example, the previous algorithms take about 29.25 seconds on an average but our new algorithm needs only 5.6 seconds.
A linear time algorithm for the problem of routing over the cells is presented. The algorithm tries to reduce significantly maximum channel density by routing some connections over the cells. The algorithm first defines a new scheme of channel representation and formulates the problem based on an intersection graph derived from the new scheme. Then, a feasible independent set of the intersection graph is found for efficiently routing some subnets over the cells. The algorithm is implemented and evaluated with several well known benchmarks. In comparison with previous research, our results are satisfactory, and the algorithm takes substantially less CPU time than those of previous work. For Deutsch's difficult example, the previous algorithms take about 29.25 seconds on an average but our new algorithm needs only 5.6 seconds.