Transduction is a powerful method for high-effort logic optimization. Unlike many local heuristics that focus on area-decreasing steps, transduction incorporates area-increasing transformations to restructure circuits, thereby uncovering unique opportunities for subsequent area reductions. Despite its potential in area optimization, transduction is computationally expensive, primarily due to the high runtime cost of computing don’t-cares. To reduce its runtime and make it more practical, we present a GPU-accelerated fast transduction algorithm. We first explore how to maximize the parallelism of transduction, followed by GPU-friendly kernel optimization techniques for reduced memory consumption and improved performance. Compared to the state-of-the-art transduction implementation in ABC, our method achieves an average speedup of 130× while delivering superior and-inverter graph (AIG) results on the large benchmarks from the IWLS2022 Programming Contest. The source code of this work is available at https://github.com/Lin-HKUST-Guangzhou/gpu-transduction.

Global routing plays a crucial role in electronic design automation (EDA), serving not only as a means of optimizing routing but also as a tool for estimating routability in earlier stages such as logic synthesis and physical planning. However, these scenarios often require global routing on unpartitioned large designs, posing unique challenges in scalability, both in terms of runtime and design size. To tackle this issue, this paper introduces useful techniques for parallelizing large-scale global routing that can significantly increase parallelism and thus reduce runtime. We also propose a new flexible layer transition technique to increase the flexibility and routing quality of directed acyclic graph (DAG) routing. Building upon these techniques, we have developed an open-source GPU-based global router that achieves state-of-the-art results in the latest ISPD’24 Contest benchmarks, thereby showcasing the effectiveness of our methods.

Recent efforts of applying e-graphs in logic synthesis have shown promising results. Nevertheless, e-graph-based gate-level logic optimization suffers from inefficiency and limited extraction quality. In this article, we propose a fast parallel e-matching algorithm for speeding up e-graph rewriting, and an efficient netlist extraction framework with high quality of results in both area and delay. Experiments show that e-graph rewriting can be accelerated by up to 8.3× over a high-performance e-graph library, and our extraction framework achieves 11.0% and 1.0% improvements in size and level on average, compared to the best results of the state-of-the-art netlist extraction method.

Critical Path Generation (CPG) is crucial for static timing analysis (STA) applications to validate timing constraints. Recent years have witnessed CPG algorithms that can rank k critical paths efficiently and accurately. However, they all suffer from the lack of incrementality, which is the ability to quickly update critical paths after the circuit is incrementally modified. To solve this problem, we introduce Ink, an efficient incremental CPG algorithm. Inspired by the large path trace similarity between adjacent CPG queries, Ink identifies a set of paths to reuse for the next query and effectively prunes the path search space. We have demonstrated the promising performance of Ink on large circuit benchmarks. Ink is up to 22.4X faster and consumes up to 31% less memory than a state-of-the-art timer when generating one million paths on a large design.

Composite Current Source (CCS) timing model plays an important role in modern static timing analysis (STA) because it precisely captures the timing behavior of a design at advanced nodes. However, CCS is extremely time-consuming due to its accurate but complicated timing models. To overcome this challenge, we introduce GCS-Timer, a GPU-accelerated CCS-based timing analysis algorithm. Unlike existing methods that perform model order reduction to trade accuracy for speed, GCS-Timer achieves high accuracy through a fast simulation-based analysis using GPU computing. Experimental results show that GCS-Timer can complete CCS analysis with better accuracy and achieve 3.2X faster runtime compared with a 16-threaded industrial standard timer. The source code is available at https://github.com/cuhk-eda/GCS-Timer.

Binary adders are a critical building block in integrated circuit (IC) design. In addition to the widely used 32/64/128-bit adders, large (1024/2048 bits) adders are important in applications such as cryptography. However, most current adder design methods target regular bitwidths, and cannot efficiently generate large adders with good performance. In practice, adders are often integrated into circuits such as a multiplier-accumulator (MAC), resulting in complex non-uniform input arrival times. To address these challenges, we propose a new algorithm for efficiently generating high-quality adders for non-uniform input arrival times. It is based on a novel divide-and-conquer-friendly problem formulation, and can effectively generate and maintain the most useful adder structures through dynamic programming. Experimental results show that it outperforms the current state-of-the-art methods in both quality and runtime. The adders generated by our algorithm have 2.8%, 8.3%, and 10.3% reductions in delay, area, and power, respectively, compared to those generated by a commercial synthesis tool.

In the face of escalating complexity and size of contemporary FPGAs and circuits, routing emerges as a pivotal and time-intensive phase in FPGA compilation flows. In response to this challenge, we present an open-source parallel routing methodology designed to expedite routing procedures for commercial FPGAs. Our approach introduces a novel recursive partitioning ternary tree to augment the parallelism of multi-net routing. Additionally, we propose a hybrid updating strategy for congestion coefficients within the routing cost function to accelerate congestion resolution in negotiation-based routing algorithms. Evaluation on public benchmarks from the FPGA24 routing contest demonstrates the efficacy of our parallel router. It achieves a 2 × speedup compared to the academic serial router RWRoute. Furthermore, when compared to the industry-standard tool Vivado, our approach not only delivers a 2 × acceleration but also yields a notable 31% enhancement in critical-path wirelength.

Global routing plays a crucial role in electronic design automation (EDA), serving not only as a means of optimizing routing but also as a tool for estimating routability in earlier stages such as logic synthesis and physical planning. However, these scenarios often require global routing on unpartitioned large designs, posing unique challenges in scalability, both in terms of runtime and design size. To tackle this issue, this paper introduces useful techniques for parallelizing large-scale global routing that can significantly increase parallelism and thus reduce runtime. Building upon these techniques, we have developed an open-source GPU-based global router that achieves the state-of-the-art results in the latest ISPD'24 Contest benchmarks, thereby showcasing the effectiveness of our methods. The source code of this work is available at https://github.com/cuhk-eda/InstantGR.

Placement serves as a fundamental step in VLSI physical design. Recently, GPU-based placer DREAMPlace 1 demonstrated its superiority over CPU-based placers. In this work, we develop an extremely fast GPU-accelerated placer Xplace which considers factors at operator-level optimization. Xplace achieves around 2x speedup with better solution quality compared to DREAMPlace. We also plug a novel Fourier neural network into Xplace as an extension. Besides, we enable Xplace to handle the detailed-routability-driven placement problem and demonstrate its superiority in terms of quality and performance. We believe this work not only proposes an extremely fast and extensible placement framework but also illustrates a possibility of incorporating a neural network component into a GPU-accelerated analytical placer. The source code of Xplace is released on GitHub.

Maze routing is usually the most time-consuming step in global routing and detailed routing. A commonly used maze routing method is to start from one pin and iteratively connect the current route to the closest unconnected pin. This method reduces the maze routing problem to multiple multisource–multidestination shortest path problems. The shortest path problem in VLSI routing has: 1) rectilinear routing directions and 2) preferably small via usage. By utilizing these two characteristics, we propose a novel parallel algorithm called GAMER to accelerate the multisource–multidestination shortest path problem for VLSI routing. GAMER decomposes the shortest path search into alternating vertical and horizontal$sweep$operations, and two parallel algorithms are proposed to accelerate a$sweep$operation from$O(n^{2})$to$O(\log _{2}{n})$on a grid graph of$n\times n$. Several techniques of applying GAMER on irregular routing regions are also introduced. Experiments are conducted by integrating GAMER into the state-of-the-art academic global router CUGR. CUGR adopts a two-level maze routing scheme, including coarse-grained routing and fine-grained routing, and they can be accelerated by$19.85\times $and$2.59\times $, respectively, with GAMER, achieving an overall speedup of$2.7\times $without quality degradation.

Logic rewriting is an important part in logic optimization. It rewrites a circuit by replacing local subgraphs with logically equivalent ones, so that the area and the delay of the circuit can be optimized. This paper introduces a parallel AIG rewriting algorithm with a new concept of logical cuts. Experiments show that this algorithm implemented with one GPU can be on average 32X faster than the logic rewriting in the logic synthesis tool ABC on large benchmarks. Compared with other logic rewriting acceleration works, ours has the best quality and the shortest running time.

The finite element method (FEM) is a well-known technique for approximately solving partial differential equations and it finds application in various engineering disciplines. The recently introduced wafer-scale engine (WSE) has shown the potential to accelerate FEM by up to 10,000×. However, accelerating FEM to the full potential of a WSE is non-trivial. Thus, in this work, we propose a partitioning algorithm to partition a 3D finite element model into tiles. The tiles can be thought of as a special netlist and are placed onto the 2D array of a WSE by our placement algorithm. Compared to the best-known approach, our partitioning has around 5% higher accuracy, and our placement algorithm can produce around 11% shorter wirelength (L1.5-normalized) on average.

Global routing is an essential step in physical design. Recently there are works on accelerating global routers using GPU. However, they only focus on certain stages of global routing, and have limited overall speedup. In this paper, we present a superfast full-scale GPU-accelerated global router and introduce useful parallelization techniques for routing. Experiments show that our 3D router achieves both good quality and short runtime compared to other state-of-the-art academic global routers.

Maze routing is usually the most time-consuming step in global routing or detailed routing. One possible way to accelerate it is to use parallel computing. Net-level parallelism is commonly used but it is affected greatly by the dependency between nets. There are few GPU-friendly parallel maze routers, which can be nontrivial to design. In this paper, we propose a pathfinding-level parallel 3D routing scheme. We implemented it in CUDA and applied it to the coarsened maze routing stage of an open source global router CUGR. Compared with CUGR on the ICCAD 2019 global routing contest benchmark suite, we achieve an average of 16 x speedup in the coarsened maze routing stage without loss of quality.