Detailed-routability-driven and timing-driven scalable parallel global routing

Electronic Design Automation (EDA) tools are used to design computer chips, which may have billions of transistors nowadays. The complexity of EDA increases rapidly as chip designs grow larger, and the algorithms as well as the objectives keep evolving as more complicated design rules are introduced in modern technology nodes. There are many stages in chip design. Routing is one of the most time-consuming stages, and it is also the last stage that directly determines the quality of the chip. The routing problem is usually solved in two steps known as global routing and detailed routing. Global routing generates a preferred routing region (Guide) for each net, and detailed routing focuses on reducing design rule violations in the routing region. Detailed routing can be easily parallelized and scaled up by parallelizing disjoint routing regions, but global routing requires complex parallelization techniques to manage the shared routing resources. Therefore, we believe it is imperative to develop high-quality and fast parallel algorithms for global routing. This dissertation studies the global routing problem. Global routing needs to generate routing guides such that (1) routability of detailed routing is considered, (2) routing is fast, and (3) timing constraints are satisfied. This dissertation proposes new algorithms as well as novel parallelization strategies to improve both the quality of result (QoR) and the runtime of global routing. The following work is presented in this dissertation. • SPRoute 1.0 proposes a non-deterministic parallelization strategy in ripup-and-reroute (RRR) maze routing. In net-level parallelization of maze routing, the livelock problem may result in redundant work and reduce the speedup of parallelization; in the worst case, it may even prevent maze routing from converging. To solve these problems, we propose a novel two-phase maze routing algorithm. This algorithm solves the livelock issue in the net-level parallelism and achieves an 11.0× speedup using 28 threads compared with a state-of-the-art single-threaded global router. • SPRoute 2.0 proposes a detailed-routability-driven technique and a deterministic parallel strategy for maze routing. We first introduce soft capacity, which reserves routing space for detailed routing based on the pin density and Rectangular Uniform wire Density (RUDY). We then propose a deterministic parallelization approach that partitions the netlist into batches and then bulk-synchronously maze-routes a single batch of nets. The advantage of this approach is that it guarantees determinacy without requiring the nets running in parallel to be disjoint, thus guaranteeing scalability. We design a scheduler that mitigates the load imbalance and livelock issues in this bulk synchronous execution model. The experimental results show that SPRoute 2.0 generates good quality of results with 43% fewer shorts, 14% fewer DRCs and a 7.4× speedup over a state-of-the-art global router. • SPRoute 3.0 targets timing-driven layer assignment in global routing. It proposes a critical net identification algorithm to dynamically determine the critical rate and a parallelization technique to parallelize layer assignment. The proposed methodology can be easily integrated with an asynchronous physical design flow and a timer. SPRoute 3.0 reduces more than 61.7% of the maximum net delay in global routing with a 1.3% increase on the quality score. It achieves good scalability with a speedup of 7.0× using eight threads compared with single thread. • Finally, I present a power router called PWRoute for the gridded cell placement flow Dali[119]. In the gridded cell, the cell height and width can be any integer multiple of two grid values, so traditional power grid generation methods for standard cells do not apply and a dedicated power router is needed. The power router consists of two steps: (i) power mesh generation and (ii) detailed power routing. PWRoute can generate DRC-clean solutions, and is verified by commercial tools and a chip tape-out.