隨著類比積體電路佈局的複雜度提高，設計者必頇花費更多時間在處理繞線（routing）問題，其中一項重要的課題即是導線電流密度的限制。因為設計者疏失或是電路平面上障礙物之間的通道寬度限制而導致電路導線過細，使得導線上的電流密度過高，而造成電子遷移（electromigration）現象，進而產生開路或短路的情況，使電路產生永久性的損毀。但是如果恣意地放大導線寬度以降低電流密度，又會導致導線面積過大、佔用過多的繞線資源。 目前的相關研究多著重在無障礙物的情況下，避免導線電子遷移現象並達到導線面積最佳化的目的。但是對於電路平面存在障礙物，或是障礙物之間存在通道寬度限制的情況，卻尚未有合適的處理技術。 本論文提出一個考量電子遷移現象以及障礙物之間通道寬度限制的類比積體電路繞線自動化技術。首先，根據起始節點、目標節點以及障礙物建立一個修正的生成圖（modified spanning graph）。接著，利用此生成圖快速找到每對起始節點與目標節點的最短路徑。針對最短路徑，我們提出一個路經編碼方式以便快速找出通道寬度限制的區域。再來，找出每對起始節點與目標節點的備用路徑，此路徑會用來避免繞線經過最壅擠的通道寬度限制區域。最後，利用線性規劃（linear programming）分配每對起始節點與目標節點的繞線路徑及決定其導線寬度以找出符合通道寬度限制且導線面積最小的繞線結果。 As the complexity of the layout of analog ICs increases, designers must spend more effort in dealing with the routing problem. A main issue is the constraint of wire current density. Because the negligence of circuit designers or the channel width constraints between obstacles lead to the width of a wire too small, making the current density of the wire is too high. This condition causes electromigration phenomenon and a permanent failure (e.g., open- or short-circuit defect). However, widening wire widths arbitrarily to reduce the current density leads to larger wire area and routing resource. Related researches focus on avoiding the electromigration phenomenon and the wire area optimization without considering obstacles. However, there does not exist suitable methods to handle obstacles and the channel width constraints between obstacles in circuits. This thesis proposes a routing automation technology for analog integrated circuits with considering obstacles and the channel width constraints between obstacles. First, a modified spanning graph is constructed according to sources, targets, and obstacles. The modified spanning graph is used to find a shortest path for each pair of a source and a target. For the shortest path, we propose an edge encoding method to detect rapidly the channel width constraints between obstacles. Then, a reserved path is found for each pair of a source and a target. The reserved path is a shortest path with avoiding pass the most congested region. Finally, linear programming is used to distribute the flow for each path to find the routing result. The routing result is satisfied the channel width constraints between obstacles with minimum wire area.
