A GREEDY ALGORITHM FOR OVER-THE-CELL CHANNEL ROUTING

Recent advances in VLSI technology have made the area over cells avail able for routing: In this paper we present a new over-the-cell channel router that uses greedy heuristics to make the over-the-cell connecti ons and to define the nets needed to complete the connections inside t he channel. The router tries to reduce the channel density by moving s egments that cross maximum density columns to the over-the-cell areas, The layout model used allows only planar connections over each cell, The final stage is to use an existing channel router to route the conn ections inside the channel. An important characteristic of the new rou ter is that there is interaction between the decisions made for the ov er-the-cell connections and the connections needed inside the channel. It performs significantly better than previous over-the-cell routers.