教師著作

Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/31276

Browse

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    晶元上佈線問題之演算法設計
    (1993-08-01) 張國恩
    本報告提出一個線性時間之演算法以解決過晶元佈線之問題。該演算法嘗試將一些佈線配置到晶元上以儘可能地減少最大通道密度。方法中首先定義了通道表示的新方式,並依此而導出一個稱為「交叉圖」的模式,然後按照此模式定義出問題之數學型態。在此型態中此交叉圖之獨立集代表了可以佈線在晶元上之連線集合。文中所提出的啟發式演算法就是要找出交叉圖之獨立集。文中方法也被實際設計,並經實測評估後得到一些結果。這些結果和以前之研究結果比較顯示我們的方法除了可有效減少通道密度外,執行速度也較快。以Deutsch's difficult example為例,文中之方法僅需花費約5.6秒,此對以前之方法而言其平均花費時間為29.25秒。