CHANNEL ROUTING FOR RECTILINEAR AND OCTILINEAR ROUTING MODELS

Abstract

Over the last two decades, circuit complexity has increased tremendously while the size of each circuit component have reciprocally decreased. Automated design of very large scale integrated (VLSI) circuits becomes increasingly important to reduce design cost, design time and design errors. In this thesis, we study a particular phase of the physical design of integrated circuits, namely that of channel routing. Two different routing models were studied, namely the rectilinear routing model and the octilinear routing model. The traditional rectilinear routing model allows rectilinear wires for routing. For this model, we developed a new lower bound for the area required to completely route a rectilinear channel routing problem. Our bound is tighter than previously known bounds. We also developed an effective branch and bound algorithm to compute this bound. This algorithm is fast in practice. For the same routing model, we also developed a channel router that uses the divide and conquer paradigm. We showed how to derive new, smaller channel routing problems from the original problem and how to merge routing solutions together. Our results are comparable to other channel routers. As fabrication technology becomes more sophisticated, new routing models have been studied to take advantages of such flexibilities. We studied the channel routing problem under the octilinear routing model which allows for diagonal wires in addition to those already used in the rectilinear routing model. Our algorithm performs very well, and improves on many existing results. This can lead to substantial savings in wiring area.