CHAPTER LIST

23.1 INTRODUCTION

Global routing is an important step in the physical design process. Because of the complexity of the overall routing problem, it is typically solved in two steps: global routing and detailed routing. During global routing, nets are routed on a coarse-grain grid structure with the objective of determining the regions within which each net will be routed. After an approximate routing solution is determined for each net, the second step is to perform detailed routing to find the exact routes of all nets. Because detailed routing is performed based on the global routes, the quality of the final interconnects depends largely on the quality of the global routing solutions.

Typically, detailed routing grids are much larger than the coarse-grain grids of global routing, and the solution space for individual nets is much larger because of the fine-grain modeling of routing resources. On the other hand, the resource model used in global routing is simplified, and the complexity of global routing one net is typically much smaller than the corresponding complexity of detailed routing. Hence, global routing helps detailed routing in two ways. First, the complexity of detailed routing can be reduced by confining its search space to...