EFFICIENT ALGORITHMS FOR WIRING CHANNELS WITH MOVABLE TERMINALS

A problem of wiring a channel of movable terminals in a VLSI chip is p resented. Two subproblems are addressed: maximum alignment and wireabl e placement. Maximum alignment is to reassign terminal positions in th e channel in order to maximize the number of nets that can be implemen ted as straight connections. Wireable placement is to find an assignme nt of the movable terminals to the vertical tracks in the channel. The assignment must eliminate the vertical conflicts between nets. We imp ose a restriction on the number of unconnected terminals in the maximu m alignment problem. The restriction ensures that the number of column s in the channel is not increased in the process. This restriction is not addressed in previous works which considered the maximum alignment problem. The two subproblems are solved using two heuristic algorithm s. Some well-known examples, including Deutsch's difficult example, ar e used as test cases to study our algorithms. The results show that bo th channel width and via usage are reduced significantly by using our procedures.