線段移動及鏡相繞線技術應用於全域繞線器

Abstract

在實體化設計中，全域繞線扮演著相當重要的角色。它可以幫助詳細繞線器能夠快速地定位出可用的繞線路徑出來。在傳統的全域繞線流程裡，迷宮式繞線法是一個找尋繞線路徑的方法。迷宮式繞線法保證能夠找出一條花費最小的路徑。但是其主要的缺點就是需要相當龐大的執行時間。因此新近的全域繞線研究常藉著發展新的繞線技術，以期能對繞線的品質及速度有顯著地改善。 在本篇論文中，我們基於擁擠度驅動繞線器的流程，提出了兩個延伸加強的方法 : 線段移動方法的精煉，以及鏡相單調繞線方法。線段移動方法是在FastRoute裡提出的一個減少氾濫數量的方法。我們藉由放鬆選擇可移動線段的限制來增進原始的線段移動方法。另外鏡相單調繞線可以提供某些模式來取代一定程度的迷宮式繞線方法。實驗結果顯示，這些加強方法能夠有效地減少迷宮式繞線階段前的氾濫數量，同時整體執行時間也跟著降低了。