空間利用率及電磁干擾考量的電路線軌指派演算法

Abstract

隨著超大型積體電路製程技術邁入奈米時代，使得電子裝置的大小及線路的寬度都隨之縮小，而且在相同層中，線路間的距離也變得越來越近。同時，晶片設計的執行脈衝頻率也往上增加到十億赫茲甚至超過十億赫茲，如此在半導體製程技術及設計上的不斷進步導致很嚴重的電阻電感電容干擾現象 ( 在兩相鄰且相互干擾的線路中容易造成訊號的錯誤、前後不一致 )。因此在高速超大型積體電路的設計中，想辦法避免或滿足電磁干擾效應的重要性也隨之提升。然而，在傳統的兩階段繞線 ( 全域繞線和精細繞線 ) 流程中，要解決這樣的問題會使得整個流程變得複雜且沒有效率。因為在全域繞線中，沒有電路線軌的資訊，所以很難去考量電磁干擾現象;而在精細繞線這原本就十分耗時的階段去考量此問題，只會增加它大量的計算，使它的負擔變的更重。因為這些原因，有人便提出了在全域繞線及精細繞線中併入一個中間的步驟，稱之為電路線軌指派。 先前著作有人用區域為主的方式在電路線軌指派時考慮電磁干擾效應，而區域為主的電路線軌指派它的線軌利用率較差，導致在固定大小的指派區域中比較無法完成所有線路的指派。我們在此篇著作提出兩個在點格式為主的系統下，同時考量線軌利用率跟電磁干擾的電路線軌指派演算法 : 混合型區域為主電路線軌指派以及交換為主的電路線軌指派。此外，還提出一個應用於非點格式系統的電路線軌指派演算法。混合型區域為主電路線軌指派演算法首先將高度影響性的線路指派到奇數的電路線軌上，若奇數的電路線軌都擺完了，再使用區域為主的方法將其餘的線路指派到偶數的電路線軌; 交換為主的電路線軌指派則是先產生一個初始的電路線軌指派，再依據可容忍的電磁干擾效應限制，將電路分成關鍵型線路以及非關鍵型線路 (超過可容忍的電磁干擾效應限制稱為關鍵型線路，反之則稱為非關鍵型線路)，最後透過交換的方式在所有電路皆滿足電磁干擾效應限制的前提下，減少整體的電磁干擾效應; 非點格式系統的電路線軌指派演算法，是一種混合型區域為主電路線軌指派演算法的變化，應用於非點格式系統上。實驗數據顯示，混合型區域為主電路線軌指派能比先前著作減少42.6%的電磁干擾效應，而交換為主的電路線軌指派則有46.8%的改善。除此之外，此兩個演算法均如預期的一樣，指派失敗的線路比先前著作要少。至於非點格式系統的電路線軌指派演算法，能確切的將不同線寬的電路指派到非點格式系統中，並且也考量了電磁干擾的效應，算是電路線軌指派在非點格式系統的一項創舉。

As the VLSI manufacturing technology advances to the Very Deep Submicron (VDSM) era, the device feature size shrinks and the minimum separation between two wires of the same layer is getting closer. Meanwhile, the operating clock rate of IC design is increasingly towards and above gigahertz. Such continuous progresses in semiconductor and design technologies bring serious RLC crosstalk that could easily introduce an inconsistent signal change between two adjacent and mutually interfering wires. Accordingly, avoiding crosstalk or satisfying crosstalk constraints for high-speed VLSI design is of growing importance. However, it is complicated and inefficient to solve the problem in conventional two-stage flow ( global routing and detailed routing ). The difficulty of minimizing crosstalk during global routing is that nets have no track information at this stage, while the difficulty for detailed routing is to increase the computation load on an already time-consuming task. Therefore, the TA, an intermediate stage between global routing and detailed routing, is incorporated with the routing flow. Previous works of track assignment (TA) are the zone-based approaches. Zone-based TA may produce worse track utilization such that the assignment of all nets to the fixed-sized panel can not be completed. This work depicts two utilization- and crosstalk-driven TA algorithms: hybrid zone-based TA (HZTA) and switching-based TA (SBTA). HZTA places the highly impacted nets on the odd tracks first, and then apply the zone-based approach to complete the assignment of even tracks. SBTA first produces a utilization-driven TA, and then, divides the nets into critical nets and non-critical nets, where a critical net is the net whose coupling effect exceeds the coupling budget. It reduces the crosstalk by switching nets under the crosstalk budget satisfaction. Gridless TA is an application of HZTA. It not only can assign the variable nets exactly on a gridless environment, but also considers the coupling effect. The experiment results display that HZTA can reduce more coupling effects than previous work by 42.6%, while SBTA algorithm can perform better crosstalk reduction by 46.8%. Besides, as expected, both HZTA and SBTA have fewer failed nets than previous work. Otherwise, Gridless TA is the first work about TA in gridless environment.