In this paper, we propose RegularRoute, an efficient detailed router encouraging regular routing patterns. RegularRoute is proposed for potentially better design rule satisfaction based on a correct-by-construction methodology. Given the underlying spacing-based design rules, 2-D global routing solution, and 3-D detailed routing tracks, RegularRoute generates a 3-D detailed routing solution in a bottom-up layer-by-layer framework. At the beginning, local nets, i.e., nets or subnets that are inside one G-cell, are routed using vertical spine routing topology. Routing usage of local nets is treated as blockage when assigning global segments. Then, for each layer we formulate the problem of global segment assignment inside each panel, i.e., grouped routing tracks, as a maximum weighted independent set (MWIS) problem. We propose a fast and effective heuristic to solve the MWIS problem. Unassigned segments are partially routed by a greedy technique. For the unrouted portion of each segment, its terminals are promoted so that the assignment is deferred to the upper layers. At the top layers, we apply the panel merging and maze routing techniques to improve routability. RegularRoute generates a detailed routing solution that satisfies the basic spacing-based design rules. To satisfy all the design rules, we propose an abstract idea of local optimization based on local shift and rip-up-and-reroute, assuming that most design rules are complex functions of local and neighboring geometries. Because of the unavailability of proper academic grid-based detailed routing benchmarks, we propose two sets of detailed routing test cases derived from ISPD98 and ISPD05/06 placement benchmark suites, respectively. Our experimental results demonstrate the effectiveness and efficiency of RegularRoute.

In this brief, we propose congestion refinement of placement (CROP) for improving the congestion of mixed-size placement solutions. CROP consists of a congestion-driven module shifting technique and a congestion-driven detailed placement (CDDP) technique. The shifting technique is proposed for better allocation of routing resources. We shift modules based on the shifting of G-cell boundaries. Shifting in each direction can be formulated as a linear program (LP) for resizing each cell in the global routing grid (i.e., G-cell). We degenerate and solve the LP by a very efficient longest path computation. Then the CDDP technique is proposed for distributing the routing demands better. Congestion reduction is realized by weighting the half-perimeter wirelength with the congestion factor during detailed placement. Theoretically, our tool is capable of handling most mixed-size placement benchmarks with movable and/or fixed macro (FM) blocks. In order to better analyze its performance, the ISPD-GR benchmark suite (ISPD05/06 derived global routing benchmarks) with FM modes is developed. The experimental results show that CROP effectively alleviates congestion for unroutable placement solutions in short runtimes for different placers.

Improving detailed routing routability is an important objective of a global router. In this paper, we propose GDRouter, an interleaved global routing and detailed routing algorithm for the ultimate routability i.e., detailed routing routability. The newly proposed router makes the global routing aware of detailed routing routability by correctly setting global capacity to reduce the inconsistency between the two stages. The final result contains both the detailed routing guided global routing and deailed routing solutions.

Detailed routing is an important phase of realizing exact routing paths for optimizing various design objectives and satisfying increasingly complicated design rules. In this paper, we propose RegularRoute, a fast detailed router trying to use regular routing patterns in a correct-by-construction strategy for better routability and design rule satisfaction. Given a 2-D global routing solution and the underlying routing tracks, we generate a detailed routing solution in a bottom-up layer-by-layer manner. For each layer, the routing tracks are partitioned into a number of panels. We formulate the problem of assigning global segments into different tracks of each panel as a Maximum Weighted Independent Set (MWIS) problem.

The number of vias generated during the global routing stage is a critical factor for the yield of final circuits. However, most global routers only approach the problem by charging a cost for vias in the maze routing cost function. In this paper, we present a global router that addresses the via number optimization problem throughout the entire global routing flow. We introduce the via aware Steiner tree generation, 3-bend routing and layer assignment with careful ordering to reduce via count. We integrate these three techniques into FastRoute 3.0 and achieve significant reduction in both via count and runtime.

Modern circuits become harder to route with the ever decreasing design features. Previous routability-driven placement techniques are usually tightly coupled with the underlying placers. So usually they cannot be easily integrated into various placement tools. In this paper, we propose a tool called CROP (Congestion Refinement of Placement) for mixed-size placement solutions. CROP is independent of any placer. It takes a legalized placement solution and then relocates the modules to improve routability without significantly disturbing the original placement solution.

As an easily implemented approach, ripup and reroute has been employed by most of todaypsilas global routers, which iteratively applies maze routing to refine solution quality. But traditional maze routing is susceptible to get stuck at local optimal results. In this work, we will present a fast and high quality global router FastRoute3.0, with the new technique named virtual capacity. Virtual capacity is proposed to guide the global router at maze routing stage to achieve higher quality results in terms of overflow and runtime. During maze routing stage, virtual capacity works as a substitute for the real edge capacity in calculating the maze routing cost. There are two sub techniques included: (1) virtual capacity initialization, (2) virtual capacity update. Before the maze routing stage, FastRoute3.0 initializes the virtual capacity by subtracting the predicted overflow generated by adaptive congestion estimation (ACE) from the real edge capacity. And in the following maze routing iterations, we further reduce the virtual capacity by the amount of existing overflow(edge usage minus real edge capacity) for the edges that are still congested. To avoid excessive ldquopushing-awayrdquo of routing wires, the virtual capacity is increased by a fixed percentage of the existing overflow if edge usage is smaller than real edge capacity. Experimental results show that FastRoute3.0 is highly proficient dealing with ISPD98, ISPD07 and ISPD08 benchmark suites. The results outperform published ripup and reroute based academic global routers in both routability and runtime. In particular, (1) FastRoute3.0 completes routing all the ISPD98 benchmarks. (2) For ISPD07 and ISPD08 global routing contest benchmarks, it generates 12 out of 16 congestion free solutions. (3) The total runtime is enhanced greatly.