Efficient Detailed Routing on Optimized Tracks

Abstract

The subject of this thesis is detailed routing of very large scale integrated (VLSI) circuits. This task is very challenging due to the enormous instance sizes as well as the theoretical hardness of the problem. Large instances can include several million nets which are to be packed into a graph with hundreds of billions of nodes. Even much simpler sub-problems like finding a minimum length Steiner tree or the vertex disjoint path problem on grid graphs are NP-hard. Furthermore, complex design rules and other side constraints need to be obeyed.<br /> We improve main components of BonnRouteDetailed, the detailed routing tool developed at the Research Institute for Discrete Mathematics at the University of Bonn in a cooperation with IBM. It has been and is used by IBM to successfully develop some of the most complex and powerful processor chips of the world. We give a comprehensive overview of BonnRouteDetailed and briefly describe the most important parts of this state-of-the-art detailed routing tool.<br /> In this thesis we describe two key contributions in detail. First, we discuss the problem of generating soft track patterns automatically. We discuss different objectives and combine them into a simple and effective objective function. We present an efficient algorithm computing optimal solutions for up to three track patterns and describe how it can be used to compute high-quality soft track patterns for BonnRouteDetailed.<br /> Second, we develop an axiomatic description of diff-net rules and derive important properties. We use this theoretical foundation to describe diff-net rules that can be effectively handled by our routing tool. We develop an efficient algorithm for checking such diff-net rules and present a highly optimized implementation inside the parallelization framework of BonnRouteDetailed.<br /> Last but not least, we present excellent experimental results with both our novel automatic soft track pattern generation as well as our fast implementation of diff-net rules inside BonnRouteDetailed. Our automatic soft track patterns generation does not only save the time to manually provide hard-coded soft track pattern and make the detailed routing flow much more robust, they also lead to clearly superior results. Run time is reduced by 40% and 33% on 14nm and 7nm instances respectively. Almost all metrics to measure the quality of results improve significantly. Wire length and number of vias decrease, there are fewer scenics and fewer layer and taper fuses. Also, the number of remaining design rule violations decreases substantially.<br /> Our efficient diff-net rule checking implementation speeds up the total run time of BonnRouteDetailed by more than a factor 2. Furthermore, unlike the previous approach, BonnRouteDetailed is now able to check many diff-net rules exactly. Parallelization of this implementation is very good, the main routing step of BonnRouteDetailed achieves a speedup of factor 40 with 64 threads on 14nm instances and a speedup of factor 32 with 64 threads on newer 7nm instances.<br /> Together, our contributions substantially improve the run time of BonnRouteDetailed as well as the quality of routing solutions computed by BonnRouteDetailed and in particular improve its ability do deal with complex diff-net rules exactly as well as pack wires of different widths efficiently.