As the size of circuit designs continues to grow, it has long been a significant challenge to accelerate the circuit compilation flow for modern FPGAs. Many parallel algorithms have been proposed to speed up routing, the most time-consuming stage of FPGA circuit compilation, by leveraging more computing resources. However, the high density of net distribution in modern FPGAs leads to severe data conflicts, making it difficult to achieve high parallelism. In this work, we propose a mixed-grained FPGA parallel routing framework, RND, which implements task decoupling by dividing the FPGA routing graph into disjoint regions and decomposing the signal nets into in-region connections. In the FPGA 2024 routing contest benchmarks, our proposed router achieves an average 5.41× speedup with 32 threads over the serial router RWRoute and is 26.7% faster than Potter-S, the fastest deterministic router for UltraScale FPGAs. Meanwhile, our router does not sacrifice routing quality for acceleration.

As a critical step in electronic design automation (EDA), global routing provides a guide to subsequent steps and provides valuable feedback to previous steps, including congestion, timing, and power estimation. However, given the complexity of timing and power calculation, it is difficult to estimate the impact on timing and power during the routing process. To address this issue, we propose a gradient-guided framework that computes the ''capacity sensitivity'' and ''resistance sensitivity'' of each segment to estimate their influence on the timing objectives. Integrating these two values as weights to constrain the changes in capacitance and resistance of the wire segments, we develop a timing-driven global router with superior performance. Power is also considered by optimizing the cells' switching power. Tested on ISPD25 Contest benchmarks, we can achieve 14.3% and 18.5% improvements in worst negative slack and total negative slack, respectively, with comparable congestion. With power optimization, we can further improve switching power by 10.6%.

With the growth of circuit size and FPGA complexity, routing becomes an increasingly complicated and timeconsuming task for modern FPGAs. To accelerate FPGA routing, many parallel algorithms have been proposed to perform concurrent routing for multiple independent nets that have no overlaps in routing resources. The requirement on net independence can help reduce the synchronization overhead by circumventing the data race in different threads, but it will significantly limit the parallelism due to the large number of overlapping nets in modern circuit designs. Therefore, to strive for large-scale parallelism, it is a promising direction to explore the parallel routing for overlapping nets. In this work, we first propose a parallel overlap-tolerant router, called Potter, including the runtimefirst Potter-R and the stability-first Potter-S. Potter-R employs a partitioning-based recursive net scheduling algorithm to divide nets into balanced groups while minimizing resource overlaps among net groups. These net groups are then routed independently and concurrently. A novel factor updating mechanism is proposed to accelerate solving congestion in the negotiation-based routing algorithm. Furthermore, based on Potter-R, we devise an efficient synchronization strategy in Potter-S to maintain determinism when concurrently routing overlapping nets. An enhanced clustering-based net scheduling method is developed to minimize overlaps among different net groups. In the FPGA24 routing contest benchmarks, our proposed method outperforms the state-of-the-art methods in both running time and wire length. Potter-R not only achieves the largest 12.34× speedup to the sequential router RWRoute but also has the best 4% improvements on wire length. Furthermore, compared with the fastest deterministic parallel router CUFR, Potter-S can

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

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

Timing is a critical issue in electronic design automation (EDA). To reduce the delay of a net, an important strategy is to minimize the path lengths from the source to the sinks. However, minimizing the path lengths will inevitably sacrifice the total wirelength. To balance the two objectives, researchers use shallow-light tree (SLT) to model and optimize the problem. In this article, we introduce MALT, a novel approach that uses a neural network to guide the construction of Steiner shallow-light trees. The constructed trees are further refined by a dynamic programming-based branch merging algorithm, which improves the wirelength without sacrificing the path lengths of any sinks. Our experimental results demonstrate that the proposed framework achieves significant improvements over both state-of-the-art traditional SLT generation algorithms and existing machine learning enhanced methods.

This paper proposes smaRTLy: a new optimization technique for multiplexers in Register-Transfer Level (RTL) logic synthesis. Multiplexer trees are very common in RTL designs, and traditional tools like Yosys optimize them by traversing the tree and monitoring control port values. However, this method does not fully exploit the intrinsic logical relationships among signals or the potential for structural optimization. To address these limitations, we develop innovative strategies to remove redundant multiplexer trees and restructure the remaining ones, significantly reducing the overall gate count. We evaluate smaRTLy on the IWLS-2005 and RISC-V benchmarks, achieving an additional 8.95% reduction in AIG area compared to Yosys. We also evaluate smaRTLy on an industrial benchmark in the scale of millions of gates, results show that smaRTLy can remove 47.2% more AIG area than Yosys. These results demonstrate the effectiveness of our logic inferencing and structural rebuilding techniques in enhancing the RTL optimization process, leading to more efficient hardware designs.

Combinational equivalence checking (CEC) is a fundamental task in the realization of digital designs which is unlikely to have universally efficient algorithms due to its co-NP-completeness. Recent researches of CEC have been focusing on SAT sweeping. This paper provides a new perspective other than SAT for tackling CEC, namely exhaustive simulation, and presents a simulation-based CEC engine constructed with fast GPU-parallel algorithms. The proposed engine can solve 4 out of the 9 large cases in the experiments on its own, with up to $88.11 \times$ speed-up compared with the checker in ABC. Moreover, a combination of the proposed engine with the ABC checker achieves averaged accelerations of $4.89 \times$ and $4.88 \times$ over the standalone ABC checker and a commercial checker, respectively.

The analysis of IR-drop stands as a fundamental step in optimizing the power distribution network (PDN), and subsequently influences the design performance. However, traditional IR-drop analysis using commercial tools proves to be exceedingly time-consuming. Fast and accurate IR-drop analysis is desperately in demand to achieve high performance on timing and power. Recently, machine learning approaches have garnered attention owing to their remarkable speed and extensibility in IC designs. However, prior works for dynamic IR-drop prediction presented limited performance since they did not exploit the time-varying activities. In this paper, we proposed a dual-path model with spatial-temporal transformers to extract the static spatial features and dynamic time-variant activities for dynamic IR drop prediction. Experimental results on the large-scale advanced dataset CircuitNet show that our model significantly outperforms the state-of-the-art works.

Reinforcement learning (RL)-based macro placement has garnered significant interest in both the fields of artificial intelligence and electronic design automation (EDA), due to its excellent potential for achieving better performance, power and area optimization compared to analytical methods. However, existing techniques are restricted in the ASIC and ignore the other hardware architectures like FPGA. Neglecting the intrinsic characters of FPGA structures, conventional RL-based methods for ASICs may result in a large exploration space and low sample efficiency. In this work, we propose TRPlaceFPGA-MP, a two-stage RL-based macro placement framework for Ultrascale FPGAs. Leveraging the columnar architecture, we first train a tiny RL model to determine the candidate columns for each macro in the first stage. With the pruned searching space, a more sophisticated RL model is then trained in the second stage to determine the ultimate positions of the macros. Experimental results on the MLCAD2023 contest benchmark demonstrate that TRPlaceFPGA-MP still maintains superior placement performance compared with Vivado and DreamplaceFPGA-MP. Furthermore, it improves the convergence rate by 2.28 x and accelerates the exploration process by$1.61 x$compared to the one-stage RL approach.

ASIC technology mapping consists of mapping a technology-independent Boolean network into an equivalent circuit utilizing cells from a specified library, a process that is vital in electronic design automation (EDA). However, existing algorithms in the literature are sequential in nature and often neglect to account for the actual delay of the cells during the mapping process, resulting in significant discrepancy between estimated and actual delay. In this paper, we propose an ASIC technology mapper that considers load information of intermediate solutions. This approach enables the identification of critical nodes and a better selection of delay-oriented cells for those nodes. Furthermore, we introduce a dual recovery method for delay and area to enhance performance. Finally, these innovations are integrated within a configuration-level parallelism framework on GPU. Experimental results on different technology libraries demonstrate that our method achieves on average 32% reduction in delay with 3% area penalty compared to the public synthesis tool ABC. Additionally, our approach provides a significant speedup of 65.33×.

Routing is an important but complicated step in physical synthesis. Considering the potential of leveraging AI to seek higher efficiency and better quality in solving routing problems, we study in this work the methodology of AI-assisted routing in a systematic way. Decoupling the functionalities of different routing components will give a high flexibility in determining where and how AI can be used in an effective manner, while maintaining a high degree of interpretability. Two applications along this direction are presented, aiming at tackling the difficulties in routing with AI assistance. These provide examples of how to implement the methodology in practice, while revealing its effectiveness and potential.

Lookup-table (LUT) mapping has been extensively utilized in logic synthesis, including being an indispensable step in FPGA design, serving as a building block in high-effort synthesis flows, and providing an algorithmic framework for logic optimization. Hence, a fast mapping algorithm is vital to satisfying the demand for synthesizing high-quality, large-scale modern VLSI designs. This article proposes two efficient GPU-parallel algorithms, namely LUT mapping and and-inverter graph (AIG) optimization using a precomputed database, which rely on a common parallel mapping framework that consists of novel fine-grained parallel mapping passes with high degree of parallelism. The mapping pass is enhanced by specifically tailored cut evaluation and memory management methods for GPUs that enable fast mapping of large circuits with limited GPU memory. Parallel timing analysis passes and parallel cut expansion passes are also proposed for constructing a fully GPU-accelerated LUT mapping flow. The core of parallel AIG optimization is a plugin of the mapping framework, which contains a self-adaptive parallel candidate structure evaluation procedure with high time efficiency and low hardware resource usage. Experiments show that on average, GPU LUT mapping and AIG optimization achieve$34.6\times $and$99.9\times $speedup with similar result quality, compared with the high-performance LUT mapper and AIG optimization algorithm with a database implemented in ABC, respectively, on large benchmarks. When combining the two algorithms with other GPU logic optimization algorithms, a GPU-based sequence targeting LUT network synthesis achieves$46.7\times $speedup with 4.7% smaller area and 0.2% smaller delay over ABC.

The emerging technologies of 3D integrated circuits (3DICs) unveil a new avenue for expanding the design space into the 3D domain and present the opportunity to overcome the bottleneck of Moore’s Law for the traditional 2DICs. Among various technologies, the face-to-face bonding structure provides high integration density and reliable performance. Most commercial EDA tools, however, do not support 3DIC and cannot give a convincing solution. To exploit the benefits of stacking multiple tiers vertically, placement algorithms for 3DIC are imperatively in need. In this paper, we proposed a design flow that optimizes partitioning and placement quality for 3DICs in a unified way. Experimental results on the ICCAD2022 contest benchmark show that our work outperforms the first-place team by 3.35% in quality with less runtime and terminals used.

Lookup-table (LUT) mapping is an indispensable step in FPGA design flows, and also serves as a building block in many technology-independent optimization algorithms. Therefore, it is crucial to accelerate LUT mapping in order to satisfy the demand for synthesizing high-quality, large-scale VLSI designs. Previous work on GPU LUT mapping suffers from low speedup due to limited degree of parallelism. In this paper, we propose an ultra-fast GPU-parallel LUT mapping engine named FineMap, which is composed of a novel fine-grained mapping phase with a high degree of parallelism, a parallel cut expansion phase and a parallel timing analysis pass. The mapping phase is enhanced by specifically tailored cut evaluation and memory management algorithms for GPUs that enable fast mapping of large circuits with limited GPU memory. Experiments show that compared with the high-performance mapper implemented in ABC, FineMap achieves 128.7× speedup with better quality in terms of area on large benchmarks.

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

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

Resubstitution is a flexible algorithmic framework for circuit restructuring that has been incorporated into many high-effort logic optimization flows. It is thus important to speed up resubstitution in order to obtain high-quality realizations of large-scale designs. This paper proposes a massively parallel AIG resubstitution algorithm targeting GPUs, with effective approaches to addressing cyclic dependencies and restructuring conflicts. Compared with ABC and mockturtle, our algorithm achieves 41.9× and 50.3× acceleration on average without quality degradation. When combining our resubstitution with other GPU algorithms, a GPU-based resyn2rs sequence obtains 46.4× speedup over ABC with 0.8% and 5.8% smaller area and delay respectively.

Macro placement significantly influences the performance of the FPGA placement. However, constraints in modern designs like relative placement constraint (RPC) and regional constraint (RC) are often overlooked in existing routability-driven FPGA placers during macro placement. These constraints introduce challenges in optimizing routability during global placement and macro legalization stages. In this paper, we propose a novel macro placer that specifically addresses these constraints while optimizing routability. Our macro placer integrates macro size-aware pseudo nets, RC guided spreading, and multi-stage look-ahead legalization techniques to enhance routability with specified design constraints. Experimental results show that compared with DreamplaceFPGA-MP and the macro placer in Vivado, our proposed approach achieves 6% and 8% total routing score reduction on the MLCAD2023 contest benchmark. Moreover, the place and route time is reduced by 3.5% on average and up to 43% after our macro placer is integrated into Vivado. These compelling results demonstrate the efficiency gains and superior routability optimization achieved through our approach.

With the ever-increasing complexity of microprocessors, microarchitectural design becomes over-challenging. Design space exploration (DSE) of microarchitecture configurations to obtain high-quality designs with different PPA trade-offs is time-consuming, due to the huge configuration space and inefficient VLSI verification flow. Many DSE frameworks proposed in previous works failed to systematically analyze the contribution of each algorithmic component to the full flow. This paper provides a novel methodology for designing DSE frameworks by separating DSE flow into stages, and discussing algorithmic instantiations in each stage with theoretical and experimental analyses. Newly formulated DSE frameworks guided by this methodology achieve state-of-the-art results in ICCAD’22 DSE contest evaluation environments.

Due to the lengthy design cycle, generating legal, diverse and valid layout patterns artificially to expand VLSI layout pattern libraries has become an important problem to solve in order to facilitate modern design-for-manufacturability (DFM) studies. Considering the more realistic demands and to enhance functionality, this work proposes a style-controllable and violation-fixable layout pattern generation framework based on conditional diffusion models named ControLayout, which treats pattern category and complexity as conditions to control the style of generated patterns, and leverages the idea of image masking-inpainting to fix violations adaptively. Experiments reveal its promising performance in controllability and different metrics compared with the state-of-the-art methods.

With minimal compromises on other metrics, eliminating overflow and lowering congestion level of global routing results as much as possible is a crucial topic for reducing violations and hotspots in subsequent design phases. Different from current common practices of using maze routing according to some explicit orders to sequentially re-route particular nets of interest, this paper proposes a collaborative refinement framework that can generate multiple paths simultaneously to enlarge the solution space based on a multi-agent generative model, serving as a flexible post-processing plug-in on existing global routing results to reduce congestion. Experimental results well reveal its effectiveness.

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

Large-scale multi-FPGA prototyping platforms play an indispensable role in the functional verification of complex IC designs. The process of compiling circuit designs typically entails tasks such as partitioning, global placement and routing using a fixed multi-FPGA network. However, different circuit designs often exhibit varying inter-FPGA communication requirements after compilation. Neglecting this distinction, the use of fixed multi-FPGA networks may impede the performance enhancement of circuit verification. In this study, we investigate dynamic networking for multi-FPGA platforms and propose a comprehensive framework, which integrates simultaneous networking and system-level placement and routing. Based on theoretical analysis, we formulate this dynamic networking problem as an Integer Linear Programming (ILP) problem. Additionally, we introduce two innovative techniques, namely two-level ILP optimization and edge grouping, to expedite the ILP-solving process. Compared to the baselines on Titan23 and ICEEC22 benchmarks, our method achieves remarkable 11% and 47% improvements in system frequency respectively.

Placement is a crucial step in the physical synthesis flow that significantly determines the timing performance of a design. In this paper, we propose a timing-driven global placement framework with a hybrid pin-based weighting scheme that considers both graph and path information and an optimization-friendly RC tree and wirelength model. A calibration method is proposed to further improve the incremental timing. Experiment results show over 37% improvement on TNS and 15% improvement on WNS, with 4.2% less HPWL on the ICCAD 2015 benchmark compared to the state-of-the-art GPU-accelerated differentiable timing-driven placer, while also being around 2x faster.

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

Routing is a time-consuming stage in FPGA compilation, and various parallel approaches have been proposed to accelerate it by concurrently routing non-overlapping nets. However, the requirement for non-overlapping nets limits the potential for large-scale parallelism, primarily due to two factors: (1) large circuits inherently contain many nets with overlapping bounding boxes, and (2) in modern FPGAs, such as Xilinx UltraScale FPGAs, a net with a large bounding box often has high occupancy but low utilization of the routing resources. To overcome these limitations, we present Potter, a novel parallel overlap-tolerant router designed to maximize parallelism. Our approach employs recursive partitioning to divide nets into balanced partitions with minimized overlap and allows for routing these partitions in parallel. Additionally, we propose an innovative mechanism for updating the congestion factors to enhance PathFinder in handling routing resource overflows. Evaluations on the FPGA 2024 contest benchmarks demonstrate that Potter achieves significant performance improvements, with average speedups of 12× and 8× compared to RWRoute and Vivado, respectively, while also reducing wire lengths by 4% and 45%. Notably, in some congested benchmarks, Potter exhibits a substantial 30× speedup over RWRoute.

Today, we have abundant parallel computing resources, while most EDA tools are still running sequentially. It is interesting to see how physical design can be advanced by leveraging this massive parallel computing power. To achieve significant speedup, it is usually not simply running the same sequential method a few copies in parallel. Innovative parallel algorithms that solve the problem from a new perspective using different mechanisms are needed. We will look at a few examples in physical design and logic synthesis in this talk to illustrate some methodologies and techniques in parallelizing design automation.

Abstract Within the electronic design automation (EDA) domain, artificial intelligence (AI)-driven solutions have emerged as formidable tools, yet they typically augment rather than redefine existing methodologies. These solutions often repurpose deep learning models from other domains, such as vision, text, and graph analytics, applying them to circuit design without tailoring to the unique complexities of electronic circuits. Such an “AI4EDA” approach falls short of achieving a holistic design synthesis and understanding, overlooking the intricate interplay of electrical, logical, and physical facets of circuit data. This study argues for a paradigm shift from AI4EDA towards AI-rooted EDA from the ground up, integrating AI at the core of the design process. Pivotal to this vision is the development of a multimodal circuit representation learning technique, poised to provide a comprehensive understanding by harmonizing and extracting insights from varied data sources, such as functional specifications, register-transfer level (RTL) designs, circuit netlists, and physical layouts. We champion the creation of large circuit models (LCMs) that are inherently multimodal, crafted to decode and express the rich semantics and structures of circuit data, thus fostering more resilient, efficient, and inventive design methodologies. Embracing this AI-rooted philosophy, we foresee a trajectory that transcends the current innovation plateau in EDA, igniting a profound “shift-left” in electronic design methodology. The envisioned advancements herald not just an evolution of existing EDA tools but a revolution, giving rise to novel instruments of design-tools that promise to radically enhance design productivity and inaugurate a new epoch where the optimization of circuit performance, power, and area (PPA) is achieved not incrementally, but through leaps that redefine the benchmarks of electronic systems’ capabilities.

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

Recently, various pipeline parallelism strategies are proposed to tackle the scalability problem of training a large DNN model on a distributed system. However, most of the works focus on pipeline scheduling while lacking a general methodology to handle network partitioning and mapping to distributed systems with heterogeneous interconnection. In this work, we propose an efficient design flow, named Parmesan, to map the training of a large DNN onto a system with general device topology to maximize the throughput. Parmesan works in an end-to-end manner and solves the whole optimization problem in two phases. The first phase aims at producing well-balanced partitions, and the second phase works towards placing the DNN on devices connected by an arbitrary topology network, considering the heterogeneity of the interconnection bandwidth. We show that Parmesan speeds up the pipeline training throughput on systems with different GPU topologies and is able to handle the mapping problem for heterogeneously interconnected architectures. We believe our proposed general device topology mapping algorithm will provide valuable information for architecture designers and assist them in designing a more DNN-friendly architecture.

Pin access analysis is a critical step in detailed routing, one of the most complicated stages in the very-large-scale integration (VLSI) physical design flow. In numerous physical design scenarios, where intricate design rules and pin shapes are involved, there is a growing need for efficient and precise evaluation of pin accessibility. Therefore, we introduce FastPass, an improved framework for fast and accurate pin access analysis. FastPass begins by generating pin access routes that adhere to design rules. After that, FastPass preprocesses the conflicts between routes and then employs incremental SAT solving to determine an optimized scheme for pin access. We further integrate FastPass into Dr. CU, a state-of-the-art detailed router to validate its effectiveness. Experimental results on the ISPD 2018 Initial Detailed Routing Contest Benchmark suite show that FastPass can generate design rule checking (DRC)-clean pin access schemes for all cases while being an order of magnitude faster than the known best- acrlong PAAF. With the integration of FastPass, Dr. CU is able to produce detailed routing results with much less short area and fewer DRC violations.

In multi-FPGA systems, Time-Division Multiplexing (TDM) is a widely used method for transferring multiple signals over a common wire. The circuit performance will be significantly influenced by this inter-FPGA delay. Some inter-FPGA nets are driven by different clocks, in which case they cannot share the same wire. In this paper, to minimize the maximum delay of inter-FPGA nets, we propose a two-step framework. First, a TDM-aware partitioning algorithm is adopted to minimize the maximum cut size between an FPGA-pair. A TDM ratio assignment method is then applied to assign TDM ratio for each inter-FPGA net optimally. Experimental results show that our algorithm can reduce the maximum TDM ratio significantly within reasonable runtime.

Routing is one of the most time-consuming steps in the modern VLSI design flow. A well-designed global routing algorithm can effectively shrink the overall routing time and improve the quality of design after routing. Unlike many global routers that rely heavily on time-consuming path search algorithms like maze routing to resolve overflows, we propose to use directed acyclic graph (DAG) to explore the routing space more efficiently and create detours only when necessary. Experimental results on the ICCAD’19 benchmarks show that our algorithm improves the state-of-the-art quality of result by 1.4% and runs with a single thread faster than the fastest multi-threaded global router.

The efficiency issue of logic optimization becomes critical as the scale of VLSI designs grows. Since various algorithms are interleaved during optimization to ensure quality, it is necessary to accelerate those commonly used algorithms for obtaining substantial total speed-up. This paper proposes novel parallel algorithms for AIG refactoring and AND-balancing. Equipped with delicately designed parallel-friendly, data-race-free frameworks and GPU data structures, our algorithms obtain significant speed-up and enable the resyn2 sequence to be fully GPU-parallelized when combined with GPU rewriting. Experiments show that on large AIGs, we achieve average accelerations up to 45.9×over ABC with comparable or better qualities.

Circuit partitioning is a critical step in hardware-assisted functional verification that involves splitting a circuit into multiple partitions and assigning them to specific hardware. However, partitioning a large circuit can require considerable computation resources and time, especially when complex hardware constraints are involved. Moreover, the path delay after partitioning can have a significant impact on verification efficiency, making early path delay prediction crucial for refining the circuit effectively. In this work, we propose a novel circuit partitioning predictor, named CPP, to rapidly and accurately predict the path delay after partitioning. To achieve this, we use circuit coarsening to develop a multi-level path representation and employ a convolutional neural network (CNN) that can capture both local and global path structures for delay prediction. Through extensive experiments on large industrial circuits, we demonstrate the superiority of our prediction framework.

With the size of modern VLSI circuits growing in size to billions of transistors, multi-FPGA systems have been widely applied in circuit emulation and prototyping. To make full advantage of limited FPGA resources and improve the system frequency, designing a flexible multi-FPGA system with a corresponding design compilation flow is an important research problem in both industry and academia. In this work, we propose a practical and scalable partitioning and routing framework, named SPARK, for a multi-FPGA system with an adjustable near-square mesh shape and the minimum number of FPGAs. To resolve the significant constraints on multiple hardware resources for partitioning, SPARK leverages the general hypergraph partitioning tool by combining it with an efficient legalization algorithm to minimize cut size without resource overflow. We also propose novel max_cut-driven maze routing and max_hop-driven refinement algorithms to optimize the max_cut and max_hop in multi-FPGA systems meanwhile and improve the system frequency. Extensive experiments using the largest public circuit benchmarks for FPGA and several small FPGA settings from the industry demonstrate the effectiveness and efficiency of SPARK.

Pin access analysis is a critical step in detailed routing. With complicated design rules and pin shapes, efficient and accurate pin accessibility evaluation is desirable in many physical design scenarios. To this end, we present FastPass, a fast and robust pin access analysis framework, which first generates design rule checking (DRC)-clean pin access route candidates for each pin, pre-computes incompatible pairs of routes, and then uses incremental SAT solving to find an optimized pin access scheme. Experimental results on the ISPD 2018 benchmarks show that FastPass produces DRC-clean pin access schemes for all cases while being 14.7× faster than the known best pin access analysis framework on average.

Due to cost benefits, supply chains of integrated circuits (ICs) are largely outsourced nowadays. However, passing ICs through various third-party providers gives rise to many threats, like piracy of IC intellectual property or insertion of hardware Trojans, i.e., malicious circuit modifications.

Placement and routing are essential steps in physical synthesis of VLSI designs. Modern circuits contain billions of cells and nets, which significantly increases the computational complexity of physical synthesis and brings big challenges to leading-edge physical design tools. With the fast development of GPU architecture and computational power, it becomes an important direction to explore speeding up physical synthesis with massive parallelism on GPU. In this talk, we will look into opportunities to improve EDA algorithms with GPU acceleration. Traditional EDA tools run on CPU with limited degree of parallelism. We will investigate a few examples of accelerating some classical algorithms in placement and routing using GPU. We will see how one can leverage the power of GPU to improve both quality and computational time in solving these EDA problems.

Recently, the topic of how to utilize prior knowledge obtained by machine-learning (ML) techniques during the EDA flow has been widely studied. In this article, we study this topic and propose a practical plug-in named PROS for both routability optimization and routed wirelength estimation which can be applied in the state-of-the-art commercial EDA tool or an academic EDA flow with negligible runtime overhead. PROS consists of three parts: 1) an effective fully convolutional network (FCN)-based predictor that only utilizes the data from placement result to forecast global routing (GR) congestion; 2) a parameter optimizer that can reasonably adjust GR cost parameters based on the prediction result to generate a better GR solution for detailed routing (DR); and 3) a convolutional neural network (CNN)-based wirelength estimator which can report accurate routed wirelength at the placement stage by using the predicted GR congestion. Experiments show that on the industrial benchmark suite in the advanced technology node, PROS can achieve high accuracy of GR congestion prediction and significantly reduce design rule checking (DRC) violations by 11.65% on average, and on the DAC-2012 benchmark suite, PROS can achieve a very low error rate (1.82%) for wirelength estimation which greatly outperforms that of FLUTE (21.52%) by 19.70%.

Multiple patterning lithography decomposition (MPLD) and mask optimization enable the ever-shrinking device feature sizes far below the lithography system limit. Conventional MPLD is solved by mathematical programming or graph-based approaches, where a set of predetermined rules is indispensable to identify the conflicts to be resolved. In this article, we explore rule-free layout decomposition following a simple but sweet principle, let the mask optimizer “teach” the layout decomposer how to generate suitable decompositions. Our flow includes a reinforcement-learning-based layout decomposer and a deep-learning-based mask optimizer. Without any handcrafted rules, our framework can perform competitively and even surpass the state-of-the-art rule-based methods with notable$(7\times \sim 63\times)$turn-around-time speedup.

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

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

Placement serves as a fundamental step in VLSI physical design. Recently, GPU-based global placer DREAMPlace[1] demonstrated its superiority over CPU-based global placers. In this work, we develop an extremely fast GPU accelerated global placer Xplace which achieves around 2x speedup with better solution quality compared to DREAMPlace. We also plug a novel Fourier neural network into Xplace as an extension to further improve the solution quality. We believe this work not only proposes a new, fast, extensible placement framework but also illustrates a possibility to incorporate a neural network component into a GPU accelerated analytical placer.

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

Inverse lithography technology (ILT) is one of the promising resolution enhancement techniques (RETs) in modern design-for-manufacturing closure, however, it suffers from huge computational overhead and unaffordable mask writing time. In this paper, we propose A2-ILT, a GPU-accelerated ILT framework with spatial attention mechanism. Based on the previous GPU-accelerated ILT flow, we significantly improve the ILT quality by introducing spatial attention map and on-the-fly mask rectilinearization, and strengthen the robustness by Reinforcement-Learning deployment. Experimental results show that, comparing to the state-of-the-art solutions, A2-ILT achieves 5.06% and 11.60% reduction in printing error and process variation band with a lower mask complexity and superior runtime performance.

In this paper, we will first have a brief review of the ISPD 2018 and 2019 Initial Detailed Routing Contests. We will then visit a few important and interesting topics in VLSI routing that includes GPU accelerated routing, signal speed optimization in routing, PCB routing and AI-driven analog routing.

Identifying root causes of systematic defects is a crucial step in yield enhancement process of integrated circuit (IC) manufacturing. With increasing complexity of fabrication processes and decreasing sizes of pattern features, more systematic defects occur at advanced technology nodes, and traditional methods are unfeasible to directly identify failure causes, due to expensive time and labor costs. Root cause analysis (RCA) technology is thus studied to automatically identify common root causes in a short time. In this paper, we develop RCANet, an end-to-end unsupervised learning-based RCA framework, which analyses diagnosis reports of failing dies within a wafer and identifies both layout-aware and cell-internal root causes efficiently. Experimental results on designs with different technologies demonstrate that RCANet outperforms both a commercial tool and the state-of-the-art method.

The tremendous growth in deep learning (DL) applications has created an exponential demand for computing power, which leads to the rise of AI-specific hardware. Targeted toward accelerating computation-intensive DL applications, AI hardware, including but not limited to GPGPU, TPU, ASICs, etc., have been adopted ubiquitously. As a result, domain-specific CAD tools play more and more important roles and have been deeply involved in both the design and compilation stages of modern AI hardware. Recently, ISPD 2020 contest introduced a special challenge targeting at the physical mapping of neural network workloads onto the largest commercial DL accelerator, CS-1 wafer-scale engine (WSE). In this article, we proposed CU.POKer, a high-performance engine fully customized for WSE’s deep neural network workload placement challenge. A provably optimal placeable kernel candidate searching scheme and a data-flow-aware placement tool are developed accordingly to ensure the state-of-the-art (SOTA) quality on the real industrial benchmarks. Experimental results on ISPD 2020 contest evaluation suites demonstrated the superiority of our proposed framework over not only the SOTA placer but also the conventional heuristics used in general floorplanning.

Optical proximity correction (OPC) in modern design closures has become extremely expensive and challenging. Conventional model-based OPC encounters performance degradation and large process variation, while aggressive approach, such as inverse lithography technology (ILT), suffers from large computational overhead for both mask optimization and mask writing processes. In this article, we developed Neural-ILT, an end-to-end learning-based OPC framework, which literally conducts mask prediction and ILT correction for a given layout in a single neural network, with the objectives of: 1) mask printability enhancement; 2) mask complexity optimization; and 3) flow acceleration. A domain-specific model pretraining recipe, which introduces the domain knowledge of lithography system, is proposed to help Neural-ILT achieving faster and better convergence. Quantitative results show that compared to the state-of-the-art (SOTA) learning-based OPC solutions and conventional OPC flows, Neural-ILT can achieve$15\times $to$30\times $turnaround time (TAT) speedup and the best mask printability with relatively lower mask complexity. Based on the developed infrastructure, we further investigated the feasibility of handling multiple mask optimization tasks for different datasets within a common Neural-ILT platform. We believe this work could bridge well-developed deep learning toolkits to GPU-based high-performance lithographic computations to achieve groundbreaking performance boosting on various computational lithography-related tasks.

Placement is one of the most critical stages in the physical synthesis flow. Circuits with increasing numbers of cells of multirow height have brought challenges to traditional placers on efficiency and effectiveness. Besides providing an overlap-free solution close to the global placement (GP) solution, constraints on power and ground (P/G) alignments, fence region, and routability (e.g., edge spacing and pin short/inaccessible) should be considered. In this article, we propose a legalization method for mixed-cell-height circuits by a window-based cell insertion technique and two post-processing network flow-based optimizations. Compared with the champion of the ICCAD 2017 Contest, our algorithm achieves 35% and 13% less average and maximum displacement, respectively, as well as significantly fewer routability violations. Comparing our algorithm with the state-of-the-art algorithms on this problem, there is an 8% improvement in average displacement with comparable maximum displacement. The source code of our legalization is available athttps://github.com/cuhk-eda/ripple.

Deep neural networks are being used in disparate VLSI design automation tasks, including layout printability estimation, mask optimization, and routing congestion analysis. Preliminary results show the power of deep learning as an alternate solution in state-of-the-art design and sign-off flows. However, deep learning is vulnerable to adversarial attacks. In this paper, we examine the risk of state-of-the-art deep learning-based layout hotspot detectors under practical attack scenarios. We show that legacy gradient-based attacks do not adequately consider the design rule constraints. We present an innovative adversarial attack formulation to attack the layout clips and propose a fast group gradient method to solve it. Experiments show that the attack can deceive the deep neural networks using small perturbations in clips which preserve layout functionality while meeting the design rules. The source code is available at https://github.com/phdyang007/dlhsd/tree/dct_as_conv.

In multi-FPGA systems, time-division multiplexing (TDM) is a widely used technique to transfer signals between FPGAs. While TDM can greatly increase logic utilization, the inter-FPGA delay will also become longer. A good time-multiplexing scheme for inter-FPGA signals is very important for optimizing the system performance. In this work, we propose a fast algorithm to generate high quality time-multiplexed routing results for multiple FPGA systems. A hybrid routing algorithm is proposed to route the nets between FPGAs, by maze routing and by a fast minimum terminal spanning tree method. After obtaining a routing topology, a two-step method is applied to perform TDM assignment to optimize timing, which includes an initial assignment and a competitive-based refinement. Experiments show that our system-level routing and TDM assignment algorithm can outperform both the top winner of the ICCAD 2019 Contest and the state-of-the-art methods. Moreover, compared to the state-of-the-art works [17, 22], our approach has better run time by more than 2x with better or comparable TDM performance.

Rectilinear Steiner Minimum Tree (RSMT) is the shortest way to interconnect a net’s n pins using rectilinear edges only. Constructing the optimal RSMT is NP-complete and nontrivial. In this work, we design a reinforcement learning based algorithm called REST for RSMT construction. After training, REST constructs RSMT of $\leq 0.36\%$ length error on average for nets with $\leq 50$ pins. The average time needed for one net is fewer than 1.9 ms, and is much faster than traditional heuristics of similar quality. This is also the first successful attempt to solve this problem using a machine learning approach.

Having a set of comprehensive VLSI layout patterns is important in researches and applications of design for manufacturability (DFM). However, due to the complexity of the manufacturing process, a large and diverse layout pattern library is usually not available, especially during the early stages of the next technology generation, and this will slow down the technology node development. Many previous pattern generation methods rely on complex rule-based manual guidance or a massive number of existing patterns in the new technology node for learning, which are both costly and with limited availability. Instead of requiring these expensive resources, we propose an attentional transfer-based framework, named CUP-EUV, learning to reuse knowledge from previous technology nodes that should have reserved an enormous amount of layout resources. With the guidance of transferred knowledge, a pattern generation model can be trained by only a small number of patterns from the expensive EUV designs. Experiments show that our model can generate new patterns with much higher performance than the state-of-the-art approaches.

With the continuous shrinkage of device technology node, the tremendously increasing demands for resolution enhancement technologies (RETs) have created severe concerns over the balance between computational affordability and model accuracy. Having realized the analogies between computational lithography tasks and deep learning-based computer vision applications (e.g., medical image analysis), both industry and academia start gradually migrating various RETs to deep learning-enabled platforms. In this paper, we propose a unified self-training paradigm for building up an end-to-end mask optimization framework from undisclosable layout patterns. Our proposed flow comprises (1) a learning-based pattern generation stage to massively synthesize diverse and realistic layout patterns following the distribution of the undisclosable target layouts, while keeping these confidential layouts blind for any successive training stage, and (2) a complete self-training stage for building up an end-to-end on-neural-network mask optimization framework from scratch, which only requires the aforementioned generated patterns and a compact lithography simulation model as the inputs. Quantitative results demonstrate that our proposed flow achieves comparable state-of-the-art (SOTA) performance in terms of both mask printability and mask correction time while reducing 66% of the turn around time for flow construction.

Split manufacturing of integrated circuits means to delegate the front-end-of-line (FEOL) and back-end-of-line (BEOL) parts to different foundries, in order to prevent overproduction, intellectual property (IP) piracy, or targeted insertion of hardware Trojans (i.e., threats arising from adversaries in the FEOL foundry). This article challenges the security promise of split manufacturing by formulating various layout-level placement and routing hints as vector-based and image-based features that enable a sophisticated deep neural network (DNN), which can infer the missing BEOL connections with high accuracy. Compared with the network-flow attack (Wanget al., 2018), we achieve on average$1.21 \times $and$1.12 \times $of their correct connection rate (CCR; the higher, the better) when splitting after M1 and M3, respectively, with less than 1% of their runtime (across the same set of ISCAS-85 and ITC-99 benchmarks). Compared with Zenget al.(2019), ours reduces the candidate list (the smaller, the better) by 47% with only 1% loss of accuracy, and we further achieve an average CCR of$2.2 \times $of that of Zenget al.(2019). Aside from these superior results, we propose a randomized, routing-blockage-centric defense strategy to escalate the resilience against our and other attacks. Our defense strategy, which can be integrated into any commercial design flow, leads on average to$22.78~pp$(percentage points) degradation in CCR when compared with unprotected layouts, while inducing only 3.3% and 3.2% overheads on power and timing, respectively, within the same die outlines (i.e., zero area cost). The source code of our heterogeneous feature extraction is available athttps://github.com/cuhk-eda/split-extract, and the source code of our DNN is available athttps://github.com/cuhk-eda/split-attack.

Many competitive global routers adopt the technique of compressing the 3D routing space into 2D in order to handle today's massive circuit scales. It has been shown as an effective way to shorten the routing time, however, quality will inevitably be sacrificed to different extents. In this paper, we propose two routing techniques that directly operate on the 3D routing space and can maximally utilize the 3D structure of a grid graph. The first technique is called 3D pattern routing, by which we combine pattern routing and layer assignment, and we are able to produce optimal solutions with respect to the patterns under consideration in terms of a cost function in wire length and routability. The second technique is called multi-level 3D maze routing. Two levels of maze routing with different cost functions and objectives are designed to maximize the routability and to search for the minimum cost path efficiently. Besides, we also designed a cost function that is sensitive to resources changes and a post-processing technique called patching that gives the detailed router more flexibility in escaping congested regions. Finally, the experimental results show that our global router outperforms all the contestants in the ICCAD'19 global routing contest.

Recently the topic of routability optimization with prior knowledge obtained by machine learning techniques has been widely studied. However, limited by the prediction accuracy, the predictors of the existing related works can hardly be applied in a real-world EDA tool without extra runtime overhead for feature preparation. In this paper, we revisit this topic and propose a practical plug-in for routability optimization named PROS which can be applied in the state-of-the-art commercial EDA tool with negligible runtime overhead. PROS consists of an effective fully convolutional network (FCN) based predictor that only utilizes the data from placement result to forecast global routing (GR) congestion and a parameter optimizer that can reasonably adjust GR cost parameters based on prediction result to generate a better GR solution for detailed routing. Experiments on 19 industrial designs in advanced technology node show that PROS can achieve high accuracy of GR congestion prediction and significantly reduce design rule checking (DRC) violations by 11.65% on average.

The tremendous growth in deep learning (DL) applications has created an exponential demand for computing power, which leads to the rise of AI-specific hardware. Targeted towards accelerating computation-intensive deep learning applications, AI hardware, including but not limited to GPGPU, TPU, ASICs, etc., have been adopted ubiquitously. As a result, domain-specific CAD tools play more and more important roles and have been deeply involved in both the design and compilation stages of modern AI hardware. Recently, ISPD 2020 contest introduced a special challenge targeting at the physical mapping of neural network workloads onto the largest commercial deep learning accelerator, CS-1 Wafer-Scale Engine (WSE). In this paper, we proposed CU.POKer, a high-performance engine fully-customized for WSE's DNN workload placement challenge. A provably optimal placeable kernel candidate searching scheme and a data-flow-aware placement tool are developed accordingly to ensure the state-of-the-art quality on the real industrial benchmarks. Experimental results on ISPD 2020 contest evaluation suites [1] demonstrated the superiority of our proposed framework over other contestants.

Optical proximity correction (OPC) for advanced technology node now has become extremely expensive and challenging. Conventional model-based OPC encounters performance degradation and large process variation, while aggressive approach such as inverse lithography technology (ILT) suffers from large computational overhead for both mask optimization and mask writing processes. In this paper, we developed Neural-ILT, an end-to-end learning-based OPC framework, which literally conducts mask prediction and ILT correction for a given layout in a single neural network, with the objectives of (1) mask printability enhancement, (2) mask complexity optimization and (3) flow acceleration. Quantitative results show that, comparing to the state-of-the-art (SOTA) learning-based OPC solution and conventional ILT flow, Neural-ILT can achieve 30× ~ 70× turn around time (TAT) speedup with lower mask complexity and comparable mask printability. We believe this work could arouse the interests of bridging well-developed deep learning toolkits to GPU-based high-performance lithographic computations to achieve groundbreaking performance boosting on various computational lithography-related tasks.

VLSI layout patterns plays an important role in various research in Design for Manufacturing (DFM), such as optical proximity correction, lithography hotspot detection and so on. However, a large and diverse layout pattern library is usually not available during development stages due to the long and iterative technology life cycle, which brings potential difficulties to related research and slows down the development process. Although some previous works managed to enlarge pattern libraries with different solutions, there are still many challenges on generating complex DRC-clean two-dimensional patterns with specific styles. To address this problem, we explored the capability of generative machine learning models to learn the inherent distribution of a given set of non-trivial layouts for synthesizing diverse and realistic layout patterns with little manual guidance. For this purpose, we propose CUP, the CU pattern generation and legalization framework, which consists of two learning-based modules for pattern topology generation and design rule legalization respectively. Experiments show that CUP can generate diverse legal layout patterns which are comparable to actual design layouts in terms of resemblance in style and validity.

Different from global routing, detailed routing takes care of many detailed design rules and is performed on a significantly larger routing grid graph. In advanced technology nodes, it becomes the most complicated and time-consuming stage in the very large-scale integration physical design flow. We propose Dr. CU, an efficient and effective detailed router, to tackle the challenges. To handle a 3-D detailed routing grid graph of enormous size, a set of two-level sparse data structures is designed for runtime and memory efficiency. For handling the minimum-area constraint, an optimal correct-by-construction path search algorithm is proposed. Besides, an efficient bulk synchronous parallel scheme is adopted to further reduce the runtime usage. Compared with the other state-of-the-art academic detailed routers, Dr. CU reduces the number of design rule violations by one or two orders of magnitude. At the same time, it uses shorter wire length, fewer vias, and significantly less runtime. The source code of Dr. CU is available at https://github.com/cuhk-eda/dr-cu.

In a weighted undirected graph, a spanning/Steiner shallow-light tree (SLT) simultaneously approximates: 1) shortest distances from a root to the other vertices and 2) the minimum tree weight. The Steiner SLT has been proved to be exponentially lighter than the spanning one. In this paper, we propose a novel Steiner SLT construction method called Steiner SLT (SALT), which is efficient and has the tightest bound over all the state-of-the-art general-graph SLT algorithms. Applying SALT to Manhattan space offers a smooth tradeoff between rectilinear Steiner minimum tree and rectilinear Steiner minimum arborescence for VLSI routing. The adaption also reduces the time complexity from O(n2) to O(n log n). Besides, several effective post-processing methods, including safe refinement and shallowness-constrained edge substitution, are proposed to further improve the result. The experimental results show that SALT can achieve not only short path lengths and wirelength but also small delay, compared to both classical and recent routing tree construction methods.

In global routing, both timing and routability are critical criteria to measure the performance of a design. However, these two objectives naturally conflict with each other during routing. In this paper, we propose reconnection approaches to fix timing. We first formulated a quadratic program (QP), which adjusts routing topologies of all the nets by only reconnecting critical sinks and takes congestion into consideration to tradeoff timing and routability objectives. A machine learning (ML)-based technique is applied to accelerate our algorithm, which offers a fast and effective way to solve the problem. By exploring more reconnection candidates, we then formulated a QP to reconnect any sink of a net and utilized a multilabel classifier to accelerate the process. The experimental results on ICCAD 2015 benchmarks show that our algorithms can achieve timing improvement with no significant degradation in routability and wirelength. With ML-based acceleration, our results can be obtained in almost negligible runtime.

Mask optimization has been a critical problem in the VLSI design flow due to the mismatch between the lithography system and the continuously shrinking feature sizes. Optical proximity correction (OPC) is one of the prevailing resolution enhancement techniques (RETs) that can significantly improve mask printability. However, in advanced technology nodes, the mask optimization process consumes more and more computational resources. In this article, we develop a generative adversarial network (GAN) model to achieve better mask optimization performance. We first develop an OPC-oriented GAN flow that can learn target-mask mapping from the improved architecture and objectives, which leads to satisfactory mask optimization results. To facilitate the training process and ensure better convergence, we propose a pretraining scheme that jointly trains the neural network with inverse lithography technique (ILT). We also propose an enhanced generator design with a U-Net architecture and a subpixel super-resolution structure that promise a better convergence and a better mask quality, respectively. At convergence, the generative network is able to create quasi-optimal masks for given target circuit patterns and fewer normal OPC steps are required to generate high quality masks. The experimental results show that our flow can facilitate the mask optimization process as well as ensure a better printability.

There is substantial interest in the use of machine learning (ML)-based techniques throughout the electronic computer-aided design (CAD) flow, particularly those based on deep learning. However, while deep learning methods have surpassed state-of-the-art performance in several applications, they have exhibited intrinsic susceptibility to adversarial perturbations - small but deliberate alterations to the input of a neural network, precipitating incorrect predictions. In this article, we seek to investigate whether adversarial perturbations pose risks to ML-based CAD tools, and if so, how these risks can be mitigated. To this end, we use a motivating case study of lithographic hotspot detection, for which convolutional neural networks (CNN) have shown great promise. In this context, we show the first adversarial perturbation attacks on state-of-the-art CNN-based hotspot detectors; specifically, we show that small (on average 0.5% modified area), functionality preserving, and design-constraint-satisfying changes to a layout can nonetheless trick a CNN-based hotspot detector into predicting the modified layout as hotspot free (with up to 99.7% success in finding perturbations that flip a detector's output prediction, based on a given set of attack constraints). We propose an adversarial retraining strategy to improve the robustness of CNN-based hotspot detection and show that this strategy significantly improves robustness (by a factor of ∼3) against adversarial attacks without compromising classification accuracy.

<?tight?>To increase the resource utilization in multi-FPGA (field-programmable gate array) systems, time-division multiplexing (TDM) is a widely used technique to accommodate a large number of inter-FPGA signals. However, with this technique, the delay imposed by the inter-FPGA connections becomes significant. Previous research has shown that the TDM ratios of signals can greatly affect the performance of a system. In this article, to minimize the system clock period and support more practical constraints in modern multi-FPGA systems, we propose an analytical framework to optimize the TDM ratios of inter-FPGA nets. A Lagrangian relaxation-based method first gives a continuous result under relaxed constraints. A binary search--based discretization algorithm is then used to assign the TDM ratio of each net such that the resulting maximum displacement is optimal and all the constraints are satisfied. Finally, a swapping-based post refinement is performed to further optimize the TDM ratios. For comparison, we also solve the problem using linear programming (LP)--based methods, which have guaranteed error bounds to the optimal solutions. Experimental results show that our framework can achieve similar quality with much shorter runtime compared to the LP-based methods. Moreover, our framework scales for designs with over 45,000 inter-FPGA nets while the runtime and memory usage of the LP-based methods will increase dramatically as the design scale becomes larger.

Different from global routing, detailed routing takes care of many detailed design rules and is performed on a significantly larger routing grid graph. In advanced technology nodes, it becomes the most complicated and time-consuming stage. We propose Dr. CU, an efficient and effective detailed router, to tackle the challenges. To handle a 3D detailed routing grid graph of enormous size, a set of two-level sparse data structures is designed for runtime and memory efficiency. For handling the minimum-area constraint, an optimal correct-by-construction path search algorithm is proposed. Besides, an efficient bulk synchronous parallel scheme is adopted to further reduce the runtime usage. Compared with the first place of ISPD 2018 Contest, our router improves the routing quality by up to 65% and on average 39%, according to the contest metric. At the same time, it achieves 80--93% memory reduction, and 2.5--15X speed-up.

Continuous shrinking of VLSI technology nodes brings us powerful chips with lower power consumption, but it also introduces many issues in manufacturability. Lithography simulation process for new feature size suffers from large computational overhead. As a result, conventional mask optimization process has been drastically resource consuming in terms of both time and cost. In this paper, we propose a high performance machine learning-based mask printability evaluation framework for lithography-related applications, and apply it in a conventional mask optimization tool to verify its effectiveness.

The continuous development of modern VLSI technology has brought new challenges for on-chip interconnections. Different from classic net-by-net routing, bus routing requires all the nets (bits) in the same bus to share similar or even the same topology, besides considering wire length, via count, and other design rules. In this paper, we present MARCH, an efficient maze routing method under a concurrent and hierarchical scheme for buses. In MARCH, to achieve the same topology, all the bits in a bus are routed concurrently like marching in a path. For efficiency, our method is hierarchical, consisting of a coarse-grained topology-aware path planning and a fine-grained track assignment for bits. Additionally, an effective rip-up and reroute scheme is applied to further improve the solution quality. In experimental results, MARCH significantly outperforms the first place at 2018 IC/CAD Contest in both quality and runtime.

Dummy fill insertion is a mandatory step in modern semiconductor manufacturing process to reduce dielectric thickness variation, and provide nearly uniform pattern density for the chemical mechanical planarization (CMP) process. However, with the continuous shrinking of the VLSI technology nodes, the coupling effects between the inserted metal fills and signal tracks can severely affect the original timing closure of the layout design. In this paper, we propose a robust, efficient and high-performance framework for timing-aware dummy fill insertion, which simultaneously minimizes the coupling capacitance of critical signal wires and other wires. The experimental results on IC/CAD 2018 contest benchmarks shows that our proposed framework outperforms contest winner by 8% on critical coupling capacitance with 3.3× runtime speedup.

The notion of integrated circuit split manufacturing which delegates the front-end-of-line (FEOL) and back-end-of-line (BEOL) parts to different foundries, is to prevent overproduction, piracy of the intellectual property (IP), or targeted insertion of hardware Trojans by adversaries in the FEOL facility. In this work, we challenge the security promise of split manufacturing by formulating various layout-level placement and routing hints as vector- and image-based features. We construct a sophisticated deep neural network which can infer the missing BEOL connections with high accuracy. Compared with the publicly available network-flow attack [1], for the same set of ISCAS-85 benchmarks, we achieve 1.21× accuracy when splitting on M1 and 1.12× accuracy when splitting on M3 with less than 1% running time.

By retrospecting the classical deferred-merge embedding (DME) algorithm, we found an intrinsic relationship between the zero-skew tree (ZST) problem and the hierarchical clustering (HC) problem. To be more specific, the wire length of a ZST is proved a linear function of the sum of diameters of its corresponding HC. With this new insight, an effective O(n log n)-time O(1)-approximation algorithm and an optimal dynamic programming for ZST are designed. Using the ZST construction black box and a linear-time optimal tree decomposition algorithm, an improved algorithm for constructing the bounded-skew tree (BST) is derived. In the experiment, our approach shows superior wire length compared with previous methods for both ZST and BST.

Detailed routing becomes a crucial challenge in VLSI design with shrinking feature size and increasing design complexity. More complicated design rules were added to guarantee manufacturability, which made detailed routing an even harder task to achieve in the design flow. In this paper, we propose a detailed router that judiciously handles hard-to-access pins and new design rules including length-dependent parallel run length spacing, end-of-line spacing with parallel edges, and corner-to-corner spacing. Our experimental results show that our framework can effectively reduce the number of violations with comparable wirelength. Comparing our algorithm with the best score of each released designs in the ISPD'19 Contest, there is 2% score improvement. Compared with the state-of-the-art work, our algorithm achieves 69% better scores. The source code of Dr. CU 2.0 is available at https://github.com/cuhk-eda/dr-cu.

To increase the resource utilization in multi-FPGA systems, time-division multiplexing (TDM) is a widely used technique to accommodate a large number of inter-FPGA signals. However, with this technique, the delay imposed by the inter-FPGA connections becomes significant. Previous research has shown that the TDM ratios of signals can greatly affect the performance of a system. In this paper, to minimize the system clock period and support more practical constraints in modern multi-FPGA systems, we propose a two-step analytical framework to optimize the TDM ratios of inter-FPGA nets. A Lagrangian relaxation-based method first gives a continuous result under relaxed constraints. A binary search-based discretization algorithm is then used to finalize the TDM ratios such that the resulted maximum displacement is optimal. For comparison, we also solve the problem using linear programming (LP)-based methods, which have guaranteed error bounds to the optimal solutions. Experimental results show that our framework can achieve similar quality with much shorter runtime compared to the LP-based methods. Moreover, our framework scales for designs with over 45000 inter-FPGA nets while the runtime and memory usage of the LP-based methods will increase dramatically as the design scale becomes larger.

This paper studies the application of fixed-parameter tractable (FPT) algorithms to solve computer-aided design (CAD) problems. Specifically, we focus on layout decomposition problems for four lithography technologies: 1) double patterning lithography (DPL); 2) DPL with e-beam lithography; 3) DPL with directed self-assembly; and 4) DPL with directed self-assembly and e-beam lithography. Layout decomposition for the first three technologies are long-standing open problems without efficient optimal solutions, and the fourth technology is very promising in the future. The proposed approaches use ideas drastically different from all the previous works and can normally get optimal solutions in a short time. We show the great potential of applying FPT algorithms to solve more NP-hard problems efficiently in CAD.

Detecting layout hotspots is a key step in the physical verification flow. Although machine learning solutions show benefits over lithography simulation and pattern matching-based methods, it is still hard to select a proper model for large scale problems and inevitably, performance degradation occurs. To overcome these issues, in this paper, we develop a deep learning framework for high performance and large scale hotspot detection. First, we use feature tensor generation to extract representative layout features that fit well with convolutional neural networks while keeping the spatial relationship of the original layout pattern with minimal information loss. Second, we propose a biased learning (BL) algorithm to train the convolutional neural network to further improve detection accuracy with small false alarm penalties. In addition, to simplify the training procedure and seek a better tradeoff between accuracy and false alarms, we extend the original BL to a batch BL algorithm. Experimental results show that our framework outperforms previous machine learning-based hotspot detectors in both ICCAD 2012 Contest benchmarks and large scale industrial benchmarks. Source code and trained models are available at https://github.com/phdyang007/dlhsd.

Three-dimensional integrated circuit (3D IC) technology offers a potential breakthrough to enable a paradigm-shift strategy, called “more than Moore,” with novel features and advantages over the conventional 2D process technology. By having three-dimensional interconnections, 3D IC provides substantial wirelength reduction and a massive amount of bandwidth, which gives significant performance improvement to overcome many of the nontrivial challenges in semiconductor industry. Moreover, 3D integration technology enables to stack disparate technologies with various functionalities into a single system-in-package (SiP), introducing “true 3D IC” design. As the first physical design (PD) step, IC floorplanning takes a crucial role to determine IC’s overall design qualities such as footprint area, timing closure, power distribution, thermal management, and so on. However, lack of efficient 3D floorplanning algorithms that practically implement advantages of 3D integration technology is a critical bottleneck for PD automation of 3D IC design and implementation. 3D floorplanning (or packing, block partitioning) is a well-known NP-hard problem, and most of 3D floorplanning algorithms rely on heuristics and iterative improvements. Thus, developing complete and efficient 3D floorplan representations is important, since floorplan representation provides the foundation of data structure to search the solution space for 3D IC floorplanning. A well-defined floorplan representation provides a well-organized and cost-effective methodology to design high-performance 3D IC. We propose a new 3D IC floorplan representation methodology using corner links and partial order . Given a fixed number of cuboidal blocks and their volume, algorithmic 3D floorplan representations describe topological structure and physical positions/orientations of each block relative to the origin in the 3D floorplan space. In this article, (1) we introduce our novel 3D floorplan representation, called corner links representation , (2) we analyze the equivalence relation between the corner links representation and its corresponding partial order representation , and (3) we discuss several key properties of the corner links representation and partial order representation. The corner links representation provides a complete and efficient structure to assemble the original 3D mosaic floorplan. Also, the corner links representation for the non-degenerate 3D mosaic floorplan can be equivalently expressed by the four trees representation . The partial order representation defines the topological structure of the 3D floorplan with three transitive closure graphs (TCG) for each direction and captures all stitching planes in the 3D floorplan in the order of their respective directions. We demonstrate that the corner links representation can be reduced to its corresponding partial order representation, indicating that the corner links representation shares well-defined and -studied features/properties of 3D TCG-based floorplan representation. If the partial order representation describes relations between any pairs of blocks in the 3D floorplan, then the floorplan is a valid floorplan. We show that the partial order representation can restore the absolute coordinates of all blocks in the 3D mosaic floorplan by using the given physical dimensions of blocks.

Boolean matching is one of the most widely used engines in industrial applications. However, existing Boolean matching researches mainly focus on NPNP-equivalence. In this paper, we study a more practical problem of Boolean matching, which is Non-exact Projective NPNP (NP3). A two-step search engine is used to solve the problem and several heuristics and constraints are proposed to accelerate the whole process. In particular, we explore a new kind of symmetry properties in NP3 equivalence checking which helps to prune the solution space efficiently. Experimental results show that our proposed approach can achieve the best results among the winning teams of the ICCAD 2016 contest in quality within a given time limit.

Placement is one of the most critical stages in the physical synthesis flow. Circuits with increasing numbers of cells of multi-row height have brought challenges to traditional placers on efficiency and effectiveness. Furthermore, constraints on fence region and routability (e.g., edge spacing, pin access/short) should be considered, besides providing an overlap-free solution close to the global placement (GP) solution and fulfilling the power and ground (P/G) alignments. In this paper, we propose a legalization method for mixed-cell-height circuits by a window-based cell insertion technique and two post-processing network-flow-based optimizations. Compared with the champion of the IC/CAD 2017 Contest, our algorithm achieves 18% and 12% less average and maximum displacement respectively as well as significantly fewer routability violations. Comparing our algorithm with the state-of-the-art algorithms on this problem, there is a 9% improvement in total displacement with 20% less running time.

Mask optimization has been a critical problem in the VLSI design flow due to the mismatch between the lithography system and the continuously shrinking feature sizes. Optical proximity correction (OPC) is one of the prevailing resolution enhancement techniques (RETs) that can significantly improve mask printability. However, in advanced technology nodes, the mask optimization process consumes more and more computational resources. In this paper, we develop a generative adversarial network (GAN) model to achieve better mask optimization performance. We first develop an OPC-oriented GAN flow that can learn target-mask mapping from the improved architecture and objectives, which leads to satisfactory mask optimization results. To facilitate the training process and ensure better convergence, we also propose a pre-training procedure that jointly trains the neural network with inverse lithography technique (ILT). At convergence, the generative network is able to create quasi-optimal masks for given target circuit patterns and fewer normal OPC steps are required to generate high quality masks. Experimental results show that our flow can facilitate the mask optimization process as well as ensure a better printability.

While high-level synthesis (HLS) offers sophisticated techniques to optimize designs for area and performance, HLS-estimated resource usage and timing often deviate significantly from actual quality of results (QoR) achieved by FPGA-targeted designs. Inaccurate HLS estimates prevent designers from performing meaningful design space exploration without resorting to the time-consuming downstream implementation process. To address this challenge, we first build a large collection of C-to-FPGA results from a diverse set of realistic HLS applications and identify relevant features from HLS reports for estimating post-implementation metrics. We then leverage these features and data to train and compare a number of promising machine learning models to effectively and efficiently bridge the accuracy gap. Experiments demonstrate that our proposed approach is able to dramatically reduce the estimation errors for different families of FPGA devices. By extracting domain-specific insights from our experiments, we explore the implications of our models and predictive influence of various features for enabling fast and accurate QoR estimation in HLS. We have released our dataset to springboard future efforts in this area.

In global routing, both timing and routability are critical criterions to measure the performance of a design. However, these two objectives naturally conflict with each other during routing. In this paper, a tree surgery technique is presented to adjust routing tree topologies in global routing to fix timing. We formulate the problem as a quadratic program(QP), which adjusts routing topologies of all the nets from a global perspective and takes congestion into consideration to trade off timing and routability objectives. We also apply machine learning-based techniques to accelerate our algorithm, which offers a fast and effective way to solve the problem. Experimental results on ICCAD~2015 benchmarks show that our algorithms can achieve 10.12% timing improvement with no significant degradation in routability and wirelength. With machine learning-based acceleration (MLA), our results can be obtained in almost negligible runtime.

As a good tradeoff between central processing unit (CPU) and application specific integrated circuit (ASIC), field-programmable gate array (FPGA) is becoming more widely used in both industry and academia. The increasing complexity and scale of modern FPGA, however, impose great challenges on the FPGA placement and packing problem. In this paper, we propose RippleFPGA to solve the packing and placement simultaneously through a set of novel techniques: 1) smooth stair-step flow; 2) implicit packing similar to ASIC legalization (LG); and 3) two-level detailed placement (DP). To enable the flow, a generic, efficient, and false-alarm-free legality checking method is also proposed. Besides, due to the insufficiency of ASIC-like congestion alleviation methods, some FPGA-routing-architecture-aware optimization techniques are proposed to improve the routability. When evaluated by ISPD 2016 Contest benchmarks, RippleFPGA has 5.1% better routed wirelength and 5.5× speedup compared to all the state-of-the-art FPGA placers.

Block copolymer directed self-assembly (DSA) is a promising technique to print contacts/vias for the 10 nm technology node and beyond. By using hybrid lithography that incorporates DSA with multiple patterning, multiple masks are used to print the DSA templates and then the templates can be used to guide the self-assembly of the block copolymer. In this paper, we propose approaches to solve the simultaneous template optimization and mask assignment problem for DSA with multiple patterning. We verified in experiments that our approaches remarkably outperform the state-of-the-art work in reducing the manufacturing cost.

1-D gridded design is one of the most promising solutions that can enable the scaling to 10 nm technology node and beyond. Line-end cuts are needed to fabricate 1-D layouts, where two techniques are available to resolve the conflicts between cuts: 1) cut redistribution and 2) cut mask assignment. In this paper, we consider incorporating the two techniques to enable the manufacturing of cut patterns in 1-D gridded design. We consider both 2-mask case (double patterning is performed on the cuts) and 3-mask case (triple patterning is performed on the cuts). We first present an accurate integer linear programming (ILP) formulation that can solve the co-optimization of cut redistribution and mask assignment optimally. In addition, we propose efficient graph-theoretic approaches based on a novel integrated graph model and a longest-path-based refinement algorithm. Experimental results demonstrate that our graphtheoretic approaches are orders of magnitude faster than the ILP-based method and meanwhile it can obtain very comparable results. For 2-mask case, comparing with the method that solves mask assignment and cut redistribution optimally but separately, our graph-theoretic approach that solves the two tasks simultaneously can achieve 95.0× smaller cost on average. We also extend our graph-theoretic approach to 3-mask case. Comparing with the method that reduces the 3-mask problem to 2-mask problem and solves it indirectly, our innovative approach that solves the problem directly based on a novel framework of identifying and solving 4-cliques can achieve 7.6% smaller cost on average.

This paper studies the application of fixed-parameter tractable (FPT) algorithms to solve computer-aided design (CAD) problems. Specifically, we focus on layout decomposition problems for three lithography technologies: double patterning lithography (DPL), DPL with E-beam lithography (DPL+EBL), and DPL+DSA+EBL. Layout decomposition for the first two technologies are long-standing open problems without efficient optimal solutions, and the third technology is very promising in the future. The proposed approaches use ideas drastically different from all the previous works and can get optimal solutions in a short time. We show the great potential of applying FPT algorithms to solve more NP-hard problems efficiently in CAD.

Liquid cooling shows great potential in resolving the huge thermal obstacle in 3D ICs. However, it brings new challenges including large thermal gradient and high pumping requirement. In this paper, liquid cooling networks with flexible topology are investigated to achieve more desirable trade-offs between energy efficiency and thermal profile. Specifically, a fast thermal model for the cooling network is proposed and analyzed, followed by our optimization methodologies to construct cooling networks targeting at pumping power saving and thermal gradient reduction, respectively. Experimental results show that, under the same constraints, the cooling network can save as much as 84.03% pumping power or reduce 37.65% thermal gradient compared to straight microchannels.

Detecting layout hotspots is one of the key problems in physical verification flow. Although machine learning solutions show benefits over lithography simulation and pattern matching based methods, it is still hard to select a proper model for large scale problems and it is inevitable that performance degradation will occur. To overcome these issues, in this paper we develop a deep learning framework for high performance and large scale hotspot detection. First, feature tensor generation is proposed to extract representative layout features that fit well with convolutional neural networks while keeping the spatial relationship of the original layout pattern with minimal information loss. Second, we propose a biased learning algorithm to train the convolutional neural network to further improve detection accuracy with small false alarm penalties. Experimental results show that our framework outperforms previous machine learning-based hotspot detectors in both the ICCAD 2012 Contest benchmarks and large scale industrial benchmarks.

In a weighted undirected graph, a spanning/Steiner shallow-light tree (SLT) simultaneously approximates (i) shortest distances from a root to the other vertices, and (ii) the minimum tree weight. The Steiner SLT has been proved to be exponentially lighter than the spanning one [1], [2]. In this paper, we propose a novel Steiner SLT construction method called SALT (Steiner shAllow-Light Tree), which is efficient and has the tightest bound over all the state-of-the-art SLT algorithms. Applying SALT to Manhattan space offers a smooth trade-off between rectilinear Steiner minimum tree (RSMT) and rectilinear Steiner minimum arborescence (RSMA) for VLSI routing. In addition, the adaption further reduces the time complexity from O(n2) to O(n log n). The experimental results show that SALT can achieve not only short path lengths and wirelength but also small delay, compared to both classical and recent routing tree construction methods.

As the complexity and scale of circuits keep growing, clocking architectures of FPGAs have become more complex to meet the timing requirement. In this paper, to optimize wirelength and meanwhile meet emerging clocking architectural constraints, we propose several detailed placement techniques, i.e., two-step clock constraint legalization and chain move. After integrating these techniques into our FPGA placement framework, experimental results on ISPD 2017 benchmarks show that our proposed approach yields 2.3% shorter routed wirelength and the running time is 2x faster compared to the first place winner in the ISPD 2017 contest. Moreover, we explore the possibilities to use machine learning-based methods to predict routing congestion in UltraScale FPGAs. Experimental results on both ISPD 2016 and ISPD 2017 benchmarks show that our proposed congestion estimation model is a good approximation to the one obtained from Vivado and can lead to good placement results compared to the previous methods.

Advanced semiconductor process technologies are producing various circuit layout patterns, and it is essential to detect and eliminate problematic ones, which are called lithography hotspots. These hotspots are formed due to light diffraction and interference, which induces complex intrinsic structures within the formation process. Though various machine learning based methods have been proposed for this problem, most of them cannot capture the intrinsic structure of each data. In this paper, we propose a novel feature extraction by representing each data sample in matrix form. We argue that this method can well preserve the intrinsic feature of each sample, leading to better performance.We then further propose a bilinear lithography hotspot detector, which can tackle data in matrix form directly to preserve the hidden structural correlations in the lithography process. Experimental results show that the proposed method outperforms state-of-the-art ones with remarkably large margin in both false alarms and runtime, with 98.16% detection accuracy.

Block Copolymer Directed Self-Assembly (DSA) is a promising technique to print contacts/vias for the 10nm technology node and beyond. By using hybrid lithography that cooperates DSA with multiple patterning, multiple masks are used to print the DSA templates and then the templates can be used to guide the self-assembly of the block copolymer. In this paper, we propose approaches to solve the simultaneous template optimization and mask assignment problem for DSA with multiple patterning. We verified in experiments that our approaches remarkably outperform the state of the art work in reducing the manufacturing cost.

Typical standard cell placement algorithms assume that all cells are of the same height such that cells can be aligned along the placement rows. However, modern standard cell designs are getting more complicated and multiple-row height cell becomes more common. With multiple-row height cells, placement of cells are not independent among different rows. It turns out that most of the commonly used detailed placement and legalization techniques cannot be extended easily to handle the problem. We propose a novel algorithm in handling legalization of placement involving multiple-row height cells. The algorithm can efficiently legalize a local region of cells with various heights, which is especially useful for local cell movement, cell sizing, and buffer insertion. Experiments on the application of the technique in detailed placement show that our approach can effectively and efficiently legalize global placement results and obtain significant improvement in the objective function.

1D gridded design is one of the most promising solutions that can enable the scaling to 10nm technology node and beyond. Line-end cuts are needed to fabricate 1D layouts, where two techniques are available to resolve the conflicts between cuts: cut redistribution and cut mask assignment. In this paper, we consider incorporating the two techniques to enable the manufacturing of cut patterns in 1D gridded design. We first present an accurate integer linear programming (ILP) formulation that can solve the co-optimization of cut redistribution and mask assignment optimally. In addition, we propose an efficient graph-theoretic approach based on a novel integrated graph model and a longest-path-based refinement algorithm. Experimental results demonstrate that our graphtheoretic approach is orders of magnitude faster than the ILP-based method and meanwhile can obtain very comparable results. Comparing with the method that solves mask assignment and cut redistribution optimally but separately, our graph-theoretic approach that solves the two tasks simultaneously can achieve 95.0× smaller cost and 84.8× speedup on average.

As the complexity and scale of FPGA circuits grows, resolving routing congestion becomes more important in FPGA placement. In this paper, we propose a routability-driven placement algorithm for large-scale heterogeneous FPGAs. Our proposed algorithm consists of (1) partitioning, (2) packing, (3) global placement with congestion estimation, (4) window-base legalization, and (5) routing resource-aware detailed placement. Experimental results show that our proposed approach can give routable placement results for all the benchmarks in the ISPD2016 contest and can achieve good result compared to the other wining teams of the ISPD2016 contest.

With the continuous shrinking of technology nodes, lithography hotspot detection and elimination in the physical verification phase is of great value. Recently machine learning and pattern matching based methods have been extensively studied to overcome runtime overhead problem of expensive full-chip lithography simulation. However, there is still much room for improvement in terms of accuracy and Overall Detection and Simulation Time (ODST). In this paper, we propose a unified machine learning based hotspot detection framework, where feature extraction and optimization is guided by an information-theoretic approach and solved by a dynamic programming model. More importantly, our framework can be naturally extended to online learning scenario, where some newly detected and verified layout patterns are integrated into the learning model. Experimental results show that the proposed batch detection model outperforms all state-of-the-art methods with 3.47% of accuracy improvement and 58.88% of ODST reduction on ICCAD-2012 contest benchmark suite. More importantly, equipped with online learning, our framework can further improve both accuracy and ODST.

Routability is one of the most important problems in high-performance circuit designs. From the viewpoint of placement design, two major factors cause routing congestion: (i) interconnections between cells and (ii) connections on macro blockages. In this article, we present a routability-driven placer, Ripple 2.0, which emphasizes both kinds of routing congestion. Several techniques will be presented, including (i) cell inflation with routing path consideration, (ii) congested cluster optimization, (iii) routability-driven cell spreading, and (iv) simultaneous routing and placement for routability refinement. With the official evaluation protocol, Ripple 2.0 outperforms other published academic routability-driven placers. Compared with top results in the ICCAD 2012 contest, Ripple 2.0 achieves a better detailed routing solution obtained by a commercial router.

To reduce chip-scale topography variation, dummy fill is commonly used to improve the layout density uniformity. Previous works either sought the most uniform density distribution or sought to minimize the inserted dummy fills while satisfying certain density uniformity constraint. However, due to more stringent manufacturing challenges, more criteria, like line deviation and outlier, emerge at newer technology nodes. This article presents a joint optimization scheme to consider variation, total fill, line deviation, outlier, overlap, and running time simultaneously. More specifically, first we decompose the rectilinear polygons and partition fillable regions into rectangles for easier processing. After decomposition, we insert dummy fills into the fillable rectangular regions optimizing the fill metrics simultaneously. We propose three approaches, Fast Median approach, LP approach, and Iterative approach, which are much faster with better quality, compared with the results of the top three contestants in the ICCAD Contest 2014.

No abstract available.

Triple patterning lithography (TPL) is regarded as a promising technique to handle the manufacturing challenges in the 14nm technology node and beyond. It is necessary to consider TPL in early design stages to make the layout more TPL friendly and reduce the manufacturing cost. In this paper, we propose a flow to co-optimize cell layout decomposition and detailed placement. Our cell decomposition approach can enumerate all coloring solutions with the minimum number of stitches. The experimental results show that our approach can outperform the existing work in all aspects of stitch number, half-perimeter wirelength (HPWL), and running time. We further extend our placer to consider the displacement of cells as a constraint and as an objective, respectively, which can help to preserve the quality of the input placement. Effectiveness of the extensions is verified by the experiments.

3-D chips rely on massive interconnect structures, i.e., large groups of through-silicon vias coalesced with large multibit buses. We observe that wirelength optimization, a classical technique for floorplanning, is not effective while planning massive interconnects. This is due to the interconnects' strong impact on multiple design criteria like wirelength, routability, and temperature. To facilitate early design progress of massively-interconnected 3-D chips, we propose a novel 3-D-floorplanning methodology which accounts for different types of interconnects in a unified manner. One key idea is to align cores/blocks simultaneously within and across dies, thus increasing the likelihood of successfully implementing complex and massive interconnects. While planning such interconnects, we also target fast, yet accurate, thermal management, routability, and fixed-outline floorplanning. Experimental results on Gigascale Systems Research Center and IBM-HB+ circuits demonstrate our tool's capabilities for both planning massive 3-D interconnects and for multiobjective 3-D floorplanning in general.

Three-dimensional integrated circuits rely on optimized interconnect structures for blocks which are spread among one or multiple dies. We demonstrate how 2D and 3D block alignment can be efficiently utilized for structural planning of different interconnects. To realize this, we extend the corner block list and provide effective techniques for 3D layout generation, i.e., block placement and alignment. Our techniques are made available in an open-source, simulated-annealing-based tool. Besides block alignment, it accounts for key objectives in 3D design like fast thermal management and fixed-outline floorplanning. Experimental results on GSRC and IBM-HB+ circuits demonstrate the capabilities of our tool for both planning 3D-IC interconnects by block alignment and for 3D floorplanning in general.

The number of control pins used is a major factor affecting the manufacturing cost of Digital Microfluidic Biochip (DMFB). Pin-count on a DMFB can be reduced by sharing of control pins between electrodes. Most existing works on reducing pin-count are problem specific. Problem specific optimizations result in DMFB that can only perform certain specific bioassays. Cross-Referencing DMFB has a full array layout that is fully reconfigurable for any bioassay. Conventional Cross-Referencing DMFB uses m + n number of pins. We have devised a non-problem specific pin assignment methodology that uses only √2(√m + √n) number of pins. The resulting DMFB are still fully reconfigurable. We have developed a droplet router specifically for cross-referencing DMFB with shared control pins. All real bioassay tested can be routed using a fixed and problem independent control pin mapping. Reduction on pin count ranges from 50% to 67%.

As the sizes of modern circuits become bigger and bigger, implementing those large circuits into FPGA becomes arduous. The state-of-the-art academic FPGA place-and-route tool, VPR, has good quality but needs around a whole day to complete a placement when the input circuit contains millions of lookup tables, excluding the runtime for routing. To expedite the placement process, we propose a routability-driven placement algorithm for FPGA that adopts techniques used in ASIC global placer. Our placer follows the lower-bound-and-upper-bound iterative optimization process in ASIC placers like Ripple. In the lower-bound computation, the total HPWL, modeled using the Bound2Bound net model, is minimized using the conjugate gradient method. In the upper-bound computation, an almost-legalized result is produced by spreading cells linearly in the placement area. Those positions are then served as fixed-point anchors and fed into the next lower-bound computation. Furthermore, global routing will be performed in the upper-bound computation to estimate the routing segment usage, as a mean to consider congestion in placement. We tested our approach using 20 MCNC benchmarks and 4 large benchmarks for performance and scalability. Experimental results show that based on the island-style architecture which VPR is most optimized for, our approach can obtain a placement result 8x faster than VPR with 2% more in channel width, or 3x faster with 1% more in channel width when congestion is being considered. Our approach is even 14x faster than VPR in placing large benchmarks with over 10,000 lookup tables, with only 7% more in channel width.

Triple Patterning Lithography (TPL) is regarded as a promising technique to handle the manufacturing challenges in 14nm and beyond technology node. It is necessary to consider TPL in early design stages to make the layout more TPL friendly and reduce the manufacturing cost. In this paper, we propose a flow to co-optimize cell layout decomposition and detailed placement. Our cell decomposition approach can enumerate all coloring solutions with the minimum number of stitches. Experimental results show that our approach can outperform the existing work in all aspects of stitch number, HPWL and running time.

E-Beam Lithography (EBL) is a maskless nano-lithography technology that creates features on a wafer by directly shooting a beam of electrons onto the wafer. Different from the current mainstream optical lithography technology, i.e. 193nm ArF immersion lithography, EBL overcomes the limit of light diffraction. As one of the most promising next generation lithography (NGL) technologies, it can achieve very high resolution even for sub-10nm technology node. However, before EBL can be used for High Volume Manufacturing (HVM), its problem of low throughput has to be solved. Character Projection (CP) with a set of pre-defined characters is thought to be an essential technology for throughput improvement. With CP, a key problem is stencil planning, which is to select and place the best characters onto the stencil such that the throughput of the system can be maximized. If the overlapping between characters are awared, the throughput can be further optimized. In this paper, we investigate this 2D overlapping-aware stencil planning problem. Experiments show that our approach can achieve significant throughput improvement and remarkable speed-up comparing with previous works.

Digital Microfluidic Biochip(DMFB) allows traditional laboratory procedures to be conducted autonomously on a small chip. On a DMFB, the number of control pins is a limiting factor on maximum chip size and a major factor affecting the manufacturing cost. We have developed a methodology that reduces pin count in cross-referencing DMFB. Our algorithm simultaneously optimizing routing and control pin assignment. Experiments show that the proposed scheme can reduce pin-count by 23% to 32% with minimal effect on routing time.

Character projection is a key technology to enhance throughput of e-beam lithography, in which characters need to be selected and placed on the stencil. This paper solves the problem of planning for overlapping-aware row-structure stencil, and also considers multi-column cell system for further throughput improvement. We propose an integrated framework to solve the subproblems of character selection, row distribution, single-row ordering and inter-row swapping efficiently. Experiments show that our approach outperforms the existing methods on all the benchmarks. We can achieve significant throughput improvement and up to 1782X speedup comparing with previous works. The average speedup is 704X.

Modern placement process involves global placement, legalization, and detailed placement. Global placement produce a placement solution with minimized target objective, which is usually wire-length, routability, timing, etc. Legalization removes cell overlap and aligns the cells to the placement sites. Detailed placement further improves the solution by relocating cells. Since target objectives like wire-length and timing are optimized in global placement, legalization and detailed placement should not only minimize their own objectives but also preserve the global placement solution. In this paper, we propose a detailed placement algorithm for minimizing wire-length, while preserving the global placement solution by cell displacement constraint and target cell density objective. Our detailed placer involves two steps: Global Move that allocates each cell into a bin/region that minimizes wire-length, while not overflowing the target cell density. Local Move that finely adjust the cell locations in local regions to further minimize the wire-length objective. With large-scale benchmarks from ICCAD 2013 detailed placement contest, the results show that our detailed placer, RippleDP, can improve the global placement results by 13.38% - 16.41% on average under displacement constraint and target placement density objective.

Due to a significant mismatch between the objectives of wirelength and routing congestion, the routability issue is becoming more and more important in VLSI design. In this paper, we present a high quality placer Ripple 2.0 to solve the routability-driven placement problem. We will study how to make use of the routing path information in cell spreading and relieve congestion with tangled logic in detail. Several techniques are proposed, including (1) lookahead routing analysis with pin density consideration, (2) routing path-based cell inflation and spreading and (3) robust optimization on congested cluster. With the official evaluation protocol, Ripple 2.0 outperforms the top contestants on the ICCAD 2012 Contest benchmark suite.

Triple Patterning Lithography (TPL) is widely recognized as a promising solution for 14/10nm technology node. In this paper, we propose an efficient layout decomposition approach for TPL, with the objective to minimize the number of conflicts and stitches. Based on our analysis of actual benchmarks, we found that the whole layout can be reduced into several types of small feature clusters, by some simplification methods, and the small clusters can be solved very efficiently. We also present a new stitch finding algorithm to find all possible legal stitch positions in TPL. Experimental results show that the proposed approach is very effective in practice, which can achieve significant reduction of manufacturing cost, compared to the previous work.

In this paper, an effective simultaneous routing and placement refinement tool called SRP is proposed for routability improvement. SRP is independent of any placer and global router. Based on a given placement layout and global routing result, SRP relocates problematic cells by considering routing and placement simultaneously. Not only overflow from local nets, but overflow from global and semi-global nets can be solved by SRP. A cell will be relocated and its associated nets will be rerouted if its connections go across any congested region, even if the cell is not in the congested region. Therefore, our method can reduce the overflow effectively. Given the layouts generated by the top four routability-driven placers in the DAC Contest 2012, our method can still reduce the total overflow by 32.6% in average while the routed wirelength and HPWL are not increased obviously.

The significant mismatch between the objective of wirelength and routing congestion makes the routability issue even more important in placement. In this paper, we describe a routability-driven placer called Ripple. Each step, including global placement, legalization, and detailed placement, is made to trade-off between routability and wirelength. We propose a robust and effective flow by using cell inflation to relieve routing congestion. Cell inflation has traditionally been used to deal with congestion and we will discuss how this technique can be used easily and robustly in the global placement. Besides, unlike many previous works that focus on different types of swapping strategies, we analyze and propose some simple and effective approaches when considering routability in the legalization and detailed placement steps. Experimental results show that Ripple is particularly effective in improving routability. When compared to the top results in the ISPD 2011 Contest and SimPLR, Ripple can obtain the smallest overflow and half-perimeter wirelength on average, while the congestion hot spots are also distributed sparsely in Ripple.

In this paper, we present ObSteiner, an exact algorithm for the construction of obstacle-avoiding rectilinear Steiner minimum trees (OARSMTs) among complex rectilinear obstacles. This is the first paper to propose a geometric approach to optimally solve the OARSMT problem among complex obstacles. The optimal solution is constructed by the concatenation of full Steiner trees among complex obstacles, which are proven to be of simple structures in this paper. ObSteiner is able to handle complex obstacles, including both convex and concave ones. Benchmarks with hundreds of terminals among a large number of obstacles are solved optimally in a reasonable amount of time.

Link based non-tree clock network is an effective and economic way to reduce clock skew caused by variations. However, it is still an open topic where links should be inserted in order to achieve largest skew reduction with smaller extra resources. We propose a new method using linear program to solve this problem in this paper. In our approach, clock skew in a non-tree clock network is computed using the delay model in [13] and the information is used to select the node pairs for link insertion. Tradeoff between crosslink length and skew reduction effect is explored. Based on the analysis, we propose a new algorithm to insert crosslinks into a clock network. We compare our work with the method in [1] and a recent work [4] which inserts links between internal nodes of a tree. Experiments show that our method can reduce skew under variations effectively.

This work studies the problem of finding a rectilinear Steiner minimum tree (RSMT) for a set of given terminals in the presence of obstacles. In modern VLSI designs, obstacles usually block the device layer and a fraction of metal layers. Therefore, routing wires on top of obstacles is possible. However, if a long wire is routed over an obstacle, there will be signal integrity problems because buffers cannot be placed on top of any obstacle. To tackle this problem, we impose slew constraints on the interconnects that are routed over an obstacle. This is called the obstacle-avoiding rectilinear Steiner minimum trees (OARSMT) problem with slew constraints over obstacles. In this paper, we first analyze an optimal solution to this problem and show that the tree structures over obstacles with slew constraints will follow some very simple forms. Based on this observation, we propose an algorithm to find an optimal solution embedded in the extended Hanan grid [1]. The solutions can guarantee the interconnect performance and avoid post-routing electrical fixups due to slew violations. We also show that our algorithm achieves over 800 times speedup and is able reduce nearly 5% routing resources on average in comparison with the state-of-the-art optimal OARSMT algorithm.

Designing a high-quality clock network is very important in very large-scale integrated designs today, as it is the clock network that synchronizes all the elements of a chip, and it is also a major source of power dissipation of a system. Early study by Pham in 2006 shows that about 18.1% of the total clock capacitance was due to this postgrid clock routing (i.e., lower mesh wires plus clock twig wires). In this paper, we proposed a partition-based path expansion algorithm to solve this postgrid clock routing problem effectively. Experimental results on industrial test cases show that our algorithm can improve over the latest work by Shelar on this problem significantly by reducing the wire capacitance by 24.6% and the wirelength by 23.6%.

High power consumption will not only shorten the battery life of handheld devices, but also cause thermal and reliability problems. To lower power consumption, one way is to reduce the supply voltage as in multisupply voltage (MSV) designs. In region-based MSV, a circuit will be partitioned into “voltage islands” where each island occupies a contiguous physical space and operates at one supply voltage. In the work of Wu et al. [2005], this voltage supply problem is addressed, and the input placement is partitioned into a set of rectangular voltage islands by a slicing structure. However, the constraint of using a slicing structure prohibits better solutions in their approach. In the work of Ching et al. [2006], the constraint of obtaining rectangular shapes is relaxed; their method forms islands of very irregular shapes. In this article, we propose a method that focuses on forming rectangular voltage islands to minimize the power consumption, while at the same time favoring the power routing step. It is found that, even with this reduced flexibility on island shapes, we can still perform as well as, or in some cases, even better than the previous work of Ching et al. [2006] that does not control the shapes of the islands, in terms of power saving and island number.

In this paper, we introduce and study the Rectangle Escape Problem (REP), which is motivated by PCB bus escape routing. Given a rectangular region R and a set S of rectangles within R, the REP is to choose a direction for each rectangle to escape to the boundary of R, such that the resultant maximum density over R is minimized. We prove that the REP is NP-Complete, and show that it can be formulated as an Integer Linear Program (ILP). A provably good approximation algorithm for the REP is developed by applying Linear Programming (LP) relaxation and a special rounding technique to the ILP. This approximation algorithm is also shown to work for a more general version of REP with weights (weighted REP). In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. Our approach is tested on a set of industrial PCB bus escape routing problems. Experimental results show that the optimal solution can be obtained within 3 seconds for each of the test cases.

In this paper, we present an exact algorithm for the construction of obstacle-avoiding rectilinear Steiner minimum trees (OARSMTs) among complex rectilinear obstacles. This is the first work to propose a geometric approach to optimally solve the OARSMT problem among complex obstacles. The optimal solution is constructed by the concatenation of full Steiner trees (FSTs) among complex obstacles, which are proven to be of simple structures in this paper. The algorithm is able to handle complex obstacles including both convex and concave ones. Benchmarks with hundreds of terminals among a large number of obstacles are solved optimally in a reasonable amount of time.

Bus escape routing is a critical problem in modern PCB design. Due to the huge pin count and high density of the pin array, it usually requires multiple layers to route the buses without any conflict. How to assign the escape routing of buses to different layers becomes an important issue. In addition, some buses are required to be assigned on consecutive layers, which adds more difficulties to the layer assignment problem. In this paper, we propose a branch-and-bound based algorithm that optimally solves the layer assignment problem of bus escape routing. Our algorithm guarantees to produce a feasible layer assignment of the buses with a minimum number of layers. We applied our algorithm on industrial data and the experimental results validate our approach.

Monte-Carlo arithmetic is a form of self-validating arithmetic that accounts for the effect of rounding errors. We have implemented a floating point unit that can perform either IEEE 754 or Monte-Carlo floating point computation, allowing hardware accelerated validation of results during execution. Experiments show that our approach has a modest hardware overhead and allows the propagation of rounding error to be accurately estimated.

In this paper, we describe a routability-driven placer called Ripple. Two major techniques called cell inflation and net-based movement are used in global placement followed by a rough legalization step to reduce congestion. Cell inflation is performed in the horizontal and the vertical directions alternatively. We propose a new method called net-based movement, in which a target position is calculated for each cell by considering the movement of a net as a whole instead of working on each cell individually. In detailed placement, we use a combination of two kinds of strategy: the traditional HPWL-driven approach and our new congestion-driven approach. Experimental results show that Ripple is very effective in improving routability. Comparing with our pervious placer, which is the winner in the ISPD 2011 Contest, Ripple can further improve the overflow by 38% while reduce the runtime is reduced by 54%.

Clock distribution in VLSI designs is of crucial importance and it is also a major source of power dissipation of a system. For today's high performance microprocessors, clock signals are usually distributed by a global clock grid covering the whole chip, followed by post-grid routing that connects clock loads to the clock grid. Early study [2] shows that about 18.1% of the total clock capacitance dissipation was due to this post-grid clock routing (i.e., lower mesh wires plus clock twig wires). This post-grid clock routing problem is thus an important one but not many previous works have addressed it. In this paper, we try to solve this problem of connecting clock ports to the clock grid through reserved tracks on multiple metal layers, with delay and slew constraints. Note that a set of routing tracks are reserved for this grid-to-ports clock wires in practice because of the conventional modular design style of high-performance microprocessors. We propose a new expansion algorithm based on the heap data structure to solve the problem effectively. Experimental results on industrial test cases show that our algorithm can improve over the latest work on this problem [1] significantly by reducing the capacitance by 24.6% and the wire length by 23.6%. We also validate our results using hspice simulation. Finally, our approach is very efficient and for larger test cases with about 2000 ports, the runtime is in seconds.

This paper presents an efficient method to solve the obstacle-avoiding rectilinear Steiner tree (OARSMT) problem optimally. Our work is developed based on the GeoSteiner approach in which full Steiner trees (FSTs) are first constructed and then combined into a rectilinear Steiner minimum tree (RSMT). We modify and extend the algorithm to allow obstacles in the routing region. For each routing obstacle, we first introduce four virtual terminals located at its four corners. We then give the definition of FSTs with blockages and prove that they will follow some very simple structures. Based on these observations, a two-phase approach is developed for the construction of OARSMTs. In the first phase, we generate a set of FSTs with blockages. In the second phase, the FSTs generated in the first phase are used to construct an OARSMT. Finally, experiments on several benchmarks are conducted. Results show that the proposed method is able to handle problems with hundreds of terminals in the presence of multiple obstacles, generating an optimal solution in a reasonable amount of time.

Power consumption has become a crucial problem in modern circuit design. Multiple supply voltage (MSV) design is introduced to provide higher flexibility in controlling the power and performance tradeoff. One important requirement of MSV design is that timing constraints of the circuit must be satisfied after voltage assignment of the cells. In this article, we develop two algorithms to solve the voltage assignment problem under timing constraints, namely, min-cost flow (MCF) and value-oriented branch-and-bound (VOBB). In the MCF algorithm, the voltage assignment problem is formulated as a convex cost dual network flow problem, and can be solved optimally in polynomial time under certain conditions by calling a MCF solver. The VOBB algorithm, which is a VOBB-based searching method, solves the voltage assignment problem optimally in general cases by employing the MCF algorithm and a linear programming solver as subroutines. At last, we propose a MSV-driven floorplanning framework that optimizes power consumption and physical layout of a circuit simultaneously during the floorplanning stage, by embedding the MCF algorithm into a simulated annealing-based floorplanner and applying the VOBB algorithm as a postprocessing step. We compared our approach with the latest works on this problem, and the experimental results show that, using our approach, significant improvement on power saving can be achieved in much less running time, which confirms the effectiveness and efficiency of our method.

In today's system-on-chip designs, both digital and analog parts of a circuit will be implemented on the same chip. Parasitic mismatch induced by layout will affect circuit performance significantly for analog designs. Consideration of symmetry and common centroid constraints during placement can help to reduce these errors. Besides these two specific types of placement constraints, other constraints, such as alignment, abutment, preplace, and maximum separation, are also essential in circuit placement. In this paper, we will present a placement methodology that can handle all these constraints at the same time. To the best of our knowledge, this is the first piece of work that can handle symmetry constraint, common centroid constraint, and other general placement constraints, simultaneously. Experimental results do confirm the effectiveness and scalability of our approach in solving this mixed constraint-driven placement problem.

Power consumption and the thermal wall have become the major factors limiting the speed of very-large-scale integration (VLSI) circuits, while interconnect is becoming a primary power consumer. These factors bring new demands on the communication architecture of system-on-chips (SoCs). High bandwidth is desired to enhance parallelism for better performance, and the power efficiency on this bandwidth is critical to the overall SoC power consumption. Current bus architectures such as AMBA, Coreconnect, and Avalon are convenient for designers but not efficient on power. This paper proposes a physical synthesis scheme for on-chip buses and bus matrices to minimize the power consumption, without changing the interface or arbitration protocols. By using a bus gating technique, data transactions can take shortest paths on chip, reducing the power consumption of bus wires to minimal. Routing resource and bandwidth capacity are also optimized by the construction of a shortest-path Steiner graph, wire sharing among multiple data transactions, and wire reduction heuristics on the Steiner graph. Experiments indicate that the gated bus from our synthesis flow can save more than 90% dynamic power on average data transactions in current AMBA bus systems, which is about 5-10% of total SoC power consumption, based on comparable amount of chip area and routing resources.

Computer-aided design problems of digital microfluidic biochips are receiving much attention, and most of the previous works focus on direct-addressing biochips. In this paper, we solve the placement and droplet routing problem in cross-referencing biochips. In these biochips, the electrodes are addressed in a row-column manner, which may cause electrode interference that prevents simultaneous movements of multiple droplets. We propose a routing algorithm that solves the droplet routing problem directly. A two-coloring graph-theoretic method is used in our router to detect and prevent the electrode interference. In addition, we propose an integer linear programming based method to solve the placement problem. Our method considers the characteristics of cross-referencing biochips and is aware of droplet routing. Real-life benchmarks are used to evaluate the proposed methods. Compared with previous works, our router improves on average 4% in routing time and 58% in runtime. It can route all the benchmarks within the time limits, while the latest work fails in some cases. Moreover, experimental results show that by running our router on the placement result generated by our method and those generated by the latest work, an average improvement of 11%, 29%, 54%, and 46% in the maximum routing time, average routing time, stalling steps, and cell usage can be achieved.

In nanometer-scale VLSI physical design, clock network becomes a major concern on determining the total performance of digital circuit. Clock skew and PVT (process, voltage and temperature) variations contribute a lot to its behavior. Previous works mainly focused on skew and wirelength minimization. It may lead to negative influence towards these process variation factors. In this paper, a novel clock network synthesizer is proposed and several algorithms are introduced for performance improvement. A dual-MST (DMST) geometric matching approach is proposed for topology construction. It can help balancing the tree structure to reduce the variation effect. A recursive buffer insertion technique and a blockage handling method are also presented, and they are developed for proper distribution of buffers and saving of capacitance. Experimental results show that our matching approach is better than the traditional methods, and in particular our synthesizer has better performance compared to the results of the winner in the ISPD 2009 contest.

In this paper, we present a novel algorithm for 3D floorplanning with fixed outline constraints and a particular emphasis on thermal awareness. A computationally efficient thermal model that can be used to guide the thermal-aware floorplanning algorithm to reduce the peak temperature is proposed. We also present a novel white space redistribution algorithm to dissipate hotspot. Thermal through-silicon via (TSV) insertion is performed during the floorplanning process as a means to control the peak temperature. Experimental results are very promising and demonstrate that the proposed floorplanning algorithm has a high success rate at meeting the fixed-outline constraints while effectively limiting the rise in peak temperature.

Digital Microfluidic Biochip (DMFB) has drawn lots of attention today. It offers a promising platform for various kinds of biochemical experiments. DMFB that uses cross-referencing technology to drive droplets movements scales down the control pin number on chip, which not only brings down manufacturing cost but also allows large-scale chip design. However, the cross-referencing scheme that imposes different voltage on rows and columns to activate the cells, might cause severe electrode interference, and hence greatly decreases the degree of parallelism of droplet routing. Most of the previous papers get a direct-addressing result first, and then convert to cross-referencing compatible result. This paper proposes a new method that solves the droplet routing problem on cross-referencing biochip directly. Experimental results on public benchmarks demonstrate the effectiveness and efficiency of our method in comparison with the latest work on this problem.

In this paper, we present an efficient method to solve the obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem optimally. Our work is a major improvement over the work proposed in. First, a new kind of full Steiner trees (FSTs) called obstacle-avoiding full Steiner trees (OAFSTs) is proposed. We show that for any OARSMT problem there exists an optimal tree composed of OAFSTs only. We then extend the proofs on the possible topologies of FSTs in to find the possible topologies of OAFSTs, showing that OAFSTs can be constructed easily. A two-phase algorithm for the construction of OARSMTs is then developed. In the first phase, a sufficient number of OAFSTs are generated. In the second phase, the OAFSTs are used to construct an OARSMT. Experimental results on several benchmarks show that the proposed method achieves 185 times speedup on average and is able to solve more benchmarks than the approach in.

Clock network construction is one key problem in high performance VLSI design. Reducing the clock skew variation is one of the most important objectives during clock network synthesis. Local clock skew (LCS) is the clock skew between any two sinks with distance less than or equal to a given threshold. It is defined in the ISPD 2010 High Performance Clock Network Synthesis Contest, and it is a novel criterion that captures process variation effects on a clock network. In this paper, we propose a hybrid method that creates a mesh upon a tree topology. Total wire and buffer capacitance is minimized under the LCS and slew constraints. In our method, a clock mesh will be built first according to the positions and capacitance of the sinks. A top-level tree is then built to drive the mesh. A blockage-aware routing method is used during the tree construction. Experimental results show our efficiency and the solution generated by our approach can satisfy the LCS constraint of all the benchmarks in the contest, with a fair capacitance usage.

In this paper, we will present an effective layout method for analog circuits. We consider symmetry constraint, common centroid constraint, device merging and device clustering during the placement step. Symmetric routing will then be performed. In order to have successful routing, we will perform analog-based routability-driven adjustment during the placement process, taking into account for analog circuits that wires are not preferred to be layout on top of active devices. All these concepts were put together in our tool. Experimental results show that we can generate quality analog layout within minutes of time that passes the design rule check, layout-schematic verification and the simulation results are comparable with those of manual design, while a manual design will take a designer a couple of days to generate.

As the thermal wall becomes the dominant factor limiting VLSI circuit performance, and the interconnect wires become the primary power consumer, power efficiency of on-chip data throughput is nowadays a critical target for SoC designers. Under this trend, bus matrices are mostly used in current system-on-chips (SoCs) because of their simplicity and good performance. We introduce a bus matrix synthesis flow to optimize on-chip communications, to keep the low delay of buses, reduce power by bus gating, and reduce wires by wire sharing. The proposed algorithms are able to help designers create high capability yet compact and efficient bus matrices for future low power SoCs.

Digital Microfluidic Biochip (DMFB) is a revolutionary technology for performing lab-on-a-chip experiments. Comparing to traditional direct-addressing design of DMFB, Cross-Referencing Biochip is a flexible design which not only helps to reduce pin number on chip but also brings down manufacturing cost. Following the generally accepted DMFB top-down design methodology, namely task scheduling, resource binding, module placement, droplet routing, previous works that focus on cross-referencing biochip routing are all based on the placement result generated for direct-addressing biochip. In this paper, we present an ILP-based placement method that first utilizes the property of cross-referencing for the purpose of optimizing routing. Furthermore, one previously ignored electrode interference problem on modules (blocks) is addressed in this paper. Real-life bioassay protocol based benchmarks are used to evaluate the proposed method. Experimental results show that the placement result generated by our placer yields better routing result comparing with those from placer for direct-addressing DMFB.

Energy efficiency has become a very important issue to be addressed in today's system-on-a-chip (SoC) designs. One way to lower power consumption is to reduce the supply voltage. Multisupply voltage (MSV) is thus introduced to provide flexibility in controlling the power and performance tradeoff. In region-based MSV, circuits are partitioned into ¿voltage islands¿ where each island occupies a contiguous physical space and operates at one voltage level. These tasks of island partitioning and voltage level assignment should be done simultaneously in the floorplanning process in order to take those important physical information into consideration. In this paper, we consider this core-based voltage island driven floorplanning problem including islands with power down mode, and propose a method to solve it. Given a candidate floorplan solution represented by a normalized Polish expression, we are able to obtain optimal voltage assignment and island partitioning (including islands with power down mode) simultaneously to minimize the total power consumption. Simulated annealing is used as the basic searching engine. By using this approach, we can achieve significant power saving (up to 50%) for all datasets, without any significant increase in area and wire length. We compared our approach with the most updated previous work on the same problem, and results show that our approach is much more efficient and is able to save more power in most cases. We have also studied two other approaches to solve the same problem, a simple dynamic programming approach and a lowest possible power consumption approach. Experimental results show that ours can perform the best among these three approaches. Our floorplanner can also be extended to minimize the number of level shifters, to address a minVdd version of the problem and to simplify the power routing step by placing islands close to their corresponding power pins.

Interconnect dominated electronic design stimulates a demand for developing circuits on the third dimension, leading to 3-D integration. Recent advances in chip fabrication technology enable 3-D circuit manufacturing. However, there is still a possible barrier of design complexity in exploiting 3-D technologies. This article discusses the impact of migrating from 2-D to 3-D on the difficulty of floorplanning and placement. By looking at a basic formulation of the graph cuboidal dual problem, we show that the 3-D cases and the 3-layer 2.5-D cases are fundamentally more difficult than the 2-D cases in terms of computational complexity. By comparison among these cases, the intrinsic complexity in 3-D floorplan structures is revealed in the hard-to-decide relations between topological connections and geometrical contacts. The results show possible challenges in the future for physical design and CAD of 3-D integrated circuits.

In this paper, we will present a placement method for analog circuits. We consider both common centroid and 1D symmetry constraints, which are the two most common types of placement requirements in analog designs. The approach is based on a symmetric feasible condition on the sequence pair representation that can cover completely the set of all placements satisfying the common centroid and 1D symmetry constraints. This condition is essential for a good searching process to solve the problem effectively. symmetric placement is an important step to achieve matchings of other electrical properties like delay and temperature variation. We have compared our results with those presented in the most updated previous works. Significant improvements can be obtained by our approach in both common centroid and 1D symmetry placements, and we are the first who can handle both constraints simultaneously.

In this paper, we present an efficient method to solve the obstacle-avoiding rectilinear Steiner tree problem optimally. Our work is developed based on the GeoSteiner approach, modified and extended to allow rectilinear blockages in the routing region. We extended the proofs on the possible topologies of full Steiner tree (FST) in [4] to allow blockages, where FST is the basic concept used in GeoSteiner. We can now handle hundreds of pins with multiple blockages, generating an optimal solution in a reasonable amount of time. This work serves as a pioneer in providing an optimal solution to this difficult problem.

In this paper, we study the multiple voltage assignment (MVA) problem under timing constraints in floorplanning, which is generally an NP-hard problem. We will present an effective value-oriented branch-and-bound based algorithm to solve it optimally in a reasonable amount of time. A convex cost integer dual network flow approach is used to obtain a feasible upper bound solution, while a lower bound is obtained by a linear relaxation of a general formulation of the problem. We then adopt a value-oriented breadth-first branch-and-bound method with upper and lower bounds as described above to search for the optimal solution. Favorable results can be obtained in comparison with previous methods using a general linear programming solver. We integrate this algorithm into a multi-stage floorplanner. At the first stage, an initial floorplan is obtained by simulated annealing using the convex cost integer dual network flow approach as an evaluator. We then perform optimal voltage assignment to this initial floorplan. Finally, a post-processing step is done to modify the floorplan slightly to optimize the power network routing resource before invoking once more the optimal voltage assignment step at the end. Experimental results show that we can improve over the most updated work on this problem [7] by further reducing 6% of power consumption while maintaining the performance on other factors

Routability optimization has become a major concern in physical design of VLSI circuits. Due to the recent advances in VLSI technology, interconnect has become a dominant factor of the overall performance of a circuit. In order to optimize interconnect cost, we need a good congestion estimation method to predict routability in the early designing stages. Many congestion models have been proposed but there's still a lot of room for improvement. Besides, routers will perform rip-up and reroute operations to prevent overflow, but most models do not consider this case. The outcome is that the existing models will usually underestimate the routability. In this paper, we have a comprehensive study on our proposed congestion models. Results show that the estimation results of our approaches are always more accurate than the previous congestion models.

In this paper, the problem of bus driven floorplanning is addressed. Given a set of modules and bus specifications, a floorplan solution including the bus routes will be generated with the floorplan area and total bus area minimized. Some previous works have addressed this problem with restricted bus shapes of 0-bend, 1-bend or 2-bend [1]. However, in this paper, we address this bus driven floorplanning without any limitations on the shapes of the buses. We solve this problem by a simulated annealing based floorplanner using the Transitive Closure Graph (TCG) representation [6]. Experimental results show that we can improve over [1] significantly in terms of both run time and quality, since there are more flexibilities in routing the buses and complex shape validataion steps are not needed. For data sets with buses connecting a large number of blocks, our approach can still generate high quality solutions effectively, while the approach [1] of restricting to 2-bend buses often cannot give any feasible solutions.

In todaypsilas VLSI designs, there can be many blockages in a routing region. The obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem has become an important problem in the physical design stage of VLSI circuits. This problem has attracted a lot of attentions in research and several approaches have been proposed to solve this problem effectively. In this paper, we will present a heuristic maze routing based approach to solve this OARSMT problem. It is commonly believed that maze routing based approaches can only handle small scale problems and there is a lack of an effective multi-terminal variant to handle multi-pin nets in practice. We will show in this paper that maze routing based approaches can also handle large scale OARSMT problems effectively. Our approach is based on the searching process as in maze routing and can handle multi-pin nets very well in both solution quality, running time and memory space usage. We have compared our results with those of the previous works and can show that we can out-perform the best previous results on this problem [15] by giving an OARSMT with 2.01% less wire length on average and can make a 27.04% improvement in wire length in comparison with a lower bound of the optimal solution on average, while the running times are all very short and comparable to those in [15]. Besides, due to the flexibility of maze routing, we can handle different kinds of obstacles with different convex or concave rectilinear shapes directly without a need to partition each blockage into a set of rectangular sub-blockages, which will increase the size of the problem.

Power consumption has become a crucial problem in modern circuit design. Multiple Supply Voltage (MSV) design is introduced to provide higher flexibility in controlling the power and performance trade-off. One important requirement of MSV design is that timing constraints of the circuit must be satisfied after voltage assignment of the cells. In this paper, we will show that the voltage assignment task on a given netlist can be formulated as a convex cost dual network flow problem and can be solved optimally in polynomial time using a cost-scaling algorithm when the delay choices of each module are continuous in the real or integer domain. We can make use of this approach to obtain a feasible voltage assignment solution in the general cases with power consumption approximating the minimum one. Furthermore, we will propose a framework to optimize power consumption and physical layout of a circuit simultaneously during the floorplanning stage, by embedding this cost-scaling solver into a simulated annealing based floorplanner. This is effective in practice due to the short running time of the solver. We compared our approach with the latest work [9] on the same problem, and the experimental results show that, using our framework, significant improvement on power saving (18% less power cost on average) can be achieved in much less running time (7X faster on average) for all the test cases, which confirms the effectiveness of our approach.

3-D packing is an NP-hard problem with wide applications in microelectronic circuit design such as 3-D packaging, 3-D VLSI placement and dynamically reconfigurable FGPA design. We present a complete representation for general non-slicing 3-D floorplan or packing structures, which uses a labeled tree and dual sequences. For each compact placement, there is a corresponding encoding. The number of possible tree-sequence combinations is (n+1)n-1(n!)2, the lowest among complete 3-D representations up to date. The construction of placement from an encoding needs O(n2) in the worst case, but in practical cases we expect O(n4⁄3 log n) time on average for circuit blocks with limited length/width ratios. Experimental results show promising performance using the labeled tree and dual sequences on 3-D floorplan and placement optimizations

Recent advances in VLSI technology have made optimization of the interconnect delay and routability of a circuit more important. We should consider interconnect planning as early as possible. We propose a postfloorplanning step to reduce the interconnect cost of a floorplan by searching alternative packings. If a packing contains a rectangular bounding box of a group of modules, we can rearrange the blocks in the bounding box to obtain a new floorplan with the same area, but possibly with a smaller interconnect cost. Experimental results show that we can reduce the interconnect cost of a packing without any penalty in area.

Energy efficiency has become one of the most important issues to be addressed in today’s System-on-a-Chip (SoC) designs. One way to lower the power consumption is to reduce the supply voltage. Multi-supply voltage (MSV) is thus introduced to provide higher flexibility in controlling the power and performance trade-off. In regionbased MSV, circuits are partitioned into “voltage islands” where each island occupies a contiguous physical space and operates at one supply voltage. These tasks of island partitioning and voltage level assignments should be done simultaneously in the floorplanning process in order to take those important physical information into consideration. In this paper, we consider this core-based voltage island driven floorplanning problem including islands with power down mode, and propose a method to solve it. Given a candidate floorplan solution represented by a normalized Polish expression, we are able to obtain optimal voltage assignment and island partitioning (including islands with power down mode) simultaneously to minimize the total power consumption. Simulated annealing is used as the basic searching engine. By using this approach, we can achieve significant power savings (up to 50%) for all data sets, without any significant increase in area and wire length. Our floorplanner can also be extended to minimize the number of level shifters between different voltage islands and to simplify the power routing step by placing the islands in proximity to the corresponding power pins.

In order to reduce parasitic mismatch in analog circuits, some groups of devices are required to share a common centroid while being placed. Devices are split into smaller ones and placed with a common center point. We will address this problem of handling common centroid constraint in placement. A new representation called Center- based Corner Block List (C-CBL) is proposed which is a natural extension of Corner Block List (CBL) [1] to represent a common centroid placement of a set of device pairs. C-CBL is complete and non-redundant in representing any common centroid mosaic packings with pairs of blocks to be matched. To address the same problem with an additional constraint that devices are required to be placed uniformly to average out the parasitic errors, a grid-based approach is proposed. Experimental results show that both approaches are fast and promising, and have high scalability that even large data sets can be handled effectively.

In this paper, we study the retiming problem of sequential circuits with net topology optimization. Both interconnect and gate delay are considered in retiming. Most previous retiming algorithms have assumed ideal conditions for the nonlogical portions of data paths, which are not sufficiently accurate to be used in high-performance circuits today. In our modeling, we assume that the delay of a wire is directly proportional to its length. This assumption is reasonable since the quadratic component of a wire delay is significantly smaller than its linear component when the more accurate Elmore delay model is used. A simple experiment was conducted to illustrate the validity of this assumption. We present two approaches to solve the retiming problem, both of which have polynomial time complexity. The first one can compute the optimal clock period, while the second one is an improvement over the first one in terms of practical applicability. The second approach gives solutions that are very close to the optimal (0.06% more than the optimal on average) but in a much shorter runtime. The optimally retimed circuit will then be realized physically by placing the registers and finding the net topologies. In contrast to many previous works [Proc. IEEE Int. Conf. Comput.-Aided Des., p. 136, 1998], [IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 22(7) Jul. 2003] that performed simple calculations to determine the register positions, our approach can preserve the optimal clock period that is obtained by the retiming step and utilize as few registers as possible. Minimization of register number saves both area and power in register and clock loading. Our topology optimization step is shown to be optimal for nets with four or fewer pins, and this type of nets constitutes over 90% of the nets in a sequential circuit on average. Using the ISCAS89 benchmark, we tested our algorithm with a 0.35-mum complementary metal-oxide-semiconductor standard cell library. Silicon Ensemble was used to layout the design with a row utilization of 50%. Experimental results showed that our algorithm could find the best sharing of registers for a net in most of the cases, i.e., using the minimum number of registers while preserving the target clock period that is obtained by the retiming step, within a minute run on an Intel Pentium IV 1.5 GHz PC with 512 MB RAM.

Interconnect optimization has become the major concern in floorplanning. Many approaches would use simulated annealing (SA) with a cost function composed of a weighted sum of area, wirelength, and interconnect cost. These approaches can reduce the interconnect cost efficiently but the area penalty of the interconnect optimized floorplan is usually quite large. In this article, we propose an approach called deadspace utilization (DSU) to reclaim the unused area of an interconnect optimized floorplan by linear programming. Since modules are not necessarily rectangular in shape in floorplanning, some deadspace can be redistributed to the modules to increase the area occupied by each module. If the area of each module can be expanded by the same ratio, the whole floorplan can be compacted by that ratio to give a smaller floorplan. However, we will limit the compaction ratio to prevent overcongestion. Experiments show that we can apply this deadspace utilization technique to reduce the area and total wirelength of an interconnect optimized floorplan further while the routability can be maintained at the same time.

In a placed circuit, there are a lot of movable cells that can be flipped to further reduce the total wirelength, without affecting the original placement solution. We aim at solving this flipping problem optimally. However, solving such a problem optimally is non-trivial given the gigantic sizes of modern circuits. We are able to identify a large portion of cells (about 75%) of which the orientation (flipped or not flipped) can be determined independent of the orientations of all the other cells. We have derived three non-trivial conditions to identify those so called independent cells, strictly solvable cells and conditionally solvable cells. In this way, we can greatly reduce the number of cells whose orientations are dependent on each other. Finally, the cell flipping problem of the remaining dependent cells can be formulated as a Mixed Integer Linear Programming (MILP) problem and solved optimally. However, this may still be too slow for extremely large circuits and we have applied two other methods, Linear Programming (LP) and Linear Programming followed by Mixed Integer Linear Programming (LP+MILP) to solve the problem. Experimental results show that by identifying those independent and solvable cells first and applying the LP+MILP technique, we can solve this flipping problem effectively and obtain results just 0.01% more than the optimal. In addition, we can improve the wirelength and number of overflow tiles by 5% and 9% respectively on the floorplanning benchmarks.

In this paper we address the test scheduling problem for Builtin Self-tested (BISTed) embedded SRAMs (e-SRAMs) when Data Retention Faults (DRFs) are considered. The proposed test scheduling algorithm utilizes the "retention-aware"test power model [1] to minimize the total testing time of e- SRAMs while not violating given power constraints. Without losing generality, we consider both cases where the pause time for data retention faults is fixed and cases where it can be varied. Experimental results show that the "retention-aware" test scheduling algorithm can reduce the testing time of e- SRAMs up to more than 98 percent at the computational time within a second.

Multi Project Wafer (MPW) is an efficient method to share the mask cost among projects of different enterprisers for prototyping and low-volume manufacturing of IC designs. Designs from multiple customers can be put on one single mask substrate to produce MPW. Unlike traditional floorplanning, we need to consider the side-to-side wafer dicing constraint of the diamond sawing technology and different technology processes used in different projects for this problem. In our work, we use a branch and bound algorithm to solve this problem with a grid packing approach. We defined a special type of grid, called the modified α-restricted grid, to reduce the size of the searching solution space. Unlike many previous works, we consider non-zero margin width (but copies of the same design will have the same margin width), different technology processes of the projects, multiple copies of the same design on a mask, etc. In each searching step, our algorithm generates a grid and try to pack the dies into the grid by a Two Phase Packing(TPP) heuristic. We consider circular wafers and the objective is to minimize the total production cost. The experimental results are very promising and our approach can out-perform the most up-to-date works on this problem.

In modern IC design, the number of long on-chip wires has been growing rapidly because of the increasing circuit complexity. Interconnect delay has dominated over gate delay as technology advances into the deep submicron era. 3D chip is a feasible solution to these problems. It has been shown that interconnect lengths can be greatly reduced in 3D ICs. In this paper, a novel 3D floorplan representation namely Layered Transitive Closure Graph (LTCG) is proposed, which is based on the Transitive Closure Graph (TCG) representation for 2D non-slicing floorplans. In LTCG, we can impose topological relationships between both blocks of the same layer and blocks of different layers. Experimental results have shown that LTCG is very promising for multi-layer floorplanning and can handle the inter-layer alignment problem effectively.

High power consumption will shorten battery life for handheld devices and cause thermal and reliability problems. One way to lower the dynamic power consumption is to reduce the supply voltage. Multi-supply voltage (MSV) is introduced to provide higher flexibility in controlling the power and performance trade-off In region-based MSV, circuits are partitioned into "voltage islands" where each island occupies a contiguous physical space and operates at one supply voltage. In a very recent work [6], this supply voltage partitioning problem is addressed, and the input circuit is partitioned into a slicing structure with every voltage island rectangular in shape. This unnecessary restriction on the structure and island shapes has caused a significant degradation in the solution quality. In this paper, we propose a method to solove this voltage island generation problem without these restrictions. Experimental results have shown that our approach is fast and can improve the solution quality significantly. In some data sets, only two voltage islands are needed to satisfy the same power consumption bound while the approach in [6] will generate nineteen.

In order to handle device matching in analog circuits, some pairs of modules are required to be placed symmetrically. This paper addresses this device-level placement problem for analog circuits and our approach can handle symmetry constraint and other placement constraints simultaneously. The problem of placing devices with symmetry constraint has been extensively studied but none of the previous works has considered symmetry constraint with other placement constraints simultaneously. Instead of handling the constraints by having a penalty term in the cost function to penalize violations, a unified method is proposed that, by adjusting the edge weights in a pair of constraint graphs, can try to satisfy all the placement and symmetry constraints simultaneously in a candidate floorplan solution. The maximum distance of the modules in a symmetry group from the corresponding symmetry axis will be minimized in this weight adjusting step, in order to minimize the total packing area. We have compared our method with the most updated results on this problem [2] when there are only symmetry constraints and results show that our approach can give solutions of better quality, in an acceptable amount of run time. We will also demonstrate the effectiveness of our approach in handling different types of constraints simultaneously by testing on data sets with both symmetry and other placement constraints, and the results are very promising.

Routability optimization has become the major concern in floorplanning. In traditional floorplanners, area minimization is an important issue. Due to the recent advances in VLSI technology, interconnect has become a dominant factor to the overall performance of a circuit. Routability prediction is thus very important in the floorplanning stage. In this paper, we propose a new congestion model to predict the congestion after detailed routing which is not confined to the assumption of shortest Manhattan distance routes. We have compared our new models and some existing models with the actual congestion measures obtained by global routing some placement results (using the Capo placer [3]) with a publicly available maze router [2]. Results show that our models can make significant improvement in estimation accuracy over the other models.

In this paper, the problem of bus-driven floorplanning is addressed. Given a set of blocks and the bus specification (the width of each bus and the blocks that the bus need to go through), we will generate a floorplan solution such that all the buses go through its blocks, with the area of the floorplan and the total area of the buses minimized. The approach proposed is based on a Simulated Annealing framework. Using the sequence pair representation, we derived the necessary conditions for feasible buses, for which we allow 0-bend, one-bend, or two-bend. Then, we will check whether there are buses that cannot be placed at the same time. Finally, a solution will be generated giving the coordinates of the modules and the buses. Comparing with the results of the algorithm by Xiang et al., the dead space of the floorplan obtained is reduced. Besides, our algorithm can handle buses going through many blocks. For example, if the buses have to go through more than 10 blocks, is not able to generate any solution while our algorithm can still generate solutions of good quality.

As the CMOS technology is scaled into the dimension of nanometer, the clock frequencies and die sizes of ICs are shown to be increasing steadily [5]. Today, global wires that require multiple clock cycles to propagate electrical signal are prevalent in many deep sub-micron designs. Efforts have been made to pipe ine the long wires by introducing registers along these global paths, trying to reduce the impact of wire delay dominance [2, 8].The technique of retiming to relocate registers in a circuit without affecting the circuit functionality can be applied in this problem. Though the problem of retiming with gate and wire delay has been studied recent y [17, 1], the placement of registers after retiming is a new challenge. In this paper, we study the problem of realizing a retiming solution on a global netlist by inserting registers in the placement to achieve the target clock period.In contrast to many previous works [16, 11] that performed simple calculations to determine the positions of the registers, our proposed algorithm can preserve the given clock period and utilize as few registers as possible in the realization. What is more, the algorithm is shown to be optimal for nets with 4 or fewer pins and this type of nets constitutes over 90% of the nets in a sequential circuit on average.Using the ISCAS89 benchmark suite, we tested our algorithm with a 0.35 μm CMOS standard cell library, and Silicon Ensemble was used to layout the design with row utilization of 50%. Experimenta results showed that our algorithm can find the best sharing of registers for a net in most of the cases, i.e., using the minimum number of registers while preserving the target clock period, within a minute running on an Intel Pentium IV 1.5GHz PC with 512MB RAM.

Many previous works on floorplanning with nonrectangular modules assume that the modules are predesignated to have particular nonrectangular shapes, e.g., L-shaped, T-shaped, etc. However, this is not common in practice because rectangular shapes are more preferable in many designing steps. Those nonrectangular shapes are actually generated during floorplanning in order to further optimize the solution. In this paper, we study this problem of changing the shapes and dimensions of the flexible modules to fill up the unused area of a preliminary floorplan, while keeping the relative positions between the modules unchanged. This feature will also be useful in fixing small incremental changes during engineering change order modifications. We formulate the problem as a mathematical program. The formulation is such that the dimensions of all of the rectangular and nonrectangular modules can be computed by closed-form equations in O(m) time in each corresponding Lagrangian relaxation subproblem (LRS) where m is the total number of edges in the constraint graphs. As a result, the total time for the whole shaping and sizing process is O(k/spl times/m), where k is the number of iterations on the LRS. Experimental results show that the amount of area reused is 3.7% on average, while the total wirelength can be reduced by 0.43% on average because of the more compacted result packing.

In floorplan design, it is common that a designer will want to control the positions of some modules in the final packing for various purposes like datapath alignment and I/O connection. There are several previous works focusing on some particular kinds of placement constraints. In this paper, we will present a unified method to handle all of them simultaneously, including preplace constraint, range constraint, boundary constraint, alignment, abutment, and clustering, etc., in general, nonslicing floorplans. We have used incremental updates and an interesting idea of reduced graph to improve the runtime of the method. We tested our method using some benchmark data with about 1/8 of the modules having placement constraints and the results are very promising. Good packings with all the constraints satisfied can be obtained efficiently.

In traditional floorplanners, area minimization is an important issue. Due to the recent advances in VLSI technology, the number of transistors in a design and their switching speeds are increasing rapidly. This results in the increasing importance of interconnect delay and routability of a circuit. We should consider interconnect planning and buffer planning as soon as possible. In this paper, we propose a method to reduce interconnect cost of a floorplan by searching alternative packings. We found that if a floorplan F contains some rectangular supermodules, we can rearrange the blocks in the supermodule to obtain a new floorplan with the same area as F but possibly with a smaller interconnect cost. Experimental results show that we can always reduce the interconnect cost of a floorplan without any penalty in area and runtime by using this method.

In this paper, we study and implement a routability-driven floorplanner with congestion estimation and buffer block planning. We assume that buffers should be inserted at flexible intervals from each other for long enough wires. Under this buffer insertion constraint, our floorplanner will estimate congestion by computing the best possible buffer locations for each net and perform probabilistic analysis based on the solution. Dynamic programming is used such that estimations can be done very effectively. Nets are topologically grouped to consider bus-based routing and to facilitate the estimation process. We compare our results with those in paper [16] which are the latest results for this problem, and show that our approach can perform better in both quality and runtime.

In this paper, we present a clustering based algorithm for acyclic multi-way partitioning. Many existing partitioning algorithms have shown that clustering can effectively improve the solution quality. However, most of them do not consider the signal direction and thus cannot maintain the acyclic property. Our algorithm is based on clustering by computing the modified fan-out free cones. Fan-out free cone clustering can reduce a graph to a smaller and sparser one, and maintain the acyclic property at the same time. Experimental results showed that our algorithm compares favorably with the previous best acyclic multi-way partitioning algorithm in cut-size.

In this paper, we propose the idea of temporal logic replication in dynamically reconfigurable field-programmable gate array partitioning to reduce the communication cost. We show that this is a very effective means to reduce the communication cost by taking advantage of the slack logic capacity available. Given a K-stage temporal partition, the min-area min-cut replication problem is defined and we present an optimal algorithm to solve it. We also present a flow-based replication heuristic which is applicable when there is a tight area bound that limits the amount of possible replication. In addition, we show a correct network flow model for partitioning sequential circuits temporally and propose a new hierarchical flow-based performance-driven partitioner for computing initial partitions without replication.

In traditional floorplanners, area minimization is an important issue. However, due to the recent advances in very large scale integration technology, the number of transistors in a design are increasing rapidly and so are their switching speeds. This has increased the importance of interconnect delay and routability in the overall performance of a circuit. We should consider interconnect planning, buffer planning, and routability as early as possible. In this paper, we study and implement a routability-driven floorplanner with congestion estimation and buffer planning. Our method is based on a simulated annealing approach that is divided into two phases: the area optimization and congestion optimization phases. In the area optimization phase, modules are roughly placed according to the total area and wirelength. In the congestion optimization phase, a floorplan is evaluated by its area, wirelength, congestion, and routability. We assume that buffers should be inserted at flexible intervals from each other for long enough wires and probabilistic analysis is performed to compute the congestion information taken into account the constraints in buffer locations. Our approach is able to reduce the average number of wires at the congested areas and allow more feasible insertions of buffers to satisfy the delay constraints without having much penalty in increasing the area of the floorplan.

The efficiency and effectiveness of many floorplanning methods depend very much on the representation of the geometrical relationship between the modules. A good representation can shorten the searching process so that more accurate estimations on area and interconnect costs can be performed. Nonslicing floorplan is the most general kind of floorplan that is commonly used. Unfortunately, there is not yet any complete and nonredundant topological representation for nonslicing structure. In this paper, we propose the first representation of this kind. Like some previous work (Zhou et al. 2001), we have also made use of a mosaic floorplan as an intermediate step. However, instead of including a more than sufficient number of extra dummy blocks in the set of modules (that will increase the size of the solution space significantly), our representation allows us to insert an exact number of irreducible empty rooms to a mosaic floorplan such that every nonslicing floorplan can be obtained uniquely from one and only one mosaic floorplan. The size of the solution space is only O(n!2/sup 3n//n/sup 1.5/), which is the size without empty room insertion, but every nonslicing floorplan can be generated uniquely and efficiently in linear time without any redundant representation.

In floorplan design, it is useful to allow users to specify some placement constraints in the final packing. Clustering constraint is a popular type of placement constraint in which a given set of modules are restricted to be placed adjacent to one another. The wiring cost can be reduced by placing modules with a lot of interconnections closely together. Designers may also need this type of constraint to restrict the positions of some modules according to their functionalities. In this paper, a method addressing clustering constraint in slicing floorplan is presented. We devised a linear time algorithm to locate neighboring modules in a normalized Polish expression and to rearrange them to satisfy the given constraints. Experiments were performed on some benchmarks and the results are very promising.

Studies the problem of changing the shapes and dimensions of the flexible modules to fill up the unused area of a preliminary floorplan, while keeping the relative positions between the modules unchanged. The selection of modules and empty spaces is made by the users interactively. We formulate the problem as a mathematical program. We use the Lagrangian relaxation technique to solve the problem. The formulation is in such a perfect way that the dimensions of all the rectangular and nonrectangular modules can be computed by closed form equations efficiently.

In this paper, we study and implement a routability-driven floorplanner with buffer block planning. It evaluates the routability of a floorplan by computing the probability that a net will pass through each particular location of a floorplan taken into account buffer locations and routing blockages. Experimental results show that our congestion model can optimize congestion and delay (by successful buffer insertions) of a circuits better with only a slight penalty in area.

In this paper, we propose the idea of temporal logic replication in dynamically reconfigurable field-programmable gate array partitioning to reduce communication cost. Temporal logic replication has never been explored before. We define the min-area min-cut replication problem given a k-stage temporal partition satisfying all temporal constraints and devise an optimal algorithm to solve this problem. We have also devised a flow-based replication heuristic in case there is a tight area bound that limits the amount of replication. In addition, we will present a correct network flow model for partitioning sequential circuits temporally.

In traditional floorplanners, area minimization is an important issue. However, due to the recent advances in VLSI technology, the number of transistors in a design are increasing rapidly and so are their switching speeds. This has increased the importance of interconnect delay and routability in the overall performance of a circuit. We should consider interconnect planning, buffer planning and routability as early as possible. In this paper, we study and implement a routability-driven floorplanner with congestion estimation and buffer planning. Our method is based on a simulated annealing approach that is divided into two phases: the area optimization phase and the congestion optimization phase. In the area optimization phase, modules are roughly placed according to the total area and wirelength. In the congestion optimization phase, a floorplan will be evaluated by its area, wirelength, congestion and routability. We assume that every buffer should be inserted at a flexible interval from each other for long enough wires and probabilistic analysis is performed to compute the congestion information taken into accounts the constraints in buffer locations. Our approach is able to reduce the average number of wires at the congested areas and allow more feasible insertions of buffers to satisfy the delay constraints without having much penalty in increasing the area of the floorplan.

The efficiency and effectiveness of many floorplanning methods depend very much on the representation of the geometrical relationship between the modules. A good representation can shorten the searching process so that more accurate estimations on area and interconnect costs can be performed. Non-slicing floorplan is the most general kind of floorplan that is commonly used. Unfortunately, there is not yet any complete and non-redundant topological representation for non-slicing structure. In this paper, we will propose the first representation of this kind. Like some previous work [9], we have also made used of mosaic floorplan as an intermediate step. However, instead of including a more than sufficient number of extra dummy blocks in the set of modules, our representation allows us to insert an exact number of irreducible empty rooms to a mosaic floorplan in such a way that every non-slicing floorplan can be obtained by this method uniquely from one and only one mosaic floorplan. The size of the solution space is only O(n!23n/n1.5) but every non-slicing floorplan can be generated uniquely and efficiently in linear time without any redundant representation.

In floorplan design it is useful to allow users to specify placement constraints in the final packing. Clustering constraint is one kind of placement constraint in which a given set of modules are restricted to be geometrically adjacent to one another. The wiring cost can be reduced by putting modules with a lot of connections closely together. Designers may also need this type of placement constraint to pack the modules according to their functionality. In this paper, a method addressing clustering constraint in slicing floorplan is presented. A linear time algorithm is deviced to locate neighboring modules in a normalized Polish expression and re-arrange the modules in order to satisfy the constraints. Experiments were performed on some benchmarks and the results are promising.

In the early stage of floorplan design, many modules have large flexibilities in shape (soft modules). Handling soft modules in general nonslicing floorplan is a complicated problem. Many previous works have attempted to tackle this problem using heuristics or numerical methods, but none of them can solve it optimally and efficiently. In this paper, we show how this problem can be solved optimally by geometric programming using the Lagrangian relaxation technique. The resulting Lagrangian relaxation subproblem is so simple that the optimal size of each module can be computed in linear time. We implemented this method in a simulated annealing framework based on the sequence pair representation. The geometric program is invoked in every iteration of the annealing process to compute the optimal size of each module to give the best packing. The execution time is much faster (at least 15 times faster for data sets with more than 50 modules) than that of the most updated previous work by Murata and Kuh (1998). For a benchmark data with 49 modules, we take 3.7 h in total for the whole annealing process using a 600-MHz Pentium III processor while the convex programming approach described by Murata and Koh needs seven days using a 250-MHz DEC Alpha. Our technique will also be applicable to other floorplanning algorithms that use constraint graphs to find module positions in the final packing.

In floorplanning, it is common that a designer wants to have certain modules abutting with one another in the final packing. The problem of controlling the relative positions of an arbitrary number of modules in floorplan design is nontrivial. Slicing floorplan has an advantageous feature in which the topological structure of the packing can be found without knowing the module dimensions. This feature is good for handling placement constraints in general. In this paper, we make use of it to solve the abutment problem in the presence of L- and T-shaped modules. This is done by a procedure which explores the topological structure of the packing and finds the neighborhood relationship between every pair of modules in linear time. Our main contribution is a method that can handle abutment constraints in the presence of L- or T-shaped modules in such a way that the shape flexibility of the soft modules can still be fully exploited to obtain a tight packing. We tested our floorplanner with some benchmark data and the results are promising.

ABSTRACT Floorplan area minimization is an important problem because many modules have shape exibilities during the oorplanning stage. Area minimization in general non-slicing oorplan is a complicated problem. Many previous works have attempted to tackle this problem [9; 6; 5; 1] using heuristics or numerical methods but none of them can solve it optimally and e ciently. In this paper, we show how this problem can be solved optimally by a geometric programming using Lagrangian relaxation. The resulting Lagrangian relaxation subproblem is so simple that the size of each module can be found in constant time. We implemented our idea in a simulated annealing framework based on the sequence pair representation. The area minimization procedure is invoked in every iteration of the annealing process but the total execution time is still very much faster than that of the most updated previous work [4]. For a benchmark data with 49 modules, we take 19.5 hours using a 270 MHz Sun Ultra 5 while the convex programming approach in [4] takes seven days using a 250 MHz DEC Alpha. This area minimization method will be applicable to any other oorplanning algorithm which uses constraint graphs to nd module positions in the nal packing.

In floorplanning, it is important to allow users to specify placement constraints. Floorplanning with preplaced constraint was considered recently in Murata et al. (1997) and Young and Wong (1998). In this paper, we address a more general kind of placement constraint called range constraint in which a module must be placed within a given rectangular region in the floorplan. This is a more general formulation of the placement constraint problem and any preplaced constraint can be written as a range constraint. We extend the Wong-Liu algorithm (1986) to handle range constraint. Our main contribution is a novel shape curve computation which takes range constraint into consideration. Experimental results show that the extended floorplanner performs very well and, in particular, it out-performs the floorplanner proposed by Young and Wong (1998) when specialized to handle preplaced modules.

In floorplanning of VLSI design, it is useful if users are allowed to specify some placement constraints in the packing. One particular kind of placement constraints is to pack some modules on one of the four sides: on the left, on the right, at the bottom or at the top of the final floorplan. These are called boundary constraints. In this paper, we enhanced a well-known slicing floorplanner to handle these boundary constraints. Our main contribution is a necessary and sufficient characterization of the Polish expression, a representation of the intermediate solution in a simulated annealing process, so that we can check these constraints efficiently and can fix the expression in case the constraints are violated. We tested our algorithm on some benchmark data and the performance is good.

VLSI fabrication has entered the deep sub-micron era and communication between different components has significantly increased. Interconnect delay has become the dominant factor in total circuit delay. As a result, it is necessary to start interconnect planning as early as possible. We propose a method to combine interconnect planning with floorplanning. Our approach is based on the Wong-Liu (1986) floorplaning algorithm. When the positions, orientations, and shapes of the cells are decided, the pin positions and routing of the interconnects are decided as well. We use a multi-stage simulated annealing approach in which different interconnect planning methods are used in different ranges of temperature to reduce running time. A temperature adjustment scheme is designed to give smooth transitions between different stages of simulated annealing. Experimental results show that our approach performs well.

In floorplanning, it is important to allow users to specify placement constraints.Floorplanning with pm-placed constraint is considered recently in [3, 131.In this paper, we address a more general placement constraint called range constraint, in which a module must be placed within a given rectangular region in the floorplan.This is a more general formulation because any pre-placed constraint can be written as a range constraint.We extend the Wong-Liu algorithm [ll] to handle range constraint.Our main contribution is a novel shape curve computation which takes range constraint into consideration.Experimental results show that the extended floorplanner performs very well and, in particular, it out-performs the floorplauner in [13] when specialized to handle pm-placed modules.

The structural tree-based mapping algorithm is an efficient and popular technique for technology mapping. In order to make good use of this mapping technique in FTGA design, it is desirable to design FPGA logic modules based on Boolan functions which can be represented by a tree of gates (i.e., series-parallel or SP functions). Thakur and Wong [1996a; 1996b] studied this issue and they demonstrated the advantages of designing logic modules as universal SP functions, that is, SP functions which can implement all SP functions with a certain number of inputs. The number of variables in the universal function corresponds to the number of inputs to the FPGA module, so it is desirable to have as few variables as possible in the constructed functions. The universal SP functions presented in Thakur and Wong [1996a; 1966b] were designed manually. Recently, there is an algorithm that can generate these functions automatically [Young and Wong 1997], but the number of variables in the generated functions grows exponentially. In this paper, we present an algorithm to generate, for each n > 0, a universal SP function f n for implementing all SP functions with n inputs or less. The number of variables in f n is less than n 2.376 and the constructions are the smallest possible when n is small ( n ≤ 7). We also derived a nontrival lower bound on the sizes of the optimal universal SP functions (Ω( n log n )).

In floorplanning of very large scale integration design, it is useful if users are allowed to specify some placement constraints in the packing. One particular kind of placement constraints is to pack some modules on one of the four sides: on the left, on the right, at the bottom, or at the top of the final floorplan. These are called boundary constraints. In this paper, we enhanced a well-known slicing floorplan algorithm to handle these boundary constraints. Our main contribution is a necessary and sufficient characterization of the Polish expression, a representation of the intermediate solutions in the simulated annealing process, so that we can check these constraints efficiently and can fix the expression in case the constraints are violated. We tested our algorithm on some benchmark data and the performance is good.

Existing floorplanuers that use shcing floorplans are efficient in runtime and yet can pack modties tightly.Ho~vever,none of them can handle pre-placed modules.In this paper, }ve est end a ~ve~-kno~vnslicing floorplanner [10] to handle preplaced modules.Our main contribution is a novel shape curve computation procedure \vhich can take the positions of the pre-placed moddes into consideration.The shape curve computation procedure is used repeatedly during the floorplanning process to f~y exTloit the shape flexibility of the modules to give a tight packing.Expenmentd results sho~v that the extended floorplanner performs very ~ve~.

The structural tree-based mapping algorithm is an efficient and popular technique for technology mapping. In order to make good use of this mapping technique, it is desirable to design FPGA logic modules based on Boolean functions which can be represented by a tree of gates (i.e. series-parallel or SP functions). The authors previously studied this issue and demonstrated the advantages of designing logic modules as universal SP functions, i.e. SP functions which can implement all SP functions with a certain number of inputs. However, the universal SP functions presented earlier were designed manually and an automatic generation of universal SP functions was left as an open problem. They present an algorithm to generate, for each n>0, a universal SP function for implementing all n-input SP functions. They also present an efficient Boolean matching algorithm for matching functions to the universal SP functions that we constructed. As it is important to have alternative universal SP functions from which logic-module designers can choose a design taking other criteria (e.g. area, delay, or power) into consideration, they developed an algorithm to generate alternative universal SP functions. In particular, they have found all universal SP functions for n-input SP functions, when n/spl les/6.

Given a set of modules with flexibility in shape, we show that there exists a slicing floorplan F such that area(F ) minf(1 + 1 b p rc ); 5 4 ; (1 + ff)gA total where A total is the total area of all the modules, Amax is the maximum module area, ff = q 2Amax rA total and r 2 is the shape flexibility of each module. Our result shows that slicing floorplans can provably pack modules tightly. 1. INTRODUCTION Floorplan design plays an important role in the design of VLSI circuits in today's deep submicron technology. A slicing floorplan is a floorplan which can be obtained by recursively dividing a rectangle into two parts with either a vertical line or a horizontal line. Since slicing floorplans have very simple solution representations (e.g. slicing tree [4], Polish expression [6] etc.), it is easier to design efficient strategies to search for optimal slicing floorplans. As a result, slicing floorplans are used in many existing floorplanning systems [4, 3, 6, 5]. The only ...