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

《Full Text》