具有可移動端點的三層VLSI通道佈線
作者:張國恩(國立臺灣師範大學資訊教育學系所)
摘要：
本文提出在VLSI晶片上的通道佈線問題，此問題是假定通道上的端點是可被移動的。其中有兩個子問題被考慮，即是最大調齊問題與軌道指定問題。所謂最大調 齊問題是重新指定各端點在通道上的位置使得能直拉的佈線能儘量多。而軌道指定問題是將所有的網列連線實際地連接在通道中。本文分別針對此兩子問題各提出啟發式的演算法解之。並以著名的實例測出這些演算法的效益。實驗結果知具有移動端點的通道佈線能夠很可觀地減少通道寬度與穿孔數。
《詳全文》
Journal directory listing - Volume 31-41 (1986-1996) - Volume 36 (1991)
Three-Layer Vlsi Channel Routing with Movable Terminals
Author: Kuo-En Chang(Department of Information and Computer Education, National Taiwan Normal University)
Abstract：
Abstract--A problem of wiring a channel of movable terminals in a VLSI chip is present-ed. Two subproblems are addressed, namely, maximum alignment and track assignment. Maxi-mum alignment is to reassign terminal positions in the channel in order to maximize the num-ber of nets that can be implemented as straight connections. Track assignment locates physically the interconnection of every net to the horizontal track in the channel. The two subproblems are solved using two heuristic algorithms. Some well-known examples, including Deutsch's diffi-cult example, are used as test cases to study our algorithms. The results show that both chan-nel width and via usage are reduced significantly by using our procedures when comparing to the routing with fixed terminals.
Keywords：Maximum alignment, comparability graph, maximum clique, NP-complete problem, track assignment, and bipartite graph