3-LAYER ROUTER FOR CHANNELS WITH CONSTRAINED TERMINALS

With recent advances in vertical-integration technology, it is now rea sonable to consider a three-dimensional IC structure containing either partially or completely stacked active layers. Thus it is possible to have stacked terminals at the channel edges. In this case, each termi nal is constrained to a specific layer and therefore may only enter th e channel on the layer to which it is constrained. For a channel of le ngth lambda using n layers for routing, it is now possible to have 2nl ambda terminals on the edges of the channel. A new channel-routing alg orithm is presented for routing channels consisting of stacked and con strained terminals. The algorithm employs greedy heuristics, routing t he channel column by column from left to right. The router guarantees a solution, although one or more extra columns off the end of the chan nel may be required. The heuristics of the router can be easily modifi ed to rearrange priorities or to add new requirements or constraints. The algorithm has been tested extensively using randomly-generated cha nnel descriptions. Very good solutions were obtained in a short amount of CPU time.