Abstract
在這篇論文中，我們對超大型積體電路 (VLSI) 的標準元件 (standard cell) 佈局方式 (layout style) 提出一個新的繞線方法 (routing method)。 跟傳統繞線方法 --- 把整個電路分為整體繞線 (global routing) 和細部繞線 (detailed routing) 不同的是﹕ 我們的作法不區 分成整體繞線和細部繞線、 而且我們同時處理所有的通道以讓所有的 nets 能均勻地分佈在各個繞線通道 (routing channels)，並減少整體繞 線的軌道 (number of total tracks)。如以往的 Greedy channel router 作法一樣，我們一次處理一行 (column by column)； Nets 可以 透過 feedthroughs 上下迂迴地存在鄰近的各通道，以善加利用各通道間 的空軌 (vacant tracks)。我們的併行繞線演算法包括了幾個步驟：首先 利用最小展開樹 (minimum spanning tree) 把所有多端點 net 分解成數 個二端點的 subnets。根據這些 subnets，先計算各個通道的密度 (channel 再決定出各通道的初始高度 (initial channel width)。我們 修改 Greedy channel router 的繞線規則，加上我們發展的繞線規則， 針對所有的 subnets，由左而右，一次一行，同時完成所有通道的繞線 ； 並于繞線同時，衡量目前繞線狀況，適當地加入 feedthrough cells 。我們測試了數個標準測試電路 (benchmark)，並和標準元件佈局之商用 軟體 SYMBAD/SBBS 比較，我們在軌數方面節省了40%，在整體的面積減少 也有著 15% 的進展，整體繞線長度也因而降低。本文共分五章：第一章 概論，介紹繞線問題及我們的動機；第二章相關研究；第三章提出我們的 多通道併行繞線系統；第四章實驗結果，分別和 SYMBAD/SBBS 及 TimberWolfSC6.0 比較；第五章結論及未來研究方向。 In this thesis, we propose a new routing method for row-based (e.g., standard-cell) VLSI layout designs. Unlike conventional approaches, which perform a global routing before routing each channel separately, our approach routes all channels concurrently. It proceeds column by column like a greedy router does. Nets are allowed to swing, via feedthroughs, back and forth between adjacent channels taking advantage of vacant wiring space in multiple channels. That is, as the routing proceeds from left to right (or right to left), nets tend to go to less-congested channels. A software system, called the Concurrent Router has been implemented. We have tested the Concurrent Router on some benchmark circuits from MCNC. Compared with SBBS, a standard cell placement-and-routing tool from Cadence, the Concurrent Router needs significantly (up to 40%) less number of tracks. In terms of layout area, we were able to achieve a saving of 15%.