FastGR: Global Routing on CPU-GPU with Heterogeneous Task Graph Scheduler (Extended Abstract)

1 Introduction

Routing is essential in the design flow of the modern verylarge-scale integration. Modern routing flow is divided into global routing and detailed routing. Global routing produces routing guidance for detailed routing by performing rough routing on a coarse grid graph [Liu et al., 2020]. The efficiency and efficacy of global routing are crucial to the design closure due to its recurrent invocation and guiding role.

The literature has extensively explored shortest path searching with GPU [Djidjev et al., 2015]. However, most work only explores the basic single-source shortest path algorithm. These algorithms are unsuitable for routing since we must route millions of nets while considering numerous objectives and limitations such as wirelength, number of vias, and design rules. Regarding those modern routing challenges, more appropriate GPU kernel algorithms should be designed.

In this work, we propose FastGR, a global routing framework accelerated for CPU-GPU platforms. The framework leverages a GPU-friendly pattern routing algorithm and a task graph scheduler for heterogeneous CPU-GPU systems. By utilizing the processing resources of GPUs, we can further increase the solution quality performance of our global routing framework while incurring a little runtime overhead. We develop two variants of our global routing framework: the runtime-oriented version FastGR L and the quality-oriented version FastGR H . Experiments show that when compared to the state-of-the-art global router [Liu et al., 2020], our runtime-oriented version FastGR L can achieve 2.489× overall speedup without any quality degradation. The qualityoriented version FastGR H [Liu et al., 2022b] reduces the number of shorts by 27.855% over the runtime-oriented version FastGR L [Liu et al., 2022a] while remaining 1.970× faster than the most advanced global router [Liu et al., 2020].

∗This work has been initially presented at the IEEE/ACM Proceedings Design, Automation and Test in Europe (DATE) in 2022 and IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD) in 2023.

2 Preliminaries

2.1 ProblemFormulation

A grid graph G(V,E) is defined to formulate global routing problem by considering each G-cell as a vertex (v ∈ V ) and drawing an edge (e ∈ E) between all the pairs of adjacent G-cells. Figure 1 illustrates the procedure of grid graph construction. We map all the pins into G-cells according to the pin position. In this sample, different colors represent different metal layers. There is a preferred routing direction (horizontal or vertical) for wire edges in each metal layer, represented as the colored solid lines. The black dotted lines mean the via edges in our grid graph. With the grid graph G construction, the global routing problem can be formulated as the minimum accumulated cost path searching problem on G for all the nets defined in VLSI designs.

2.2 Modern Global Router

Pattern routing [Kastner et al., 2002] plays an important role in the modern global routing framework due to its efficiency. Two popular patterns are shown in Figure 2. We illustrate the L-shape and Z-shape pattern routing paths on 2D and 3D routing spaces. As shown in Figure 2, the L-shape pattern includes one single bend point to change the routing direction, while the Z-shape pattern routing path contains two bends.

3 Algorithms

3.1 Overview

Figure 3 depicts the overall flow of FastGR. To begin, we present a heterogeneous task graph scheduler and use it to manage the execution order of multiple routing tasks in both portions of our global routing framework, the pattern routing stage, and the rip-up and reroute iterations. The conflicting relationship among these tasks is used to form the task graph. It is important to note that a conflict between two routing tasks indicates that they cannot be processed at the same time. Our task graph scheduler is utilized to determine the execution order of each conflicting pair of tasks.

3.2 Task Graph Scheduler

To determine the execution order of the global routing tasks, we develop a two-stage task graph scheduler. The first stage is to create a task conflict graph. The task graph scheduler is then used to determine the order of execution for each conflict edge. Following the task conflict graph generation, we extract one maximum non-conflicting set as the root task batch. All of these tasks can be divided into two groups: the root task batch and the non-root task batch. We assign the execution order to each pair of conflicting tasks as follows.

• Only one task is in the root task batch. The execution direction is from the root batch task to the other.
• Both the tasks are not part of the root batch. The execution order is from the task with a smaller task ID to the other and the task ID indicates the sorting result.

3.3 GPU-friendly 3D Pattern Routing

Figure 4 shows the programming architecture of our GPUfriendly pattern routing framework for all of these routing tasks during the pattern routing stage. Each batch in Figure 4 represents a single routing task, and each task contains several multi-pin nets. As shown in Figure 2, there are two common patterns in pattern routing approaches, where the L-shape pattern provides two candidate routing paths in 2D space and L × L candidate routing paths in 3D space. At the same time, there are two bend points in Z-shape patterns named the source bend point, and the target bend point since one connects to the source pin, and the other connects to the target pin. Without loss of generality, we discuss two bend points here and treat L-shape patterns as a special case. the bend point pair can get M + N candidate paths in 2D space, where M represents the width of the bounding box of the net on G and N is the height. Section 3.3 defines the notations used in our GPU-friendly 3D pattern routing algorithms for the two-pin net Ps → Pt.

We define a GPU-friendly 3D pattern routing algorithm as shown in Figure 5. The left part in Figure 5 illustrates one of the solutions of Ps → Pt with two bend points (Bs(i) , Bt(i) ), where i means the index of the candidate bend point pair and 1 ≤ i ≤ M + N. We define ls, lb, and lt as the layer of the source pin, the wire connecting two bend points, and the target pin respectively.

The double-bend routing path includes three parts,

• the wire connecting the source point Ps to the source bend point Bs(i) ls ;
• the vias to change routing metal layers from ls to lb and the wire connecting to the target bend point Bt(i) lb ;
• the vias to change routing metal layers from lb to lt and the wire connecting to the target point Tlt .

In this sample path, ls is 1, lb is 2 and lt is 4. We denote this candidate double-bend pattern routing path as P{Ps, Bs(i) ls ,Bt(i) lb , Tlt }. According to the above three parts, the formal formulation of the path cost is,

For each pair of bend points (Bs(i) ,Bt(i) ), we will generate the candidate flow i for this bend point pair. c∗(i) (Ps, Pt, lt) represents the minimum cost result of the two-pin net Ps → Pt in the ith candidate flow with the 3D pattern routing algorithm. The calculation of c∗(i) (Ps, Pt, lt) with the inter-net ordering is,

We propose a merge step to merge the results of all M + N candidate flows. We can get the final minimum cost as follows,

To better utilize the GPU resources, we reformulate it as the computation graph flow using the vector/matrix addition and minimum operation. Our proposed GPU-friendly pattern routing algorithm for the ith candidate bend point pair (Bs(i) ,Bt(i) ) is shown in the right part of Figure 5. The weight of the edge Ps → Bs(i) ls includes the bottom children cost cbc(Ps, ls) and the wire cost to connect Ps and Bs(i) . The formulation of lth s of the edge weights ⃗w(1) is,

The metal layer switch procedure at the source bend point is represented by the connection between Bs(i) ls and Bt(i) lb . Based on the connection, we formulate the entry of the edge weights matrixW(2) at the lth s row and the lth b column as

We can also define the metal layer switch procedure at the target bend point as the connection between Bt(i) lb and Tlt . The entry at lth b row and the lth t column of the edge weights matrixW(3) is defined as,

The minimum cost c∗(i) (Ps, Pt, lt) of the candidate bend point pair (Bs(i) , Bt(i) ) can be calculated as Equation (7) referring to Equation (2),

Having all the minimum cost of M + N candidate bend point pairs, we can finally get the c∗ (Ps, Pt, lt) using the merge step in Equation (3) which can also be computed as the vector minimum operation on GPU.

Both L-shape and Z-shape patterns are included in the above formulations. Separate routing algorithms can be formulated by limiting bend point pair candidates.

3.4 Parallel Rip-up and Reroute Iterations

Each multi-pin net is treated as a separate routing task. Then, we apply our task graph scheduler to these routing tasks based on the conflict relationship. Finally, all these routing tasks follow the execution order determined in the ordered task graph. As a result, utilizing Taskflow [Huang et al., 2019] and the ordered task graph, we can quickly maximize the parallelism of our rip-up and reroute iterations.

4 Experimental Results

4.1 Experimental Setup

The framework was developed in C++/CUDA based on CUGR [Liu et al., 2020]. We conducted the experiments on a 64-bit Linux machine with Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz and 1 NVIDIA GeForce RTX 3090 GPU. ICCAD2019 benchmarks[Dolgov et al., 2019] were adopted. We integrated our proposed two types of GPU-friendly pattern routing algorithms into the pattern routing stage separately to illustrate the strength of our methods. Further, the details of sorting scheme and threshold settings can be found in [Liu et al., 2022b].

4.2 Acceleration

We evaluate the total runtime, pattern routing runtime, and runtime of the rip-up and reroute iterations to demonstrate the acceleration performance. Section 4 shows that our proposed FastGR L can bring an overall 2.489× acceleration with 9.324× speedup on the pattern routing stage. Meanwhile, the proposed FastGR H can still obtain 1.970× speed up with much more candidate routing paths, in which the pattern routing stage achieves 2.070× acceleration on average and 3.157× improvement on the maze routing stage due to the reduction of the number of nets to rip up.

4.3 Evaluation on Hybrid Shape Patterns.

Section 4 shows the comparison of the solution quality after global routing. It establishes that the global router with hybrid-shape pattern routing algorithm FastGR H can beat the global router with L-shape pattern routing algorithm FastGR L [Liu et al., 2022a] with respect to the solution quality on most designs. Since our hybrid-shape pattern routing algorithm considers Z-shape patterns as the candidate routing paths, the number of vias increases reasonably. To further evaluate the solution performance, Dr.CU [Chen et al., 2019] is applied to conduct detailed routing under the guide of the global routing solution. As for the wirelength, our FastGR framework outperforms CUGR on most designs. Furthermore, FastGR can obtain comparable detailed routing performance with CUGR in many aspects (including the number of vias, the number of shorts, and the number of spacing violations) as listed in [Liu et al., 2022b].

5 Conclusion

In this paper, we propose an efficient global routing framework, FastGR, accelerated for CPU-GPU platforms. We propose two GPU-friendly pattern routing algorithms and a heterogeneous task graph scheduler. The experimental results highlight the importance of GPU-accelerated kernel algorithms and the task scheduler for inter-net ordering in routing. An adequate fuse of them can assist in reducing design cycles and improve the solution quality at the same time. In the future, we plan to extend the task graph scheduler to other critical stages and exploit the power of GPU acceleration in the VLSI flow.