Detailed routing constitutes a critical phase in the very large-scale integration (VLSI) physical design, widely regarded as the most time-consuming and computationally intensive step in the back-end design process. Due to its iterative nature and strong data dependencies, conventional parallel acceleration techniques often suffer from limited scalability and effectiveness. To address these challenges, we propose RouterAcc, an FPGA-based software–hardware co-design acceleration framework tailored for VLSI detailed routing. RouterAcc incorporates an access analysis mechanism and a termination condition strategy to accelerate convergence. Furthermore, we employ a hierarchical storage mapping scheme and a flexible dimension-partitioning architecture to alleviate memory bottlenecks and enhance data locality. Additionally, RouterAcc leverages a hierarchical comparison pipeline with fully parallelized computing units and a data preprocessing strategy to maximize computational efficiency. Experimental results on the ISPD’18 benchmarks demonstrate that RouterAcc achieves consistent speedups of 2.1×–2.3× over TritonRoute with less than 1% quality degradation. With further co-optimization, RouterAcc attains speedups of 2.7×–11.8× while maintaining routing quality comparable to TritonRoute and surpassing Dr.CU 2.0 as well as the state-of-the-art (SOTA) FPGA-based approaches.

Global routing is a critical stage in VLSI physical design, directly affecting the final Power, Performance, and Area (PPA) metrics. In this paper, we propose a high-performance global router that optimizes via count and routing congestion simultaneously. We first generate a 2D via-aware spine tree, which incorporates bend cost to reduce via usage while minimizing wire length. Then, a fast maze routing algorithm is employed to efficiently find a blockage-free path, followed by a congestion-aware layer assignment method to generate the 3D routing solution. Finally, we present an iterative rip-up and reroute strategy to resolve remaining congestion using the 3D bidirectional A* search. The A* search is guided by an adaptive cost function that dynamically adjusts via costs based on congestion, facilitating the co-optimization of congestion and via count. Compared to an advanced commercial tool and the leading academic engine OpenROAD, our algorithm achieves the best results in both overflow and via count, while preserving almost the same wire length.

As integrated circuit technology nodes scale down, high via density challenges multiple patterning lithography (MPL). Existing methods for addressing via coloring conflicts mainly focus on detailed routing, yet they cannot resolve conflicts arising from vias that are fixed before routing, such as Power/Ground vias and obstruction vias. This paper presents a co-optimization framework to eliminate such inherent via coloring conflicts and boost routing efficiency. It proposes a conflict detection method identifying odd cycle and odd wheel violation patterns, balancing efficiency and precision well. It dynamically marks Forbidden Box and Forbidden Pair for mask-decomposition-aware placement and routing. A placement adjustment based on Directed Acyclic Graph (DAG) simultaneously handles overlaps between a cell’s Forbidden Box and Power/Ground vias, as well as illegal abutment of Forbidden Pair cells. During routing, Forbidden Box constraints guide pin access and via locations, while a final check resolves remaining conflicts through rip-up and reroute. Industrial benchmark experiments show the framework completely eliminates via coloring conflicts, and slightly reduces wirelength, via count and runtime.

MBFF banking is a standard technique for clock power reduction in modern IC design, yet two systemic flaws in prior works limit its practical gains: geometric abstractions that ignore placement congestion, and open-loop workflows where late legalization failures nullify power savings. We propose a self-correcting framework that co-optimizes banking, placement, and debanking via three innovations: (1) Mahalanobis-distance clustering for placement-feasible MBFF formation; (2) a legalization-driven feedback loop with cost-aware debanking to recover unplaceable MBFFs; and (3) an OPTICS-based debanking that splits problematic MBFFs at highest-cost boundaries. Evaluated on ICCAD 2024 CAD Contest Problem B and large-scale benchmarks, our framework outperforms the 1st, 2nd, and 3rd place winners by 2.3%, 9.3%, and 4.0% in final weighted score, respectively.

Compliance with design rule constraints constitutes a fundamental prerequisite for successful fabrication in advanced integrated circuit design. As foundries progressively introduce process-specific customization for better performance, new design rule challenges emerge across the device layers, such as implant layer constraints in the designs with multiple threshold voltages, and the trim poly layer constraints in the self-aligned double patterning (SADP). Conventional methodologies typically address such topological constraints in the legalization stage. In addition, filler insertion during chip finishing serves to improve manufacturability, such as a more uniform chip surface and a more robust power integrity. However, improper filler insertion might undermine the previous legalized layout. This work presents a co-optimization framework in the legalization and filler insertion stage, adaptable to multi-layer constraint scenarios. We model the filler insertion problem as a multi-branch tree and develop a dynamic programming-based pre-pruning algorithm, which is also able to detect violations in the legalization stage. To reduce runtime, two violation detectors are introduced for legalization, including a look-up table (LUT) inference method and a greedy scanning algorithm. These components are systematically integrated into a co-optimization framework, with configurable parameterization to ensure scalability across diverse constraints. Experimental results show that our algorithm can significantly reduce the number of violations compared with state-of-the-art work and the commercial tool.

Transformers have delivered exceptional performance and are widely used across various natural language processing (NLP) tasks, owing to their powerful attention mechanism. However, the high computational complexity and substantial memory usage pose significant challenges to inference efficiency. Numerous quantization and value-level sparsification methods have been proposed to overcome these challenges. Since higher sparsity leads to greater acceleration efficiency, leveraging both value-level and bit-level sparsity (hybrid sparsity) can effectively exploit the acceleration potential of the attention mechanism. However, increased sparsity exacerbates load imbalance across compute units, potentially limiting the extent of acceleration benefits. To fully exploit the acceleration potential of hybrid sparsity, we propose Libra, an attention accelerator developed through algorithm-hardware co-design. At the algorithm level, we design the bit-group-based algorithm consisting of filtered bit-group sparsification (FBS) and dynamic bit-group quantization (DBQ) to maximize the utilization of sparsity in attention. FBS imposes structured sparsity on weights, while DBQ introduces dynamic sparsification during the computation of activations. At the hardware level, we design task pool to achieve multi-level workload balance, effectively mitigating the load imbalance among compute units induced by hybrid sparsity. Additionally, different stages in DBQ can be executed in parallel, with each stage operating at distinct bit-widths. To support this, we design an adaptive bit-width architecture that enables simultaneous computations at varying bitwidths. Our experiments demonstrate that, compared to state-of-the-art (SOTA) attention accelerators, Libra achieves up to $1.49 \times \sim 5.89 \times$ speedup and $2.65 \times \sim 10.82 \times$ enhancement in energy efficiency.

The attention mechanism is a core neural network primitive widely utilized in state-of-the-art models of Natural Language Processing (NLP) applications. However, the high computational complexity and substantial power consumption hinder its deployment and efficient inference. To address these challenges, various methods leveraging sparsity and quantization have been proposed. Compared to these methods, the exploitation of abundant bit-level sparsity in attention-based models presents great potential for the performance enhancement of attention inference. Existing bit-sparsity optimization methods primarily focus on Convolutional Neural Networks (CNNs), which are not ideally suitable for the attention mechanism, and they have not effectively solved the workload imbalance and hardware under-utilization issues caused by the irregular distribution of non-zero bits in tensor data. In this work, we introduce Blaze, an efficient attention architecture that leverages both value and bit-level sparsity in tensor data along with workload orchestration optimization. To mitigate the workload imbalance issues often encountered by sparse bit-serial architecture, we propose an Approximate-Computing-Based (ACB) workload orchestration mechanism. Additionally, to fully exploit the redundancy in the attention mechanism, we propose a Leading-Booth mechanism to further enhance the performance of attention computation. We also design a reconfigurable computing engine to support both mechanisms. Experimental results indicate that, compared to state-of-the-art (SOTA) attention accelerators, our Blaze can achieve $2.37 \times \sim 6.18 \times$ improvement in performance and $9.69 \times \sim 43.96 \times$ enhancement in energy efficiency. Our accelerator can reach up to $1.58 \times$ speedup in attention computing performance compared with the SOTA bit-sparse accelerator.

Binarization is a promising approach to significantly reduce computational complexity by replacing multiplications with hardwareefficient XNOR operations. However, the binarization of LLM activations often leads to severe accuracy degradation, while weight-only binarization fails to eliminate multipliers due to the Self-Attention mechanism. Furthermore, LLMs exhibit distinctive channel-level data distribution characteristics and differing computational and memory requirements between the Pre-fill and Decoding stages, necessitating a specialized inference framework. In response, we introduce XShift, an algorithm-hardware co-design framework optimized for efficient binarized LLM inference on FPGAs. XShift incorporates three key contributions: (1) a hardwarefriendly XNOR-Shift Encoding (XSE) format that transforms traditional multiplications into XNOR and shift operations, ensuring scalability and precision; (2) Hardware Adaptive Outlier and Sparsity (HAOS) techniques, which exploit channel-level data distribution and systolic array architectures for optimized quantization and sparsification; and (3) a dedicated hardware accelerator featuring an XNOR-Shift Systolic Array (XSSA) and an enhanced Base-2 SoftMax Converter (BSMC), designed to address the specific computational demands of binarized LLMs. Experimental evaluations on the Alveo U280 and U50 FPGA demonstrate that XShift achieves a $\mathbf{1 0 - 1 5 x}$ reduction in DSP resource usage while surpassing existing accelerators and GPUs in inference performance. Specifically, XShift delivers an average speedup of 4.174.76 x and a 14.29-6.95 x improvement in energy efficiency, alongside lower perplexity compared to other low-precision LLM techniques. These results underscore the potential of XShift for edge deployment of LLMs.

The self-attention mechanism is a fundamental component within transformer-based models. Nowadays, as the length of sequences processed by large language models (LLMs) continues to increase, the attention mechanism has gradually become a bottleneck in model inference. The LLM inference process can be separated into two phases: prefill and decode. The latter contains memory-intensive attention computation, making FPGA-based accelerators an attractive solution for acceleration. However, designing accelerators tailored for the attention module poses a challenge, requiring substantial manual work. To automate this process and achieve superior acceleration performance, we propose AttentionLib, an MLIR-based framework. AttentionLib automatically performs fusion dataflow optimization for attention computations and generates high-level synthesis code in compliance with hardware constraints. Given the large design space, we provide a design space exploration (DSE) engine to automatically identify optimal fusion dataflows within the specified constraints. Experimental results show that AttentionLib is effective in generating well-suited accelerators for diverse attention computations and achieving superior performance under hardware constraints. Notably, the accelerators generated by AttentionLib exhibit at least a 25.1 × improvement compared to the baselines solely automatically optimized by Vitis HLS. Furthermore, these designs outperform GPUs in decode workloads, showcasing over a 2× speedup for short sequences.

This paper introduces FAMERS, a tile-based hardware accelerator designed for efficient 3D Gaussian Splatting (3DGS) inference on edge-deployed Field Programmable Gate Arrays (FPGAs). 3DGS has emerged as a powerful technique for photorealistic image rendering, leveraging anisotropic Gaussians to balance computational efficiency and visual fidelity. However, the high memory and processing demands of 3DGS pose significant challenges for real-time applications on resource-constrained edge devices. To address these limitations, we present a novel architecture that optimizes both computational and memory overheads through model pruning and compression techniques, enabling high-quality rendering within the constrained memory and processing capabilities of edge platforms. Experimental results demonstrate that our implementation on the Xilinx XC7K325T FPGA achieves a 1.99× speedup and 13.46× energy efficiency compared to NVIDIA RTX 3060M Laptop GPU, underscoring the viability of our approach for real-time applications in virtual and augmented reality.

Applications constructed with multiple Deep Neural Networks (multi-DNNs) are growing rapidly in edge and data center. However, executing multi-DNNs efficiently remains chal-lenging because multi-DNNs are inherently heterogeneous. The diverse operators, dependencies and performance requirements of multi-DNNs lead to high costs of encoding and generalization. We introduce Taichi, a graph-based framework for efficiently scheduling multi-DNNs on multi-core accelerators. Specifically, Taichi consists of two phases: (1) a graph neural network (GNN) is utilized to automatically capture the features from the graph structure of multi-DNNs and (2) reinforcement learning (RL) is employed to find an optimal online scheduling strategy. Evaluation results show that TaiChi reduces latency by 1.1-2.4 x and 1.1-1.6x compared to SJF and MAGMA, and improves throughput by 26.4-63.7% and 18.6-33.7%, respectively. Moreover, TaiChi achieves an average speedup of 779 x in scheduling runtime compared to MAGMA.

Dynamic scheduling in high-level synthesis (HLS) maximizes pipeline performance by enabling out-of-order scheduling of load and store requests at runtime. However, this method introduces unpredictable memory dependencies, leading to data disambiguation challenges. Load-store queues (LSQs), commonly used in superscalar CPUs, offer a potential solution for HLS. How-ever, LSQs in dynamically scheduled HLS implementations often suffer from high resource overhead and scalability limitations. In this paper, we introduce PreVv, an architecture based on premature value validation designed to address memory disambiguation with minimal resource overhead. Our approach substitutes LSQ with several PreVv components and a straightforward premature queue. We prevent potential deadlocks by incorporating a specific tag that can send ‘fake’ tokens to prevent the accumulation of outdated data. Furthermore, we demonstrate that our design has scalability potential. We implement our design using several hardware templates and an LLVM pass to generate targeted dataflow circuits with PreVv. Experimental results on various benchmarks with data hazards show that, compared to state-of-the-art dynamic HLS, PreVV16 (a version with a premature queue depth of 16) reduces LUT usage by 43.91% and FF usage by 33.09%, with minimal impact on timing performance. Meanwhile, PreVV64 (a version with a premature queue depth of 64) reduces LUT usage by 27.21% and FF usage by 33.10%, without affecting timing performance.

In this paper, a placement algorithm is proposed for die-to-die optimization in three-dimensional space. To address the challenges of hybrid bonding overhead and wirelength optimization, our method employs a 3D global placement strategy to explore the full solution space efficiently. The algorithm not only optimizes wirelength but also significantly reduces the usage of hybrid bonding terminals. Compared to the top three winners of the ICCAD’22 CAD competition, experimental results show that our method achieves the best normalized average wirelength and reduces hybrid bonding terminal usage to approximately 28.8% of that of the top 1 winner.

In the back-end verification of integrated circuits (IC), design rule checking (DRC) plays a critical role in ensuring that the layout complies with process constraints and guarantees manufacturability. Traditional DRC for 2D layouts involves checks on parameters including line width, spacing, and density. With the advancement of 3D IC and advanced packaging technologies, new DRC requirements have emerged. These include checks on inter-die spacing, alignment relationships, and the handling of non-Manhattan geometries. Previous academic research has focused almost exclusively on optimizing 2D DRC. Meanwhile, industrial tools such as Calibre 3DSTACK can only perform 3D rule checks on layouts that have already passed 2D DRC, which increases both workflow complexity and time consumption. Targeted at these limitations, we propose 3D DRC, a U-Net-based DRC tool designed for 3D IC. Our method performs both 2D and 3D rule checks in a single pass on 3D structures, with specific optimizations for non-Manhattan geometries in 3D IC. Additionally, the tool also supports traditional 2D DRC when applied to purely 2D layouts. We evaluated the performance of 3D DRC on a variety of open-source PDK rule sets. Extensive experiments demonstrate that the model exhibits strong generalization and high accuracy, achieving an average recall of 97.5% and precision of 97.7%. Furthermore, the model demonstrates high runtime efficiency, with the 2D mode running 22.3× faster than Calibre nmDRC, and the 3D mode being 13.3× faster than Calibre 3DSTACK.

Electromigration-related reliability concerns in very large-scale integration (VLSI) circuits have garnered increasing attention as technology continues to scale. As integrated circuits shrink and their density rises, solving Korhonen's equation for the multi-segment interconnect line model becomes increasingly challenging. Recent advances in neural network-based approaches have demonstrated notable efficacy in addressing differential equations arising in physical modeling frameworks. Inspired by Physics-Informed Graph Neural Network (PIGNN) methodologies, we propose a novel Physics-Informed Message Passing (PIMNEM) architecture designed to solve coupled multi-domain Korhonen equations. At the same time, we introduce AdaptEM, which incorporates a graph partitioning mechanism with a hierarchical training strategy and employs the PIM-NEM architecture as a subgraph computation unit. AdaptEM enables multi-scale decomposition of interconnected circuits and facilitates hierarchical unsupervised learning via its hierarchical architecture. Unsupervised training is first applied to partitioned subgraphs using the PIMP mechanism, followed by global graph fine-tuning, where inter-subgraph boundary constraints are explicitly enforced through differentiable penalty terms. AdaptEM achieves a 20× speedup over FEM-based methods at the cost of about 0.5% accuracy loss. While AdaptEM may not match the absolute computational speed of state-of-the-art EM tools, its end-to-end unsupervised training framework, enhanced by a hierarchical subgraph training strategy, offers superior generalization capabilities and greater tuning flexibility.

The State Space Model (SSM), particularly the Mamba implementation, has demonstrated impressive capabilities across various domains. It offers a significant reduction in computational complexity compared to Transformers while achieving higher algorithm accuracy. However, the ineffectiveness of spatially unfolding the SSM layer leads to increased latency as sentence length grows, especially when being deployed on FPGA. Previous token reduction methods introduced in Transformers fail to maintain high performance in Mamba. Moreover, the dispersed outliers, complex model structure and variety of non-linear operators obstruct its efficient implementation on FPGA. To address these challenges, we propose ToMamba, the first algorithm-architecture co-design to optimize Mamba implementation. At the algorithmic level, ToMamba incorporates a novel progressive token merging algorithm with minimal hardware consumption and a hardware-aware fine-grained quantization strategy. On the hardware side, a dualflow systolic array is designed to unify convolution and matrix multiplication, supporting both weight stationary and output stationary dataflow. A fine-grained pipeline design is adopted for SSM computation to maximize hardware efficiency and enhance throughput. Furthermore, efficient hardware architecture and approximation method for nonlinear function units are proposed. To enable merging after the Mamba layer, ToMamba also adopts a dedicated data mapping scheme. Comprehensive evaluations across multiple benchmarks demonstrate that the token reduction method of ToMamba achieves 10% sparsity with only 0.25% accuracy loss, improving up to 16.89% in accuracy compared to previous methods. ToMamba hardware implementation on U280 FPGA achieves up to 636.00×/11.01×/1.39× speedup compared to Intel Xeon Platinum 8369B CPU, NVIDIA Tesla A100 GPU and ASIC platforms and 1280×/44.32× energy efficiency improvement compared to CPU and GPU platforms.

The rapid evolution of 3D integrated circuits (ICs) has ushered in unprecedented integration density and performance gains. However, this advancement intensifies the challenges of multi-physics interactions, particularly the intricate coupling between electromagnetic (EM) and thermal fields. Thermal and EM optimizations of 3D ICs often require extensive and complex Partial Differential Equation (PDE) simulations. Neural network-based field solvers are renowned for their high efficiency and accuracy. However, existing approaches are often trained using results from traditional physical field solvers, which are time-consuming and lack compatibility with more complex design configurations. In this paper, for the first time, we propose 3D CoSim, a Physics-Informed Neural Network (PINN) based simulator for multi-physics analysis with arbitrary 3D IC configurations. 3D CoSim has a sophisticated computational framework that learns the nonlinear functional mappings from geometrical and physical setups to multiphysics fields. Leveraging a Multi-input DeepONet architecture, 3D CoSim integrates multiple PDE configurations. This integration encompasses the heat equation, Maxwell’s equations, and a diverse range of boundary conditions, thereby enabling the derivation of a unified solution for both EM and thermal fields. This integration delivers a paradigm shift in simulation efficiency. Experimental results demonstrate that 3D CoSim achieves a speedup of 844× to 7600× compared to traditional COMSOL while maintaining comparable accuracy of 97% for EM simulation and 99.8% for thermal simulation.

Transformers have increasingly become the backbone of modern AI, excelling in tasks across natural language processing (NLP) and computer vision (CV). Despite their effectiveness, calculating them is costly, especially on source-constrained platforms like FPGAs. Among the three main computation modules in a Transformer model (QKV generation, attention computation, FFN), most prior research has primarily focused on the attention computation. However, it is typically the QKV generation and the FFN that dominate the overall computational cost in most cases. To address this gap, we propose SiST, an innovative algorithm-architecture co-design to optimize all three modules of Transformer with both sparsity and token similarity. We first propose a cross-stage sparsity prediction mechanism before QKV generation to minimize computations involved in both QKV generation and attention computing. The prediction mechanism avoids large overhead through off-line weight clustering. Further, we leverage token similarity to adapt token clustering in FFN module, thereby reducing computational load. Moreover, the sparsity of weights in FFN is explored to further optimize the computational load. Our dedicated hardware architecture can effectively handle the unstructured sparsity and token clustering, ensuring high hardware resource utilization. Comprehensive evaluations across multiple benchmarks demonstrate that SiST reduces computational overhead by 45.9% to 52.2% with less than 2% loss in accuracy. It achieves a 2.35× to 8.44× speedup, 1.50× to 14.09× normalized throughput improvement and 2.43× to 3.44× improvement in energy efficiency compared with other FPGA-based Transformer accelerators.

Routing is a critical and time-consuming stage in circuit physical design. The typical approach involves 2D routing followed by 3D layer assignment, with most state-of-the-art methods using sequential assignments, which limits the solution space due to the fixed order in which nets are processed. This paper proposes a two-stage layer assignment paradigm inspired by the placement process. First, we apply an analytical method to simultaneously assign layers for all nets, leveraging GPU acceleration to enhance computational efficiency. Then, a simulated annealing algorithm further optimizes the segment assignments. Experimental results show that, compared to state-of-the-art sequential and concurrent layer assignment algorithms, our method reduces via count by 16.9% and 1.5% in global routing and by 5.3% and 3.5% in detailed routing, respectively, with minimal wirelength increases. Additionally, our algorithm achieves the fewest DRC violations across all benchmarks.

Multi-bit flip-flops (MBFFs) are widely employed in modern digital design due to their reduced power and area consumption compared to single-bit flip-flops (SBFFs). In this paper, we present an MBFF-based framework that simultaneously optimizes the crucial power, area, and timing metrics. First, we present a mean shift-based clustering algorithm to generate power and area-friendly clusters while considering multiple clocks. Then, a feasible-region-based declustering method is developed to produce the desired timing solution. Finally, we propose a timing-aware refinement strategy to further improve the solution quality. Compared with the competitive works, the experimental results show that our proposed algorithm achieves the best performance within the shortest runtime.

Legalization holds significant importance in VLSI physical design, as it significantly influences the manufacturability and reliability of circuits. Recently, advanced foundry nodes introduced complex constraints in standard-cell legalization, which makes legalization even harder. In this paper, we develop a legalization framework with design rule constraints enhanced by Monte-Carlo-Based cell priority optimization. We first handle abnormal density distribution to reduce the subsequent legalization’s hardness. Then, we propose an interval-assisted sequential legalization algorithm considering multiple design rule constraints with a Monte-Carlo-Based cell priority decision technique. Besides, based on the characteristics and complexity of different design rule constraints, we present a refinement phase to handle the remaining design rule constraints with corresponding detectors. Compared with a leading commercial tool, experiments on industrial benchmarks show that our legalization framework achieves 11% smaller average displacement, 15% smaller maximum displacement, 1.63× speedup, and 13% fewer remaining design rule violations on average.

As the miniaturization of integrated circuits (ICs) reaches its physical limits, the industry is entering a “more-than-Moore” era, demanding new Electronic Design Automation (EDA) tools. Existing TSV-based 3D placers focus on minimizing cuts while burgeoning F2F-bonded ICs feature dense interconnection between two planar die. Towards this novel structure, we proposed an integrated adaptation methodology upon mature one-die-based placement strategies. First, we instructively utilized a one-die placer to provide a statistical looking-ahead net diagnosis. The netlist henceforth shall be coarsened topologically and geometrically using a multi-level framework. Our multi-objective gain formulation guides a level-by-level refinement of the partition. This formulation considers factors like cut expectation, heterogeneous row heights, and balanced cell distribution, enabling efficient incremental calculations at each level. Given the partition, we synchronized the behavior of analytical planar placers by balancing the density and wirelength objective function among asymmetric layers. Finally, the result will be further improved by heuristic detail placement of bonding terminals and a post-place partition adjustment. Experimental results demonstrate that our fine-grained fusion of partitioning and placement techniques are competitive compared with the top three winners of the 2022 ICCAD CAD Contest, achieving the best normalized average wirelength with competitive runtime under various 3D architectural constraints .

Escape routing is a critical problem in PCB routing, and its quality dramatically affects the cost of the PCB design. Unlike the traditional escape routing that works mainly for the BGA with unique line width and space, this paper presents a high-performance escape routing algorithm to handle problems with variable design rules and multiple constraints. We first propose a novel obstacle-avoiding method to project pins to the boundary and construct a channel projection graph combined with a channel merging technique to handle complex irregular packages. We then construct a bi-projection graph and propose a matching-based hierarchical sequencing algorithm to consider manual constraints. We perform global routing for each pin/differential pair by congestion-avoiding path initializing and rip-up and reroute path optimizing. Finally, a length-aware detail routing algorithm is developed to optimize the line length while ensuring the differential pair constraints. The experimental results on industrial PCB instances show that our algorithm can achieve 100% routability without violating the design rules and constraints, while two state-of-the-art PCB routers, FreeRouting and Allegro, cannot complete escape routing.

Field-programmable gate array (FPGA) macro placement holds a crucial role within the FPGA physical design flow since it substantially influences the subsequent stages of cell placement and routing. With the increasing number of macros and the complex cascade shape and region constraints imposed by modern FPGAs, the routability and macro placement have become much more challenging. In this paper, we propose an effective and efficient routability-driven macro placement algorithm for modern FPGAs with cascade shape and region constraints. To reserve adequate space for cell placement and guarantee routability, we first develop a routability-driven mixed-size analytical global placement that evenly distributes both macros and cells while considering cascade shape and region constraints. Particularly, the proposed global placement engine integrates a well-trained congestion prediction model, targeting benchmarks with high routing congestion to enhance overall routability. Then, we propose an integer linear programming (ILP)-based cascade shape legalization followed by matching-based macro legalization to remove macro overlaps while satisfying the region constraints. Finally, a routability-driven detailed macro placement is proposed to refine the solution. Compared with the winners of the MLCAD 2023 FPGA macro placement contest and state-of-the-art works, experimental results show that our algorithm achieves the best overall score and routability.

In very large scale integration (VLSI) circuit physical design, precise congestion prediction during placement is crucial for enhancing routability and accelerating design processes. Existing congestion prediction models often encounter challenges in handling multimodal information and lack effective fusion of placement and netlist features, limiting their prediction accuracy. In this article, we present a novel congestion prediction model that leverages dual multimodal fusions with convolution and transformer layers to effectively capture the multiscale placement information and enhance congestion prediction accuracy. We first adopt convolutional neural networks (CNNs) to extract grid-based placement features and heterogeneous graph convolutional networks (HGCNs) to extract netlist information. To help the model understand the correlation between different modalities, we then propose an early feature fusion (EFF) to integrate netlist knowledge into multiscale placement features at multimodal interaction subspace. Besides, a deep feature fusion (DFF) method is proposed to further fuse multimodal features, which has multiple vision transformer layers based on adaptive attention enhancement technology. These layers include self-attention (SA) to boost intramodal features and cross-attention (CA) to perform cross-modal feature fusion on netlist and grid-based placement features. Finally, the output features of DFF are sent into the cascaded decoder to recover the congestion map by exploiting several upsampling layers and merging with EFF features. Compared with the existing state-of-the-art congestion prediction models, experimental results demonstrate that our model not only outperforms them in prediction accuracy, but also excels in reducing routing congestion when integrated into the placer DREAMPlace.

As interconnect delay increasingly becomes the primary source of chip delay, timing analysis in the very large-scale integration (VLSI) routing process is becoming more crucial. Concurrently, to maintain computational synchronization in the chip, the bounded-skew constraint must be introduced. Additionally, the issue of obstacle-avoiding has gained attention due to the presence of routing obstacles on the chip. Furthermore, the introduction of X-architecture enables more efficient utilization of routing resources. In this article, we propose an obstacle-avoiding X-architecture bounded-skew tree (BST) algorithm under timing slack constraints, which, for the first time, simultaneously considers timing slack, bounded-skew, obstacle-avoidance, and X-architecture in a unified framework. First, an effective preprocessing strategy is presented to support fast information retrieval for the subsequent strategies. Second, a BST construction strategy is developed to ensure compliance with skew constraints by consulting and updating a dedicated skew table. Third, a local worst negative slack (WNS) optimization strategy is designed to improve the WNS of critical paths by balancing wirelength (WL) and radius. Fourth, an obstacle-avoiding strategy is implemented to navigate around routing obstacles while minimizing unnecessary WL overhead. Finally, a path refinement strategy is designed to select routing structures with maximal edge sharing to replace the initial structure, thereby further optimizing WL. Experimental results demonstrate that the proposed algorithm significantly improves both WL and the key timing metric WNS, while satisfying obstacle-avoidance and bounded-skew constraints.

The expansion of the IC dimension is ushering in a more-than-Moore era, necessitating corresponding EDA tools. Existing TSV-based 3D placers focus on minimizing cuts, while burgeoning F2F-bonded ICs features dense interconnection between two planar die. Towards this novel structure, we proposed an integrated adaptation methodology upon mature one-die-based placement strategies. First, we instructively utilized a one-die placer to provide a statistical looking-ahead net diagnosis. The netlist henceforth shall be coarsened topologically and geometrically with a multi-level framework. Level by level, the partition will be refined according to a multi-objective gain formulation, including cut expectation, heterogeneous row height, and balanced cell distribution. Given the partition, we synchronized the behavior of analytical planar placers by balancing the density and wirelength objective function among asymmetric layers. Finally, the result will be further improved by heuristic bonding terminals’ detail placement and a post-place partition adjustment. Compared to the top three winners of the 2022 CAD Contest at ICCAD, experiment results show that our fine-grained fusion upon partitioning and placement gets the best normalized average wirelength with a fairly reasonable runtime under all 3D architectural constraints.

Placement is a critical step in the modern VLSI design flow, as it dramatically determines the performance of circuit designs. Most placement algorithms estimate the design performance with a half-perimeter wirelength (HPWL) and target it as their optimization objective. The wirelength model used by these algorithms limits their ability to optimize the internal routing topology, which can lead to discrepancies between estimates and the actual routing wirelength. This paper proposes an analytical placement algorithm to optimize the internal routing topology. We first introduce a differential wirelength model in the global placement stage based on an ideal routing topology RSMT. Through screening and tracing various segments, this model can generate meaningful gradients for interior points during gradient computation. Then, after global placement, we propose a cell refinement algorithm and further optimize the routing wirelength with swift density control. Experiments on ICCAD2015 benchmarks show that our algorithm can achieve a 3% improvement in routing wirelength, 0.8% in HPWL, and 23.8% in TNS compared with the state-of-the-art analytical placer.

Recently, hybrid-row-height designs have been introduced to achieve performance and area co-optimization in advanced nodes. Hybrid-row-height designs incur challenging issues to layout due to the heterogeneous cell and row structures. In this paper, we present an effective algorithm to address the hybrid-row-height placement problem in two major stages: (1) global placement, and (2) legalization. Inspired by the multi-channel processing method in convolutional neural networks (CNN), we use the feature extraction technique to equivalently transform the hybrid-row-height global placement problem into two sub-problems that can be solved effectively. We propose a multi-layer nonlinear framework with alignment guidance and a self-adaptive parameter adjustment scheme, which can obtain a high-quality solution to the hybrid-row-height global placement problem. In the legalization stage, we formulate the hybrid-row-height legalization problem into a convex quadratic programming (QP) problem, then apply the robust modulus-based matrix splitting iteration method (RMMSIM) to solve the QP efficiently. After RMMSIM-based global legalization, Tetris-like allocation is used to resolve remaining physical violations. Compared with the state-of-the-art work, experiments on the 2015 ISPD Contest benchmarks show that our algorithm can achieve 7%; shorter final total wirelength and $2.23 \times $ speedup.

Emerging applications in Printed Circuit Board (PCB) routing impose new challenges on automatic length matching, including adaptability for any-direction traces with their original routing preserved for interactiveness. The challenges can be addressed through two orthogonal stages: assign non-overlapping routing regions to each trace and meander the traces within their regions to reach the target length. In this paper, mainly focusing on the meandering stage, we propose an obstacle-aware detailed routing approach to optimize the utilization of available space and achieve length matching while maintaining the original routing of traces. Furthermore, our approach incorporating the proposed Multi-Scale Dynamic Time Warping (MSDTW) method can also handle differential pairs against common decoupled problems. Experimental results demonstrate that our approach has effective length-matching routing ability and compares favorably to previous approaches under more complicated constraints.

Placement is a critical stage for VLSI routability optimization. A placement engine without considering the layout congestion might lead to poor solutions with routing failures. This paper introduces a Coulomb force-based global placement framework that addresses global and local routing congestions. We first present a routing path-based cell padding strategy for local congestion mitigation. Then, we construct a routability-aware placement model that utilizes virtual Coulomb forces to eliminate crucial global congestion. Compared with a leading academic placer, RePlAce, and the advanced commercial tool, Innovus, the experimental results on industrial benchmark suites show that our proposed algorithm achieves the best routability within the shortest runtime.

As technology scales down, multi-cell spacing constraints are imposed by modern circuit designs. Previous works compromise solution quality to address the problem by transforming it into two-cell spacing constraints. In this paper, we propose a detailed placement algorithm considering multi-cell spacing constraints. First, an SAT-based multi-cell spacing violation reduction method is presented to reduce the number of violations with minimum displacement. Then, a window-based violation elimination method is adopted to resolve all the remaining violations. Finally, we refine the placement result with ILP to reduce the cell displacement. Compared with the state-of-the-art work, experimental results show that our algorithm achieves a 19% improvement in displacement and a 39% reduction in runtime.

Placement is a critical stage for VLSI timing closure. A global placer without considering timing delay might lead to inferior solutions with timing violations. This paper proposes an electrostatics-based timing optimization method for VLSI global placement. Simulating the optimal buffering behavior, we first present an analytical delay model to calculate each connection delay accurately. Then, a timing-driven block distribution scheme is developed to optimize the critical path delay while considering the path-sharing effect. Finally, we develop a timing-aware precondition technique to speed up placement convergence without degrading timing quality. Experimental results on industrial benchmark suites show that our timing-driven placement algorithm outperforms a leading commercial tool by 6.7% worst negative slack (WNS) and 21.6% total negative slack (TNS).

Adherence to design rule constraints, a cornerstone principle of Design for Manufacturability (DFM), is essential for ensuring successful fabrication in modern circuit design. As the foundries keep introducing more customization for better performance, new design rule challenges emerge with the device layers, such as implant layer constraints in the designs with multiple threshold voltages, and the trim poly layer constraints in the self-aligned double patterning (SADP). These constraints are typically tackled in the legalization stage. In addition, during the chip finishing, fillers are inserted for better manufacturability, such as a more uniform chip surface and a more robust power integrity. However, improper filler insertion might undermine the previous legalized layout. This paper presents a co-optimization framework in the legalization and filler insertion stage, which is extensible for other layer constraints. We model the filler insertion problem as a multi-branch tree and present a dynamic programming-based pre-pruning algorithm, which is also able to detect violations in the legalization stage. To reduce runtime, we additionally propose two violation detectors for legalization based on the look-up table (LUT) inference and greedy algorithm. Experimental results show that our filler insertion algorithm can significantly reduce the number of violations compared with state-of-the-art work. With our violation detectors in legalization, the co-optimization framework achieves better performance compared with the commercial tool.

A growing recognition of potential vulnerabilities to layout-level Hardware Trojan (HT) attacks has spurred significant research efforts aimed at enhancing the resilience of ICs against such threats. However, traditional hardware security has been predominantly concerned with defensive measures, often overlooking the original key metrics in physical design evaluation: power, performance, and area (PPA). This study introduces an automated methodology incorporating HT considerations into the practical physical design process. Utilizing a Bayesian optimization framework, it effectively navigates the operation of commercial physical implementation tools in the solution space of hyper-parameter settings. Innovative strategies inspired by mosaic techniques, such as cell shifting and buffer insertion, realize additional improvements in layout-level trojan prevention. Comparative evaluations have shown that our approach outperforms leading entries from the ISPD 2023 Contest in terms of PPA and HT prevention metrics, thereby providing significant insights into the synergy between these critical factors.

Static IR drop analysis is a fundamental and critical task in chip design since the IR drop will significantly affect the design's functionality, performance, and reliability. However, the process of IR drop analysis can be time-consuming, potentially taking several hours. Therefore, a fast and accurate IR drop prediction is paramount for reducing the overall time invested in chip design. In this paper, we propose a global and local attention-based Inception U-Net for static IR drop prediction. Our U-Net incorporates the Transformer, CBAM, and Inception architectures to enhance its feature capture capability at different scales and improve the accuracy of predicted IR drop. Moreover, we propose 4 new features, which enhance our model with richer information. Finally, to balance the sampling probabilities across different regions in one design, we propose a series of novel data spatial adjustment techniques, with each batch randomly selecting one of them during training. Experimental results demonstrate that our proposed algorithm can achieve the best results among the winning teams of the ICCAD 2023 contest and the state-of-the-art algorithms.

As field-programmable gate array (FPGA) architectures continue to evolve and become more complex, the heterogeneity and clock constraints imposed by modern FPGAs have posed significant challenges to FPGA placement. This article proposes a high-performance placement engine for modern large-scale FPGAs with heterogeneity and clock constraints. To improve efficiency and scalability, we develop a clustering method considering both internal/external connectivity and the balance of block types to build the hierarchy. In each hierarchy level, we propose a hybrid penalty and augmented Lagrangian method (HPALM) to convert the FPGA global placement with heterogeneity and clock constraints into a series of unconstrained optimization subproblems, then use the Adam method to solve each subproblem. In particular, we prove that the HPALM is globally convergent for global placement. Besides, a matching-based IP block legalization is developed to legalize the DSPs and RAMs, and a multistage packing is presented to cluster LUTs and FFs into HCLBs. Finally, we propose a history-based legalization to legalize CLBs in an FPGA, and a simulated-annealing-based detailed placement is presented to reduce the wirelength while maintaining legality. Compared with the state-of-the-art works, experimental results based on the ISPD 2017 contest benchmarks show that the proposed algorithm can achieve the shortest routed wirelength in a reasonable runtime.

Ordered Escape Routing (OER) problem, which is an NP-hard problem, is critical in PCB design. Primary methods based on integer linear programming (ILP) or heuristic algorithms work well on small-scale PCBs with fewer pins. However, when dealing with large-scale instances, the performance of ILP strategies suffers dramatically as the number of variables increases due to time-consuming preprocessing. As for heuristic algorithms, ripping-up and rerouting is adopted to increase resource utilization, which frequently causes time violation. In this paper, we propose an efficient ILP-based routing engine for dense PCB to simultaneously minimize wiring length and runtime, considering the specific routing constraints. By weighting the length, we first model the OER problem as a special network flow problem. Then we separate the non-crossing constraint from typical ILP modeling to reduce the number of integral variables greatly. In addition, considering the congestion of routing resources, the ILP method is proposed to detect congestion. Finally, unlike the traditional schemes that deal with negotiated congestion, our approach works by reducing the local area capacity and then allowing the global automatic optimization of congestion. Compared with the state-of-the-art work, experimental results show that our algorithm can solve cases in larger scale in high routing quality of less length and reduce routing time by 76%.

Placement is a critical stage in VLSI physical design, especially for routability optimization. Due to the large scale and high integration introduced by the advanced semiconductor manufacturing technology, there remains a significant challenge in routability in the placement stage, which will affect the subsequent routing process. This paper proposes a placement framework, called PUFFER, to optimize routability by cell padding and strategy exploration. The framework first estimates congestion by imitating the behaviors of routing detours and clustered cell spreading. Then it calculates cell padding based on multiple features inspired by the characteristics of convolutional and graph neural networks. Besides, it applies a Bayesian-based method to explore a better placement strategy. Compared with a commercial tool and the state-of-the-art academic RePlAce placer, experiments on industrial benchmarks show that our framework achieves the best routability on average, with a 2.7× speedup over the commercial tool.

In modern circuits, mixed-cell-height standard cells have been prevailing to meet various requirements and achieve better trade-offs among timing, power, and routability. Besides, the constraints of the minimum-implant-area (MIA) and drain-to-drain-abutment (DDA) arise as emerging challenges at advanced technology nodes. In this paper, we present an algorithm to address the mixed-cell-height placement problem with MIA and DDA constraints in three major stages: (1) post-global placement, (2) legalization, and (3) detailed placement. In the post-global stage, we first align mixed-cell-height standard cells to the desired rows by conjugate gradient method with dynamic step size and then reorder them by the shortest path algorithm to distribute the source nodes evenly. In the legalization stage, we propose a two-step combination algorithm to cluster cells and repack the clusters to minimize the wirelength, after which we presented a queue based method to address the inter-row MIA violations. In the detailed placement, an MIA-aware DDA reduction algorithm is adopted after multi-region partitioning to eliminate DDA violations without introducing MIA violations. Experimental results show that our algorithm can resolve all MIA and almost all DDA violations with a 13% reduction in displacement, a 4% reduction in HPWL, and 25% less runtime compared with the state-of-the-art work.

Escape routing is a critical problem in PCB routing, and its quality greatly affects the PCB design cost. Unlike the traditional escape routing that works mainly for the BGA package with unique line width and space, this paper presents a high-performance escape routing algorithm to handle problems with variable design rules and manual constraints, including variable line widths/spaces, the neck mode of wires, and the pad entry for differential pairs. We first propose a novel obstacle-avoiding method to project pins to the boundary and construct a channel projection graph. We then construct a bi-projection graph and propose a matching-based hierarchical sequencing algorithm to consider manual constraints. We perform global routing for each pin/differential pair by congestion-avoiding path initialization and rip-up and reroute path optimization. Finally, we complete detailed routing in every face, ensuring the wire angle and pad entry constraints. Experimental results show that our algorithm can achieve 100% routability without any design rule violation for all given industrial PCB instances, while two state-of-the-art routers cannot complete routing.

PCB routing becomes time-consuming as the complexity of PCB design increases. Unlike traditional schemes that treat the two essential PCB routing processes separately, namely, escape and bus routing, we consider the continuity between them and present a golden-pin-based routing scheme to find the desired solution with angle and topology constraints. Further, conventional rip-up and reroute methods are often ineffective and inefficient for congestion alleviation and routability optimization. We construct a component graph by modeling components as vertices and applying the minimum weight vertex covering method to improve the routability. A self-adaptable ordering method is presented for escape routing to arrange the pin order on the component boundary, guaranteeing successful bus routing. In addition, escape routing is performed based on a disjoint path method. We construct a dynamic Hanan grid in bus routing and utilize a novel congestion adjustment technique to improve solution quality. Compared with FreeRouting and Allegro, the experiment results show that our algorithm achieves high routability and a significant 90% runtime reduction.

Modern circuits often contain standard cells of different threshold voltages (multi-VTs) to achieve a better trade-off between timing and power consumption. Due to the heterogeneous cell structures, the multi-VTs cells impose various implant layer constraints, further complicating the already time-consuming filler cell insertion process. In this paper, we present a fast and near-optimal algorithm to solve the filler insertion problem with complex implant layer rules and minimum filler width constraints. We first propose an inference-driven detecting algorithm to identify each design rule violation accurately. Then, a dynamic-programming-based insertion method is developed to reduce the implant layer violations. Finally, we design a contour-driven violation refinement strategy to further improve manufacturability. Experimental results show that our algorithm can reduce the number of violations significantly compared with state-of-the-art works. Besides, with our identifier in the legalization stage, we can avoid conflicts in advance and solve almost all violations after filler insertion in industrial cases.

Existing implementations of transformer networks by field-programmable gate array (FPGA) focus only on attention computation, or suffer from fixed model structure without flexibility. In this article, we propose an FPGA-based overlay processor, named Transformer-OPU for general accelerations of transformer networks. Experimental result shows that our Transformer-OPU achieves 5.19-15.06× and 1.14-2.89× speedup compared with CPU and GPU, respectively. We also observe 1.10-2.47× better latency compared with previously customized FPGA accelerators, and is 1.45× faster than NPE.

Existing accelerators for transformer networks with field-programmable gate array (FPGA) either focus only on attention computation or suffer from fixed data streams without flexibility. Moreover, compression and approximation methods of transformer networks have the potential for further optimization. In this article, we propose a low-latency FPGA-based overlay processor, named LTrans-OPU for general accelerations of transformer networks. Specifically, we design a domain-specific overlay architecture, including a computation unit for matrix multiplication of arbitrary dimensions. An instruction set customized for our overlay architecture is also introduced, dynamically controlling data flows by generated instructions. In addition, we introduce a hybrid pruning method common to various transformer networks, along with an efficient non-linear function approximation method. Experimental results show that our design is rather competitive and has low latency. LTrans-OPU achieves 11.10-32.20× speedup compared with CPU and 2.44-6.18 × latency reduction compared with GPU. We also observe 2.36-12.43 × lower latency compared with customized FPGA/ASIC accelerators, and can be 3.10× faster than NPE.

Transformer-based models suffer from large num-ber of parameters and high inference latency, whose deployment are not green due to the potential environmental damage caused by high inference energy consumption. In addition, it is difficult to deploy such models on devices, especially on resource constrained devices such as FPGA. Various model pruning methods are proposed to shrink the model size and resource consumption, so as to fit the models on hardware. However, such methods often introduce floating point of operations (FLOPs) as an agent of hardware performance, which is not accurate. Furthermore, structural pruning methods are always in a single head-wise or layer-wise pattern, which fails to compress the models to the extreme. To resolve the above issues, we propose a green BERT deployment method on FPGA via hardware-aware and hybrid pruning, named g-BERT. Specifically, two hardware-aware metrics are introduced by High Level Synthesis (HLS) to evaluate the latency and power consumption of inference on FPGA, which can be optimized directly while pruning. Moreover, we simultaneously consider pruning of heads and full encoder layers. To efficiently find the optimal structure, g-BERT applies differentiable neural architecture search (NAS) with a special 0–1 loss function. Compared with the BERT-base, g-BERT achieves$2.1\times$speedup,$1.9\times$power consumption reduction and$1.8\times$model size reduction with comparable accuracy, on par with the state-of-the-art methods.

There are already some works on accelerating transformer networks with field-programmable gate array (FPGA). However, many accelerators focus only on attention computation or suffer from fixed data streams without flexibility. Moreover, their hardware performance is limited without schedule optimization and full use of hardware resources. In this article, we propose a flexible and efficient FPGA-based overlay processor, named FET-OPU. Specifically, we design an overlay architecture for general accelerations of transformer networks. We propose a unique matrix multiplication unit (MMU), which consists of a processing element (PE) array based on modified DSP-packing technology and a FIFO array for data caching and rearrangement. An efficient non-linear function unit (NFU) is also introduced, which can calculate arbitrary single input non-linear functions. We also customize an instruction set for our overlay architecture, dynamically controlling data flows by instructions generated on the software side. In addition, we introduce a two-level compiler and optimize the parallelism and memory allocation schedule. Experimental results show that our FET-OPU achieves 7.33-21.27× speedup and 231× less energy consumption compared with CPU, and 1.56-4.08× latency reduction with 5.85-66.36× less energy consumption compared with GPU. Furthermore, we observe 1.56-8.21× better latency and 5.28-6.24× less energy consumption compared with previously customized FPGA/ASIC accelerators and can be 2.05× faster than NPE with 5.55× less energy consumption.

Symmetric Sparse Matrix-Vector Multiplication (SSpMV) is a prevalent operation in numerous application domains (e.g., physical simulations, machine learning, and graph processing). Existing researches focus on the SSpMV implementation and its improvement on high-performance computing platforms but ignore the resource-limited edge platforms due to the main challenges: memory access overload and limited computing parallelism feasibility. To this end, this paper proposes an embedded-FPGA-based hardware accelerator for SSpMV, called eSSpMV. We first propose an optimized data format, named Symmetric Compressed Sparse Row (SCSR), to reduce memory consumption. Moreover, a fully-pipelined computation unit is proposed to be compatible with the optimized data format. Experimental results show that eSSpMV outperforms the state-of-the-art FPGA implementation for 2.9 x speedup, while still achieving a computing resource reduction of 39.3% and 32.3% for LUT and DSP, respectively. As for edge CPU and GPU implementations, eSSpMV achieves 9.3x speedup over CPU while acquiring 13.1 x better power latency product than GPU.

Placement and routing are two critical problems in very large-scale integration physical design. However, there may be out-of-sync between the two problems considering congestion and wirelength. Therefore, it is desirable to design an efficient and highly coupled placement and routing engine to narrow the gap and minimize the mismatch between placement and routing. This article proposes an incremental 3-D global routing engine considering cell movement and complex routing constraints to relocate cells and reroute nets. We first apply a queue-based congestion-aware 3-D maze routing with routing height restriction to improve the initial routing solution. Efficient multinet-based location estimation is then presented to find the best location for each cell in multiple cell movement rounds. In each step of cell movement, we reroute nets for all candidate cell locations in parallel using a guided stack-based 3-D routing algorithm while considering the routing constraints. Finally, we adopt an edge-adjusting technique to improve the routed wirelength further. Compared with the champion of the 2020 CAD Contest at ICCAD (Hu et al., 2020) and the state-of-the-art works, experiment results based on the contest benchmarks show that our proposed algorithm achieves the best routing wirelength and competitive runtime without maximum cell movement constraint.

As design complexity keeps increasing, the 2.5D field-programmable gate array (FPGA) with large logic capacity has become popular in modern circuit applications. A 2.5D FPGA consists of multiple dies connected through super long lines (SLLs) on an interposer. Each die contains heterogeneous logic blocks and ASIC-like clocking architectures to achieve better skew and timing. Existing works consider these problems separately and thus may lead to serious timing issues or routing failure. This article presents an analytical placement algorithm for the 2.5D FPGA to simultaneously minimize the number of inter-die SLL signals and intra-die clocking violations. Using a lifting dimension technique, we first formulate the 2.5D global placement problem as a three-dimensional continuous and differential minimization problem, where the SLL-aware block distribution is modeled by 3D Poisson’s equation and directly solved to obtain an analytical solution. Then, we further reformulate the minimization problem as a separable optimization problem with linear constraints. Based on the proximal alternating direction method of multipliers optimization method, we efficiently optimize the separable subproblems one by one in an alternating fashion. Finally, clock-aware legalization and detailed placement are applied to legalize and improve our placement results. Compared with the state-of-the-art works, experimental results show that our algorithm can resolve all clocking constraints and reduce the number of SLL crossing signals by 36.9% with similar wirelength in a comparable running time.

Modern circuit layout centerline extraction is an essential step in estimating the parasitic inductance and verifying the layout performance in mask verification. As the continued feature size shrinking and the complexity of modern circuit design keeps growing, heterogeneous layout centerline extraction has become even more challenging. In this paper, we first formulate a Voronoi diagram-based problem transformation to collect all centerline points. Then, a graph-based initial centerline generation algorithm is presented to handle all invalid centerline points effectively. Finally, a heterogeneity-aware centerline optimization method is proposed to generate optimized design-violation-free centerline results for irregular structures. Compared with the state-of-the-art commercial 3D-RC parasitic parameter extraction tool RCExplorer and the 1st place in the 2019 EDA Elite Challenge Contest, experimental results show that our algorithm achieves the best average precision ratio of 99.7% on centerline extraction while satisfying all design constraints.

Routability estimation identifies potentially congested areas in advance to achieve high-quality routing solutions. To improve the routing quality, this paper presents a deep learning-based congestion estimation algorithm that applies the estimation to a global router. Unlike existing methods based on traditional compressed 2D features for model training and prediction, our algorithm extracts appropriate 3D features from the placed netlists. Furthermore, an improved RUDY (Rectangular Uniform wire DensitY) method is developed to estimate 3D routing demands. Besides, we develop a congestion estimator by employing a U-net model to generate a congestion heatmap, which is predicted before global routing and serves to guide the initial pattern routing of a global router to reduce unexpected overflows. Experimental results show that the Pearson Correlation Coefficient (PCC) between actual and our predicted congestion is high at about 0.848 on average, significantly higher than the counterpart by 21.14%. The results also show that our guided routing can reduce the respective routing overflows, wirelength, and via count by averagely 6.05%, 0.02%, and 1.18%, with only 24% runtime overheads, compared with the state-of-the-art CUGR global router that can balance routing quality and efficiency very well. In particular, our work provides a new generic machine learning model for not only routing congestion estimation demonstrated in this paper, but also general layout optimization problems.

Reference placement is promising to handle the increasing complexity in PCB design. We model the netlist into a graph and use a subgraph matching algorithm to find the isomorphism of the placed template in component combination to reuse the placement. The state-of-the-art VF3 algorithm can achieve high matching accuracy while suffering from high computation time in large-scale instances. Thus, we propose the D2BS algorithm to guarantee matching quality and efficiency. We build and filter the candidate set (CS) according to designed features to construct the CS structure. In the CS optimization, a graph diversity tolerance strategy is adopted to achieve inexact matching. Then, hierarchical match is developed to search the template embeddings in the CS structure guided by branch backtracking and matched nodes snatching. Experimental results show that D2BS outperforms VF3 in accuracy and runtime, achieving 100% accuracy on PCB instances.

The fast-growing capacity and complexity are challenging for FPGA global placement. Besides, while many recent studies have focused on the eDensity-based placement as its great efficiency and quality, they suffer from redundant frequency translation. This paper presents a CNN-inspired analytical placement algorithm to effectively handle the redundant frequency translation problem for large-scale FPGAs. Specifically, we compute the density penalty by a fully-connected propagation and gradient to a discrete differential convolution backward. With the FPGA heterogeneity, vectorization plays a vital role in self-adjusting the density penalty factor and the learning rate. In addition, a pseudo net model is used to further optimize the site constraints by establishing connections between blocks and their nearest available regions. Finally, we formulate a refined objective function and a degree-specific gradient preconditioning to achieve a robust, high-quality solution. Experimental results show that our algorithm achieves an 8% reduction on HPWL and 15% less global placement runtime on average over leading commercial tools.

With the increasing complexity of the field-programmable gate array (FPGA) architecture, heterogeneity and clock constraints have greatly challenged FPGA placement. In this paper, we present a high-performance placement algorithm for large-scale heterogeneous FPGAs with clock constraints. We first propose a connectivity-aware and type-balanced clustering method to construct the hierarchy and improve the scalability. In each hierarchy level, we develop a novel hybrid penalty and augmented Lagrangian method to formulate the heterogeneous and clock-aware placement as a sequence of unconstrained optimization subproblems and adopt the Adam method to solve each unconstrained optimization subproblem. Then, we present a matching-based IP blocks legalization to legalize the RAMs and DSPs, and a multi-stage packing technique is proposed to cluster FFs and LUTs into HCLBs. Finally, history-based legalization is developed to legalize CLBs in an FPGA. Based on the ISPD 2017 clock-aware FPGA placement contest benchmarks, experimental results show that our algorithm achieves the smallest routed wirelength for all the benchmarks among all published works in a reasonable runtime.

Placement and routing are typically defined as two separate problems to reduce the design complexity. However, such a divide-and-conquer approach inevitably incurs the degradation of solution quality due to the correlation/objectives of placement and routing are not entirely consistent. Besides, with various constraints (e.g., timing, R/C characteristic, voltage area, etc.) imposed by advanced circuit designs, bridging the gap between placement and routing while satisfying the advanced constraints has become more challenging. In this paper, we develop a robust global routing engine with high-accuracy cell movement under advanced constraints to narrow the gap and improve the routing solution. We first present a routing refinement technique to obtain the convergent routing result based on fixed placement, which provides more accurate information for subsequent cell movement. To achieve fast and high-accuracy position prediction for cell movement, we construct a lookup table (LUT) considering complex constraints/objectives (e.g., routing direction and layer-based power consumption), and generate a timing-driven gain map for each cell based on the LUT. Finally, based on the prediction, we propose an alternating cell movement and cluster movement scheme followed by partial rip-up and reroute to optimize the routing solution. Experimental results on the ICCAD 2020 contest benchmarks show that our algorithm achieves the best total scores among all published works. Compared with the champion of the ICCAD 2021 contest, experimental results on the ICCAD 2021 contest benchmarks show that our algorithm achieves better solution quality in shorter runtime.

Metal fill insertion has become an essential step in reducing dielectric thickness variation and improving pattern uniformity, which is important in mitigating process variations, thereby achieving better manufacturing yield. However, metal fills could induce coupling capacitance, which is not often considered in existing works that typically focus more on pattern density uniformity, incurring significant problems in timing closure. However, it is a great challenge to consider three types of capacitances (i.e., area, fringe, and lateral capacitances) with design rules and density constraints at the fill insertion stage simultaneously. This article presents an efficient timing-aware fill insertion algorithm for minimizing the total capacitance and fill amount, considering the density constraints. First, we present an initial metal fill insertion and design-rule-aware legalization to obtain an initial fill insertion solution quickly. Second, from critical conductors to powers/grounds in a circuit, we divide conductors into different equivalent paths and then construct a capacitance graph to reduce the capacitance of each equivalent path globally. Third, we propose a density-aware coupling capacitance optimization method and a fast Monte Carlo-based fill selection to further reduce the coupling capacitance between any pair of conductors. Finally, we present a density-aware fill deletion method to reduce the fill amount. We evaluate the performance of our algorithm on the benchmarks of the 2018 CAD Contest at ICCAD and its official contest evaluator. Compared with the first-place team of the contest and the state-of-the-artwork, experimental results show that our algorithm achieves the lowest total capacitance and the least fill amount in a comparable runtime.

Fogging and proximity effects (FPEs) are two major factors that cause inaccurate exposure and layout pattern distortions in e-beam lithography. In this article, we propose an analytical placement algorithm that considers both FPEs. We formulate the global placement problem as a separable minimization problem with linear constraints, where different objectives can be tackled one by one in an alternating fashion. Then, we propose a novel proximal group alternating direction method of multipliers (ADMM) to solve the separable minimization problem with two subproblems, where the first subproblem (associated with wirelength and density) is solved by the steepest descent method without line search, and the second one (associated with the FPEs) is handled by an analytical scheme. We prove the property of global convergence of the proximal group ADMM method. Finally, the FPEs-aware legalization and detailed placement are employed to legalize and improve the placement result. The experimental results show that our algorithm is effective and efficient for the addressed problem. Our algorithm achieved 5.7% smaller fogging variation, 6.8% lower proximity variation, and 5.4% lower runtime with a minor wirelength overhead compared with the state-of-the-art work.

Mixed-cell-height standard cells are prevailingly used in advanced technologies to achieve better design tradeoffs among timing, power, and routability. As feature size decreases, the placement of cells with multiple threshold voltages may violate the complex minimum-implant-area (MIA) layer rule arising from the limitations of patterning technologies. Existing works consider the mixed-cell-height placement problem only during legalization or handle the MIA constraints during detailed placement. In this article, we address the mixed-cell-height placement problem with MIA constraints in two major stages: 1) post-global placement (Post-GP) and 2) MIA-aware legalization. In the Post-GP stage, we first present a continuous and differentiable cost function to address the Vdd/Vss alignment constraints and add weighted pseudonets to MIA-violation cells dynamically. Then, we propose a proximal optimization method based on the given global placement result to simultaneously consider Vdd/Vss alignment constraints, MIA constraints, cell distribution, cell displacement, and total wirelength. In the MIA-aware legalization stage, we develop a graph-based method to cluster cells of specific threshold voltages and apply a strip-packing-based binary linear programming to reshape cells. Then, we propose a matching-based technique to resolve intrarow MIA violations and reduce filler insertion. Furthermore, we formulate inter-row MIA-aware legalization as a quadratic programming problem, which is efficiently solved by a modulus-based matrix splitting iteration method. Finally, MIA-aware cell allocation and refinement are performed to further improve the result. Experimental results show that without any extra area overhead, our algorithm still can achieve 5.4% shorter final total wirelength than the state-of-the-art work.

Along with device scaling, the drain-to-drain abutment (DDA) and fence region constraints arise as emerging challenges in modern circuit designs, incurring additional difficulties, especially for designs with mixed-cell-height standard cells which have prevailed in advanced technology. This article presents the first work to address the mixed-cell-height placement problem considering the DDA and fence region constraints from post-global placement throughout the detailed placement. Our algorithm consists of three major stages: 1) preprocessing; 2) legalization; and 3) detailed placement. At the preprocessing stage, we align cells to the desired rows that meet the region constraint, considering the total cell displacement and the distribution ratio of source nodes to drain nodes simultaneously. After deciding the cell ordering of every row, we first propose an interval concept to handle fixed macros and fence regions and then apply the robust modulus-based matrix splitting iteration method to remove all cell overlaps with minimized total displacement at the legalization stage. For detailed placement, unlike the existing works that can handle the DDA constraint only for single rows, we propose a satisfiability-based approach that considers the whole layout to fix the DDA violations more effectively. Besides, we further present an integer linear program (ILP)-based method to optimize the cell displacement without increasing the DDA violations. Compared with a shortest-path method, experimental results show that our proposed algorithm can significantly reduce cell violations, average cell displacement, and maximum cell displacement, in a comparable runtime.

As interconnects dominate circuit performance in modern field programmable gate arrays (FPGAs), placement becomes a crucial stage for timing closure. Traditional FPGA placers seldom consider the timing constraints and, thus, may lead to illegal routing solutions. In this article, we present an incremental timing-driven placement flow for advanced FPGAs. First, a timing-based global placement strategy is designed to guide heterogeneous blocks to desired locations with satisfied timing constraints. Then, a timing-aware packing algorithm is developed to mitigate the design complexity while improving the timing results. Finally, we propose a critical path-based optimization method to generate optimized layout without timing violations. We evaluate our algorithm based on industrial circuits using an advanced FPGA device. The experimental results show that our placer achieves a 5.1% improvement in worst slack and produce placements that require 16.7% less time to route when compared with the leading commercial tool Xilinx Vivado.

High-level synthesis (HLS) tools have gained great attention in recent years because it emancipates engineers from the complicated and heavy hardware description language writing and facilitates the implementations of modern applications (e.g., deep learning models) on Field-programmable Gate Array (FPGA) , by using high-level languages and HLS directives. However, finding good HLS directives is challenging, due to the time-consuming design processes, the balances among different design objectives, and the diverse fidelities (accuracies of data) of the performance values between the consecutive FPGA design stages. To find good HLS directives, a novel automatic optimization algorithm is proposed to explore the Pareto designs of the multiple objectives while making full use of the data with different fidelities from different FPGA design stages. Firstly, a non-linear Gaussian process (GP) is proposed to model the relationships among the different FPGA design stages. Secondly, for the first time, the GP model is enhanced as correlated GP (CGP) by considering the correlations between the multiple design objectives, to find better Pareto designs. Furthermore, we extend our model to be a deep version deep CGP (DCGP) by using the deep neural network to improve the kernel functions in Gaussian process models, to improve the characterization capability of the models, and learn better feature representations. We test our design method on some public benchmarks (including general matrix multiplication and sparse matrix-vector multiplication) and deep learning-based object detection model iSmart2 on FPGA. Experimental results show that our methods outperform the baselines significantly and facilitate the deep learning designs on FPGA.

The modern FPGA placement problem has become much more challenging than ever with various emerging design constraints, such as the location (including relative location (RLOC) and location range) and chain constraints, which have not been considered in the literature. In this paper, we propose a combinatorial algorithm for FPGA legalization with location and chain constraints. We first identify a virtual range to cluster an instance with the RLOC constraint and formulate minimum cost integer linear programming. Besides, we use an adaptive algorithm to deal with the chain-aware legalization problem for better quality and runtime trade-offs. Finally, a legalization algorithm based on minimum cost maximum flow (MCMF) is used to improve the solution quality further. Compared with the state-of-the-art work, experimental results show that our proposed algorithm can achieve respectively 4.4% and 4.9% smaller average and maximum movements, 1.7% smaller routed wirelength, and 7.6% shorter routing runtime

With the continued feature-size shrinking in modern circuit designs, the layout performance estimation and parasitic import calculation based on the extracted centerline result play an important role in mask verification. Most previous works on layout centerline extraction focus on identifying the connectivity among the devices in a mask layout, with few ones collecting accurate centerline information for mask verification while considering design constraints. In this paper, we first formulate the centerline extraction problem as a Voronoi diagram to collect centerline points. Then, we present a graph-based invalid centerline removal algorithm to generate an initial centerline result. Finally, a complexity-driven centerline optimization method is proposed to further optimize the centerline while considering design constraints. Compared with the commercial 3D-RC parasitic parameter extraction tool RCExplorer and the 1st place in the 2019 EDA Elite Challenge Contest, experimental results show that our algorithm achieves the highest average precision ratio of 99.8% on centerline extraction while satisfying all design constraints in the shortest runtime.

A parallel simulation that partitions a large circuit into sub-circuits is widely used to reduce simulation runtime. To achieve higher simulation throughput, we shall consider signal directions, and thus the final partitioning solution must be acyclic. In this paper, we model a circuit as a directed graph and consider acyclic graph partitioning to minimize edge cuts. This problem differs from the traditional partitioning problem because of the additional acyclicity constraint. Unlike traditional heuristics that tend to be trapped in local minima, especially for large graphs, we present a novel discrete dynamic filled function algorithm for the acyclic graph partitioning problem. Our algorithm can guarantee convergence and effectively move from one discrete local minimizer to another better one. Experimental results show that our algorithm achieves 8% average cutsize reduction over the state-of-the-art works in a comparable runtime.

The data imbalance problem often occurs in nanometer VLSI applications, where normal cases far outnumber error ones. Many imbalanced data handling methods have been proposed, such as oversampling minority class samples and downsampling majority class samples. However, existing methods focus on improving the quality of minority classes while causing quality deterioration of majority ones. In this paper, we propose a two-stage classifier to handle the data imbalance problem. We first develop an iterative neural network framework to reduce false alarms. Then the oversampling method on a final classification network is applied to predict the two classes better. As a result, the data imbalance problem is well handled, and the quality deterioration of majority classes is also reduced. Since the iterative stage does not change any existing network structure, any convolutional neural network can be used in the framework. Compared with the state-of-the-art imbalanced data handling methods, experimental results on the hotspot detection problem show that our two-stage classification method achieves the best prediction accuracy and reduces false alarms significantly.

With feature size scaling and complexity increase of circuit designs, hotspot detection has become a significant challenge in the very-large-scale-integration (VLSI) industry. Traditional detection methods, such as pattern matching and machine learning, have been made a remarkable progress. However, the performance of classifiers relies heavily on reference layout libraries, leading to the high cost of lithography simulation. Querying and sampling qualified candidates from raw datasets make active learning-based strategies serve as an effective solution in this field, but existing relevant studies fail to take sufficient sampling criteria into account. In this paper, embedded in pattern sampling and hotspot detection framework, an entropy-based batch mode sampling strategy is proposed in terms of calibrated model uncertainty and data diversity to handle the hotspot detection problem. Redundant patterns can be effectively avoided, and the classifier can converge with high celerity. Experiment results show that our method outperforms previous works in both ICCAD2012 and ICCAD2016 Contest benchmarks, achieving satisfactory detection accuracy and significantly reduced lithography simulation overhead.

Placement and routing are two key problems in VLSI physical design. However, there may be out of sync between the two problems with congestion and routing resources. Therefore, it is desirable to design an efficient and highly coupled placement and routing engine. This paper proposes an incremental 3D global routing engine considering cell movement and complex routing constraints to relocate cells and reroute nets. We develop an efficient movement evaluation method to find desired locations and estimated routing resources for each cell. Then, we adopt an iterative approach to move cells to reduce routing resources. To reduce the time consumption of rerouting, we propose two technologies (searching space reduction and data structure optimization) to speed up the rerouting process. Compared with the participating teams at the 2020 CAD Contest at ICCAD based on the contest benchmarks, experiment results show that our proposed algorithm achieves the best runtime and routing resources while satisfying all the routing constraints.

Modern FPGAs often contain heterogeneous architectures and clocking resources which must be considered to achieve desired solutions. As the design complexity keeps growing, placement has become critical for FPGA timing closure. In this paper, we present an analytical placement algorithm for heterogeneous FPGAs to optimize its worst slack and clock constraints simultaneously. First, a heterogeneity-aware and memory-friendly delay model is developed to accurately and rapidly assess each connection delay. Then, a two-stage clock region refinement method is presented to effectively resolve the clock and resource violations. Finally, we develop a novel timing-based co-optimization method to generate optimized placement without any clocking violations. Compared with the state-of-the-art placer based on the advanced commercial tool Xilinx Vivado 2019.1 with the Xilinx 7 Series FPGA architecture, our algorithm achieves the best worst slack and routed wirelength while satisfying all clock constraints.

High-level synthesis (HLS) tools have gained great attention in recent years because it emancipates engineers from the complicated and heavy hardware description language writing, by using high-level languages and HLS directives. However, previous works seem powerless, due to the time-consuming design processes, the contradictions among design objectives, and the accuracy difference between the three stages (fidelities). To find good HLS directives, in this paper, a novel correlated multi-objective non-linear optimization algorithm is proposed to explore the Pareto solutions while making full use of data from different fidelities. A non-linear Gaussian process is proposed to model relationships among the analysis reports from different fidelities for the same objective. For the first time, correlated multivariate Gaussian process models are introduced into this domain to characterize the complex relationships of multiple objectives in each design fidelity. A tree-based method is proposed to erase invalid solutions and obviously non-optimal solutions. Experimental results show that our non-linear and pioneering correlated models can approximate the Pareto-frontier of the directive design space in a shorter time with much better performance and good stability, compared with the state-of-the-art.

This paper describes the latest release of the DATC Robust Design Flow (RDF), RDF-2021, which has several key additions to expand its horizons. The Chisel/FIRRTL compiler is now part of DATC RDF, enabling support of recent hardware generator designs written in Chisel. Logic locking through RTL obfuscation, an updated ABC synthesis flow, and DFT support are other notable updates to the RDF. A Bookshelf-LEF/DEF converter powered by OpenDB is also added into DATC RDF's inventory as an enabler of robust benchmark conversion. We also describe efforts toward open metrics standards and datasets for machine learning (ML) applications and smart tuning of the design flow, as well as expansion of public analysis calibration data. Our paper closes with future research directions related to DATC's efforts.

Modern electron-beam lithography (EBL) suffers from the long-range fogging effect that incurs undesired excessive exposure and thus layout pattern distortions. In this article, we propose an analytical placement algorithm to tackle the fogging effect. The underlying idea is to place standard cells, guided by our efficient, yet reasonably accurate fogging effect model, to minimize the fogging variation during placement, and thus the effect can be corrected by reducing dosage uniformly over the chip. We derive a fogging source modeling and further develop an efficient, accurate evaluation scheme to estimate the fogging effect by the fast Gauss transform with the Hermite expansion. The scheme achieves a 30.2X speedup over the traditional convolution computation, with only about 2.35% absolute average errors, which enables the iterative evaluation and variation minimization of the effect during global placement. We also develop fogging-aware legalization and detailed placement to further optimize the placement quality, while limiting fogging variation. The experimental results show that our algorithm can effectively reduce the fogging variation by 35.4%, while maintaining high wirelength quality, at reasonable runtime.

Mixed-cell-height circuits have prevailed in advanced technology to address various design requirements. Along with device scaling, complex minimum-implant-area (MIA) constraints arise as an emerging challenge in modern circuit designs, adding to the difficulties in mixed-cell-height placement. Existing MIA-aware detailed placement with single-row-height standard cells is insufficient for mixed-cell-height designs: 1) filler insertion, typically used to resolve MIA violations, might incur unaffordable area and wirelength overheads and 2) mixed-height-cell perturbation could cause severe inter-row MIA violations. This article addresses the mixed-cell-height detailed placement problem considering both intra- and inter-row MIA constraints. We first fix intrarow violations by clustering violating mixed-height cells of the same threshold voltage, and then perturb each cluster to obtain a desired cell permutation by applying an efficient, optimal dynamic-programming-based algorithm for a special case and Algorithm DLX for general ones, where a provably constant performance ratio for a mixed-cell-height reshaping problem can be achieved. With a network-flow-based formulation, remaining violating cells are placed in appropriate filler-insertion positions to fix cell violations and minimize area. After performing mixed-cell-height detailed placement, we finally fix inter-row violations by shifting violating cells in minimum displacement. Experimental results show that our algorithm can efficiently solve all MIA violations without any extra area overhead.

Modern circuits often contain standard cells of different row heights to meet various design requirements. Taller cells give larger drive strengths and higher speed at the cost of larger areas and power. Multi-row height standard cells incur challenging issues for layout designs, especially the mixed-cell-height legalization problem with heterogeneous cell structures. Honoring the good cell positions from global placement, we present in this article a robust modulus-based matrix splitting iteration method (RMMSIM) to solve the mixed-cell-height legalization problem. Fixing the cell ordering from global placement and relaxing the right-boundary constraints, our proposed method first converts the problem into an equivalent linear complementarity problem (LCP), and then properly splits the matrices in the LCP so that the RMMSIM can solve the LCP optimally. The RMMSIM effectively explores the sparse characteristic of a circuit, and takes only linear time per iteration; as a result, it can solve the QP very efficiently. Finally, an allocation scheme for illegal cells is used to align such cells to placement sites on rows and fix the placement of out-of-right-boundary cells, if any. Experimental results show the effectiveness and efficiency of our proposed algorithm. In addition, the RMMSIM convergence and optimality are theoretically proved and empirically validated. In particular, this article provides a new RMMSIM formulation for various optimization problems that require solving large-scale convex quadratic programming problems efficiently.

With the increasing design requirements of modern circuits, a standard-cell library often contains cells of different row heights to address various trade-offs among performance, power, and area. However, maintaining all standard cells with integer multiples of a single-row height could cause some area overheads and increase power consumption. In this paper, we present an analytical placer to directly consider a circuit design with non-integer multiple-height standard cells and additional layout constraints. The region of different cell heights is adaptively generated by the global placement result. In particular, an exact penalty iterative shrinkage and thresholding (EPIST) algorithm is employed to efficiently optimize the global placement problem. The convergence of the algorithm is proved, and the acceleration strategy is proposed to improve the performance of our algorithm. Compared with the state-of-the-art works, experimental results based on the 2017 CAD Contest at ICCAD benchmarks show that our algorithm achieves the best wirelength and area for every benchmark. In particular, our proposed EPIST algorithm provides a new direction for effectively solving large-scale nonlinear optimization problems with non-smooth terms, which are often seen in real-world applications.

In modern circuit designs, standard cells are designed with different heights based on the power, area, and other characteristics to address various design requirements. For those cells with different heights, in particular, there are inter-cell diffusion steps if the diffusion heights of neighboring cells are different, called the neighbor diffusion effect (NDE) which has become critical in advanced technology nodes. In this paper, we present a Hamiltonian-path-based mixed-cell-height legalization algorithm for NDE mitigation. We first present a row assignment method considering both cell displacements and diffusion steps to assign cells to their desired rows that meet the power-rail alignment constraints. Then, we propose a Hamiltonian-path-based diffusion-step reduction method to effectively reduce the NDE violations while preserving the global placement solution. Particularly, we develop a 2-approximation algorithm to find a minimum weight Hamiltonian path connecting two vertices, and a 1.5-approximation algorithm to find a minimum weight Hamiltonian path with a specified end vertex. Finally, we present an NDE-aware legalization method with design compaction to resolve overlaps and NDE violations. Experimental results show that our algorithm can resolve all NDE violations without any area overhead in reasonable runtime.

As the feature sizes keep shrinking, interconnect delays have become a major limiting factor for FPGA timing closure. Traditional placement algorithms that address wirelength alone are no longer sufficient to close timing, especially for the large-scale heterogeneous FPGAs. In this paper, we resolve the crucial FPGA placement problem by optimizing wirelength and timing simultaneously. First, a smoothed routing-architecture-aware timing model is proposed to accurately estimate each interconnect delay. Then, a timing-driven delay look-up table is constructed to further speed up delay access. Finally, we present an effective wirelength and timing co-optimization strategy to produce high-quality placements without timing violations. Compared with Vivado 2019.1 on Xilinx benchmark suites for xc7k325t device, experimental results show that our algorithm achieves not only a 6.6% improvement in worst slack but also a 3.2% reduction for routed wirelength.

Multi-FPGA prototyping is widely used for modern VLSI verification, but the limited number of inter-FPGA connections in a multi-FPGA system may cause routing failures. As a result, the time-division multiplexing (TDM) technique is adopted to increase its resource utilization by transmitting multiple signals through the same routing channel. Due to the large signal delay between FPGA pairs, however, the performance of such a system greatly depends on the inter-FPGA routing quality. In this paper, we propose a TDM-based system-level routing algorithm to simultaneously minimize the maximum TDM (signal multiplexing) ratio and runtime, considering the crucial ratio constraints. By weighting the routing edges, we first model the net routing as a Steiner minimum tree (SMT) problem and solve it with an approximation algorithm with the performance bound 2(1 - 1/1), where l is the number of leaves in an optimal SMT. Then, a timing-driven assignment method is presented to evenly distribute the TDM ratio to routing signals, followed by a novel reassignment algorithm to efficiently handle unbalanced net groups. Finally, a ratio-aware refinement technique is employed to further improve the solution quality. Compared with the top-3 winners at the 2019 CAD Contest at ICCAD based on the contest benchmarks, experiment results show that our proposed algorithm achieves the best runtime and TDM ratio while satisfying all TDM constraints.

We describe the RDF-2020 release of the IEEE CEDA DATC Robust Design Flow (RDF). RDF-2020 extends the previous four years of DATC efforts to (i) preserve and integrate leading research codes, including from past academic contests, and (ii) provide a foundation and backplane for academic research in the RTL-to-GDS IC implementation arena. Implementation and analysis flows have been enhanced by the addition of steps including multi-bit flip-flop clustering, parasitic extraction and antenna checking, as well as a recent contest-winning global router. RDF-2020 also opens a new "Calibrations" direction to support academic research on key analyses such as extraction and timing. An open-source physical design database with Tcl/Python/C++ APIs, a flow integration into a single scriptable application, and support for the newly-opened SKY130 manufacturable PDK, are also new this year. Our paper closes with a discussion of potential future directions for the RDF effort.

Rare-event yield analysis is challenging for high-dimensional circuit cases. In this paper, we propose a non-Gaussian adaptive importance sampling (NGAIS) method. In order to approximate the failure region in high-dimensional space, we model it as a mixture of von Mises-Fisher distributions. We formulate the parameter estimation problem as a maximum likelihood estimation problem, and then solve with expectation-maximization algorithm. Experiments on bit cell, amplifier and SRAM column circuit validate that the proposed NGAIS method outperforms other state-of-the-art approaches in terms of accuracy and efficiency.

A modern field-programmable gate array (FPGA) often contains an ASIC-like clocking architecture which is crucial to achieve better skew and performance. Existing conventional FPGA placement algorithms seldom consider clocking resources, and thus may lead to clock routing failures. To address the special FPGA clocking architecture, this article presents an effective clock-aware placement algorithm for large-scale heterogeneous FPGAs. Our algorithm consists of four major technologies: 1) a combinatorial clock fence region method to effectively reduce the overuse of clocking resources; 2) a smoothed heterogeneous density function to lead heterogeneous blocks to desired sites and a coordinate transformation technique to facilitate CLB cell spreading; 3) a heterogeneous force modulation algorithm to stabilize placement movement and a hierarchical contraction technique to remedy an insufficiency of the multilevel placement framework; and 4) a two-level clock-aware packing and legalization scheme to generate an optimized, clocking-violation-free placement. We evaluate our results based on the ISPD 2017 Clock-Aware Placement Contest benchmark suite. Compared with the state-of-the-art placers, the experimental results show that our algorithm achieves the best-routed wirelength.

Mixed-cell-height circuits have become popular in advanced technologies for better power, area, routability, and performance tradeoffs. With technology and region constraints imposed by modern circuit designs, the mixed-cell-height legalization problem has become even more challenging. Additionally, an ideal legalization method should minimize both the average and maximum cell movements to preserve the quality of a given placement as much as possible. In this article, we present an effective and efficient mixed-cell-height legalization algorithm to consider technology and region constraints while minimizing the average and maximum cell movements. We first present a fence region handling technique to unify the fence regions and the default region. To obtain a desired cell assignment, we then propose a movement-aware cell reassignment method by iteratively reassigning cells in locally dense areas to their desired rows. After cell reassignment, a technology-aware legalization is presented to remove cell overlaps while satisfying the technology constraints. Finally, we propose a technology-aware refinement to further reduce the average and maximum cell movements without increasing the technology constraints violations. Compared with the champion of the 2017 CAD Contest at ICCAD and the state-of-the-art work, experimental results based on the 2017 CAD Contest at ICCAD benchmarks show that our algorithm achieves the best average and maximum cell movements and significantly fewer technology constraint violations, in a comparable runtime. The experimental results based on the modified 2015 ISPD Contest benchmarks also demonstrate the effectiveness of our algorithm in minimizing the average and maximum cell movements, compared with state-of-the-art mixed-cell-height legalizers.

As an emerging manufacture technology, block copolymer directed self-assembly (DSA) is promising for via layer fabrication. Meanwhile, redundant via insertion is considered as an essential step for yield improvement. For better reliability and manufacturability, in this paper, we concurrently consider DSA guiding template assignment with redundant via and dummy via insertion at post-routing stage. Firstly, by analyzing the structure property of guiding templates, we propose a building-block based solution expression to discard redundant solutions. Then, honoring the compact solution expression, we construct a conflict graph with dummy via insertion, and then formulate the problem to an integer linear programming (ILP). To make a good trade-off between solution quality and runtime, we relax the ILP to an unconstrained nonlinear programming (UNP). Finally, a line search optimization algorithm is proposed to solve the UNP. Experimental results verify the effectiveness of our new solution expression and the efficiency of our proposed algorithm.

We describe a new RDF-2019 release of the IEEE CEDA DATC Robust Design Flow (RDF). RDF-2019 enhances the DATC RDF to span the entire RTL-to-GDS IC implementation flow, from logic synthesis to detailed routing. The new release represents a significant revision of the previously-reported RDF-2018 flow. Noteworthy vertical extensions include addition of logic synthesis starting from pure behavioral RTL Verilog RTL; floorplanning that includes initial DEF creation, I/O placement and PDN layout generation; and clock tree synthesis between placement legalization and global routing. A number of horizontal extensions to RDF are achieved by incorporating additional tool options at the static timing analysis, global placement, gate sizing, and detailed routing stages of the flow. Further, for the first time, multiple open-source realizations of the entire RDF tool chain are available. Last, RDF-2019 provides significantly enhanced support of and interoperability with industry-standard tools and design formats (LEF/DEF, SPEF, Liberty, SDC, etc.). We illustrate the configuration and use of RDF-2019, with example results on open as well as commercial design enablements.

As the design complexity keep increasing, the 2.5D FPGA with large logic capacity has become popular in modern circuit applications. A 2.5D FPGA consists of multiple dies connected through super long lines (SLLs) on an interposer, where each die contains heterogeneous logic blocks and ASIC-like clocking architectures to achieve better skew and timing. To address the crucial SLL issue and the special clocking architecture, this paper presents the first analytical placement algorithm for the 2.5D FPGA with the objective of minimizing the numbers of inter-die SLL signals and intra-die clocking violations simultaneously. Using a lifting dimension technique, we first formulate the 2.5D global placement problem as a three-dimensional continuous and differential minimization problem, where the SLL-aware block distribution is modeled by 3D Poisson's equation and directly solved to obtain an analytical solution. Then, we further reformulate the minimization problem as a separable optimization problem with linear constraints. Based on the proximal alternating direction method of multipliers (ADMM) optimization method, we efficiently optimize the separable subproblems one by one in an alternating fashion. Finally, clock-aware legalization and detailed placement are applied to legalize and further improve our placement results. Compared with the state-of-the-art work, experimental results show that our algorithm can resolve all clocking constraints and reduce the number of SLL crossing signals by 36.9% with similar wirelength in comparable running time.

Metal fill insertion has become an essential step to reduce dielectric thickness variation and improve pattern uniformity, which is important in mitigating process variations, thereby achieving better manufacturing yield. However, metal fills could induce coupling capacitance, which is not often considered in existing works that typically focus more on pattern density uniformity, incurring significant problems in timing closure. In this paper, we address the timing-aware fill insertion problem that considers the total capacitance and density constraints simultaneously. First, initial metal fill insertion and design-rule-aware legalization are used to quickly obtain an initial fill insertion solution. Second, from critical conductors to powers/grounds in a circuit, we divide conductors into different equivalent paths and then construct a capacitance graph to globally reduce the capacitance of each equivalent path. Third, we present a density-aware coupling capacitance optimization method and a fast Monte Carlo based fill selection to further reduce the coupling capacitance between any pair of conductors. Finally, we present a density-aware fill deletion method to reduce the fill amounts. We evaluate the performance of our algorithm based on the benchmarks of the 2018 CAD Contest at ICCAD and its official contest evaluator. Compared with the first place team of the contest and the state-of-the-art work, experimental results show that our algorithm achieves the lowest total capacitance and the least fill amount for each benchmark.

Modern circuit designs often contain standard cells of different row heights to meet various design requirements. Due to the higher interference among heterogeneous cell structures, the legalization problem for mixed-cell-height standard cells becomes more challenging. In this paper, we present an analytical legalization algorithm for mixed-cell-height standard cells to simultaneously minimize the average and the maximum cell movements. We formulate it as a mixed integer quadratic programming problem (MIQP), which allows cell spreading concurrently in both the horizontal and vertical directions. By relaxing its discrete constraints to linear ones, we convert the MIQP into a quadratic programming problem (QP). To solve the QP efficiently, we further reformulate it as a linear complementarity problem (LCP), and solve the LCP by a modulus-based matrix splitting iteration method (MMSIM). To guarantee the convergence of the MMSIM and the equivalence between the QP and the LCP, we use a series of operations to ensure that its induced objective matrix is symmetric positive definite and its constraint matrix is of full row rank. Experimental results demonstrate the effectiveness of our algorithm in reducing both the average and the maximum cell movements for mixed-cell-height legalization.

Global placement dominates the circuit placement process in its solution quality and efficiency. With increasing design complexity and various design constraints, it is desirable to develop an efficient, high-quality global placement algorithm for modern large-scale circuit designs. In this paper, we first analyze the properties of four nonlinear optimization methods (the quadratic penalty method, the Lagrange multiplier method, and two augmented Lagrangian methods) for global placement, and then develop a generalized augmented Lagrangian method to solve this problem. Our proposed method preserves the advantages of the quadratic penalty method and the augmented Lagrangian method, and provides a smooth progress from the quadratic penalty method to the augmented Lagrangian method. We prove that the proposed generalized augmented Lagrangian method is globally convergent for the original global placement problem, even with different constraints. Compared with the other four popular optimization methods, experimental results show that our method achieves the best quality and is robust for handling different objectives. In particular, our generalized augmented Lagrangian formulation is theoretically sound and can solve generic large-scale constrained nonlinear optimization problems, which are widely used in many fields.

Fogging and proximity effects are two major factors that cause inaccurate exposure and thus layout pattern distortions in e-beam lithography. In this paper, we propose the first analytical placement algorithm to consider both the fogging and proximity effects. We first formulate the global placement problem as a separable minimization problem with linear constraints, where different objectives can be tackled one by one in an alternating fashion. Then, we propose a novel proximal group alternating direction method of multipliers (ADMM) to solve the separable minimization problem with two subproblems, where the first subproblem (mainly associated with wirelength and density) is solved by a steepest descent method without line-search, and the second one (mainly associated with the fogging and proximity effects) is handled by an analytical scheme. We prove the property of global convergence of the proximal group ADMM method. Finally, legalization and detailed placement are used to legal and further improve the placement result. Experimental results show that our algorithm is effective and efficient for the addressed problem. Compared with the state-of-the-art work, our algorithm not only can achieve 13.4% smaller fogging variation and 21.4% lower proximity variation, but also has a 1.65× speedup.

Mixed-cell-height standard cells are prevailingly used in advanced technologies to achieve better design trade-offs among timing, power, and routability. As feature size decreases, placement of cells with multiple threshold voltages may violate the complex minimum-implant-area (MIA) layer rule arising from the limitations of patterning technologies. Existing works consider the mixed-cell-height placement problem only during legalization, or handle the MIA constraints during detailed placement. In this paper, we address the mixed-cell-height placement problem with MIA constraints into two major stages: post global placement and MIA-aware legalization. In the post global placement stage, we first present a continuous and differentiable cost function to address the Vdd/Vss alignment constraints, and add weighted pseudo nets to MIA violation cells dynamically. Then, we propose a proximal optimization method based on the given global placement result to simultaneously consider Vdd/Vss alignment constraints, MIA constraints, cell distribution, cell displacement, and total wirelength. In the MIA-aware legalization stage, we develop a graph-based method to cluster cells of specific threshold voltages, and apply a strip-packing-based binary linear programming to reshape cells. Then, we propose a matching-based technique to resolve intra-row MIA violations and reduce filler insertion. Furthermore, we formulate inter-row MIA-aware legalization as a quadratic programming problem, which is efficiently solved by a modulus-based matrix splitting iteration method. Finally, MIA-aware cell allocation and refinement are performed to further improve the result. Experimental results show that, without any extra area overhead, our algorithm still can achieve 8.5% shorter final total wirelength than the state-of-the-art work.

In this paper, we present DATC Robust Design Flow (RDF) from logic synthesis to detailed routing. We further include detailed placement and detailed routing tools based on recent EDA research contests. We also demonstrate RDF in a scalable cloud infrastructure. Design methodology and cross-stage optimization research can be conducted via RDF.

Poisson's equation has been used in VLSI global placement for describing the potential field induced by a given charge density distribution. Unlike previous global placement methods that solve Poisson's equation numerically, in this paper, we provide an analytical solution of the equation to calculate the potential energy of an electrostatic system. The analytical solution is derived based on the separation of variables method and an exact density function to model the block distribution in a placement region, which is an infinite series and converges absolutely. Using the analytical solution, we give a fast computation scheme of Poisson's equation and develop an effective and efficient global placement algorithm called Pplace. Experimental results show that our Pplace achieves smaller placement wirelength than ePlace and NTUplace3, two leading wirelength-driven placers. With the pervasive applications of Poisson's equation in scientific fields, in particular, our effective, efficient, and robust computation scheme for its analytical solution can provide substantial impacts to these fields.

Mixed-cell-height circuits have become popular in advanced technologies for better power, area, routability, and performance tradeoffs. With the technology and region constraints imposed by modern circuit designs, the mixed-cell-height legalization problem has become more challenging. In this paper, we present an effective and efficient legalization algorithm for mixed-cell-height circuit designs with technology and region constraints. We first present a fence region handling technique to unify the fence regions and the default ones. To obtain a desired cell assignment, we then propose a movement-aware cell reassignment method by iteratively reassigning cells in locally dense areas to their desired rows. After cell reassignment, a technology-aware legalization is presented to remove cell overlaps while satisfying the technology constraints. Finally, we propose a technology-aware refinement to further reduce the average and maximum cell movements without increasing the technology constraints violations. Compared with the champion of the 2017 ICCAD CAD Contest and the state-of-the-art work, experimental results show that our algorithm achieves the best average and maximum cell movements and significantly fewer technology constraint violations, in a comparable runtime.

For circuit designs in advanced technologies, standard-cell libraries consist of cells with different heights; for example, the number of fins determines the height of cells in the FinFET technology. Cells of larger heights give higher drive strengths, but consume larger areas and power. Such mixed cell heights incur new, complicated challenges for layout designs, due mainly to the heterogeneity in cell dimensions and thus their larger solution spaces. There is not much published work on layout designs with mixed-height standard cells. This paper addresses the legalization problem of mixed-height standard cells, which intends to place cells without any overlap and with minimized displacement. We first study the properties of Abacus, generally considered the best legalization method for traditional single-row-height standard cells but criticized not suitable for handling the new challenge, analyze the capability and insufficiencies of Abacus for tackling the new problem, and remedy Abacuss insufficiencies and extend its advantages to develop an effective and efficient algorithm for the addressed problem. For example, dead spaces become a critical issue in mixed-cell-height legalization, which cannot be handled well with an Abacus variant alone. We thus derive a dead-space-aware objective function and an optimization scheme to handle this issue. Experimental results show that our algorithm can achieve the best wirelength among all published methods in reasonable running time, e.g., about 50% smaller wirelength increase than a state-of-the-art work.

Modern circuits often contain standard cells of different row heights to meet various design requirements. Higher cells give larger drive strengths at the costs of larger areas and power. Multi-row-height standard cells incur challenging issues to layout designs, especially the mixed-cell-height legalization problem due to the heterogeneous cell structures. Honoring the good cell positions from global placement, we present in this paper a fast and near-optimal algorithm to solve the legalization problem. Fixing the cell ordering from global placement and relaxing the right boundary constraints, we first convert the problem into a linear complementarity problem (LCP). With the converted LCP, we split its matrices to meet the convergence requirement of a modulus-based matrix splitting iteration method (MMSIM), and then apply the MMSIM to solve the LCP. This MMSIM method guarantees the optimality if no cells are placed beyond the right boundary of a chip. Finally, a Tetris-like allocation approach is used to align cells to placement sites on rows and fix the placement of out-of-right-boundary cells, if any. Experimental results show that our proposed algorithm can achieve the best cell displacement and wirelength among all published methods in reasonable runtimes. The MMSIM optimality is theoretically proven and empirically validated. In particular, our formulation provides new generic solutions and research directions for various optimization problems that require solving large-scale quadratic programs efficiently.

The common objective of very large-scale integration (VLSI) placement problem is to minimize the total wirelength, which is calculated by the total half-perimeter wirelength (HPWL). Since the HPWL is not differentiable, various differentiable wirelength approximation functions have been proposed in analytical placement methods. In this paper, we reformulate the HPWL as an l1-norm model of the wirelength function, which is exact but nonsmooth. Based on the l1-norm wirelength model and exact calculation of overlapping areas between cells and bins, a nonsmooth optimization model is proposed for the VLSI global placement problem, and a subgradient method is proposed for solving the nonsmooth optimization problem. Moreover, local convergence of the subgradient method is proved under some suitable conditions. In addition, two enhanced techniques, i.e., an adaptive parameter to control the step size and a cautious strategy for increasing the penalty parameter, are also used in the nonsmooth optimization method. In order to make the placement method scalable, a multilevel framework is adopted. In the clustering stage, the best choice clustering algorithm is modified according to the l1-norm wirelength model to cluster the cells, and the nonsmooth optimization method is recursively used in the declustering stage. Comparisons of experimental results on the International Symposium on Physical Design (ISPD) 2005 and 2006 benchmarks show that the global placement method is promising.

Ignoring some cell overlaps, global placement computes the best position for each cell to minimize some cost metric (e.g., total wire length, density overflow). It is a crucial step in very large scale integration (VLSI) physical design, because it affects rout ability, performance, and power consumption of a circuit. In this paper, we propose an Augmented Lagrangian method to solve the VLSI global placement. In this method, a cautious dynamic density weight increasing strategy is used to balance the wire length and density constraint. We incorporated our method into NTUplace3's global placement framework, and tested it on the IBM mixed-size benchmark circuits. Experimental results show that it obtains high-quality results in a reasonable running time.

Placement is the process of determining the exact locations of circuit elements within a chip. It is a crucial step in very large scale integration (VLSI) physical design, because it affects routability, performance, and power consumption of a design. In this paper, we develop a new analytical placer to solve the VLSI standard cell placement problem. The placer consists of two phases, multilevel global placement (GP) and detailed cell placement (DP). In the stage of GP, during the clustering stage, we use a nonlinear programming technique and a best-choice clustering algorithm to take a global view of the whole netlist and placement information, and then use an iterative local refinement technique during the declustering stage to further distribute the cells and reduce the wirelength. In the stage of DP, we develop a fast legalization algorithm to make the solution by global placement legal and use a cell order polishing to improve the legal solution. The proposed algorithm is tested on the IBM standard cell benchmark circuits and Peko suites. Experimental results show that our placer obtains high-quality results in a reasonable running time.

Floorplanning in very large scale integrated-circuit (VLSI) design is the first phase in the process of designing the physical layout of a chip. This makes the floorplanning problem of paramount importance, since it determines the performance, size, yield, and reliability of VLSI chips . From the computational point of view, the VLSI floorplanning is an NP-hard problem. In this paper, we present a hybrid simulated annealing algorithm (HSA) for nonslicing VLSI floorplanning. The HSA uses a new greedy method to construct an initial B*-tree, a new operation on the B*-tree to explore the search space, and a novel bias search strategy to balance global exploration and local exploitation. Experimental results on Microelectronic Center of North Carolina (MCNC) benchmarks show that the HSA can quickly produce optimal or nearly optimal solutions for all the tested problems.