具有可移動端點的三層VLSI通道佈線
No Thumbnail Available
Date
1991-06-01
Authors
張國恩
Chang, Kuo-En
Journal Title
Journal ISSN
Volume Title
Publisher
國立台灣師範大學
Abstract
本文提出在VLSI晶片上的通道佈線問題，此問題是假定通道上的端點是可被移動的。其中有兩個子問題被考慮，即是最大調齊問題與軌道指定問題。所謂最大調齊問題是重新指定各端點在通道上的位置使得能直拉的佈線能儘量多。而軌道指定問題是將所有的網列連線實際地連接在通道中。本文分別針對此兩子問題各提出啟發式的演算法解之。並以著名的實例測出這些演算法的效益。實驗結果知具有移動端點的通道佈線能夠很可觀地減少通道寬度與穿孔數。
Abstract-A problem of wiring a channel of movable terminals in a VLSI chip is presented. Two subproblems are addressed, namely, maximum alignment and track assignment. Maximum alignment is to reassign terminal positions in the channel in order to maximize the number of nets that can be implemented as straight connections. Track assignment locates physicallythe interconnection of every net to the horizontal track in the channel. The two subproblemsare solved using two heuristic algorithms. Some well-known examples, including Deutsch's difficult example, are used as test cases to study our algorithms. The results show that both channel width and via usage are reduced significantly by using our procedures when comparing tothe routing with fixed terminals.
Abstract-A problem of wiring a channel of movable terminals in a VLSI chip is presented. Two subproblems are addressed, namely, maximum alignment and track assignment. Maximum alignment is to reassign terminal positions in the channel in order to maximize the number of nets that can be implemented as straight connections. Track assignment locates physicallythe interconnection of every net to the horizontal track in the channel. The two subproblemsare solved using two heuristic algorithms. Some well-known examples, including Deutsch's difficult example, are used as test cases to study our algorithms. The results show that both channel width and via usage are reduced significantly by using our procedures when comparing tothe routing with fixed terminals.