A Greedy Algorithm for Over-The-Cell Channel Routing

Recent advances in VLSI technology have made the area over cells available for routing. Inthis paper we present a new over-the-cell channel router that uses greedy heuristics to makethe over-the-cell connections and to define the nets needed to complete the connectionsinside the channel. The router tries to reduce the channel density by moving segments thatcross maximum density columns to the over-the-cell areas. The layout model used allowsonly planar connections over each cell. The final stage is to use an existing channel router toroute the connections inside the channel. An important characteristic of the new router is thatthere is interaction between the decisions made for the over-the-cell connections and theconnections needed inside the channel. It performs significantly better than previous over the-cell routers