The noisy intermediate-scale quantum (NISQ) computer significantly advances quantum computing technology. Due to the physical connectivity constraints of the NISQ device, its induced qubit mapping problem becomes more challenging. Recent works employ heuristics to achieve promising outcomes. However, they are limited to using only one type of center for graph matching, and their exhaustive traversal of the coupling graph results in high computation time. This paper strategically generates specific subgraphs during the initial mapping stage to reduce the solution space for the coupling graph. Then, we employ a bidirectional graph isomorphism search to improve initial mapping. In the main mapping stage, we develop an efficient search algorithm to minimize the number of inserted gates. Experimental results show that our method significantly outperforms the state-of-the-art work in reducing the number of inserted CNOT gates by 13.22% and the runtime by 19.61%.

Automatic printed circuit board (PCB) routing is essential to handle modern PCB designs with fast-growing problem sizes and complicated design constraints. Previous PCB routing studies have two major limitations: they consider uniform wire widths and keep-out distances (clearance rules) across all elements within the same layer. However, in modern PCB design, the mixed layout of high-current power wires and signal wires makes vastly different wire widths and complex clearance conditions issues that need to be addressed. Besides, irregular component shapes and special requirements for power loops impose more challenges. This paper presents a new PCB routing algorithm based on A*-search to handle these issues effectively. A frontier-checking method is proposed to efficiently verify whether the grid violates the complex clearance rules of any wire widths during routing. Besides, we propose a scheme to divide multi-pin nets in order to reduce the total wire length while effectively handling power-related constraints. Experimental results show that our routing algorithm significantly outperforms a state-of-the-art PCB router in terms of routability, total wire length, and runtime. Moreover, our algorithm achieves human-level performance and significantly outperforms Altium on the industrial benchmark.

In modern advanced packaging, redistribution layers (RDLs) are often used for signal transmission among chips, and vias are used for communication among different layers. Most existing RDL routers perform via planning before routing. However, since vias can be placed at arbitrary locations under the irregular via structure, via planning limits the solution space and reduces layout flexibility. This work proposes a new flow with a novel routing graph model for 90-and 135-degree routing, which allows dynamic via insertion during routing. The proposed algorithm enlarges the solution space by providing more choices during path-finding, achieving higher routing quality. The experimental results based on commonly used benchmark suites show that our router achieves shorter wirelength and runtime than state-of-the-art works, including an any-angle router.

The mismatch in thermal expansion coefficients among different materials leads to nonuniform deformation in a package, known as warpage. The warpage has become a significant reliability issue in advanced packaging that requires careful management. To address the issue, we have developed a high-fidelity warpage modeling approach that contains preprocessing followed by matrix calculations. This method transforms a three-dimensional packaging structure into a two-dimensional thermo-mechanical coupling problem, simplifying the packaging analysis. We apply finite element methods to the model and obtain the balance between accuracy and efficiency. Experimental results show that our model offers superior accuracy compared to the widely used Suhir’s model, achieving average speedups of 11.0X in preprocessing and 12130X in matrix calculations, with an overall speedup of 233.9X and only 1.0% error compared to the Ansys commercial analysis tool. This high efficiency and accuracy make our model suitable for large-scale optimization, package simulation, and modeling applications.

Placement plays a crucial role in modern chip design, aiming to determine the positions of circuit blocks (macros and standard cells). Traditional data structure-centric heuristics often yield suboptimal placement prototypes, ineffectively guiding downstream mixed-size analytical placement to find the desired results for modern large-scale designs. Recent works have showcased the potential of reinforcement learning (RL) to enhance chip placement by training a policy to place macros as a board game. However, placing macros and fixing them in the earlier stages without sufficient information often incurs undesired solutions. This paper proposes a novel RL-based mixed-size placer with iteratively moving the blocks to characterize dense rewards and comprehensive layout information in each step. We further introduce a semi-concurrent moving mechanism to learn the collaborative dynamics among actions on a subset of blocks at each step. We integrate continuous action spaces to develop a deep Q network-based model for learning the semi-concurrent moving policy to derive the proposed moving strategy. Compared with the state-of-the-art methods, experimental results show that our RL-based placer achieves the best placement quality based on commonly used mixed-size placement benchmarks.

The wavelength-routed optical network-on-chip (WRONoC) is a promising solution for system-on-chip designs. Recent work in the WRONoC topology designs mainly utilizes crossing switching elements (CSEs) as switching mechanisms on predefined templates. However, using CSEs incurs more microring resonator (MRR) usage and waveguide crossings than parallel switching elements (PSEs), and their predefined templates constrain the solution spaces. To remedy these disadvantages, we propose a fully automated topology design flow that utilizes PSE structures to reduce MRR usage and waveguide crossings. Our add-drop filter sequence model expands the solution space and leverages the advantage of the crossing-free PSE structure. Our fixed-node crossing-aware edge routing effectively minimizes the waveguide crossings, and our A*-search preserves the admissibility property and guarantees an optimal routing solution. Besides, our design flow thoroughly considers the physical layout information. Experimental results show that our design substantially outperforms state-of-the-art works on customized designs.

IR drop analysis in the power delivery network (PDN) is crucial for the signoff of integrated circuit (IC) design. Static IR drop significantly affects the IC reliability. Machine learning (ML) has recently been applied to static IR drop prediction for its high accuracy and efficiency. However, most previous works cannot predict with unseen designs, and none can handle different technologies. These problems lead to long training times and data-gathering difficulties, making ML-based methods impractical in the industry. Therefore, a more applicable methodology for static IR drop predictions is needed. This paper proposes a fast, robust, highly technology-transferable image-to-image ML-based methodology for static IR-drop prediction. To enhance transferability and accuracy, we introduce a new input feature, layerwise maps, which encapsulates the PDN network topology well. We further derive a novel generic ML model for various designs and technologies with different numbers of PDN layers. Experimental results demonstrate our methodology's high accuracy, robustness, and technology transferability. We used only ten circuits to tune our pre-trained model on a new technology and achieved an average error rate of 10.4% IR drop value on unseen circuits. Additionally, we tuned our pre-trained model for the 2023 ICCAD CAD Contest. Compared to the contest winner, our method gets a comparable average error rate of 0.000152mV with a run time of less than 1.5 seconds and improves the MAE of the worst case by 29.7%.

The complexity of design rules and intense time-to-market demands have made auto-placement tools essential for advanced printed circuit board (PCB) designs. This paper presents a novel PCB placement framework to handle pad-to-pad clearance constraints and heterogeneous components to address these challenges. Unlike existing academic placers, our framework focuses on the following key features: a wire-area model to account for various routing resource needs between power and signal nets, a pad-to-pad clearance model to minimize spacing violations, and a two-sided, pad-type-aware density model to reduce component and pad overlap. We further develop a quadratic programming-based legalizer to resolve constraint violations among components of varying shapes. Experimental results show the effectiveness and efficiency of our framework, surpassing two state-of-theart academic placers in post-routing quality on both academic and industrial benchmarks.

This paper presents the first warpage-aware generative learningbased floorplanning algorithm to effectively model the warpage effect and optimize the die floorplan on a fixed outlined substrate. With more heterogeneous materials and dense interconnects in advanced packaging, warpage is a main reliability concern and may degrade system performance. We present a novel transformer-based encoding scheme to learn node and edge representations, followed by parallel decoding and warpage-aware legalization to jointly minimize die displacement and warpage. Experimental results show that our algorithm improves warpage by 9.9% and wirelength by 8.3% on average, compared with the state-of-the-art work.

Global routing is a critical stage in the VLSI design flow, aiming to provide a robust guide for detailed routing and serve as early design feedback for placement. Many approaches have leveraged GPU parallelization to achieve significant acceleration. However, with the fast-growing complexity of modern large-scale designs, recent GPU-accelerated maze routing algorithms, driven by the sweep operation, struggle to find solutions efficiently with limited GPU memory resources. In order to address this issue, this paper proposes a scalable, GPU-friendly sweep-based maze routing that requires significantly less memory and fewer kernel function calls while accelerating overall runtime. We introduce a sweep-sharing technique that allows multiple nets to be routed simultaneously within a single sweeping process, substantially reducing memory consumption and kernel launching overhead. We further propose an edge-level rip-up-andreroute technique that selectively reroutes only overflowed segments, preserving feasible parts of the solution to reduce runtime substantially. Experimental results on the latest ISPD’24 Contest benchmarks demonstrate that our GPUfriendly maze routing with sweep sharing can significantly improve the efficiency of the state-of-the-art GPU-accelerated maze router.

Clustering single-bit flip-flops (SBFFs) into multi-bit flip-flops (MBFFs) effectively reduces power and area. However, excessive displacement during the clustering and legalization process may incur significant timing degradation. To address this issue, we propose the first comprehensive MBFF placement methodology that addresses excessive displacement caused by pre-placed cells during clustering and legalization while simultaneously optimizing timing, power, area, and bin utilization. Our methodology includes three main features: (1) a force model to relocate flip-flops and reduce timing violations, (2) a clustering and legalization process to reduce timing degradation caused by displacement, and (3) a multi-objective function to identify flip-flop candidates suitable for MBFF clustering. Our methodology outperforms all participating teams in the 2024 CAD Contest at ICCAD on Power and Timing Optimization Using Multi-Bit Flip-Flops, based on exactly the same settings.

In modern printed circuit board (PCB) designs, the increasing complexity poses more challenges for automatic placement. Existing PCB placement methods cannot handle complex constraints with heterogeneous, irregular-shaped, and any-oriented components for double-sided PCB designs well. This paper proposes the first constraint graph-based legalization approach for these constraints. We use a slicing technique to model a component more accurately with a set of rectangles instead of resorting to the naive bounding box approximation. Unlike the commonly used linear programming method for macro placement in integrated circuit (IC) designs, we employ a mixed integer linear programming (MILP) formulation to effectively expand the solution space for heterogeneous, irregular-shaped, and any-oriented components, particularly with high-density designs. Experimental results demonstrate the effectiveness and the robustness of our work.

This paper introduces an automated placement framework to optimize component positioning on modern printed circuit boards (PCBs), addressing challenges posed by heterogeneous components, irregular geometries, and complex design rules. The framework employs three key techniques to enhance placement quality and efficiency: (1) a global placement approach integrating collision detection via the Separating Axis Theorem to handle exact component contours and board shapes, (2) a multi-stage force-directed method that dynamically adjusts attractive and repulsive forces to meet clearance and routability constraints, and (3) a scanline-based legalization technique to resolve overlaps and enforce spacing requirements. Our methodology effectively adapts to diverse design limitations and accelerates the process while preserving placement quality. Experimental results demonstrate that our placer significantly improves routability over state-of-the-art solutions, demonstrating robust performance on industrial PCB designs with complex and irregular constraints.

Power distribution networks (PDNs) are designed to deliver sufficient and stable power to circuit components. For high-speed printed circuit boards (PCBs), transient current pulses increasingly affect the power integrity in PDNs, potentially leading to circuit malfunction or component damage. Decoupling capacitors (decaps) are placed on a PDN to ensure power stability. Minimizing the number of decaps becomes critical and has been extensively studied. Traditional heuristic methods often search for unnecessary spaces or get stuck in local minima. To overcome these limitations, we propose an analytical approach that reformulates the nonlinear decap placement problem as an equivalent integer semidefinite programming model. We adopt techniques like integer relaxation and port reduction to improve scalability and minimize the usage of decaps by an adaptive optimization scheme. Experimental results on industrial benchmarks demonstrate that our analytical decap placer achieves better results than the state-of-the-art non-deterministic methods and even significantly outperforms the commercial tool in solution quality and runtime.

This paper presents the first performance-driven pre-assignment routing algorithm for high-speed package designs. The proposed algorithm guarantees the minimum critical path length while preventing wire crossings within a single metal layer. A novel dynamic programming-based method is introduced to efficiently generate a high-quality baseline routing solution, allowing early termination in the subsequent search stage. Then, an efficient search-based method with effective pruning techniques is developed to optimally arrange all nets’ physical routing order, ensuring the minimum critical path length while avoiding suboptimal search branches. The proposed algorithm achieves a 32.9% reduction in the critical path length with only a 0.6% increase in the total path length compared with the previous work across five industrial designs. Furthermore, the proposed search-based method completes the largest design with more than 1000 nets in less than 1.6 seconds, delivering a 5000× speedup over exhaustive branch-and-bound methods while preserving optimality.

Warpage caused by the manufacturing thermal process can significantly reduce product yield in advanced packaging. As a result, numerical simulations such as finite element methods (FEMs) are often used to analyze warpage effects. However, constrained by the mesh generation and large matrix-solving requirements in finite element methods, optimizing for warpage can be time-consuming. This paper presents a fundamental physical model, training framework, and methodology for a warpage surrogate model based on DeepONets, a physics-informed operator learning framework. Experimental results show that our warpage model achieves an average speedup of 435X compared to traditional solvers while maintaining a minimal average warpage error of just 1.9%.

The fast-growing complexity of VLSI circuits with non-integer multiple-cell-height (NIMCH) standard cells poses new challenges for timing-aware node remapping. The existing remapping flow suffers from significant computational overhead due to exhaustive enumeration of all node-to-gate mapping combinations, including nodes and their fanin nodes. To remedy this inefficiency, we propose a novel NIMCH node remapping flow consisting of the following two schemes: a parallel longest-path-first scheme and an iterative minimum-slack-first scheme. Both schemes prioritize timing-critical nodes to reduce runtime. Moreover, the first scheme enables parallel execution, substantially accelerating the remapping process. Experimental results show that our proposed method achieves an average runtime speedup of 5.58X compared to the state-of-the-art approach, while preserving placement quality. The improved efficiency and scalability of our flow make it well-suited for large-scale physical design applications where rapid timing closure is essential.

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

This paper proposes a mixed-size 3D analytical placement framework for face-to-face stacked integrated circuits fabricated with heterogeneous technology nodes and connected by hybrid bonding technology. The proposed framework efficiently partitions a given netlist into two dies and optimizes the positions of each macro, standard cell, and hybrid bonding terminal (HBT). A multi-technology objective function and a multi-technology density penalty calculation process are adopted to handle the heterogeneous-technology-node constraints during mixed-size 3D global placement. Furthermore, a 3D objective function is used to refine the placement result during HBT-cell co-optimization. Our placer achieves the best results for all contest test cases compared with the participating teams at the 2023 CAD Contest at ICCAD on 3D Placement with Macros.

In modern advanced packaging, redistribution layers (RDLs) are often used for signal transmission among chips, and vias are used for communication among different layers. Most existing RDL routers perform via planning before routing. However, since vias can be placed at arbitrary locations under the irregular via structure, via planning limits the solution space and reduces layout flexibility. This paper proposes a new flow with a novel routing graph model for 90- and 135-degree routing, which allows dynamic via insertion during routing. The proposed algorithm enlarges the solution space by providing more choices during path-finding, achieving higher routing quality. The experimental results based on commonly used benchmark suites show that our router achieves over 10% better wirelength with over 29X speedup over the state-of-the-art work and even achieves 0.4% better wirelength with 55X speedup over the state-of-the-art any-angle router.

This paper proposes a power rail routing flow for advanced multi-layered printed circuit boards (PCBs) to optimize segment area and via usage while satisfying IR drop requirements. With increasing current/voltage demands in modern PCBs, ultra-wide power rails may consume most routing space and cause significant routing problems. We present an effective overlap-aware rail sizing technique to distribute routing spaces appropriately according to current/voltage demands and a resistance-aware A*-search algorithm to resolve overlapping regions by rail detouring. Experimental results show that our work significantly outperforms the state-of-the-art rail router in the metal area and runtime, achieving respective reductions of 49% and 28%, without any current/voltage violations.

Existing printed circuit board (PCB) placement often fails to address complex constraints (e.g., diverse wire widths and intricate spacing rules) arising from heterogeneous components in modern designs. Manual placement requires expertise and is time-consuming. Thus, automated PCB placement is desired for large-scale, complex designs considering irregular component shapes, clearance conditions, wire areas, power circuit flow, and routability. This paper proposes an efficient force-directed global placement followed by legalization to handle these constraints. We derive power circuit anchor points to guide global placement when considering the power circuit flow and present a simulated annealing-based pad alignment method to handle complex spacing constraints. After global placement, we perform window-based legalization to remove component overlaps considering various constraints. Experimental results show our placer's superior routability and efficiency with complex constraints.

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

The mismatch of thermal expansion coefficients between different materials incurs nonuniform deformation in a package called warpage. The warpage effect has evolved into a crucial reliability concern that demands careful management in advanced packaging. Considering the severe impact of the effect, we develop an efficient, high-fidelity warpage modeling of preprocessing followed by matrix calculation to address the issue by transforming a three-dimensional packaging structure to a two-dimensional thermo-solid coupling problem. The transformation provides an efficient measure to reduce the complexity of the packaging analysis. We then apply formal numerical methods to this model for a better trade-off between accuracy and efficiency. Experimental results show that our model averagely achieves respective speedups of 11.0X and 12130X in preprocessing and matrix calculation and an overall speedup of 233.9X with only 1.0% error over the Ansys commercial analysis tool. In particular, such high efficiency and accuracy enable our model for large-scale optimization, simulation, and modeling applications.

To achieve the power, performance, and area (PPA) target in modern semiconductor design, the trend to go for More-than-Moore heterogeneous integration by packing various components/dies into a package becomes more obvious as the economic advantages of More-Moore scaling for on-chip integration are getting smaller and smaller. In particular, we have already encountered the high cost of moving to more advanced technology and the high fabrication cost associated with extreme ultraviolet (EUV) lithography , mask, process, design, electronic design automation (EDA), etc. Heterogeneous integration refers to integrating separately manufactured components into a higher-level assembly (in a package or even multiple packages in a PCB) that provides enhanced functionality and improved operating characteristics. Unlike the on-chip designs with relatively regular components and wirings, the physical design problem for heterogeneous integration often needs to handle arbitrary component shapes, diverse metal wire widths, and different spacing requirements between components, wire metals, and pads, with multiple cross-physics domain considerations such as system-level, physical, electrical, mechanical, thermal, and optical effects, which are not well addressed in the traditional chip design flow. In this paper, we first introduce popular heterogeneous integration technologies and options, their layout modeling and physical design challenges, survey key published techniques, and provide future research directions for modern physical design for heterogeneous integration.

Qubit mapping is crucial in optimizing the performance of quantum algorithms for physical executions on quantum computing architectures. Many qubit mapping algorithms have been proposed for superconducting systems recently. However, due to their limitations on the physical qubit connectivity, costly SWAP gates are often required to swap logical qubits for proper quantum operations. Trapped-ion systems have emerged as an alternative quantum computing architecture and have gained much recent attention due to their relatively long coherence time, high-fidelity gates, and good scalability for multi-qubit coupling. However, the qubit mapping of the new trapped-ion systems remains a relatively untouched research problem. This paper proposes a new coupling constraint graph with multi-pin nets to model the unique constraints and connectivity patterns in one-dimensional trapped-ion systems. To minimize the time steps for quantum circuit execution satisfying the coupling constraints for trapped-ion systems, we devise a divide-and-conquer solution using Satisfiability Modulo Theories for efficient qubit mapping on trapped-ion quantum computing architectures. Experimental results demonstrate the superiority of our approach in scalability and effectiveness compared to the previous work.

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

Topological quantum error correction (TQEC) using the surface code is among the most promising techniques for fault-tolerant quantum circuits. The required resource of a TQEC circuit can be modeled as a space-time volume of a three-dimensional diagram by describing the defect movement along the time axis. For large-scale complex problems, it is crucial to minimize the space-time volume for a quantum algorithm with a reasonable physical qubit number and computation time. Previous work proposed an automated tool for bridge compression on a large-scale TQEC circuit. However, the existing automated bridge compression is only for dual defects and not for primal defects. This paper presents an algorithm to simultaneously perform bridge compression on primal and dual defects. In addition, the automatic compression algorithm performs initialization/measurement simplification and flipping to improve the compression. Compared with the state-of-the-art work, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 53%.

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

Two-dimensional directed self-assembly (2D-DSA) is an emerging lithography technology for advanced process nodes. We can determine the orientations of double posts to guide block copolymers to form feasible 2D guiding template patterns by the 2D-DSA process. This paper presents the first work to handle the 2D-DSA simultaneous placement and routing problem. We first propose a novel graph to model feasible guiding templates with a constant-time update scheme for each double-post assignment. Based on a graph model, we then present an algorithm for 2D-DSA simultaneous placement and routing, with a broadcast-based cost function for 2D-DSA cell placement and a graph-based scheme for DSA-compliant routing. Finally, we employ a strongly effective region property to minimize the cuts in the final layout. Experimental results show that our algorithm can efficiently generate a 2D-DSA placement and routing solution with high routability and a low cut number.

The wavelength-routed optical network-on-chip (WRONoC) emerges as a promising solution for multi-core system communication, providing high-bandwidth, high-speed, and low-power transmission. As the number of cores in a WRONoC increases, however, some WRONoC topologies could be infeasible with bandwidth and crosstalk constraints if bit-level parallelism is not considered during topology generation. Previous work optimized the parallelism only for the radius selection of microring resonators but not for topology generation. To remedy this drawback, we present a parallelism-aware WRONoC topology generation flow. The proposed flow guarantees to generate a parallelism-optimal topology for full connectivity; and a parallelism-optimal topology for customized connectivity if the netlist meets certain conditions. Compared with the state-of-the-art methods, experimental results show a 67.5% improvement in parallelism.

This paper proposes a high-quality 3D placement algorithm to determine the positions of standard cells and inter-die vias to optimize wirelength considering multiple manufacturing technologies for different dies. The algorithm consists of three major novel techniques: (1) a multi-technologies weighted-average (MTWA) wirelength model, (2) a weighted inter-die-connection cost controlling the net-degree distribution of the cut set, and (3) a via-cell co-optimization technique to further improve the quality of placement solutions. Compared with the winners at the 2022 CAD Contest at ICCAD on 3D Placement with D2D Vertical Connections, our placer achieves the best results for all nontrivial cases.

Redistribution layers (RDLs) are widely applied for signal transmissions in advanced packages. Traditional redistribution layer (RDL) routers use only 90- and 135-degree turns for routing. With technological advances, routing in RDLs can be any obtuse angle, leading to larger routing solution spaces and shorter total wirelength. This paper proposes the first any-angle routing algorithm in the literature for multiple RDLs. We first give a novel global routing algorithm with accurate routing resource estimation. A multi-net access point adjustment method is then proposed based on dynamic programming and our partial net separation scheme. Finally, we develop an efficient tile routing algorithm to obtain valid routes with fixed access points. Experimental results show that our algorithm can achieve a 15.7% shorter wirelength compared with a traditional RDL router.

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

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

The wavelength-routed optical network-on-chip (WRONoC) is a promising solution for advanced signal communication because of its high-bandwidth, low-latency, and power-efficient signal transmissions. Existing WRONoC topology designs rely on pre-defined network templates with limited solution space and design purposes. To remedy these disadvantages, we present a general model for WRONoC topologies. Based on this model, we propose a novel design flow for customized and fault-tolerant topologies to minimize the maximum insertion loss and the wavelength and micro-ring resonator (MRR) usage. Besides, we present two fault-tolerant topologies for full-connectivity netlists, namely the Actin-STAR and Zygo-STAR topologies. We prove that the Actin-STAR topology has a performance bound of 2.22 in the primary-path maximum insertion loss, and the Zygo-STAR topology has a performance bound of 1.39 in the backup-path one. Experimental results show that our designs significantly outperform the state-of-the-art designs in wavelength, MRR usage, and maximum insertion loss.

Modern heterogeneous integration requires dense IO interconnections among chips, such as CPU and memory, to facilitate bandwidth-aware packaging. The embedded multi-die interconnect bridge (EMIB) has attracted much attention recently by providing a high wiring density and low manufacturing cost. However, EMIB optimization must consider constrained wire orientations and crosstalk. This paper presents the first work on floorplanning for EMIB-based packaging. We first model the floorplanning problem for EMIB-based packaging. Based on a hybrid structure of transitive closure graphs and B*-trees, we present a novel simulated-annealing-based algorithm to efficiently generate the desired EMIB-aware floorplans. We employ maximum-spanning-tree-based partitioning and tree-based classification for already found partial topologies to search for desired solutions more efficiently. Experimental results show that our algorithm can significantly improve the area, total wirelength, and computation time compared with simulated annealing based on TCGs alone.

The dramatic growth of hardware attacks and the lack of security-concern solutions in design tools lead to severe security problems in modern IC designs. Although many existing countermeasures provide decent protection against security issues, they still lack the global design view with sufficient security consideration in design time. This paper proposes a security-aware framework against Trojan insertion, frontside probing, and fault injection attacks at the design stage. The framework consists of two major techniques: (1) a large-scale shielding method that effectively covers the exposed areas of assets and (2) a cell-movement-based method to eliminate the empty spaces vulnerable to Trojan insertion. Experimental results show that our framework effectively reduces the vulnerability of these attacks and achieves the best overall score compared with the top-3 teams in the 2022 ACM ISPD Security Closure of Physical Layouts Contest.

The dynamic IR drop of a power/ground (PG) network is a critical problem in modern circuit designs. Excessive IR drop slows down circuit performance and causes potential functional failures. Most industrial practices tend to over-design the PG network for the dynamic IR drop constraints, reducing routing resources and incurring routing congestion. Existing machine learning-based approaches target only dynamic IR drop prediction without considering the routability affected by the P/G network. This article develops a machine learning-based method to solve the dynamic IR drop and routing resources tradeoffs. Our model can predict the two targets accurately by adopting a multi-task learning scheme, achieving a 0.99 high correlation coefficient. We show that our trained model is generalizable by testing different placement results. Our algorithm also achieves significant speedups of up to 29× compared to the time-consuming dynamic IR drop simulation by a leading commercial tool. Experimental results show that our algorithm can save about 13% routing resources without worsening the dynamic IR drop peak value.

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

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

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

Recently, successful applications of reinforcement learning to chip placement have emerged. Pretrained models are necessary to improve efficiency and effectiveness. Currently, the weights of objective metrics (e.g., wirelength, congestion, and timing) are fixed during pretraining. However, fixed-weighed models cannot generate the diversity of placements required for engineers to accommodate changing requirements as they arise. This paper proposes flexible multiple-objective reinforcement learning (MORL) to support objective functions with inference-time variable weights using just a single pretrained model. Our macro placement results show that MORL can generate the Pareto frontier of multiple objectives effectively.

The optical interconnection is a promising solution for on-chip signal communication in modern system-on-chip (SoC) and heterogeneous integration designs, providing large bandwidth and high-speed transmission with low power consumption. Previous works do not handle two main issues for on-chip optical-electrical (O-E) co-design: the thermal impact during O-E routing and the trade-offs among power consumption, wirelength, and congestion. As a result, the thermal-induced band shift might incur transmission malfunction; the power consumption estimation is inaccurate; thus, only suboptimal results are obtained. To remedy these disadvantages, we present a thermal-aware optical-electrical routing co-design flow to minimize power consumption, thermal impact, and wirelength. Experimental results based on the ISPD 2019 contest benchmarks show that our co-design flow significantly outperforms state-of-the-art works in power consumption, thermal impact, and wire-length.

In modern VLSI designs, I/O counts have been growing continuously as the system becomes more complicated. To achieve higher routability, the hexagonal array is introduced with higher pad density and a larger pitch. However, the routing for hexagonal arrays is significantly different from that for traditional gird and staggered arrays. In this paper, we consider the Y-architecture-based flip-chip routing used for the hexagonal array. Unlike the conventional Manhattan and the X-architectures, the Y-architecture allows wires to be routed in three directions, namely, 0-, 60-, and 120-degrees. We first analyze the routing properties of the hexagonal array. Then, we propose a triangular tile model and a chord-based internal node division method that can handle both pre-assignment and free-assignment nets without wire crossing. Finally, we develop a novel dynamic programming-based bend minimization method to reduce the number of routing bends in the final solution. Experimental results show that our algorithm can achieve 100% routability with minimized total wirelength and the number of routing bends effectively.

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

Topological quantum error correction (TQEC) using the surface code is among the most promising techniques for fault-tolerant quantum circuits. The required resource of a TQEC circuit can be modeled as a space-time volume of a three-dimensional diagram by describing the defect movement along the time axis. For large-scale complex problems, it is crucial to minimize the space-time volume for a quantum algorithm with a reasonable physical qubit number and computation time. Previous work proposed an automated tool to perform bridge compression on a large-scale TQEC circuit. However, the existing automated bridging compression is only for dual defects and not for primal defects. This paper presents an algorithm to perform bridge compression on primal and dual defects simultaneously. In addition, the automatic compression algorithm performs initialization/measurement simplification and flipping to improve the compression. Compared with the state-of-the-art work, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 47%.

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

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

In advanced packages, redistribution layers (RDLs) are extra metal layers for high interconnections among the chips and printed circuit board (PCB). To better utilize the routing resources of RDLs, published works adopted flexible vias such that they can place the vias everywhere. Furthermore, some regions may be blocked for signal integrity protection or manually prerouted nets (such as power/ground nets or feeding lines of antennas) to achieve higher performance. These blocked regions will be treated as obstacles in the routing process. Since the positions of pads, obstacles, and vias can be arbitrary, the structures of RDLs become irregular. The obstacles and irregular structures substantially increase the difficulty of the routing process. This paper proposes a three-stage algorithm: First, the layout is partitioned by a method based on constrained Delaunay triangulation (CDT). Then we present a global routing graph model and generate routing guides for unified-assignment netlists. Finally, a novel tile routing method is developed to obtain detailed routes. Experiment results demonstrate the robustness and effectiveness of our proposed algorithm.

In modern heterogeneous integration technologies, chips with different processes and functionality are integrated into a package with high interconnection density and large I/O counts. Integrating multiple chips into a package may suffer from severe warpage problems caused by the mismatch in coefficients of thermal expansion between different manufacturing materials, leading to deformation and malfunction in the manufactured package. The industry is eager to find a solution for warpage optimization. This paper proposes the first warpage-aware floorplanning algorithm for heterogeneous integration. We first present an efficient qualitative warpage model for a multi-chip package structure based on Suhir's solution, more suitable for optimization than the time-consuming finite element analysis. Based on the transitive closure graph floorplan representation, we then propose three perturbations for simulated annealing to optimize the warpage more directly and can thus speed up the process. Finally, we develop a force-directed detailed floorplanning algorithm to further refine the solutions by utilizing the dead spaces. Experimental results demonstrate the effectiveness of our warpage model and algorithm.

Resistive Random Access Memory (ReRAM) Crossbars are a promising process-in-memory technology to reduce enormous data movement overheads of large-scale graph processing between computation and memory units. ReRAM cells can combine with crossbar arrays to effectively accelerate graph processing, and partitioning ReRAM crossbar arrays into Operation Units (OUs) can further improve computation accuracy of ReRAM crossbars. The operation unit utilization was not optimized in previous work, incurring extra cost. This paper proposes a two-stage algorithm with a crossbar OU-aware scheme for sparse graph index remapping for ReRAM (SGIRR) crossbars, mitigating the influence of graph sparsity. In particular, this paper is the first to consider the given operation unit size with the remapping index algorithm, optimizing the operation unit and power dissipation. Experimental results show that our proposed algorithm reduces the utilization of crossbar OUs by 31.4%, improves the total OU block usage by 10.6%, and saves energy consumption by 17.2%, on average.

As the design complexity grows dramatically in modern circuit designs, 2.5D/3D heterogeneous integration (HI) becomes effective for system performance, power, and cost optimization, providing promising solutions to the increasing cost of more-Moore scaling. In this talk, we investigate the chip, package, and board co-design methodology with advanced packages and optical communication considering essential issues on physical design, electrical, thermal, and mechanical effects, timing, and testing, and suggest future research opportunities. Layout: A robust and vertically integrated physical design flow for HI design is needed. We address chip-, package-, and board-level component planning, package-level RDL routing, board-level routing, optical routing, and placement and routing considering warpage and thermal effects. Timing: New chip-level and cross-chip timing analysis techniques are desired. We address timing propagation under current source delay model (CSM), timing analysis and optimization for optical-electrical routing, multi-corner multi-mode analysis for HI, hierarchical MCMM analysis. Testing: The scope covers functional-like test generation, System-in-Package (SiP) online testing, photonic integrated circuits (PIC) testing and design-for-test (DfT), etc. Integration: We shall address chip, package, and board co-design considering multi-domain physics, including physical, electrical, thermal, mechanical, and optical effects and optimization.

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

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

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

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

The wavelength-routed optical network on chip (WRONoC) is a promising solution for signal transmission in modern System-on-Chip (SoC) designs. Previous works do not simultaneously handle all the following four main issues for WRONoCs: 1) correlations between the topological structure and physical layout; 2) tradeoffs between the maximum insertion loss and the number of wavelengths; 3) runtime scalability of wavelength assignment scheme; and 4) a fully automated flow to generate predictable designs. As a result, their insertion loss estimation is inaccurate, their wavelength assignment is inefficient, and thus, only suboptimal results are obtained. To remedy these disadvantages, we present a fully automated topological structure and a physical layout co-design flow with improved wavelength assignment schemes to minimize the maximum insertion loss and the laser power simultaneously with a significant speedup. The experimental results show that our co-design flow significantly outperforms state-of-the-art works in the maximum insertion loss, laser power, and runtimes.

As the VLSI technology continues to scale down, combined with increasing demands for large bandwidth and low-power consumption, the optical interconnections with wavelength-division multiplexing (WDM) become an attractive alternative for on-chip signal transmission. Previous WDM-aware optical routing works consist of three main drawbacks: they are based mainly on heuristics or restricted integer linear programming to handle optical routing, the addressed types of insertion loss, and WDM overheads are incomplete, and the crosstalk noise during concurrent signal transmission is neglected. As a result, no performance guarantees can be achieved on their WDM clustering results, the reliability of the optical network is impaired, and/or their computations are too time consuming. To remedy these disadvantages, we present a new WDM-aware optical routing flow to minimize the insertion loss, the WDM overheads, and the crosstalk noise with a significant speedup. In the proposed flow, the WDM-aware path clustering algorithm guarantees to find an optimal solution for 1-, 2-, and 3-path clustering and has the constant performance bound for most cases of 4-path clustering; the crosstalk-aware path assignment guarantees to minimize the number of crosstalk signal pairs within the given displacement bound. Experimental results based on the ISPD 2007 and 2019 contest benchmarks and a real optical design show that our optical router significantly outperforms published works in wirelength, insertion loss, wavelength power, crosstalk noise, and runtimes.

Topological quantum error correction (TQEC) is promising for scalable fault-tolerant quantum computation. The required resource of a TQEC circuit can be modeled as its space-time volume of a three-dimensional geometric description. Implementing a quantum algorithm with a reasonable physical qubit number and computation time is challenging for large-scale complex problems. Therefore, it is desirable to minimize the space-time volume for large-scale TQEC circuits. Previous work proposed bridge compression, which can significantly compress a TQEC circuit, but it was performed manually. This article presents the first automated tool that can perform bridge compression on a large-scale TQEC circuit. Our proposed algorithm applies the bridge compression technique to compactify TQEC circuits with modularization. Besides, we offer a time-ordering-aware 2.5-D placement for compacting TQEC circuits and satisfying time-ordered measurement constraints. On the other hand, we suggest friend net-aware routing to effectively reduce the required routing resource under topological deformation. Compared with the state-of-the-art work, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 84%.

The integrated fan-out (InFO) wafer-level chip-scale package (WLCSP) is introduced for modern system-in-package designs with larger I/O counts, higher interconnection density, and small form factors. A redistribution layer (RDL) in an InFO package is an extra metal layer for interchip connections, and RDL routing is crucial for achieving desired interchip connections. In a high-density InFO package, multiple RDLs with flexible vias are often adopted. To integrate chips of different technology nodes into one package, irregular pad structures need to be considered; however, no published RDL routing work considers flexible vias or irregular pad structures. This article formulates a new RDL routing problem with unified-assigned pad pairs on a via-based multilayer multichip InFO package with irregular pad structures and presents the first algorithm for this problem. The algorithm consists of a preprocessing stage, three routing stages, and a layout optimization stage. The preprocessing stage analyzes routing resources and potential routing congestion. The first routing stage performs layer assignment based on a weighted maximum planar subset of chords algorithm to route interchip nets concurrently. The second routing stage constructs a 3-D routing graph based on partitioned octagonal tiles to handle the irregular layout structure and applies A*-search to route remaining interchip nets. The third routing stage transforms a routing graph into a network-flow model to perform concurrent routing for chip-to-board nets by applying the minimum-cost maximum-flow algorithm. Finally, we develop an efficient linear-programming-based layout optimization algorithm to find desired solutions. Experimental results show that our router can achieve 100% routablility for all benchmarks under limited RDLs, while the previous state-of-the-art work cannot.

In modern packaging technology, redistribution layers (RDLs) are often used to redistribute interconnections among multiple chips and between I/O pads and bump pads. For high-density RDL routing, irregular vias, where vias can be placed at arbitrary locations, are adopted to better utilize RDL resources to obtain desired routing solutions. As the problem size increases, however, using irregular vias may suffer from high computation overheads. Moreover, most previous works route pre-assignment (PA) and free-assignment (FA) nets in separate stages, incurring routing resource competition. To remedy these disadvantages, we propose a simultaneous PA and FA routing framework with irregular RDL via planning. In this paper, we first propose a novel partitioning method based on the Voronoi diagram to handle irregular via structures and derive a theoretical upper bound on the number of generated regions. We then propose a chord-based tile model and a net-sequence list to generate non-crossing guides for PA and FA nets on the same routing graph. Finally, we develop a novel geometry-based pattern routing to obtain the final solutions. Experimental results show that our work can achieve 100% routability and an average 30X speedup over the-state-of-the-art work.

A multi-FPGA system consists of multiple FPGAs connected by physical wires, and a circuit is partitioned to fit each FPGA and routed on the system by such physical wires. Due to the limited numbers of input/output (I/O) pins in an FPGA, however, not all signals can be transmitted between FPGAs directly. Moreover, the routing resource may not be sufficient to accommodate many cross-FPGA signals from circuit partitioning. As a result, input/output time-division multiplexing (TDM) is introduced to send a group of cross-FPGA signals in a routing channel with a timing penalty. To optimize the performance of such a system, we shall develop a simultaneous partitioning and routing algorithm considering the timing penalty caused by I/O TDM. Considering the TDM delay penalty, we propose a simultaneous partitioning and routing algorithm to remedy the insufficiency of the two-stage flow of partitioning followed by routing. Our algorithm consists of two major steps: (1) a novel routing-aware partitioning framework to obtain an initial solution considering irregular, asymmetric connections, and (2) a partition-aware routing scheme to optimize routing in each partitioning pass. Experimental results show that our proposed algorithm can achieve better timing than the classical flow.

AI-dedicated hardware designs are growing dramatically for various AI applications. These designs often contain highly connected circuit structures, reflecting the complicated structure in neural networks, such as convolutional layers and fully-connected layers. As a result, such dense interconnections incur severe congestion problems in physical design that cannot be solved by conventional placement methods. This paper proposes a novel placement framework for CNN accelerator units, which extracts kernels from the circuit and insert kernel-based regions to guide placement and minimize routing congestion. Experimental results show that our framework effectively reduces global routing congestion without wirelength degradation, significantly outperforming leading commercial tools.

The topological quantum error correction (TQEC) scheme is promising for scalable and reliable quantum computing. A TQEC circuit can be modeled by a three-dimensional diagram, and the implementation resource of a TQEC circuit is abstracted to its space-time volume. Implementing a quantum algorithm with a reasonable physical qubit number and reasonable computation time is challenging for large-scale practical problems. Therefore, minimizing the space-time volume of a TQEC circuit becomes a crucial issue. Previous work shows that bridge compression can greatly compress TQEC circuits, but it was performed only manually. It is desirable to develop automated compression techniques for TQEC circuits to achieve low-overhead, large-scale quantum computations. In this paper, we present the first work that can automatically perform bridge compression on TQEC circuits. Compared with the state-of-the-art method, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 83%.

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

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

Photonic integrated circuits (PICs), which introduce optical interconnections for on-chip communication, have become one of the most promising solutions to the increasing requirements with large bandwidth and low-power consumption. Routing techniques for optical interconnections have been proposed to deal with various routing issues in PICs, including transmission losses, thermal reliability, etc. However, in some emerging applications, different optical paths should be closely matched (in terms of the path length, the number of bends, the radius of curvature of bends, and the crossing count) to operate correctly. To the best of our knowledge, no previous work deals with these matching constraints in optical routing. This paper proposes a complete algorithm flow based on an optimal Steiner tree construction and integer linear programming with a hexagonal routing style to handle the matching constraints while minimizing the total transmission loss in a design. Compared with A*-search-based net-matching routing, experimental results show that our optical router can route all nets without violating any matching constraints while achieving lower total/maximum transmission loss, based on the optical netlists from a state-of-the-art work.

A circuit design with non-integer multiple cell height (NIMCH) is more flexible for optimizing area, timing, and power simultaneously. A cell with a larger height provides higher pin accessibility, higher drive strength, and shorter delay. In contrast, one with a smaller height has a smaller area, pin capacitance, and power consumption. Such NIMCH design must satisfy additional layout constraints that existing tool flows cannot handle well. This paper presents a row-based algorithm for non-integer multiple-cell-height placement. Our algorithm consists of two main techniques: (1) a k-mean-based clustering method to assign heights to each row to define the regions of particular cell heights, and (2) a legalization method to move cells to satisfy NIMCH constraints. Experimental results show that our approach can significantly reduce the average routed wirelength and the average total power compared with the state-of-the-art approach.

Multi-FPGA system prototyping has become popular for modern VLSI logic verification, but such a system realization is often limited by its number of inter-FPGA connections. As a result, time-division multiplexing (TDM) is employed to accommodate more inter-FPGA signals than the connections in a multi-FPGA system. However, the inter-FPGA signal delay induced by TDM becomes significant due to time-multiplexing. Researchers have shown that TDM ratios (signal time-multiplexing ratios) significantly affect the performance of a multi-FPGA system and inter-FPGA routing highly influences the quality of this system. This paper presents a framework to minimize the system clock period for a system-level FPGA while considering the inter-FPGA routing topology and the timing criticality of nets. Our framework consists of two stages: (1) a distributed profiling scheme to generate the desired net-ordering and then alleviate the routing congestion, and (2) a net-/edge-based refinement to assign TDM ratios efficiently with a strict decrease in the ratios. Based on the 2019 CAD contest at ICCAD benchmarks and the contest evaluation metric with both quality and efficiency, experimental results show that our framework achieves the best overall score among all the participating teams and published works.

In 5G, the requirement of transmission latency is stricter than that in 4G. To enhance transmission efficiency, a user plane function (UPF) with a specific packet processing mechanism is necessary. However, UPF must communicate with the session management function (SMF), which will send the packet processing rules to UPF. Those rules will substantially occupy UPF storage. Moreover, customizing a UPF needs to reconstruct N3, N4, N6, and N9 interfaces, which takes much time for developers. To this end, we propose the user plane function development framework (UPFDF), which modularizes the functions in the UPF, supporting customization to connect different types of packet processing mechanisms. With UPFDF, we address the UPF capacity problem and improve the flexibility of the system.

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

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

As clock frequencies increase, topology-matching bus routing is desired to provide an initial routing result which facilitates the following buffer insertion to meet the timing constraints. In this article, we present a complete topology-matching bus routing framework considering nonuniform track configurations. In the framework, a bus clustering technique is proposed to reduce the routing complexity by grouping buses sharing similar pin locations. To perform topology-matching routing in a nonuniform track configuration, we propose a directed acyclic graph-based algorithm to connect a bus in a specific topology. Furthermore, a rip-up and reroute scheme is applied to alleviate the routing congestion. Compared with the state-of-the-art topology-matching bus routers, our proposed algorithm significantly improves the routing quality and reduces the number of spacing violations in comparable runtime.

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

A 2.5-dimensional integrated circuit, which introduces an interposer as an interface between chips and a package, is one of the most popular integration technologies. Multiple chips can be mounted on an interposer, and inter-chip nets are routed on redistribution layers (RDLs). In traditional designs, the wire widths and spacings are uniform (i.e., grid-based). To improve circuit performance in modern designs, however, variable widths and spacings are also often adopted (i.e., gridless designs). In this paper, we propose the first unified routing framework that can handle both grid-based and gridless routing on RDLs based on the modulus-based matrix splitting iteration method (MMSIM) and bipartite matching. The MMSIM-based method assigns each wire a rough position while considering multiple design rules, and bipartite matching is applied to further refine those positions. We also prove the optimality of our RDL routing framework for grid-based designs and validate it empirically. Experimental results show that our framework can solve all the gridless and grid-based designs provided by industry effectively and efficiently. In particular, our framework is general and readily extends to other routing (and some quadratic optimization) problems.

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

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

Latch clustering is a critical stage to reduce power consumption at cost of timing disruption during a modern SoC design flow. However, most existing latch clustering researches mitigate timing disruptions by indirectly minimizing latch displacement during clustering, which is inaccurate and insufficient for timing closure in the design flow. Further, most researches do not control the amount of inserted clock buffers during clustering, which is the key factor to provide flexibility for timing and power trade-off. To address the two issues above, this paper presents a novel timing-power co-optimized latch clustering framework: we augment an integer linear programming (ILP) formulation of a facility-location allocation (FLA) problem to (1) directly optimize timing with a path-based timing model and (2) accurately control the number of inserted buffers by the FLA formulation for power optimization. We evaluate the framework with a displacement-optimized clustering approach and a state-of-the-art approach. Experimental results show 46% total negative slack timing overhead reduction, and 21% reduction for total power consumption.

The wavelength-routed optical network-on-chip (WRONoC) is a promising solution for signal transmission in modern system-on-chip (SoC) designs. Previous works do not handle three main issues for WRONoCs: correlations between the topological structure and physical layout, trade-offs between the maximum insertion loss and wavelength power, and a fully automated flow to generate predictable designs. As a result, the insertion loss estimation is inaccurate, and thus only suboptimal results are obtained. To remedy these disadvantages, we present a fully automated topological structure and physical layout codesign flow to minimize the maximum insertion loss and the wavelength power simultaneously with a significant speedup. Experimental results show that our codesign flow significantly outperforms state-of-the-art works in the maximum insertion loss, wavelength power, and runtimes.

As the VLSI technology continues to scale down, combined with increasing demands for large bandwidth and low-power consumption, the optical interconnections with Wavelength Division Multiplexing (WDM) become an attractive alternative for on-chip signal transmission. Previous WDM-aware optical routing works consist of two main drawbacks: they are based mainly on heuristics or restricted integer linear programming to handle optical routing, and the addressed types of transmission loss and WDM overheads are incomplete. As a result, no performance guarantees can be achieved on their WDM clustering results, and/or their computations are too time-consuming. To remedy these disadvantages, we present a polynomial-time provably good WDM-aware clustering algorithm and a new WDM-aware optical routing flow to minimize the transmission loss and the WDM overheads with a significant speedup. The proposed WDM-aware clustering algorithm guarantees to find an optimal solution for 1-, 2-, and 3-path clustering, and has the constant performance bound 3 for most cases of 4-path clustering. Experimental results based on the ISPD 2007 and 2019 contest benchmarks and a real optical design show that our optical router significantly outperforms published works in wirelength, transmission loss, wavelength power, and runtimes.

The integrated fan-out (InFO) wafer-level chip-scale package is introduced for modern system-in-package designs with larger I/O counts and higher interconnection density. A redistribution layer (RDL) in an InFO package is an extra metal layer for inter-chip connections. To achieve flexible and compact inter-chip connections, the RDL routing problem for InFO packages has become a crucial problem for modern electronic designs. In advanced high-density InFO packages, multiple RDLs with flexible vias are often adopted. On the other hand, to integrate chips of different technology nodes into one package, irregular pad structures need to be considered. To our best knowledge, however, there is no published work for RDL routing considering flexible vias or irregular pad structures. In this paper, we present the first work to handle the routing problem with pre-assigned pad pairs (i.e., the hardest pre-assignment routing problem) on the via-based multi-chip multi-layer InFO package with irregular pad structures. We first propose a layer assignment method based on a weighted maximum planar subset of chords algorithm to concurrently route as many inter-chip nets as possible. We then propose an octagonal tile model with a layout partitioning method to tackle increasingly popular irregular structures. Finally, we develop an efficient linear-programming-based layout optimization algorithm to find solutions with high-quality wirelength and via arrangements. Experimental results demonstrate the effectiveness and robustness of our algorithm.

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

As the design complexity grows dramatically in modern circuit designs, 2.5D/3D chip/package/board integration has become a key to beat process limitation for optimizing system performance and power consumption. Among the explored technologies, the wafer-level integrated fan-out (InFO) package-on-package (PoP) has been adopted by major companies such as TSMC to achieve high-density, high-performance, low-cost packaging solutions. To achieve a high-quality 2.5D/3D heterogeneous integration system, we shall study the chip, package, and board codesign methodology with advanced packages and explore key techniques to handle the emerging challenges in physical design, timing, electrical effects, and testing.1

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

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

In this paper, we present a new hybrid representation of slicing trees and multi-packing trees, called multi-domain-packing trees (MDP-trees), for macro placement to handle ultra large-scale multi-domain mixed-size designs. A multi-domain design typically consists of a set of mixed-size domains, each with hundreds/thousands of large macros and (tens of) millions of standard cells, which is often seen in modern high-end applications (e.g., 4G LTE products and upcoming 5G ones). To the best of our knowledge, there is still no published work specifically tackling the domain planning and macro placement simultaneously. Based on binary trees, the MDP-tree is very efficient and effective for handling macro placement with multiple domains. Previous works on macro placement can handle only single-domain designs, which do not consider the global interactions among domains. In contrast, our MDP-trees plan domain regions globally, and optimize the interconnections among domains and macro/cell positions simultaneously. The placement area of each domain is well reserved, and the macro displacement is minimized from initial macro positions of the design prototype. Experimental results show that our approach can significantly reduce both the average half-perimeter wirelength and the average global routing wirelength.

As clock frequencies increase, topology-matching bus routing is desired to provide an initial routing result which facilitates the following buffer insertion to meet the timing constraints. Our algorithm consists of three main techniques: (1) a bus clustering method to reduce the routing complexity, (2) a DAG-based algorithm to connect a bus in the specific topology, and (3) a rip-up and re-route scheme to alleviate the routing congestion. Experimental results show that our proposed algorithm outperforms all the participating teams of the 2018 CAD Contest at ICCAD, where the top-3 routers result in 145%, 158%, and 420% higher costs than ours.

The analytical formulation has been shown to be the most effective for circuit placement. A key ingredient of analytical placement is its wirelength model, which needs to be differentiable and can accurately approximate a golden wirelength model such as half-perimeter wirelength. Existing wirelength models derive gradient from differentiating smooth maximum (minimum) functions, such as the log-sum-exp and weighted-average models. In this paper, we propose a novel bivariate gradient-based wirelength model, namely BiG, which directly derives a gradient with any bivariate smooth maximum (minimum) function without any differentiation. Our wirelength model can effectively combine the advantages of both multivariate and bivariate functions. Experimental results show that our BiG model effectively and efficiently improves placement solutions.

A robust redistribution layer (RDL) router is required for advanced package designs, where the length-matching constraint for a group of nets needs to be considered to preserve good timing properties at the package level. For area-I/O flip-chip design with pre-assigned nets on RDLs, we propose the first group-based length-matching routing framework that can simultaneously minimize the wirelengths of an arbitrary group of nets with and without equal-length constraints, based on an equal-length-aware A*-search algorithm and a bounded sliceline grid (BSG) snaking one. For the irregular structure of the area-I/O flip-chip design, we apply Delaunay triangulation and Voronoi diagram to model the routing resources more precisely. To effectively consider the equal-length constraints in the earlier stage, we first profile the routing resource to obtain an approximation of the longest net, and then adopt the equal-length-aware A*-search algorithm to extend shorter nets to match the estimated longest net. A BSG-based snaking method is then applied to meet the equal-length constraint, while preserving the minimized wirelength of unconstrained nets. Experimental results demonstrate that our framework can solve all benchmarks effectively and efficiently.

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

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

Two-dimensional (2D) directed self-assembly (DSA) is a promising technology for sub-5nm process, which forms patterns through combinations of oriented double posts. In 2D DSA, line-end cuts are employed to fabricate 2D patterns to derive desired layouts, and cut redistribution is applied to eliminate cut spacing violations. In this paper, we present the first work to handle the 2D DSA cut redistribution problem. We first solve this problem by basic integer linear programming (ILP) with solution optimality guarantees. We then propose an efficient graph-based optimality-preserving framework to handle this problem, where the spacing violations between template candidates are evaluated in linear time. This framework simplifies the cut redistribution problem with a lower-complexity binary ILP, where the numbers of variables and constraints can be reduced from quadratic to only linear. Experimental results show that our algorithm can effectively and efficiently redistribute cuts with zero spacing violations and the minimum wire extensions.

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

2-D directed self-assembly (DSA) is an emerging lithography for the 5-nm process node and beyond that can substantially increase design flexibility in critical routing layers and reduce the number of cuts for better yield. The state-of-the-art 2-D DSA process manipulates the orientation of double posts inside guiding templates to guide block copolymers (BCPs) to form 2-D patterns. However, a key challenge arises on how to correctly assign double post orientations and place cut patterns to make desired net connections for a given routing instance. In this paper, we propose a novel 2-D DSA-compliant routing (2-D-DCR) framework to systematically derive feasible orientation assignments for double posts to maximize routability. Specifically, 2-D-DCR features a complete set of new routing rules which transform the underlying physical BCP growth principles for large-scale routing, adopts a network-flow-based double-post assignment routing algorithm, and leverages a 2-D DSA line-end creation property to maximally reduce line-end cuts. Experimental results show that our 2-D-DCR can effectively generate a 2-D-DCR solution with zero double post conflicts, maximized routability, and minimized the number of cuts.

I. VLSI Systems: A Glance Into The Last Decades Since their inception in 1970s, VLSI systems have enabled several new technological capabilities and made them accessible to an unceasingly wider range of users, reaching a scale that has been exponentially increasing over the decades[1](seeFig. 1). Relentless integration of more complex systems has driven such remarkable evolution, as made possible by the inexorable miniaturization. As shown inFig. 1, more functionality has been crammed in a consistently smaller form factor, as exemplified by the physical volume shrinking of computers by 100 X/decade[2],[3]. At the same time, the energy per task has been decreasing at 10–100 X/decade, as shown inFig. 2, for several systems and system-on-chip subsystems[4]. This allowed packing more capabilities into the same power envelope, as generally observed in the electronic systems, even before the advent of the integrated circuit[5].

The emerging design requirements with the FinFET technology, along with traditional geometrical constraints, make the FinFET-based analog placement even more challenging. Previous works can handle only partial FinFET-induced design constraints because some new constraints are intrinsically different from the traditional ones; as a result, directly extending previous methods to handle FinFET-induced constraints would incur solution quality degradation and runtime overhead. To remedy these disadvantages, we present a new hybrid graph (meshed tree) representation of a window mesh and CB-trees (namely, WB-trees) and a new placement flow with effective and efficient schemes to simultaneously handle FinFET-based design constraints and traditional ones. Experimental results based on industrial designs with various constraints show that our placer outperforms published works in both solution quality and runtime.

As Engineering Change Order (ECO) has attracted substantial attention in modern VLSI design, the open net problem, which aims at constructing a shortest obstacle-avoiding path to reconnect the net shapes in an open net, becomes more critical in the ECO stage. This paper addresses a multi-layer obstacle-avoiding region-to-region Steiner minimal tree (SMT) construction problem that connects all net shapes by edges on a layer or vias between layers, and avoids running through any obstacle with a minimal total cost. Existing multi-layer obstacle-avoiding SMT algorithms consider pin-to-pin connections instead of region-to-region ones, which would limit the solution quality due to its lacking region information. In this paper, we present an efficient algorithm based on our new multi-layer obstacle-avoiding region-to-region spanning graph to solve the addressed problem, which guarantees to find an optimal solution for a net connecting two regions on a single layer. Experimental results show that our algorithm outperforms all the participating routers of the 2017 CAD Contest at ICCAD in both solution quality and runtime.

As integrated circuit technology nodes continue to shrink, dense via distribution becomes a severe challenge, requiring multiple masks to avoid spacing violations in via layers. Meanwhile, the directed self-assembly (DSA) technique shows a great promise in via printing by employing feasible guiding templates. Combining DSA with double patterning lithography can significantly reduce the number of masks for via layers. In this paper, we propose a detailed routing algorithm considering DSA with DPL based on a conflict and compatibility graph model. A net planning algorithm is developed to reduce via-dense areas and determines a prerouting nets order, while the graph model is employed to capture the feature of DSA and DPL to better guide detailed routing. Besides, DSA grouping is performed for critical vias during detailed routing to avoid attracting more vias inserted in surrounding grids to reduce via-spacing violations. Experimental results demonstrate that our routing algorithm can effectively minimize the number of via spacing violations, with an even smaller total via count.

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

The 2.5D FPGA is a promising technology to accommodate a large design in one FPGA chip, but the limited number of inter-die connections in a 2.5D FPGA may cause routing failures. To resolve the failures, input/output time-division multiplexing is adopted by grouping cross-die signals to go through one routing channel with a timing penalty after netlist partitioning. However, grouping signals after partitioning might lead to a suboptimal solution. Consequently, it is desirable to consider simultaneous partitioning and signal grouping although the optimization objectives of partitioning and grouping are different, and the time complexity of such simultaneous optimization is usually high. In this paper, we propose a simultaneous partitioning and grouping algorithm that can not only integrate the two objectives smoothly, but also reduce the time complexity to linear time per partitioning iteration. Experimental results show that our proposed algorithm outperforms the state-of-the-arts flow in both cross-die signal timing criticality and system-clock periods.

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

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

Detailed routing is the most complicated and time-consuming stage in VLSI design and has become a critical process for advanced node enablement. To handle the high complexity of modern detailed routing, initial detailed routing is often employed to minimize design-rule violations to facilitate final detailed routing, even though it is still not violation-free after initial routing. This paper presents a novel initial detailed routing algorithm to consider industrial design-rule constraints and optimize the total wirelength and via count. Our algorithm consists of three major stages: (1) an effective pin-access point generation method to identify valid points to model a complex pin shape, (2) a via-aware track assignment method to minimize the overlaps between assigned wire segments, and (3) a detailed routing algorithm with a novel negotiation-based rip-up and re-route scheme that enables multithreading and honors global routing information while minimizing design-rule violations. Experimental results show that our router outperforms all the winning teams of the 2018 ACM ISPD Initial Detailed Routing Contest, where the top-3 routers result in 23%, 52%, and 1224% higher costs than ours.

Along with device scaling, the drain-to-drain abutment (DDA) constraint arises as an emerging challenge in modern circuit designs, which incurs additional difficulties especially for designs with mixed-cell-height standard cells which have prevailed in advanced technology. This paper presents the first work to address the mixed-cell-height placement problem. considering the DDA constraint from post global placement throughout detailed placement Our algorithms consists of three major stages: (1) DDA-aware preprocessing, (2) legalization, and (3) detailed placement. In the DDA-aware preprocessing stage, we first align cells to desired rows, considering the distribution ratio of source nodes to drain nodes. After deciding the cell ordering of every row, we adopt the modulus-based matrix splitting iteration method to remove all cell overlaps with minimum total displacement in the legalization stage. For detailed placement, we propose a satisfiability-based approach which considers the whole layout to flip a subset of cells and swap pairs of adjacent cells simultaneously. Compared with a shortest-path method, experimental results show that our proposed algorithm can significantly reduce cell violations and displacements with reasonable runtime.

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

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

A placer without considering modern technology and region constraints could generate solutions with irresolvable detailed-routing (DR) violations or even illegal solutions. This paper presents a high-quality placement algorithm to satisfy technology and region constraints and optimize DR routability with five major techniques: 1) a clustering algorithm followed by two-round quadratic placement to obtain an initial placement satisfying region constraints; 2) a novel density control technique to handle prefixed architectures and minimize global routing congestions; 3) an analytical placement algorithm with new wirelength and density models to consider region constraints; 4) a dynamic penalty increment strategy that reduces wirelength increments during global placement; and 5) a legalization algorithm that preserves the solution quality of global placement while satisfying technology and region constraints. Compared with the winning teams of the ISPD 2015 Blockage-Aware Detailed Routing-Driven Placement Contest and recent works, our placer achieves the best overall score and DR results.

Electron beam lithography (EBL) has been used for high-resolution photomask fabrication; its successive heating process in a certain region, however, may cause critical dimension (CD) distortion. As a result, subfield scheduling, which reorders a sequence of subfields in the writing process, is desirable to avoid the heating problem and thus CD distortion. To consider longer range heat dissipation, this paper models a subfield scheduling problem with blocked region consideration as a constrained max–min$m$-neighbor traveling salesman problem (called constrained$m$-nTSP). To solve the constrained$m$-nTSP which is NP-complete in general, we decompose a constrained$m$-nTSP into subproblems conforming to a special case with points on two parallel lines, solve each of them with a provably good linear-time approximation algorithm, and merge them into a complete scheduling solution. In particular, our algorithm can also minimize the distances between successive subfields to alleviate the throughput degradation of EBL writing due to moving a writing head, while minimizing the heating problem. Average reductions of 10% in the maximum temperature and 14% in the distances between successive subfields over the state-of-the-art work can be achieved.

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

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

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

Extracting similar datapath bit slices which handle highly parallel bit operations can help a modern placer to obtain better solutions for datapath-oriented designs. A current state-of-the-art datapath bit slicing method achieves the best extraction results using a network-flow-based algorithm. However, this work has two major drawbacks: (1) it extracts only a limited number of bit slices for datapaths with different I/O widths, which are commonly seen in real designs, and (2) it does not consider bit-slice similarity, which is an important feature for placement considering datapaths. To remedy these drawbacks, we present (1) a balanced bipartite edge-cover algorithm to fully slice a datapath with different I/O widths, and (2) a simulated annealing scheme to further improve bit-slice similarity, while maintaining fully-sliced structures. Compared with the state-of-the-art work, experimental results show that our slicing algorithm extracts more bit slices with similar structures, and helps a leading academic placer achieve averagely 5% smaller routed wirelength. The results also validate the high correlation between datapaths and structure regularity/similarity.

Two-dimensional directed self-assembly (2D-DSA), a promising nanotechnology, manipulates the orientation of double posts to guide block copolymers to fabricate 2D patterns in nanoscale. In this paper, we present the first detailed placement algorithm for 2D-DSA. We first propose an orientation-number model for nets to estimate post orientations. Then, a cost model based on the orientation numbers is defined to estimate the 2D-DSA routability efficiently during placement, and a novel detailed placement framework is proposed to consider the orientationsto optimize wirelength. In this framework, we develop a dynamic-programming-based algorithm for single-row detailed placement with a specialized pruning technique based on the defined orientation cost. Experimental results show that our algorithm can effectively generate a 2D-DSA friendly placement solution.

In this paper, we present a damped-wave constructive macro placement framework which packs big macros to optimize both wirelength and routability simultaneously. Unlike traditional V-shaped and Λ-shaped multilevel frameworks which might lack respective local and global information during processing, our dampedwave framework considers both local and global information by the following two major techniques: (1) macro clustering to improve scalability, and (2) constructive macros declustering to assist a standard-cell placer to obtain better solutions. We also present a macro-grouping cost model to remedy the key drawback of ignoring the mismatches of standard-cell locations between the prototyping and the final standard-cell placement stages in existing three-stage mixed-size placers (containing prototyping, macro placement, and standard cell placement). We further propose the regularity penalty model to guide macros to form an integral, regular region during macro placement, facilitating the succeeding placement of standard cell. Compared with manual placement from industrial and a leading mixed-size placer, experimental results show that our damped-wave multilevel framework and cost models are efficient and effective in reducing half-perimeter wirelength and routed wirelength and overflows. In particular, our work provides a new research direction on effective frameworks for large-scale designs, which readily apply to many optimization problems limited with scalability.

FPGAs have emerged as a popular style for modern circuit designs, due mainly to their non-recurring costs, in-field reprogrammability, short turn-around time, etc. A modern FPGA consists of an array of heterogeneous logic components, surrounded by routing resources and bounded by I/O cells. Compared to an ASIC, an FPGA has more limited logic and routing resources, diverse architectures, strict design constraints, etc.; as a result, FPGA placement and routing problems become much more challenging. With growing complexity, diverse design objectives, high heterogeneity, and evolving technologies, further, modern FPGA placement and routing bring up many emerging research opportunities. In this paper, we introduce basic architectures of FPGAs, describe the placement and routing problems for FPGAs, and explain key techniques to solve the problems (including three major placement paradigms: partitioning, simulated annealing, and analytical placement; two routing paradigms: sequential and concurrent routing, and simultaneous placement and routing). Finally, we provide some future research directions for FPGA placement and routing.

With the increasing use of pre-designed macros in a modern chip and its induced high design complexity, macro placement has become a challenging problem in today's design houses. Most popular macro placement algorithms adopt a three-stage approach: placement prototyping, macro placement, and standard-cell placement, where cell positions after macro placement are assumed the same as those at the prototyping stage, possibly misguiding succeeding standard-cell placement. To close the gap between macro and standard-cell placement, we propose a macro-refining algorithm that adopts an integrated spreading technique considering the spreading of both macros and cells and the dynamic information of cell positions to improve macro placement. We further propose a new force-modulation technique to refine macro placement and a congestion-aware macro shifter to preserve more space for better routability. Extensive experiments based on various macro placements show that our proposed techniques are effective and our macro-refining algorithm can find significantly better placement solutions for large-scale mixed-size circuit designs.

A modern FPGA often contains an ASIC-like clocking architecture which is crucial to achieve better skew and performance. Existing conventional FPGA placement algorithms seldom consider clocking resources, and thus may lead to clock routing failures. To address the special FPGA clocking architecture, this paper presents a novel clock-aware placement algorithm for large-scale heterogeneous FPGAs. Our algorithm consists of three major stages: (1) a nonlinear global placement framework with clock fence region construction, (2) a clock-aware packing scheme, and (3) clock-aware legalization and detailed placement. We evaluate our results based on the 2017 ISPD Clock-Aware Placement Contest benchmark suite. Compared with the top three winners, the results show that our algorithm achieves the best overall routed wirelength. On average, our algorithm outperforms the top-3 winners by 3.6%, 7.5%, and 12.9% in routed wirelength, respectively.

The wafer-level integrated fan-out (InFO) package-on-package (PoP) is a promising 3D packaging technology, which usually consists of a bottom package with the InFO technique, and a top package stacked on the bottom package. Different from the traditional PoPs, there are frontside and backside redistribution layers (RDLs) in the InFO PoP for signal redistributions. To the best of our knowledge, there is still no previous work specifically tackling the RDL routing for the InFO PoP. Previous works on RDL routing mainly deal with the following three types of routing: the free-assignment, pre-assignment, and unified-assignment routing for single or multiple chips. In this paper, a new RDL routing problem for the InFO PoP is formulated. To remedy the deficiencies of lacking the interactions between frontside and backside RDLs, we present the first work in the literature to handle the unified-assignment multi-layer multi-package RDL routing problem (without RDL vias), considering layer assignment, layer number minimization, and total wirelength minimization. We propose an algorithm based on extracting increasing subsequences (IS), which transforms a routing sequence into two directed acyclic graphs (DAGs), namely, IS-DAG and Constraint-DAG. By minimizing the number of vertices on the longest path on the Constraint-DAG, we implicitly minimize the layer number. Furthermore, we perform backtracking on the IS-DAG to efficiently assign the connections to appropriate layers to avoid long detours. Experimental results show that our router can achieve 100% routablility for all given test cases, while the previous works with extensions fail all test cases even with more frontside RDLs.

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

Wirelength is the most fundamental objective in placement because it also affects various placement metrics (routability, timing, etc.). Half-perimeter wirelength (HPWL) is a pervasive metric for circuit placement. However, preplaced blocks (i.e., blockages) might misguide an HPWL-based placer to generate a placement solution that incurs significant routing detours. Consequently, it is desirable to develop an effective method to resolve the HPWL-rooted routing detour problem for placement optimization. This paper presents an efficient, generic, yet effective terminal propagation algorithm as a pre-placement process which can readily be integrated into a traditional placement flow to improve wirelength (and routability). Our algorithm identifies a region for each preplaced terminal according to its connectivity, and applies a minimum-cost maximum flow algorithm to propagate all preplaced terminals to their feasible propagation locations with the minimum total propagation length. Experimental results show that our flow with terminal propagation can reduce both global routed wirelength and routing congestion by 4% on average, compared with one without terminal propagation. In particular, our work also provides a long unnoticed insight into placement optimization with blockages, which can be addressed with an efficient, generic, yet effective scheme.

This paper introduces popular algorithmic paradigms for circuit placement, presents Goto's classical placement framework based on the generalized force directed relaxation (GFDR) method with an optimal region (OR) formulation and its impacts on modern circuit placement and applications, and provides future placement research directions based on the GFDR and OR formulations.

Directed-self-assembly (DSA) technology is a promising candidate for cut printing in sub-10nm 1-D gridded designs, where cuts might need to be redistributed such that they could be patterned by DSA guiding templates. In this paper, we first propose a linear-time optimal dynamic-programming-based algorithm for a special case of the template guided cut redistribution problem, where there is at most one dummy wire segment on a track. We then extend our algorithm to general cases by applying a bipartite matching algorithm to decompose a general problem to a set of subproblems conforming to the special case (thus each of them can be solved optimally). Our resulting algorithm can achieve a provably good performance bound, with the cost of a template distribution only linearly to the problem size. Experimental results show that our algorithm can resolve all spacing rule violations, with smaller running times, compared with the previous works on a set of common benchmarks. In addition, we also extend our algorithm to consider general design rules, simple templates, and dummy cuts.

1-D nanowires are one of the most promising next-generation lithography technologies for 7 nm process node and beyond. The 1-D nanowire process first constructs a 1-D nanoarray through template synthesis followed by line-end cutting with additional cut masks. To achieve better yield and manufacturability, the cut patterns shall satisfy specified restricted design rules, and thus it is desirable to develop a novel routing methodology to better address the challenges arising from cut patterns. In this paper, we propose the first nanowire-aware routing system, considering high cut-mask complexity based on a two-pass, bottom-up multilevel routing framework. Experimental results show that our nanowire-aware router can effectively and efficiently reduce cut numbers, cut spacing violations, and line-end extension length.

As I start my second two-year term (2017–2018) as the Editor-in-Chief (EIC) of the IEEE Transactions on Very Large Scale Integration Systems (TVLSI), I wish the TVLSI readership a very happy new year and continued professional success. It gives me great pleasure to report on the state of the journal and our performance metrics. Over the past two years, TVLSI has seen a healthy increase in the number of submissions—from 687 in 2014 to 770 in 2015, and at the time of writing of this editorial, we are at 760 submissions for 2016. We expect the number of submissions for 2016 to cross 800 before the end of the year. TVLSI, therefore, continues to be the premier archival journal for university researchers and industry practitioners in the broad area of VLSI system design.

A modern system-on-a-chip (SoC) typically consists of a large number of mixed-size circuit components with big macros and standard cells. Pre-placed macros (obstacles) and big macros further complicate such mixed-size circuit placement, and thus often make existing works fail to obtain a legal mixed-size placement. In this paper, we present an obstacle-aware macro placement algorithm which locates big macros to simultaneously optimize wirelength and routability. We first propose a circular contour to characterize the region formed by all obstacles. With the circular contour, we can effectively avoid the overlap between movable macros and obstacles, and simultaneously optimize the shape and area of the region for standard-cell placement. Unlike most previous macro placers that spend much time on searching for a feasible solution, our circular packing scheme packs movable macros around the obstacle contour to generate feasible solutions efficiently, and thus assists simulated annealing to focus on solution-quality optimization. Experimental results show that our algorithm can achieve the best quality, compared to manual designs provided by industry and leading academic mixed-size placers.

Directed self-assembly (DSA) technology is a promising candidate for cut printing in sub-10nm 1-D gridded designs, where cuts might need to be redistributed such that they could be patterned by DSA guiding templates. In this paper, we first propose a linear-time optimal dynamic-programming-based algorithm for a special case of the template guided cut redistribution problem, where there is at most one dummy wire segment on a track. We then extend our algorithm to general cases by applying a bipartite matching algorithm to decompose a general problem to a set of subproblems conforming to the special case (thus each of them can be solved optimally). Our resulting algorithm can achieve a provably good performance bound, with the cost of a template distribution only linearly to the problem size. Experimental results show that our algorithm can resolve all spacing rule violations, with smaller running times, compared with the previous works on a set of common benchmarks.

Analog and mixed-signal integrated circuits play an important role in many modern emerging system-on-chip (SoC) design applications. With the expansion of the markets of those applications, the demands of analog/mixed-signal ICs have been dramatically increased. Although analog/mixed-signal ICs have gained more and more importance and demands in modern SoC applications, the development of analog electronic design automation (EDA) tools is still farther behind that of digital EDA tools. As a result, analog/mixed-signal IC design, especially the analog layout design, is still a manual, time-consuming, and error-prone task. In order to speed up modern SoC design for large varieties of emerging applications, it is desirable to develop novel analog/mixed-signal IC deign methodologies and algorithms, as well as new analog EDA tools. The purpose of this paper is to summarize recent research progress during the past decade, address new analog layout design challenges in advanced technology nodes, and facilitate more research activities in analog layout synthesis.

As interconnects dominate circuit performance in modern chip designs, placement becomes an essential stage in optimizing timing. Recent timing-driven placement (TDP) techniques focus mainly on optimizing late slack rather than early slack. This paper presents a TDP algorithm to improve the early slack while preserving an optimized late slack. The preservation is achieved by accurately predicting optimal Steiner tree topologies after each move in our TDP algorithm. An optimality-preserving pruning scheme for each move is proposed to speed up the optimization process, without sacrificing the solution quality. Experimental results show that our algorithm can substantially improve the early slacks and the overall quality scores of the top-2 winning placers of the 2015 ICCAD Incremental Timing-Driven Placement Contest, while preserving their late slacks.

Due to the continuous shrinking of technology nodes, the minimum implant area (MIA) constraint has become a critical issue for modern circuit placement. With a fixed cell height, this constraint can be transferred into a minimum cell width constraint, and thus cells of small widths may have MIA violations. To solve such violations, we may shift neighboring cells to preserve whitespace or abut violating cells with the same threshold voltages (VTs). This paper presents an MIA-aware detailed placement algorithm to effectively solve the placement problem with the MIA constraint by clustering violating cells with the same VTs, and then apply cluster-based detailed placement algorithms to solve this problem. To further minimize the design area, an MIA-aware cell flipping algorithm based on linear-time dynamic programming is presented. Experimental results show that our algorithm can achieve high-quality results for this problem and is very robust for different multi-VT designs and MIA constraints.

A modern analog placer often needs to consider various geometrical constraints to generate desired layouts. To handle general constraints simultaneously, current state-of-the-art works adopt simulated annealing based on topological representations, due to their smaller solution spaces and higher efficiency. However, no published work achieves the optimal time complexity for general geometrical constraint handling and module packing. Besides, only limited constraints are considered and handled in each work. To remedy these insufficiencies, we present a new hybrid representation of a quadtree and B*-trees (QB-tree, for short) to handle general geometrical constraints while achieving linear, lower-bound time complexity of module packing and constraint handling. Experimental results based on real industrial designs with various constraints show that our placer outperforms the leading published works in both runtime and solution quality.

The integrated fan-out (InFO) wafer-level chip-scale package (WLCSP) is an emerging packaging technology, which typically consists of multiple redistribution layers (RDLs) for signal redistributions among multiple chips. There is still no published work specifically on the RDL routing for the InFO WLCSP. Published RDL routing works consider different types of routing, namely free-assignment, pre-assignment, and unified-assignment routing, for a single chip. With the integration of multiple chips under the InFO WLCSP, however, previous works cannot achieve high efficiency or effectiveness with simple extensions. To remedy the deficiencies of poor interactions between chips and multiple RDLs, we formulate a new RDL routing problem for the InFO WLCSP and present the first work in the literature to handle the unified-assignment, multi-layer multi-chip RDL routing problem (without RDL vias), considering signal integrity, layer assignment, layer number minimization, and total wirelength minimization. We propose a concentric-circle model which models all the connections among one chip and all other chips. Based on this model, we assign the connections between chips to appropriate layers to avoid long detours. In addition, this model transforms the geometrical information of the pre-assignment connections among chips into a network-flow model to generate a routing prototype in a fan-out region not covered by any chip efficiently and effectively. Experimental results demonstrate the high quality and efficiency of our algorithm.

The directed self-assembly (DSA) technology for next-generation lithography has been shown its great potential for fabricating highly dense via patterns and cut masks in the sub-5 nm technology node and beyond. However, DSA via and cut optimizations were performed independently, which may induce infeasible via and cut templates and spacing violations. It is thus desirable to develop a novel routing system to better address the co-optimization challenges for DSA via and cut templates. In this paper, we propose the first simultaneous DSA via- and cut-template-aware routing system, named VCR, to practically consider both via and cut templates during routing and post-routing based on a two-pass, bottom-up multilevel routing framework. Experimental results show that VCR can effectively reduce via- and cut-template spacing violations.

Two-dimensional (2D) directed self-assembly (DSA) is an emerging lithography for the 5 nm process node and beyond that can substantially increase design flexibility in critical routing layers and reduce the number of cuts for better yield. The state-of-the-art 2D DSA process manipulates the orientation of double posts inside guiding templates to guide block copolymers (BCPs) to form 2D patterns. However, a key challenge arises on how to correctly assign double post orientations and place cut patterns to make desired net connections for a given routing instance. In this paper, we propose a novel 2D DSA-compliant routing framework, named 2D-DCR, to systematically derive feasible orientation assignments for double posts to maximize routability. Specifically, 2D-DCR features a complete set of new routing rules which transform the underlying physical BCP growth principles for large-scale routing, adopts a network-flow-based double-post assignment routing algorithm, and leverages a 2D DSA line-end creation property to maximally reduce line-end cuts. Experimental results show that our 2D-DCR can effectively generate a 2D DSA-compliant routing solution with zero double post conflicts, maximized routability, and minimized the number of cuts.

Directed self-assembly (DSA) technology has emerged as a promising candidate for cut printing in advanced 1-D gridded layouts, where cuts might need to be redistributed such that they can be patterned by specific DSA guiding templates. The cut redistribution significantly affects the performance and manufacturability of a circuit. In this paper, we propose an algorithm incorporating DSA with double patterning for a template guided cut redistribution problem. We first develop a linear-time optimal algorithm for a special case of the template guided cut redistribution problem, with contiguous rows. For the general problem, a linear-time double-patterning aware partitioning method is developed to select a set of subproblem candidates to generate a template distribution to minimize the impact on circuit performance and manufacturing. Consequently, we decompose a general problem into a set of subproblems conforming to the aforementioned special case, solve each subproblem optimally, and merge the solutions to the subproblems to obtain an overall solution to the general one. Experimental results show that our algorithm can resolve all spacing rule violations, with even smaller extended wire costs and running times, compared with the state-of-the-art works on a set of common benchmarks.

Extreme ultraviolet (EUV) flare and post-chemical mechanical polishing (CMP) metal thickness are two main manufacturability concerns that introduce critical dimension distortions in nanometer process technology. Dummification, the addition of dummy patterns, is an effective technique to address the two concerns. However, while the two dummification objectives are competing in nature, existing works only tackle them separately, leading to problem-prone solutions because optimizing one would unavoidably deteriorate the other. This paper presents a new and effective method that simultaneously considers both concerns during dummification. Manufacturing sensitivity toward the two concerns are taken into account with a user-specified evaluation model adaptive to the adopted technology. Given the point spread function of a system and the evaluation model, our proposed two-stage method is able to find at the first stage an initial dummy assignment with better EUV flare uniformity than that obtained by a previous quasi-inverse method. With the initial assignment as the starting point, the gradient-guided optimization is then adopted to iteratively refine dummy distribution toward improved CMP quality. Experimental results on industrial test cases show the effectiveness of our method.

Self-aligned double patterning (SADP) is one of the most promising techniques for sub-20 nm technology. Spacer-is-dielectric SADP using a cut process is getting popular because of its higher design flexibility; for example, it can decompose odd cycles without the need of inserting any stitch. This paper presents the first work that applies the cut process for decomposing odd cycles during routing. For SADP, further, overlay control is a critical issue for yield improvement; while published routers can handle only partial overlay scenarios, this paper identifies all the scenarios that induce overlays and proposes a novel constraint graph to model all overlays. With the developed techniques, our router can achieve high-quality routing results with significantly fewer overlays (and thus better yields). Compared with three state-of-the-art studies, our algorithm can achieve the best quality and efficiency, with zero cut conflicts, smallest overlay length, highest routability, and fastest running time.

Layout-dependent effects (LDEs) have become a critical issue in modern analog and mixed-signal circuit designs. The three major sources of LDEs, well proximity, length of oxide diffusion, and oxide-to-oxide spacing, significantly affect the threshold voltage and mobility of devices in advanced technology nodes. In this paper, we propose the first work to consider the three major sources of LDEs during analog placement. We first transform the three LDE models into nonlinear analytical placement models. Then an LDE-aware analytical analog placement algorithm is presented to mitigate the influence of the LDEs while improving circuit performance. Experimental results show that our placement algorithm can effectively and efficiently reduce the LDE-induced variations and improve circuit performance.

As nanometer technology advances, conventional optical proximity correction (OPC) that minimizes the edge placement error (EPE) at the nominal process condition alone often leads to poor process windows. To improve the mask printability across various process corners, process-window OPC optimizes EPE for multiple process corners, but often suffers long runtime, due to repeated lithographic simulations. This paper presents an efficient process variation (PV)-aware mask optimization framework, namely PVOPC, to simultaneously minimize EPE and PV band with fast convergence. The PVOPC framework includes EPE-sensitivity-driven dynamic fragmentation, PV-aware EPE modeling, and correction with three new EPE-converging techniques and a systematic subresolution-assisted feature insertion algorithm. Experimental results show that our approach efficiently achieves high-quality EPE and PV band results.

Self-aligned double patterning (SADP) has become a preferred double patterning technology, due to its better overlay controllability. Two types of layout decomposition schemes are used to define two-dimensional layout patterns in SADP: Spacer-is-Metal (SIM) and Spacer-is-Dielectric (SID), and SIM-type layout decomposition typically has higher decomposition flexibility (especially for gridless designs). While SID-type layout decomposition has been studied extensively, however, only one previous work extended a satisfiability-based SID-type decomposer to SIM-type layout decomposition; this SAT-based method is inefficient for large-scale designs and not applicable to non-decomposable layouts. This paper introduces an efficient graph-based SIM-type layout decomposition heuristic. The decomposition problem is first transformed into a constrained set-covering problem. Then, an efficient algorithm composed of a greedy heuristic followed by a partition-based solution refinement scheme is proposed to simultaneously minimize the conflicts on both core masks and cut masks. Experimental results show that the algorithm can efficiently derive a good decomposition solution with minimized pattern conflicts.

Considering decomposition constraints earlier during routing becomes critical for realizing triple patterning lithography. In addition, stitches typically cause significant yield loss because of the overlay errors among different masks. As a result, leading foundries even get rid of the use of stitches in their design methodology. In order to completely avoid stitch-induced yield loss, we address the non-stitch triple patterning-aware routing problem. We observe that directly extending a state-of-the-art triple patterning-aware routing work to non-stitch routing might generate improper self-crossing nets and degrade routing quality due to sequential coloring for mask selection. To resolve these problems, we propose a new graph model to prevent self-crossing nets during routing and use a weighted conflict graph to globally consider net coloring. We then propose the first non-stitch triple patterning-aware routing scheme, which consists of two main stages: (1) conflict graph pre-coloring followed by (2) pre-coloring-based non-stitch routing. Experimental results show the effectiveness and efficiency of our routing scheme.

Due to the significant mismatch between global-routing congestions estimated during placement and the resulting design-rule violations in detailed routing, considering both global and detailed routability during placement is of particular importance for modern circuit designs. This paper presents an analytical standard-cell placement algorithm to optimize detailed routability with three major techniques: (1) A routability-driven wirelength model that directly minimizes routing congestion and wirelength simultaneously with no additional computational overhead in global placement. (2) A detailed-routability-aware whitespace allocation technique in legalization. (3) A multi-stage congestion-aware cell spreading method in detailed placement. Compared with the participating teams of the 2014 ISPD Detailed-Routing-Driven Placement Contest and a state-of-the-art routability-driven placer, our placer achieves the best quality in both detailed-routing violation and wirelength scores.

As process nodes continue to shrink, the semiconductor industry faces severe manufacturing challenges. Two most expected technologies may push the limits of next-generation lithography: extreme ultraviolet lithography (EUVL) and electron beam lithography (EBL). EUVL works by emitting intense beams of ultraviolet light that are reflected from a reflective mask into a resist for nanofabrication, while EBL scans focused beams of electrons to directly draw high-resolution feature patterns on a resist without employing any mask. Each of the two technologies encounters unique design challenges and requires solutions for a breakthrough. In this paper, we focus on the design-for-manufacturability issues for EUVL and EBL. We investigate the most critical design challenges of the two technologies, flare and shadowing effects for EUVL, and heating, stitching, fogging, and proximity effects for EBL. Preliminary solutions for these effects are explored, which can contribute to the continuing scaling of the CMOS technology. Finally, we provide future research directions for these key effects.

Placement is a crucial stage for FPGA implementation. Most FPGA placers optimize their placement results by minimizing half-perimeter wirelength (HPWL). Due to the segmented routing architecture in FPGAs, however, the HPWL function cannot model routed wirelength and delay well. The mismatch of the HPWL function might lead to inferior routing results. Further, heterogeneous circuit blocks in a modern FPGA make the placement problem more complex. Consequently, it is desirable to consider the segmented routing and heterogeneous circuit architecture for FPGA placement. This paper presents a routing-architecture-aware analytical placement algorithm for heterogeneous FPGAs. Our algorithm proposes a routing-architecture-aware cost function to make placement results adapt to the corresponding routing architecture, and a complex block density model to effectively handle the heterogeneity. Experimental results show that our placer can achieve 9% smaller critical path delay and 5% shorter routed wirelength with shorter runtime, compared to the state-of-the-art academic placer.

Self-aligned double patterning (SADP) with complementary e-beam lithography (EBL) is one of the most promising hybrid-lithography techniques for sub-20nm designs. The complementary EBL mitigates the deficiencies of using a single cut mask in SADP. However, the low throughput and negative side effects of EBL might significantly increase the manufacturing costs and damage the symmetry properties in analog circuits. In this paper, we present the first work that considers SADP with EBL during analog placement to simultaneously optimize the area, wirelength, overlay errors, and e-beam shots. We first propose an overlay and cut conflict-aware SADP decomposition algorithm to optimize the overlay errors and e-beam shots in a layout. Then, a dynamic programming based module shifting technique is developed based on a symmetry-feasible slicing tree formulation to further minimize the differences of overlay errors and e-beam shots between symmetry modules during analog placement. To explore and obtain a desired placement, an analog placement flow is also presented. Experimental results show that our flow can effectively and efficiently reduce area, overlay errors, and e-beam shots while satisfying the symmetry constraints for analog placement.

Layout-dependent effects (LDEs) have become a critical issue in modern analog and mixed-signal circuit designs. The three major sources of LDEs, well proximity, length of oxide diffusion, and oxide-to-oxide spacing, significantly affect the threshold voltage and mobility of devices. In this paper, we propose the first work to consider the three major sources of LDEs during analog placement. We first transform the three LDE models into nonlinear analytical placement models. Then an LDE-aware analytical analog placement algorithm is presented to mitigate the influence of the LDEs while improving circuit performance. Experimental results show that our placement algorithm can effectively and efficiently reduce the LDE-induced variations and improve circuit performance.

One-dimensional nanowires are one of the most promising next-generation lithography technologies for 7 nm process node and beyond. The 1D nanowire process first constructs a 1D nanoarray through template synthesis followed by line-end cutting with additional cut masks. To achieve better yield and manufacturability, the cut patterns shall satisfy specified restricted design rules, and thus it is desirable to develop a novel routing methodology to better address the challenges arising from cut patterns. In this paper, we propose the first nanowire-aware routing system, called NWR, considering high cut-mask complexity based on a two-pass, bottom-up multilevel routing framework. Experimental results show that our nanowire-aware router can effectively and efficiently reduce cut numbers, cut spacing violations, and line-end extension length.

A placer without considering modern technology and region constraints could generate solutions with irresolvable detailed-routing violations or even illegal solutions. This paper presents a high-quality placement algorithm to satisfy technology and region constraints and optimize detailed-routing routability with three major techniques: (1) a clustering algorithm followed by two-round quadratic placement to obtain an initial placement satisfying region constraints, (2) an analytical placement algorithm with new wirelength and density models to consider region constraints, and (3) a legalization algorithm that preserves the solution quality of global placement while satisfying technology/region constraints. Compared with the winning teams of the ISPD 2015 Blockage-Aware Detailed Routing-Driven Placement Contest, our placer achieves the best overall score and detailed-routing results.

Electron beam lithography (EBL) has been used for high-resolution photomask fabrication; its successive heating process in a certain region, however, may cause critical dimension (CD) distortion. As a result, subfield scheduling which reorders a sequence of subfields in the writing process is desirable to avoid the heating problem and thus CD distortion. To consider longer-range heat dissipation, this paper models a subfield scheduling problem with blocked region consideration as a constrained max-min m-neighbor travelling salesman problem (called constrained m-nTSP). To solve the constrained m-nTSP which is NP-complete in general, we decompose a constrained m-nTSP into subproblems conforming to a special case with points on two parallel lines, solve each of them with a provably good linear-time approximation algorithm, and merge them into a complete scheduling solution. In particular, our algorithm can also minimize the distances between successive subfields to alleviate the throughput degradation of EBL writing due to moving a writing head, while minimizing the heating problem. Average reductions of 10% in the maximum temperature and 14% in the distances between successive subfields over the state-of-the-art work can be achieved.

Capacitance-ratio mismatch in a switched-capacitor circuit could significantly degrade circuit performance. In the nanometer era, the parasitic effects and lengths of interconnects both have significant impacts on the capacitance ratio. This paper presents the first routing work for the problem of coupling-aware length-ratio-matching routing for capacitor arrays in analog integrated circuits. The router adopts a two-stage approach of topology generation followed by detailed routing to route unit capacitors such that the coupling-aware wire length ratio can match the desired capacitance ratio. Given a length ratio, in particular, the length-ratio-matching routing problem can be handled by transforming the problem into an easier classical wirelength minimization one. Experimental results show that our algorithm can solve the addressed problem with substantially smaller costs.

Multiple e-beam lithography (MEBL) is one of the most promising next generation lithography technologies for high volume manufacturing, which improves the most critical issue of conventional single e-beam lithography, throughput, by simultaneously using thousands or millions of e-beams. For parallel writing in MEBL, a layout is split into stripes and patterns are cut by stripe boundaries, which are defined as stitching lines. Critical patterns cut by stitching lines could suffer from severe pattern distortion or even yield loss. Therefore, considering the positions of stitching lines and avoiding stitching line-induced bad patterns are required during layout design. In this paper, we propose the first work of stitch-aware routing framework for MEBL based on a two-pass bottom-up multilevel router. We first identify three types of stitching line-induced bad patterns which should not exist in an MEBL-friendly routing solution. Then, stitch-aware routing algorithms are, respectively, developed for global routing, layer/track assignment, and detailed routing. Experimental results show that our stitch-aware routing framework can effectively reduce stitching line-induced bad patterns and thus may not only improve the manufacturability but also facilitate the development of MEBL.

Metal-configurable gate-array spare cells, which have versatile functionality, are developed to overcome the inflexibility of standard spare cells used in conventional metal-only engineering change order (ECO). In this paper, we focus on functional ECO optimization using the new type of spare cells to fully exploit its strength. We observe that this functional ECO problem has the nature of dynamic logical and physical costs for selecting spare gate arrays. Unlike existing functional ECO works, which perform technology mapping based on ECO patches, we perform reverse mapping from spare gate arrays to handle these dynamic costs. We devise a spare array relation graph to record geometrical adjacency among spare gate arrays and interleave with the and-inverter network of ECO patches. To avoid redundant traversal and monitor the dynamic costs, we adopt A* search to simultaneously traverse and map between the logical ECO network and the physical spare array relation graph.

We present a new floorplan representation, called circular-packing trees (CP-trees), for the problem of macro placement. Our CP-trees can flexibly pack movable macros toward corners or pre-placed macros along chip boundaries circularly to optimize macro positions/orientations for better wirelength and routing congestion. Unlike previous macro placers that often consider only the interconnections among macros, we develop a routability-aware wirelength model to fast estimate the wirelength among macros and standard cells and to consider macro porosity effects for better routability. Compared with leading academic mixed-size placers, experimental results show that our algorithm can achieve the shortest routed wirelength for industrial benchmarks.

Asynchronous circuits are a promising design style for low-power and high-performance applications, where asynchronous templates have been widely used to automate the design of asynchronous circuits to reduce design efforts such as the implementation of handshaking mechanisms. Among the templates, pipeline templates are popular in high-performance systems. This paper presents an asynchronous template that can generate pipelines with low glitch-power consumption under the two-phase bundled-data protocol. Moreover, operations of our pipeline template can be hazard-free by simple techniques. We further analyze the timing constraints of pipelines based on the template, and then introduce two practical extensions of using the template. Compared with the prior work considering glitch-power reduction, pipelines using our proposed template can achieve significantly higher performance, lower power consumption, and less area overhead, with similar glitch-power reduction.

EUV flare and CMP metal thickness are two main manufacturability concerns for nanometer process technology. The two dummification objectives, however, are conflicting with each other in nature, but existing works only tackle them separately, leading to problem-prone solutions because optimizing one would deteriorate the other. This paper presents the first work that simultaneously considers both concerns during manufacturability optimization. Given a system's point spread function, our proposed method first finds an initial solution with better-than-state-of-the-art EUV flare uniformity, then followed by gradient-guided optimization to iteratively refine density uniformity. Experimental results show the effectiveness of our method.

Self-aligned double patterning (SADP) is one of the most promising techniques for sub-20nm technology. Spacer-is-dielectric SADP using a cut process is getting popular because of its higher design flexibility; for example, it can decompose odd cycles without the need of inserting any stitch. This paper presents the first work that applies the cut process for decomposing odd cycles during routing. For SADP, further, overlay control is a critical issue for yield improvement; while published routers can handle only partial overlay scenarios, our work identifies all the scenarios that induce overlays and proposes a novel constraint graph to model all overlays. With the developed techniques, our router can achieve high-quality routing results with significantly fewer overlays (and thus better yields). Compared with three state-of-the-art studies, our algorithm can achieve the best quality and efficiency, with zero cut conflicts, smallest overlay length, highest routability, and fastest running time.

As FPGA architecture evolves, complex heterogenous blocks, such as RAMs and DSPs, are widely used to effectively implement various circuit applications. These complex blocks often consist of datapath-intensive circuits, which are not adequately addressed in existing packing and placement algorithms. Besides, scalability has become a first-order metric for modern FPGA design, mainly due to the dramatically increasing design complexity. This paper presents efficient and effective packing and analytical placement algorithms for large-scale heterogeneous FPGAs to deal with issues on heterogeneity, datapath regularity, and scalability. Compared to the well-known academic tool VPR, experimental results show that our packing and placement algorithms achieve respective 199.80X and 3.07X speedups with better wirelength, and our overall flow achieves 50% shorter wirelength, with an 18.30X overall speedup.

As nanometer technology advances, conventional OPC (Optical Proximity Correction) that minimizes the EPE (Edge Placement Error) at the nominal corner alone often leads to poor process window. To improve the mask printability across various process corners, process-window OPC optimizes EPE for multiple process corners, but often suffers long runtime, due to repeated lithographic simulations. This paper presents an efficient process-variation-aware mask optimization framework, namely PVOPC (Process-Variation OPC), to simultaneously minimize EPE and PV (Process-Variation) band with fast convergence. The PVOPC framework includes EPE-sensitivity-driven dynamic fragmentation, process-variation-aware EPE modeling, and post correction with three new EPE-converging techniques and a systematic sub-resolution assisted feature insertion algorithm. Experimental results show that our approach efficiently achieves high-quality EPE and PV band results.

Extreme ultraviolet (EUV) lithography is one of the most promising next-generation lithography technologies, while chemical mechanical polishing (CMP) is the key planarization process for improving chip surface topography. The two techniques are highly related to layout pattern distribution and require different (even conflicting) distributions for EUV flare and CMP variation optimization to achieve better yields. Placement is a critical stage for controlling layout pattern distribution. In this paper, we propose the first work of simultaneous EUV flare-and CMP-aware placement to address the conflicting pattern distribution requirements with the two techniques. We present a sigmoid distribution model to reduce EUV flare effects and a metal-aware pin model to improve metal distribution. The two models are incorporated into a non-linear analytical optimization framework to achieve desired placement solutions. Experimental results show the effectiveness and efficiency of our proposed method.

A clock tree typically consumes substantial dynamic power, and thus the considerable heat generated by itself can cause serious clock-skew variations. In this paper, we propose a self-heating-aware buffered clock tree synthesis flow. A mixed integer linear programming (MILP) formulation is proposed to simultaneously model heat spreading, place buffers, and determine a temperature-aware clock tree topology. The formulation is then transformed into a succession of low-complexity feasibility problems to further reduce the runtime. In addition, a fast superposition approach is proposed to incrementally update thermal profiles to reduce simulation time. Experimental results show that our synthesis flow can achieve averagely 50.57% worst-case clock skew reduction, compared with the original symmetrical clock tree.

While double patterning lithography (DPL) has been widely recognized as one of the most promising solutions for the sub-22 nm technology node to enhance pattern printability, triple patterning lithography (TPL) will be required for gate, contact, and metal-1 layers which are too complex and dense to be split into only two masks, for the 15 nm technology node and beyond. Nevertheless, there is very little research focusing on the layout decomposition for TPL. Recent work proposed the first systematic study on the layout decomposition for TPL. However, the proposed algorithm extending a stitch-finding method used in DPL may miss legal stitch locations and generate conflicts that can be resolved by inserting stitches for TPL. In this paper, we point out two main differences between DPL and TPL layout decompositions. Based on the two differences, we propose a novel TPL layout decomposition algorithm. We first present two new graph reduction techniques to reduce the problem size without degrading overall solution quality. We then propose a stitch-aware mask assignment algorithm, based on a heuristic that finds a mask assignment such that the conflicts among the features in the same mask are more likely to be resolved by inserting stitches. Finally, stitches are inserted to resolve as many conflicts as possible. Experimental results show that the proposed layout decomposition algorithm can achieve around 56% reduction of conflicts and more than 40X speed-up, as compared to the previous work.

The flip-chip packaging is introduced for modern IC designs with higher integration density and larger I/O counts. It is necessary to consider routing obstacles for modern flip-chip designs, where the obstacles could be regions blocked for signal integrity protection (especially for analog/mixed-signal modules), prerouted or power/ground nets, and even for through-silicon vias for 3-D IC designs. However, no existing published works consider obstacles. To remedy this insufficiency, this paper presents the first work to solve the free-assignment flip-chip routing problem considering obstacles. For the free-assignment routing problem, most existing works apply the network-flow formulation. Nevertheless, we observe that no existing network-flow model can exactly capture the routability of a local routing region (tile) in presence of obstacles. This paper presents the first work that can precisely model the routability of a tile, even with obstacles. Based on this new model, a two-stage approach of global routing followed by detailed routing is proposed. The global routing computes a routing topology by the minimum-cost maximum-flow algorithm, and the detailed routing determines the precise wire positions. Dynamic programming is applied to further merge tiles to reduce the problem size. Compared to a state-of-the-art flow model with obstacle handling extensions, experimental results show that our algorithm can achieve 100% routability for all circuits while the extensions of the previous work cannot complete routing for any benchmark circuit with obstacles.

A wirelength-driven placer without considering routability could introduce irresolvable routing-congested placements. Therefore, it is desirable to develop an effective routability-driven placer for modern mixed-size designs employing hierarchical methodologies for faster turnaround time. In this paper, we propose a novel routability-driven analytical placement algorithm for hierarchical mixed-size circuit designs. This paper presents a novel design hierarchy identification technique to effectively identify design hierarchies and guide placement for better wirelength and routability. The proposed algorithm optimizes routability from four major aspects: 1) narrow channel handling; 2) pin density; 3) routing overflow optimization; and 4) net congestion optimization. Routability-driven legalization and detailed placement are also proposed to further optimize routing congestion. Compared with the participating teams for the 2012 ICCAD Design Hierarchy Aware Routability-driven Placement Contest, our placer can achieve the best quality (both the average overflow and wirelength) and the best overall score (by additionally considering running time).

Symmetry, common-centroid, topology-matching, and length-matching constraints are four major routing considerations to improve the performance of an analog circuit. Symmetry constraints are specified to route matched nets symmetrically with respect to some common axes. Common-centroid constraints are also specified to route matched net symmetrically with respect to some common centers. Topology-matching constraints are commonly imposed on critical yet asymmetry nets with the same number of bends, vias, and wirelength. Length-matching constraints are specified to route the nets which have limited resources with the same wirelength. These four constraints can reduce current mismatches and unwanted electrical effects between two critical nets. In this paper, we propose the first work to simultaneously consider the four constraints for analog routing while minimizing total wirelength, bend numbers, via counts, and coupling noise at the same time. We first present a basic integer linear programming (ILP) formulation to simultaneously consider the four constraints for analog routing. Then, a prioritized-constraint-aware routing algorithm is proposed to assist analog designers for assigning the four matching constraints and optimizing routing topologies. Effective reduction techniques are also employed to reduce the numbers of ILP variables and constraints for the two routing algorithms. To further enhance the routing performance, a nonuniform multilevel routing framework is presented and integrated into our routing algorithms. Experimental results show that our approach can obtain better routing results and satisfy all specified routing constraints while optimizing circuit performance.

As the technology advances, the pin number of a high-end PCB design keeps increasing. The staggered pin array is used to accommodate a larger pin number than the grid pin array of the same area. Nevertheless, escaping a large pin number to the boundary of a dense staggered pin array, namely multilayer escape routing for staggered pin arrays, is significantly harder than that for grid pin arrays. This paper addresses this multilayer escape routing problem to minimize the number of used layers in a staggered pin array for manufacturing cost reduction. We first present an escaped pin selection method to assign a maximal number of escaped pins in the current layer and also to increase useful routing regions for subsequent layers. Missing pins are also modeled in our routing network to utilize the routing resource effectively. Experimental results show that our approach can significantly reduce the required layer number for escape routing.

For high-performance synchronous systems, non-uniform/non-ideal supply voltages of buffers (e.g., due to IRdrop) may incur a large clock skew and thus serious performance degradation. This paper addresses this problem and presents the first symmetrical buffered clock-tree synthesis flow that considers supply voltage differences of buffers. We employ a two-phase technique of bottom-up clock sink clustering to determine the tree topology, followed by top-down buffer placement and wire routing to complete the clock tree. At each level of processing, clock skew and wirelength are minimized by the determination of buffer embedding regions and the alignment of buffer supply voltages. Experimental results show that our method can reach, on average, respective 76% and 40% clock skew reduction compared to the state-of-the-art work (1) without supply voltage consideration and (2) with an extension for supply voltages based on our top-down flow. The reduction is achieved by marginal resource and runtime overheads. Note that our method can meet the stringent skew constraint set by the 2010 ISPD contest for all cases, while other counterparts cannot. In particular, our work provides a key insight into the importance of handling practical design issues (such as IR-drop) for real-world clock-tree synthesis.

Double patterning lithography (DPL) is one of the most promising solutions for the 28nm technology node and beyond. The main idea of DPL is to decompose the layout into two sub-patterns and manufacture the layout by two masks. In addition to traditional analog design constraints, the pre-coloring constraint should also be considered, in which patterns of critical or sensitive modules have predefined masks before layout decomposition to reduce mismatches. In this paper, we present the first work that considers DPL during analog placement and simultaneously minimizes area, wirelength, and DPL conflicts. We first propose an extended conflict graph (ECG) to represent the relation between patterns of analog modules and apply an integer linear programming (ILP) formulation to determine the orientation of each module and the color of each pattern for conflict minimization. ILP reduction schemes are proposed to further reduce the runtime. Finally, we present a three-stage flow and DPL-aware perturbations to obtain desired solutions. Experimental results show that the proposed flow can effectively and efficiently reduce area, wirelength, and DPL conflicts.

Multiple e-beam lithography (MEBL) is one of the most promising next generation lithography (NGL) technologies for high volume manufacturing, which improves the most critical issue of conventional single e-beam lithography, throughput, by simultaneously using thousands or millions of e-beams. For parallel writing in MEBL, a layout is split into stripes and patterns are cut by stripe boundaries, which are defined as stitching lines. Critical patterns cut by stitching lines could suffer from severe pattern distortion or even yield loss. Therefore, considering the positions of stitching lines and avoiding stitching line-induced bad patterns are required during layout design. In this paper, we propose the first work of stitch-aware routing framework for MEBL based on a two-pass bottom-up multilevel router. We first identify three types of stitching line-induced bad patterns which should not exist in an MEBL-friendly routing solution. Then, stitch-aware routing algorithms are respectively developed for global routing, layer/track assignment and detailed routing. Experimental results show that our stitch-aware routing framework can effectively reduce stitching line-induced bad patterns and thus may not only improve the manufacturability but also facilitate the development of MEBL.

An interposer-based three-dimensional integrated circuit, which introduces a silicon interposer as an interface between chips and a package, is one of the most promising integration technologies for modern and next-generation circuit designs. Inter-chip connections can be routed on the interposer by chip-scale wires to enhance design quality. However, its design complexity increases dramatically due to the extra interposer interface. Consequently, it is desirable to simultaneously consider the co-design of the interposer and multiple chips mounted on it. This paper addresses the first work of chip-interposer codesign to place multiple chips on an interposer to reduce inter-chip wirelength. For this problem, we propose a new hierarchical B*-tree to simultaneously place multiple chips, macros, and I/O Buffers. An approach based on bipartite matching is then proposed to concurrently assign signals from I/O buffers to micro bumps. Experimental results show that our approach is effective and efficient for the codesign problem.

Capacitance-ratio mismatch in a switched-capacitor circuit could significantly degrade circuit performance. In the nanometer era, the parasitic effects and lengths of interconnects both have significant impacts on the capacitance ratio. This paper presents the first routing work for the problem of coupling-aware length-ratio-matching routing for capacitor arrays in analog integrated circuits. The router adopts a two-stage approach of topology generation followed by detailed routing to route unit capacitors such that the coupling-aware wire length ratio can match the desired capacitance ratio. Given a length ratio, in particular, the length-ratio-matching routing problem can be handled by transforming the problem into an easier classical wirelength minimization one. Experimental results show that our algorithm can solve the addressed problem with substantially smaller costs.

A wirelength-driven placer without considering routability could introduce irresolvable routing-congested placements. Therefore, it is desirable to develop an effective routability-driven placer for modern mixed-size designs employing hierarchical methodologies for faster turnaround time. This paper presents a novel two-stage technique to effectively identify design hierarchies and guide placement for better wirelength and routability. To optimize wirelength and routability simultaneously during placement, a new analytical net-congestion-optimization technique is also proposed. Compared with the participating teams for the 2012 ICCAD Design Hierarchy Aware Routability-driven Placement Contest, our placer can achieve the best quality (both the average overflow and wire-length) and the best overall score (by additionally considering running time).

The increasing design complexity of modern circuits has made traditional FPGA placement techniques not efficient anymore. To improve the scalability, commercial FPGA placement tools have started migrating to analytical placement. In this paper, we propose the first academic multilevel timing-and-wirelength-driven analytical placement algorithm for FPGAs. Our proposed algorithm consists of (1) multilevel timing-and-wirelength-driven analytical global placement with the novel block alignment consideration, (2) partitioning-based legalization, (3) wirelength-driven block matching-based detailed placement, and (4) timing-driven simulated-annealing-based detailed placement. Experimental results show that our proposed approach can achieve 6.91x speedup on average with 7% smaller critical path delay and 1% shorter routed wirelength compared to VPR, the well-known, state-of-the-art academic simulated-annealing-based FPGA placer.

Current-flow and current-density are two major considerations for placement and routing of analog layout synthesis. The current-flow constraints are specified to the critical nets with monotonic current/signal paths to reduce parasitic impacts. The current-density constraints are usually specified on the nets with variable wire widths to avoid the IR-drop and electromigration problems. In this paper, we propose the first work to simultaneously consider current-flow and current-density constraints while placing and routing the analog circuits with minimized chip area, routed wirelength, bend numbers, via counts, and coupling noise at the same time. We first present an enhanced B*-tree representation to simultaneously model modules and interconnects for an analog circuit. Then a simultaneous placement and routing algorithm is presented to generate a layout while satisfying the current-flow and current-density constraints with minimized chip area, routed wire-length, bend numbers, via counts, and coupling noise. Experimental results show that our approach can obtain better layout results and satisfy all specified constraints while optimizing circuit performance.

As the process technology advances to the nanometer nodes, Optical Proximity Correction (OPC) is the most popular Resolution-Enhancement Technique (RET) in industry for subwavelength lithography, and the inter-level dielectric (ILD) thickness variation caused by the planarization step of the Chemical-Mechanical Polishing (CMP) process also plays a key role for interconnect yield. Considering the OPC and CMP effects simultaneously during the routing stage can significantly alleviate the width and thickness variations (and thus the whole 3D geometry variations) of post-layout RET and CMP operations. In this paper, we first present an efficient, yet sufficiently accurate closed-form formula for printed width computation and dummy-insertion-aware routing cost derivation. The formula provides a cost modeling for post-layout OPC and CMP optimization during routing. Incorporating the OPC and CMP costs, the router can be guided to optimize the effects of layout correction and planarization. Compared with the state-of-the-art OPC-friendly router, QL-MGR (which does not consider CMP), the experimental results show that our approach can achieve respective 19% and 6% reductions in the maximum and average layout distortions. Compared with the state-of-the-art CMP-aware router, TTR (which does not consider OPC), the experimental results show that our approach can achieve respective 19% and 25% reductions in the peak-to-peak thickness and thickness variance. These results indicate that our simultaneous OPC- and CMP-aware router contributes a significant improvement for layout integrity.

Due to the rapidly increasing design complexity in modern IC designs, metal-only engineering change order (ECO) becomes inevitable to achieve design closure with a low respin cost. Traditionally, preplaced redundant standard cells are regarded as spare cells. However, these cells are limited by predefined functionalities and locations, and they always consume leakage power despite their inputs being tied off. To overcome the inflexibility and power overhead, a new type of spare cells, called metal-configurable gate-array spare cells, are introduced. In this paper, we address a new ECO problem, which performs design changes using metal-configurable gate-array spare cells. We first study the properties of this new ECO problem and propose a new cost metric, aliveness, to model the capability of a spare gate array. Based on aliveness and routability, we then develop two ECO optimization frameworks, one for timing ECO and the other for functional ECO. Experimental results show that our approach delivers superior efficiency and effectiveness.

Electron beam lithography has shown great promise in photomask fabrication; however, its successive heating process centralizing in a small region may cause a severe problem of critical dimension (CD) distortion. Consequently, subfield scheduling that reorders the sequence of the writing process is needed to avoid successive writing of neighboring subfields. In addition, the writing process of a subfield raises the temperature of neighboring regions and may block other subfields for writing. This paper presents the first work to solve the subfield scheduling problem while considering blocked regions by formulating the problem into a constrained maximum scatter traveling salesman problem (constrained MSTSP). To tackle the constrained MSTSP that can be shown to be NP-complete in general, we identify a special case thereof with points on two parallel lines and solve it optimally in linear time. We then decompose the constrained MSTSP into subproblems conforming to the special case, solve each subproblem optimally and efficiently by a graph-based algorithm, and then merge the subsolutions into a complete scheduling solution. We also extend our algorithm to handle the cases when the moving time of an e-beam writing head is comparable with the writing time of a subfield. Experimental results show that our algorithms are effective and efficient in finding good subfield scheduling solutions that can alleviate the successive heating problem (and thus reduce CD distortion) for e-beam photomask fabrication.

To accommodate the ever-growing pin number of complex printed circuit board (PCB) designs, the staggered pin array is introduced for modern designs with higher pin density. However, the escape routing for staggered pin arrays, which is a key component of PCB routing, is significantly different from that for grid arrays. This paper presents a routing algorithm for the escape routing for staggered-pin-array PCBs. We first analyze the properties of staggered pin arrays, and propose an orthogonal-side wiring style that fully utilizes the routing resource of the staggered pin array. A linear programming/integer linear programming-based algorithm is presented to solve the staggered-pin-array escape routing problem. Experimental results show that our approach successfully routes all test cases efficiently and effectively.

Through-silicon vias (TSVs) are required for transmitting signals among different dies for the 3-D integrated circuit (IC) technology. The significant silicon areas occupied by TSVs bring critical challenges for 3-D IC placement. Unlike most published 3-D placement works that only minimize the number of TSVs during placement due to the limitations in their techniques, this paper proposes a new 3-D cell placement algorithm that can additionally consider the sizes of TSVs and the physical positions for TSV insertion during placement. The algorithm consists of three stages: 1) 3-D analytical global placement with density optimization and whitespace reservation for TSVs; 2) TSV insertion and TSV-aware legalization; and 3) layer-by-layer detailed placement. In particular, the global placement is based on a novel weighted-average (WA) wirelength model, giving the first published model that can outperform the well-known log-sum-exp wirelength model theoretically and empirically. Also, a scheme is proposed to enhance the numerical stability of the WA wirelength model. Furthermore, 3-D routing can easily be accomplished by traditional 2-D routers since the physical positions of TSVs are determined during placement. Experimental results show the effectiveness of our algorithm. Compared with state-of-the-art 3-D cell placement works, our algorithm can achieve the best routed wirelength, TSV counts, and total silicon area, in shortest running time.

Due to the rapidly increasing design complexity in modern IC designs, metal-only engineering change order (ECO) becomes inevitable to achieve design closure with a low respin cost. Traditionally, preplaced redundant standard cells are regarded as spare cells. However, these cells are limited by predefined functionalities and locations, and they always consume leakage power despite their inputs are tied off. To overcome the inflexibility and power overhead, a new type of spare cells, metal-configurable gate-array spare cells, are considered. Therefore, in this paper, we address a new ECO problem: Timing ECO optimization using metal-configurable gate-array spare cells. We first study the properties for this new ECO problem, propose a new metric, aliveness, to model the capability of a spare gate array, and then develop a timing ECO optimization framework based on aliveness, routability, and timing satisfaction. Experimental results show that our approach delivers superior efficiency and effectiveness.

Datapath is one of the most important components in high performance circuit designs, such as microprocessors, as it is used to manipulate all data. For better performance, a datapath is usually placed with high regularity and compactness. Although cell placement has been studied extensively, not much work addresses the optimization of datapaths which are often treated as big macros. In this paper, we propose a structure-aware placement algorithm that can exploit the regular structures of datapath circuits and meanwhile leverage effective techniques to achieve high quality and scalability. Our algorithm applies a nonlinear optimization for wirelength minimization and a sigmoid based density model for density control in datapath circuits. Compared with state-of-the-art works, our algorithm can achieve the best structure-aware placement results efficiently.

Extreme Ultraviolet Lithography (EUVL) is one of the most promising Next Generation Lithography (NGL) technologies. Due to the surface roughness of the optical system used in EUVL, the rather high level of flare (i.e., scattered light) becomes one of the most critical issues in EUVL. In addition, the layout density non-uniformity and the flare periphery effect (the flare distribution at the periphery is much different from that in the center of a chip) also induce a large flare variation within a layout. Both of the high flare level and the large flare variation could worsen the control of critical dimension (CD) uniformity. Dummification (i.e., tiling or dummy fill) is one of the flare compensation strategies to reduce the flare level and the flare variation for the process with a clear-field mask in EUVL. However, existing dummy fill algorithms for Chemical-Mechanical Polishing (CMP) are not adequate for the flare mitigation problem in EUVL due to the flare periphery effect. This paper presents the first work that solves the flare mitigation problem in EUVL with a specific dummification algorithm flow considering global flare distribution. The dummification process is guided by dummy demand maps, which are generated by using a quasi-inverse lithography technique. In addition, an error-controlled fast flare map computation technique is proposed and integrated into our algorithm to further improve the efficiency without loss of computation accuracy. Experimental results show that our flow can effectively and efficiently reduce the flare level and the flare variation, which may contribute to the better control of CD uniformity.

While double patterning lithography (DPL) has been widely recognized as one of the most promising solutions for the sub-22nm technology node to enhance pattern printability, triple patterning lithography (TPL) will be required for gate, contact, and metal-1 layers which are too complex and dense to be split into only two masks, for the 15nm technology node and beyond. Nevertheless, there is very little research focusing on the layout decomposition for TPL. The recent work [16] proposed the first systematic study on the layout decomposition for TPL. However, the proposed algorithm extending a stitch-finding method used in DPL may miss legal stitch locations and generate conflicts that can be resolved by inserting stitches for TPL. In this paper, we point out two main differences between DPL and TPL layout decompositions. Based on the two differences, we propose a novel TPL layout decomposition algorithm. We first present two new graph reduction techniques to reduce the problem size without degrading overall solution quality. We then propose a stitch-aware mask assignment algorithm, based on a heuristic that finds a mask assignment such that the conflicts among the features in the same mask are more likely to be resolved by inserting stitches. Finally, stitches are inserted to resolve as many conflicts as possible. Experimental results show that the proposed layout decomposition algorithm can achieve around 56% reduction of conflicts and more than 40X speed-up compared to the previous work.

In today's IC production, the design processes of chips, packages, and boards are typically separate from each other. The lack of information from other domains causes significant design convergence problems and greatly reduces design quality. In this paper, we propose the first chip-package-board code-sign methodology that provides true bi-directional information interactions among the three design domains. The code-sign adopts a two-pass flow of board-package-chip followed by chip-package-board routing interactions to facilitate the overall design integration. Experimental results show that our code-sign flow succeeds in the routing for all test cases, while a traditional flow and two board-driven flows fail all cases.

The flip-chip packaging is introduced for modern IC designs with higher integration density and larger I/O counts. It is necessary to consider routing obstacles for modern flip-chip designs, where the obstacles could be regions blocked for signal integrity protection (especially for analog/mixed-signal modules), pre-routed or power/ground nets, and even for through-silicon vias for 3D IC designs. However, no existing published works consider obstacles. To remedy this insufficiency, this paper presents the first work to solve the free-assignment flip-chip routing problem considering obstacles. For the free-assignment routing problem, most existing works apply the network-flow formulation. Nevertheless, we observe that no existing network-flow model can exactly capture the routability of a local routing region (tile) in presence of obstacles. This paper presents the first work that can precisely model the routability of a tile, even with obstacles. Based on this new model, a two-stage approach of global routing followed by detailed routing is proposed. The global routing computes a routing topology by the minimum-cost maximum-flow algorithm, and the detailed routing determines the precise wire positions. Dynamic programming is applied to further merge tiles to reduce the problem size. Compared to a state-of-the-art flow model with obstacle handling extensions, experimental results show that our algorithm can achieve 100% routability for all circuits while the extensions of the previous work cannot complete routing for any benchmark circuit with obstacles.

Symmetry, topology-matching, and length-matching constraints are three major routing considerations to improve the performance of an analog circuit. Symmetry constraints are specified to route matched nets symmetrically with respect to some common axes. Topology-matching constraints are commonly imposed on critical yet asymmetry nets with the same number of bends, vias, and wirelength. Length-matching constraints are specified to route the nets which have limited resources with the same wirelength. These three constraints can reduce current mismatches and unwanted electrical effects between two critical nets. In this paper, we propose the first work to simultaneously consider the three constraints for analog routing while minimizing total wirelength, bend numbers, via counts, and coupling noise at the same time. We first present an integer linear programming (ILP) formulation to simultaneously consider the three constraints for analog routing, and employ effective reduction techniques to further reduce the numbers of ILP variables and constraints. Then, a non-uniform multilevel routing framework is presented to enhance the performance of our routing algorithm. Experimental results show that our approach can obtain better routing results and satisfy all specified routing constraints while optimizing circuit performance.

Unaddressed thermal issues can seriously hinder the development of reliable and low power systems. In this paper, we propose a statistical approach for analyzing thermal behavior under leakage power variations stemming from the manufacturing process. Based on the proposed models, we develop floorplanning techniques targeting thermal optimization. The experimental results show that peak temperature is reduced by up to 8.8°C, while thermal-induced leakage power and maximum thermal variance are reduced by 13% and 17%, respectively, with no additional area overhead compared with best performance-driven optimized design.

Electron beam lithography (EBL) has shown great promise for photomask fabrication; however, its successive heating process centralizing in a small region may cause a severe problem of critical dimension (CD) distortion. Consequently, subfield scheduling which reorders the sequence of the writing process is needed to avoid successive writing of neighboring subfields. In addition, the writing process of a subfield raises the temperature of neighboring regions and may block other subfields for writing. This paper presents the first work to solve the subfield scheduling problem while taking into account blocked regions by formulating the problem into a constrained maximum scatter travelling salesman problem (constrained MSTSP). To tackle the constrained MSTSP which can be shown to be NP-complete in general, we identify a special case thereof with points on two parallel lines and solve it optimally in linear time. We then decompose the constrained MSTSP into subproblems conforming to the special case, solve each subproblem optimally and efficiently by a graph-based algorithm, and then merge the sub-solutions into a complete scheduling solution. Experimental results show that our algorithm is effective and efficient in finding good subfield scheduling solutions that can alleviate the successive heating problem (and thus reduce CD distortion) for e-beam photomask fabrication.

Due to the rapidly increasing design complexity in modern integrated circuit design, more and more timing failures are detected at late stages. Without deferring time-to-market, metal-only engineering change order (ECO) is an economical technique to correct these late-found failures. Typically, a design might need to undergo many ECO runs in design houses; consequently, the usage of spare cells for ECO is of significant importance. In this paper, we aim at timing ECO by using as few spare cells as possible. We observe that a path with good timing is desired to be geometrically smooth. Unlike negative slack and gate delay used in most prior work, we propose a new metric of timing criticality, fixability, by considering the smoothness of timing violating paths. To measure the smoothness of a path, we use the Bézier curve as the golden path. Furthermore, in order to concurrently fix timing violations, we derive a propagation property to divide violating paths into independent segments. Based on Bézier curve smoothing, fixability identification, and the propagation property, we develop an efficient algorithm to fix timing violations. Experimental results show that we can effectively resolve all timing violations with significant speedups over the state-of-the-art works.

Double patterning technology (DPT), in which a dense layout pattern is decomposed into two separate masks to relax its pitch, is the most popular lithography solution for the sub-22 nm node to enhance pattern printability. Previous work focused on stitch insertion to improve the decomposition success rate. However, there exist native conflicts (NCs) which cannot be resolved by any kind of stitch insertion. A design with NCs is not DPT-compliant and may fail the decomposition, resulting in design for manufacturability redesign and longer design cycles. In this paper, we give a sufficient condition for the NC existence and propose a geometry-based method for NC prediction to develop an early-stage analyzer for DPT decomposability checking. Then, a wire perturbation algorithm is presented to fix as many NCs in the layout as possible. The algorithm is based on iterative 1-D compaction and can easily be embedded into existing industrial compaction systems. The algorithm is then further applied to further reduce the number of stitches required for the decomposition process. Experimental results show that the proposed algorithm can significantly reduce the number of NCs by an average of 85% and reduce the number of stitches by an average of 39%, which may effectively increase the decomposition success rate for the next stage.

Due to increasing integrated circuit design complexity, engineering change orders (ECOs) have become a necessary technique to resolve late-found functional errors and/or performance deficiencies. To fix timing violations, gate sizing and buffer insertion are commonly used in postmask ECO. These techniques, however, may not be powerful enough, especially when spare cells are inserted to balance between functional and timing repair capabilities. We propose a postmask ECO technique, called TRECO, to remedy timing violations based on technology remapping, which also supports functional ECO. Unlike conventional technology mapping, TRECO performs technology mapping with respect to a limited set of spare cells and confronts dynamic changes of wiring cost incurred by selection of different spare cells. With a precomputed lookup table of representative circuit templates, TRECO iteratively performs technology remapping to restructure timing critical subcircuits until no timing violation can be further removed. Experimental results on five industrial designs show the effectiveness of TRECO in ECO timing optimization and in timing-aware functional ECO.

A modern chip often contains large numbers of predesigned macros (e.g., embedded memories, IP blocks) and standard cells, with very different sizes. The fast-growing design complexity with large-scale mixed-size macros and standard cells has caused significant challenges to modern circuit placement. Analytical algorithms have been shown to be most effective for standard-cell placement, but the problems with the rotation and legalization of large macros impose intrinsic limitations for analytical placement. Consequently, most recent works on mixed-size placement resort to combinatorial macro placement. Instead, this paper presents the first attempt to resolve the intrinsic problems with a unified analytical approach. Unlike traditional analytical placement that uses only wire and density forces to optimize the positions of circuit components, we present a new force, the rotation force, to handle macro orientation for analytical mixed-size placement. The rotation force tries to rotate each macro to its desired orientation based on the wire connections on this macro. A cross potential model is also proposed to increase the rotation freedom during placement. The final orientation of each macro with legalization consideration is then determined by mathematical programming. A macro flipping force is also proposed to determine the flipping orientation of each macro at the end of global placement. Compared with start-of-the-art mixed-size placement approaches (such as FLOP, CG, and MP-tree), our approach achieves the best average wirelength efficiently.

The flip-chip package is introduced for modern integrated circuit (IC) designs with higher integration density and larger I/O counts. In this paper, we consider the pre-assignment flip-chip routing problem with predefined connections between driver pads and bump pads. This problem has been shown to be much more difficult than the free-assignment one, but is more popular in real-world designs because the connections between driver pads and bump pads are typically predetermined by IC or packaging designers. Based on the concept of routing sequence exchange, we propose a very efficient approach to guide the global routing by computing the longest common subsequence and the maximum planar subset of chords for pre-assignment flip-chips. We observe that the existing work over-constrains the capacity of a routing tile, which might miss some critical solution space with a better routing solution (e.g., smaller wirelength), and provide a remedy for this insufficiency to identify a better solution in a more complete solution space. We also develop a constant-time routability analyzer to check if a given set of wires can pass through a tile. Experimental results show that our router can achieve a$125\times$speedup with even better solution quality (same routability with slightly smaller wirelength), compared with a state-of-the-art flip-chip router based on integer linear programming.

In high-performance synchronous chip design, a buffered clock tree with small clock skew is essential for improving clocking speed. Due to the insufficient accuracy of timing models for modern chip design, embedding simulation into a clock-tree synthesis flow becomes inevitable. Consequently, the running time for clock-tree synthesis becomes prohibitively huge as the complexity of chip designs grows rapidly. To construct a buffered clock tree efficiently, we propose an efficient timing-model independent approach to perform skew minimization by structural optimization. To achieve the goal, a novel clock-tree structure, called symmetrical structure, is presented. At each level of a symmetrical clock tree, the number of branches, the wirelength, and the inserted buffers are almost the same. It is natural that the clock skew could be minimized if the configurations of all paths from the clock source to sinks are similar. By symmetrically constructing a clock tree, the clock skew can be minimized without referring to simulation information. Experimental results show that our approach can not only efficiently construct a buffered clock tree but also effectively minimize clock skew with marginal wiring overheads. Based on a set of commonly used IBM benchmarks, e.g., a state-of-the-art work without (with) ngspice simulation results in averagely 10.04X (3.44X) clock skew and requires 163X (61906X) running time over our approach.

Metal-only ECO is prevalent at design houses to perform incremental design changes to resolve last found functional and/or timing failures. However, it is hard to perform mixed functional and timing changes manually. Prior endeavors focus on functional or timing ECO alone, but we observe that separating them may fail to fix all timing violations. Consequently, this paper presents the first work to perform simultaneous functional and timing ECO. We use an augmented bipartite graph to model both types of ECO. In addition, through comprehensive constant insertion and bridging, the functional capability of each spare cell is enhanced, thus facilitating spare cell selection. Experimental results show that our simultaneous functional and timing ECO engine can successfully resolve mixed functional and timing ECO that is unsolvable by the sequential scheme. Moreover, our engine outperforms the state-of-the-art works for timing ECO with a 117X speedup, and for functional ECO with 6--15% wirelength reductions.

Through-silicon vias (TSVs) are required for transmitting signals among different dies for the three-dimensional integrated circuit (3D IC) technology. The significant silicon areas occupied by TSVs bring critical challenges for 3D IC placement. Unlike most published 3D placement works that only minimize the number of TSVs during placement due to the limitations in their techniques, this paper proposes a new 3D cell placement algorithm which can additionally consider the sizes of TSVs and the physical positions for TSV insertion during placement. The algorithm consists of three stages: (1) 3D analytical global placement with density optimization and whitespace reservation for TSVs, (2) TSV insertion and TSV-aware legalization, and (3) layer-by-layer detailed placement. In particular, the global placement is based on a novel weighted-average wirelength model, giving the first model in the literature that can outperform the well-known log-sum-exp wirelength model theoretically and empirically. Further, 3D routing can easily be accomplished by traditional 2D routers since the physical positions of TSVs are determined during placement. Compared with state-of-the-art 3D cell placement works, our algorithm can achieve the best routed wirelength, TSV counts, and total silicon area, in shortest running time.

Due to the rapidly increasing design complexity in modern IC design, more and more timing failures are detected at late stages. Without deferring time-to-market, metal-only ECO is an economical technique to correct these late-found failures. Typically, a design undergoes many ECO runs in design houses; the usage of spare cells is of significant importance. Hence, in this paper, we aim at timing ECO using the least number of spare cells. We observe that a path with good timing is desired to be geometrically smooth. Different from negative slack and gate delay used in most of prior work, we propose a new metric of timing criticality - fixability - considering the smoothness of critical paths. To measure the smoothness of a path, we use Bézier curve as the golden path. Furthermore, in order to concurrently fix timing violations, we derive the dominance property to divide violated paths into independent segments. Based on Bézier curve smoothing, fixability identification, and the dominance property, we develop an efficient algorithm to fix violations. Compared with the state-of-the-art works, experimental results show that our algorithm not only effectively resolves all timing violations with few spare cells but also achieves 22.8X and 42.6X speedups.

Symmetry constraints and regular structures are two major considerations for expert analog layout designers. Symmetry constraints are specified to place matched modules symmetrically with respect to some common axes to reduce unwanted electrical effects. Regular structures are commonly followed by experienced designers to enhance routability and suppress parasitics induced by extra bends of wires and via cost. In this paper, we propose a heterogeneous B*-tree representation to consider symmetry and regularity simultaneously. Corresponding moves and a new regularity cost modelling for the representation are also presented. Experimental results show that our approach can efficiently generate regularly structured placement satisfying all symmetry constraints. For example, our placer achieves a 18X runtime speedup, 28% smaller area, and 68% shorter wirelength than the previous work, based on placement results, and 60% fewer overflows, 39% fewer vias, and 86% shorter routed wirelength, based on global routing results.

Pulsed latches have emerged as a popular technique to reduce the power consumption and delay for clock networks. However, the current physical synthesis flow for pulsed latches still performs circuit placement and clock-network synthesis separately, which limits achievable power reduction. This paper presents the first work in the literature to perform placement and clock-network co-synthesis for pulsed-latch designs. With the interplay between placement and clock-network synthesis, the clock-network power and timing can be optimized simultaneously. Novel progressive network forces are introduced to globally guide the placer for iterative improvements, while the clock-network synthesizer makes use of updated latch locations to optimize power and timing locally. Experimental results show that our framework can substantially minimize power consumption and improve timing slacks, compared to existing synthesis flows.

To accommodate the ever-growing pin number of complex PCB designs, the staggered pin array is introduced for modern designs with higher pin density. However, the escape routing for staggered pin arrays, which is a key component of PCB routing, is significantly different from that for grid arrays. This paper presents a routing algorithm for the escape routing for staggered-pin-array PCBs. We first analyze the properties of staggered pin arrays, and propose an orthogonal-side wiring style that fully utilizes the routing resource of the staggered pin array. An LP/ILP based algorithm is presented to solve the staggered-pin-array escape routing problem. Experimental results show that our approach successfully completed the routing for all testcases efficiently and effectively.

Due to the significant mismatch between existing wirelength models and the congestion objective in placement, considering routability during placement is particularly significant for modern circuit designs. In this paper, a novel routability-driven analytical placement algorithm for large-scale mixed-size circuit designs is proposed. Unlike most existing works which usually optimize routability by reallocating whitespace or net-based congestion removal, the proposed algorithm optimizes routability from three major aspects: (1) Pin density: Most existing works optimize routability based on net distribution, while our work considers both the density of pins and their routing directions; (2) Routing overflow optimization: Unlike most previous works that use white space allocation or net-based congestion removal to improve routability, our work optimizes routing overflow by a novel sigmoid function during global placement; (3) Macro porosity consideration: A virtual macro expansion technique is applied to consider the constrained routing resource incurred by big macros. Routability-driven legalization and detailed placement are also proposed to further optimize routing congestion. Experimental results show the effectiveness and efficiency of our proposed algorithm. Compared with the participating teams for the 2011 ACM ISPD Routability-Driven Placement Contest, our algorithm achieves the best average overflow and routed wirelength.

Modern circuit placement, especially analog placement, often needs to consider various constraints, such as symmetry, proximity, preplaced, variant, fixed-boundary, minimum separation, boundary, and fixed-outline constraints, for better electrical effects and higher performance. To handle these diverse constraints, topological floorplan representations are pervasively used because of their higher flexibility and smaller solution space. Due to their intrinsic limitation in deriving module adjacency information directly from the representations themselves, however, they might incur difficulties in handling related constraints. In this paper, we work on B*-trees, which have been shown to be most effective and efficient for floor-plan/placement problems, and present a corner stitching compliant B*-tree (CB-tree, for short) to remedy the significant deficiency in its module adjacency handling. A CB-tree is a B*-tree integrated with modified corner stitching to offer much higher flexibility/efficiency, especially for adjacent module identification/packing. Compared with the previous works, CB-trees can achieve the lowest time complexity for module packing with the aforementioned constraints. Experimental results show that the CB-trees achieve the best solution quality and consume the least running time for industrial designs with various constraints. In particular, our work provides key insights into the handling of comprehensive placement constraints with a topological representation.

Utilizing pulsed-latches in circuit designs is one emerging solution to timing improvements. Pulsed-latches, driven by a brief clock signal generated from pulse generators, possess superior design parameters over flip-flops. If the pulse generator and pulsed-latches are not placed properly, however, pulse-width degradations at pulsed-latches and thus timing violations might occur. In this paper, we present a unified placement framework for pulsed-latches to maintain the timing integrity. Our new placer has the following distinguished features: 1) a multilevel analytical placement framework to effectively prevent the potential pulse-width distortion problem; 2) a physical-location aware pulse-generator insertion algorithm to identify each desired group of a pulse generator and latches; and 3) a new optimization gradient for global placement to consider the impact of load capacitance of generators. Experimental results show that our placement flow can effectively consider pulse-width integrity and thus achieve much smaller total/worst negative slacks with marginal wirelength overheads, compared to a leading commercial and an academic placement flows.

Excessive supply voltage drops in a circuit may lead to significant circuit performance degradation and even malfunction. To handle this problem, existing power delivery aware placement algorithms model voltage drops as an optimization objective. We observe that directly minimizing the voltage drops in the objective function might not resolve voltage-drop violations effectively and might cause problems in power-integrity convergence. To remedy this deficiency, in this paper, we propose new techniques to incorporate device power spreading forces into a mixed-size analytical placement framework. Unlike the state-of-the-art previous work that handles the worst voltage-drop spots one by one, our approach simultaneously and globally spreads all the blocks with voltage-drop violations to desired locations directly to minimize the violations. To apply the power force, we model macro current density and power rails for our placement framework to derive desired macro/cell locations. To further improve the solution quality, we propose an efficient mathematical transformation to adjust the power force direction and magnitude. Experimental results show that our approach can substantially improve the voltage drops, wirelength, and runtime over the previous work.

Double patterning technology (DPT) and layout migration (LM) are two closely related problems on design for manufacturability in the nanometer era. DPT decomposes a layout into two masks and applies double exposure patterning to increase pitch size and, thus, printability. In this paper, we present the first algorithm in the literature for the simultaneous layout migration and decomposition (SMD) problem. Our algorithm first constructs a potential conflict graph and DPT-aware constraint graphs, and then applies integer linear programming (ILP) corresponding to the graphs to obtain a decomposed and migrated layout. We further present an effective graph-based reduction technique to prune the ILP solution space, which maintains the same DPT conflicts. We also present a new DPT-aware objective for the SMD problem to minimize the difference between the original and migrated layouts while considering the DPT effects. In addition, we present an approach to generate DPT-aware standard cells by considering the DPT effects on the cell boundaries; this technique improves the layout printability and facilitates electronic design automation tools to consider DPT. Experimental results show that our algorithms can effectively generate conflict-free migrated layouts with 11% smaller layout areas and 21% smaller layout changes, compared with the traditional method of layout decomposition followed by LM. In particular, our reduction technique reduces the ILP variables by 45.7%, the ILP constraints by 58.5%, and the DPT edges by 79.9% over the basic ILP formulation, leading to a substantial speedup. For example, it can reduce the runtimes for the test cases from more than one day to only seconds.

Digital microfluidic biochips have emerged as a popular alternative for laboratory experiments. Pin-count reduction and cross-contamination avoidance are key design considerations for practical applications with different droplets being transported and manipulated on highly integrated biochips. This paper presents the first design automation flow that considers the cross-contamination problems on pin-constrained biochips. The factors that make the problems harder on pin-constrained biochips are explored. To cope with these cross contaminations, this paper proposes: 1) early crossing minimization algorithms during placement, and 2) systematic wash droplet scheduling and routing that require only one extra control pin and zero assay completion time overhead for practical bioassays. Experimental results show the effectiveness and scalability of our algorithms for practical bioassays.

With the thermal effect, improper analog placements may degrade circuit performance because the thermal impact from power devices can affect electrical characteristics of the thermally-sensitive devices. There is not much previous work that considers the desired placement configuration between power and thermally-sensitive devices for a better thermal profile to reduce the thermally-induced mismatches. This paper first introduces the properties of a desired thermal profile for better thermal matching of the matched devices. It then presents a thermal-driven analog placement methodology to achieve the desired thermal profile and to consider the best device matching under the thermal profile while satisfying the symmetry and the common-centroid constraints. Experimental results based on real analog circuits show that the proposed approach can achieve the best analog circuit performance/accuracy with the least impact due to the thermal gradient, among existing works.

The six selected papers exemplify the broad scope of modern physical design (PD), covering system-level physical synthesis, layout optimization, analog circuit placement, beyond-die routing, biochip design automation, and emerging device performance optimization.

Three Dimensional Integrated Circuits (3D ICs) are currently being developed to improve existing 2D designs by providing smaller chip areas and higher performance and lower power consumption. However, before 3D ICs become a viable technology, the 3D design space needs to be fully explored and 3D EDA tools need to be developed. To help explore the 3D design space and help fill the need for 3D EDA tools, the 3D Floorplan and Power/Ground (P/G) Co-synthesis tool is developed in this work, which develops the floorplan and the P/G network concurrently. Most current 3D IC floorplanners neglect the effects of the 3D P/G network on the design, which may lead to large IR drops in the circuit. To create feasible floorplans with efficient P/G networks, the 3D Floorplan and P/G Co-synthesis tool optimizes the floorplan in terms of wirelength, area and P/G routing area and IR drops. The tool integrates a 3D B*-tree floorplan representation, a resistive P/G mesh, and a Simulated Annealing (SA) engine to explore the 3D floorplan and P/G network. The results of experiments using the 3D Floorplan and P/G Co-synthesis tool show that 3D ICs tend to increase the P/G routing area while decreasing the IR drops in the circuit. By considering the IR drop while floorplanning, exploring the 3D P/G design space, and evaluating 3D IC's effect on 3D P/G networks, the 3D Floorplan and P/G Co-synthesis tool can develop a more efficient 3D IC.

Due to the increasing IC design complexity, Engineering Change Orders (ECOs) have become a necessary technique to resolve late-found functional and/or timing deficiencies. To fix timing violations, the principles of gate sizing and buffer insertion are commonly used in post-mask ECO. These techniques however may not be powerful enough, especially when spare cells are inserted in a way of striking a balance between functional and timing repair capabilities. We propose a post-mask ECO technique, called TRECO, to remedy timing violations based on technology remapping, which supports functional ECO as well. Unlike conventional technology mapping, TRECO performs technology mapping with respect to a limited set of spare cells and confronts dynamic changes of wiring cost incurred by different spare-cell selections. With a pre-computed lookup table of representative circuit templates, TRECO iteratively performs technology remapping to restructure timing critical sub-circuits until no timing violation remains. Experimental results on five industrial designs show the effectiveness of TRECO in ECO timing optimization.

In high-performance nanometer synchronous chip design, a buffered clock tree with high tolerance of process variations is essential. The nominal clock skew always plays a crucial role in determining circuit performance and thus should be a first-order objective for clock-tree synthesis. The clock latency range (CLR), which is the latency difference under different supply voltages, is defined by the 2009 ACM ISPD Clock Network Synthesis Contest as the major optimization objective to measure the effects of process variation on clock-tree synthesis. In this paper, we propose a three-level framework which effectively constructs clock trees by performing blockage-avoiding buffer insertion with both nominal skew and CLR minimization. To cope with the objectives, we present a novel three-stage TTR clock-tree construction algorithm which consists of clock-tree Topology Generation, Tapping-Point Determination, and Routing. Experimental results show that our framework with the TTR algorithm achieves the best average quality for both nominal skew and CLR, compared to all the participating teams for the 2009 ISPD Clock Network Synthesis Contest.

Utilizing pulsed latches in a circuit is one emerging solution to timing improvements. Pulsed latches, driven by a brief clock signal generated from pulse generators, possess superior design parameters over flip-flops. If pulse generators and pulsed latches are not placed properly, however, pulse-width degradations at pulsed latches and thus timing violations might occur. In this paper, we introduce the pulsed-latch aware placement problem for timing integrity and present a unified placement framework to tackle this problem. Our new placer has the following distinguished features: (1) a multilevel pulsed-latch aware analytical placement framework to effectively prevent the potential pulse-width distortion problem, (2) a physical-information aware latch grouping algorithm to identify each desired group of a pulse generator and pulsed latches, and (3) a new optimization gradient for global placement to consider the impact of load capacitance of generators. Experimental results show that our placement flow can effectively consider pulse-width integrity and thus achieve much smaller total/worst negative slacks with marginal wirelength overheads, compared to a leading commercial and an academic placement flows.

Digital microfluidic biochips have emerged as a popular alternative for laboratory experiments. Pin-count reduction and cross-contamination avoidance are key design considerations for practical applications with different droplets being transported and manipulated on highly integrated biochips. We present in this paper the first design automation flow that considers the cross-contamination problems on pin-constrained biochips. We explore the factors that make the problems harder on pin-constrained biochips. To cope with these cross contaminations, we propose (1) early crossing minimization algorithms during placement, and (2) systematic wash droplet scheduling and routing that require only one extra control pin and zero assay completion time overhead for practical bioassays. Experimental results show the effectiveness and scalability of our algorithms for practical bioassays.

In high-performance synchronous chip design, a buffered clock tree with small clock skew is essential for improving clocking speed. Due to the insufficient accuracy of timing models for modern chip design, embedding simulation into a clock-tree synthesis flow becomes inevitable. Consequently, the runtime for clock-tree synthesis becomes prohibitively huge as the complexity of chip designs grows rapidly. To construct a buffered clock tree efficiently, we propose an ultra fast timing-model independent approach to perform skew minimization by structure optimization. To achieve the goal, a novel clock-tree structure, called symmetrical structure, is presented. At each level of a symmetrical clock tree, the number of branches, the wire-length, and the inserted buffers are almost the same. It is natural that the clock skew could be minimized if the configurations of all paths from the clock source to sinks are similar. By symmetrically constructing a clock tree, the clock skew can be minimized without referring to simulation information. Experimental results show that our approach can not only efficiently construct a buffered clock tree, but also effectively minimize clock skew with marginal wiring overheads. Based on a set of commonly used IBM benchmarks, for example, a state-of-the-art work without (with) ngspice simulation results in averagely 7.93X (2.77X) clock skew and requires 46X (24343X) runtime over our approach.

The double patterning technology (DPT), in which a dense layout pattern is decomposed into two separate masks to relax its pitch, is the most popular lithography solution for the sub-22nm node to enhance pattern printability. Previous works focus on stitch insertion to improve the decomposition success rate. However, there exist native conflicts (NC's) which cannot be resolved by any kind of stitch insertion. A design with NC's is not DPT-compliance and will eventually fail the decomposition, resulting in DFM redesign and longer design cycles. In this paper, we give a sufficient condition for the NC existence and propose a geometry-based method for NC prediction to develop an early stage analyzer for DPT decomposability checking. Then, a wire perturbation algorithm is presented to fix as many NC's in the layout as possible. The algorithm is based on iterative 1D-compaction and can easily be embedded into existing industrial compaction systems. Experimental results show that the proposed algorithm can significantly reduce the number of NC's by an average of 85%, which can effectively increase the decomposition success rate for the next stage.

Routability is a mandatory metric for modern large-scale mixed-size circuit placement which typically needs to handle hundreds of large macros and millions of small standard cells. However, most existing academic mixed-size placers either focus on wirelength minimization alone, or do not consider the impact of movable macros on routing. To remedy these insufficiencies, this paper formulates design-hierarchy information as a novel fence force in an analytical placement framework. Unlike a state-of-the-art routability-driven placer that simply removes net bounding boxes during placement, this paper utilizes two different optimization forces, the global fence force and the local spreading force, to determine the positions of both standard cells and macros. We utilize design-hierarchy information to determine block distributions globally, and locally we add additional spreading forces to preserve sufficient free space among blocks by a net-topology estimation. With the interactions between these two forces, our placer can well balance routability and wirelength. Experimental results show that our placer can achieve the best routability and routing time among all published works.

Spare cells are often used in engineering change order (ECO) timing optimization. By applying spare-cell rewiring techniques, timing-violated paths in a design can be fixed. In addition, mask re-spin cost economization has become a critical challenge for modern IC design, and it can be achieved by reducing the number of layers used to rewire spare cells. This paper presents the first work for the problem of ECO timing optimization considering redundant wires (unused wires or dummy metals) to minimize the number of rewiring layers. We first propose a multi-commodity flow model for the spare-cell selection problem and apply integer linear programming (ILP) to simultaneously optimize all timing-violated paths. The ILP formulation minimizes the number of used spare cells and considers the routability of the selected spare cells. Then, we develop a tile-based ECO router which minimizes the number of rewiring layers by reusing redundant wires. Experimental results based on five industry benchmarks show that our algorithm not only effectively resolves timing violations but also reduces the number of rewiring layers under reasonable runtime.

A modern chip often contains large numbers of pre-designed macros (e.g., embedded memories, IP blocks) and standard cells, with very different sizes. The fast-growing design complexity with large-scale mixed-size macros and standard cells has caused significant challenges to modern circuit placement. Analytical algorithms have been shown to be most effective for standard-cell placement, but the problems with the rotation and legalization of large macros impose intrinsic limitations for analytical placement. Consequently, most recent works on mixed-size placement resort to combinatorial macro placement. Instead, this paper presents the first attempt to resolve the intrinsic problems with a unified analytical approach. Unlike traditional analytical placement that uses only wire and density forces to optimize the positions of circuit components, we present a new force, the rotation force, to handle macro orientation for analytical mixed-size placement. The rotation force tries to rotate each macro to its desired orientation based on the wire connections on this macro. A cross potential model is also proposed to increase the rotation freedom during placement. The final orientation of each macro with legalization consideration is then determined by mathematical programming at the end of global placement. Experimental results show the effectiveness and efficiency of our approach. Compared with state-of-the-art mixed-size placement approaches (such as FLOP, CG, and MP-tree), our approach achieves the best average wirelength efficiently.

Double patterning technology (DPT) has recently gained much attention and is viewed as the most promising solution for the sub-32-nm node process. DPT decomposes a layout into two masks and applies double exposure patterning to increase the pitch size and thus printability. This paper proposes the first mask-sharing methodology for DPT, which can share masks among different designs, to reduce the number of costly masks for double patterning. The design methodology consists of two tasks: template-mask design and template-mask-aware routing. A graph matching-based algorithm is developed to design a flexible template mask that tries to accommodate as many design patterns as possible. We also present a template-mask-aware routing (TMR) algorithm, focusing on DPT-related issues to generate routing solutions that satisfy the constraints induced from double patterning and template masks. Experimental results show that our designed template mask is mask-saving, and our TMR can achieve conflict-free routing with 100% routability and save at least two masks for each circuit with reasonable wirelength and runtime overheads.

The flip-chip package is introduced for modern IC designs with higher integration density, larger I/O counts, faster speed, better signal integrity, etc. To ease design changes, an extra metal layer is introduced to redistribute nets between wire-bonding (I/O) pads in a die and bump pads in a package carrier. Flipchip routing is performed by redistributing and interconnecting nets between the I/O and bump pads. As the design complexity grows, routing has played a pivotal role in flip-chip design. In this paper, we first introduce popular flip-chip structures, their routing-region modeling, and induced routing problems, survey key published techniques for flip-chip routing with respect to specific structures and pad assignment methods, and provide some future research directions for the modern flip-chip routing problem.

For high-performance chip designs, a clock network with high tolerance towards process-variation is essential for chip synchronization. Clock mesh structure are widely used in these designs because of its resistant to variations. However, traditional mesh structures suffer from several drawbacks such as difficulty in timing estimation, inability to handle obstacles, and high power consumption. This paper proposes a new obstacle-avoiding clock mesh synthesis method which applies a two-stage approach of mesh construction followed by driving-tree synthesis. The method achieves very low skew through structural optimization, thus eliminating the need of direct timing estimation and/or SPICE simulation during clock network synthesis. In addition, our approach handles obstacles with the structural consideration, and reduces power consumption by removing non-critical mesh components and optimizing the driving-tree structure. Based on the benchmarks of the ISPD'10 Clock Network Synthesis Contest, the top contest performers result in 1.32X skew over our approach by using mesh structure, and more than 2.0X skew over our approach by using tree structure. Our approach runs 8326X/11421X faster than teams that used simulation, and 67X/90X times faster than teams that did not use simulation.

Optical Proximity Correction (OPC) is the most popular technique to handle design shape distortions arising from subwavelength lithography. Existing OPC models are typically very computationally expensive and thus not efficient to be incorporated for layout optimization. In this paper, we present an efficient, yet sufficiently accurate OPC cost model which can predict the optimal location of a wire segment for OPC optimization and give an upper bound of the interference amount, guaranteeing that the interference amount is never underestimated. Based on this cost model, we propose an OPC-aware wire perturbation algorithm for post-layout interconnect optimization. We show that the effects of wire perturbation have the concavity or monotonicity property which can dramatically reduce the search space for finding the optimal location of each wire for OPC optimization. Further, we can incrementally update the OPC cost of a wire by recomputing only the affected wires because of the property of superposition of our model. Experimental results show that our algorithm can efficiently obtain much better OPC results than a state-of-the-art OPC-friendly router, based on a leading commercial OPC tool.

In the nanometer IC design, dummy fill is often performed to improve layout pattern uniformity and the post-CMP quality. However, filling dummies might greatly increase interconnect coupling capacitance and thus circuit delay, and might also lead to explosion of mask data due to the extra layout patterns. Traditional dummy-fill algorithms try to make each tile (window) density satisfy foundry's density upper and lower bounds under the coupling constraint. As technology advances, however, it is not sufficient to just keep the pattern density variation of each layer within density bounds. The density gradient, besides the density variation, plays a pivotal role in determining the post-CMP thickness of modern circuit designs. In this paper, we present the first gradient-driven dummy-fill algorithm to address the density gradient and other classical objectives (such as density variation, coupling constraints, dummy count) as well. Our dummy-fill algorithm has the two distinguished features: (1) Gaussian smoothing based gradient-driven multilevel dummy density analysis to minimize density gradient level by level, and (2) ILP-based fill synthesis to insert the fewest dummies within the coupling-violation-free feasible regions while satisfying the density constraints. Experimental results show that our algorithm can achieve promising results by inserting minimal dummies to reduce the density gradient and variation under the coupling constraints with a reasonable runtime overhead.

Due to the subwavelength lithography, manufacturing sub-90-nm feature sizes require intensive use of resolution-enhancement techniques, among which optical proximity correction (OPC) is the most popular technique in industry. Considering the OPC effects during routing can significantly alleviate the cost of postlayout OPC operations. In this paper, we present an efficient, accurate, and economical analytical formula for intensity computation and develop the first modeling of postlayout OPC based on a quasi-inverse lithography technique. The technique provides key insights into a new direction for postlayout OPC modeling during routing. Extensive simulations with SPLAT, the golden lithography simulator in academia and industry, show that our intensity formula has high fidelity. Incorporating the OPC costs computed by the quasi-inverse lithography technique for our postlayout OPC modeling into a router, the router can be guided to maximize the effects of the correction. Compared with a rule-based OPC method, the experimental results show that our approach can achieve 15% and 16% reductions in the maximum and average layout distortions, respectively.

The area-input/output (I/O) flip-chip package provides a high chip-density solution to the demand of more I/Os in very large scale integration designs; it can achieve smaller package size, shorter wirelength, and better signal and power integrity. In this paper, we introduce the routing problem for chip and package co-design and present thefirstwork in the literature to handle the multiple re-distribution layer (RDL) routing problem (without RDL vias) for flip-chip designs, considering pin and layer assignment, signal integrity, signal-skew and total wirelength minimization, and chip-package co-design. Our router adopts a two-stage technique of global routing followed by RDL routing. The global routing assigns each block port to a unique bump pad via an I/O pad and decides the RDL routing among I/O pads and bump pads. Based on the minimum-cost maximum-flow algorithm, we can guarantee 100% RDL routing completion after the assignment and the optimal solution with the minimum wirelength. The RDL routing efficiently distributes the routing points between two adjacent bump pads and then generates a 100% routable sequence to complete the routing. Experimental results based on 12 industry designs demonstrate that our router can achieve 100% routability and the optimal routing wirelength under reasonable central processing unit times, while related works cannot.

We introduce in this paper a new problem of post-mask engineering change order (ECO) timing optimization using spare-cell rewiring and present a two-phase framework for this problem. Spare-cell rewiring is a popular technique for incremental timing optimization and/or functional change after the placement stage. The spare-cell rewiring problem is very challenging because of its dynamic wiring cost nature for selecting a spare cell, while the existing related problems consider only static wiring cost: once a standard cell is placed, its physical location is fixed and so is its wiring cost. For the spare-cell rewiring problem, each rewiring could make some spare cells become ordinary standard cells and some standard cells become new spare cells simultaneously. As a result, the wiring cost becomes dynamic and further complicates the optimization process. For the addressed problem, we present a two-phase framework of 1) buffer insertion and gate sizing followed by 2) technology remapping. For Phase 1, we present a dynamic programming algorithm considering the dynamic cost, called dynamic cost programming, for the ECO timing optimization with spare cells. Without loss of solution optimality, we further present an effective pruning method by selecting spare cells only inside an essential bounding polygon to reduce the solution space. For those ECO timing paths that cannot be fixed during Phase 1, we apply technology remapping on the spare cells to restructure the circuit to fix the timing violations. The whole framework is integrated into a commercial design flow. Experimental results based on five industry benchmarks show that our method is very effective and efficient in fixing the timing violations of ECO paths.

Global routing for modern large-scale circuit designs has attracted much attention in the recent literature. Most of the state-of-the-art academic global routers just work on a simplified routing congestion model that ignores the essential via capacity for routing through multiple metal layers. Such a simplified model would easily cause fatal routability problems in subsequent detailed routing. To remedy this deficiency, a more effective congestion metric that considers both the in-tile nets and the residual via capacity for global routing is presented. Experimental results show that our global router can achieve very high-quality routing solutions with more reasonable via usage.

Digital microfluidic biochips have emerged as a popular alternative for laboratory experiments. To make the biochip feasible for practical applications, pin-count reduction is a key problem to higher-level integration of reactions on a biochip. Most previous works approach the problem by post-processing the placement and routing solutions to share compatible control signals; however, the quality of such sharing algorithms is inevitably limited by the placement and routing solutions. We present in this paper a comprehensive pin-constrained biochip design flow that addresses the pin-count issue at all design stages. The proposed flow consists of three major stages: 1) pin-count aware stage assignment that partitions the reactions in the given bioassay into execution stages; 2) pin-count aware device assignment that determines a specific device used for each reaction; and 3) guided placement, routing, and pin assignment that utilize the pin-count saving properties from the stage and device assignments to optimize the assay time and pin-count. For both the stage and device assignments, basic integer linear programming formulations and effective solution-space reduction schemes are proposed to minimize the assay time and pin-count. Experimental results show the efficiency of our methods and a 55-57% pin-count reduction over the state-of-the-art algorithms/flow.

Global routing is an important step for physical design. In this paper, we develop a new global router, NTUgr, that contains three major steps: prerouting, initial routing, and enhanced iterative negotiation-based rip-up/rerouting (INR). The prerouting employs a two-stage technique of congestion-hotspot historical cost pre-increment followed by small bounding-box area routing. The initial routing is based on efficient iterative monotonic routing. For traditional INR, it has evolved as the main stream for the state-of-the-art global routers, which reveals its great ability to reduce the congestion and overflow. As pointed out by recent works, however, traditional INR may get stuck at local optima as the number of iterations increases. To remedy this deficiency, we replace INR by enhanced iterative forbidden-region rip-up/rerouting (IFR) which features three new techniques of (1) multiple forbidden regions expansion, (2) critical subnet rerouting selection, and (3) look-ahead historical cost increment. Experimental results show that NTUgr achieves high-quality results for the ISPD'07 and ISPD'08 benchmarks for both overflow and runtime.

In this paper, we present a novel flip-chip routing algorithm for package-board co-design. Unlike the previous works that can consider only either free- or pre-assignment routing, our router is the first work in the literature that can handle both the free-and pre-assignment routing. Based on the computational geometry techniques (e.g., the Delaunay triangulation and the Voronoi diagram), the router applies a unified network-flow formulation to perform congestion estimation for the pre-assignment routing. According to the congestion map, the network-flow formulation can also consider the free-assignment nets during the routing for the pre-assignment ones. Then, the router modifies the network-flow formulation to optimally assign and route the free-assignment nets, considering the routed pre-assignment nets. With the package and board co-design flow, we can achieve 100% routing completion. Experimental results based on industry designs demonstrate the high-quality of our algorithm.

Post-silicon validation has recently drawn designers' attention due to its increasing impacts on the VLSI design cycle and cost. One key feature of the post-silicon validation is the use of spare cells. In the literature, most existing works focus on developing new delicate spare cell structures. On the other hand, the placement of spare cells has a crucial impact on the design cycle and cost of the post-silicon debugging; however, there exists not much work on this placement problem. In this paper, we propose the first spare-cell-aware analytical placement framework which predicts the spare cell requirement and considers spare cell insertion during global placement. We also propose a multilevel spare cell insertion technique which provides a more efficient spare cell planning and a better control of quality impact due to spare cell insertion. To guide the selection of available spare cell positions during insertion, we propose a mixed-integer-linear-programming formulation to determine the optimal spare cell positions. Experimental results show that our algorithm can averagely achieve 17--33% and 1.77--2.61X better quality of spare cell insertion than that of the existing spare cell insertion algorithms, UniSpare [10] and PostSpare [22, 26], on the tested real designs with 1--5% spare cell insertion rates.

Digital microfluidic biochips have emerged as a popular alternative for laboratory experiments. To make the biochip feasible for practical applications, pin-count reduction is a key problem to higher-level integration of reactions on a biochip. Most previous works approach the problem by post-processing the placement and routing solutions to share compatible control signals; however, the quality of such sharing algorithms is inevitably limited by the placement and routing solutions. We present in this paper a comprehensive pin-constrained biochip design flow that addresses the pin-count issue at all design stages. The proposed flow consists of three major stages: (1) pin-count aware stage assignment that partitions the reactions in the given bioassay into execution stages, (2) pin-count aware device assignment that determines a specific device used for each reaction, and (3) guided placement, routing, and pin assignment that utilize the pin-count saving properties from the stage and device assignments to optimize the assay time and pin count. For both the stage and device assignments, exact ILP formulations and effective solution-space reduction schemes are proposed to minimize the assay time and pin count. Experimental results show the efficiency of our algorithms/flow and a 55--57% pin-count reduction over the state-of-the-art algorithms/flow.

With the thermal effect, improper analog placements may degrade circuit performance because the thermal impact from power devices can affect electrical characteristics of the thermally-sensitive devices. There is not much previous work that considers the desired placement configuration between power and thermally-sensitive devices for a better thermal profile to reduce the thermally-induced mismatches. In this paper, we first introduce the properties of a desired thermal profile for better thermal matching of the matched devices. We then propose a thermal-driven analog placement methodology to achieve the desired thermal profile and to consider the best device matching under the thermal profile while satisfying the symmetry and the common-centroid constraints. Experimental results based on real analog circuits show that our approach can achieve the best analog circuit performance/accuracy with the least impact due to the thermal gradient, among existing works.

Built-in Self Test (BIST) is a crucial technique for testing embedded memory cores in a System-on-Chip (SoC). However, there is not much published work on BIST design optimization for multiple memory cores in the SoC designs. In this paper, we present a method for the BIST design optimization problem for large-scale SoC embedded memory cores, considering various real-world constraints such as peak current, IR drop, etc. Our method is based on a three-stage technique: (1) assignment, (2) legalization, and (3) refinement. The first stage adopts an integer linear programming (ILP) formulation for each memory partition to find a desired assignment of memory cores to controllers. The second stage then legalizes the assignment to meet user-specified assignment constraints. The last stage refines the solution to further reduce its cost. Experimental results show that our method can reduce the test time by 26.6%, the routing length by 8.9%, and the area by 24.1%, compared with a heuristic method currently used in industry.

Excessive supply voltage drops in a circuit may lead to significant circuit performance degradation and even malfunction. To handle this problem, existing power delivery aware placement algorithms model voltage drops as an optimization objective. We observe that directly minimizing voltage drops in an objective function might not resolve voltage-drop violations and might even cause problems in power-integrity convergence. To remedy this deficiency, in this paper, we propose new techniques to incorporate device power spreading forces into a mixed-size analytical placement framework. Unlike the state-of-the-art previous work that handles the worst voltage-drop spots one by one, our approach simultaneously and globally spreads all the blocks with voltage-drop violations to desired locations directly to minimize the violations. To apply the power force, we model macro current density and power rails for our placement framework to derive desired macro/cell locations. To further improve the solution quality, we propose an efficient mathematical transformation to adjust the power force direction and magnitude. Experimental results show that our approach can substantially improve the voltage drops, wirelength, and runtime over the previous work.

Double patterning technology (DPT) and layout migration are two closely related problems on design for manufacturability in the nanometer era. DPT decomposes a layout into two masks and applies double exposure patterning to increase the pitch size and thus printability. In this paper, we present the first algorithm in the literature for the simultaneous layout migration and decomposition (SMD) problem. Our algorithm first constructs a conflict graph and DPT-aware constraint graphs, and then applies integer linear programming (ILP) corresponding to the graphs to obtain a decomposed and migrated layout. We further present an effective graph-based reduction technique to prune the ILP solution space, which maintains the same DPT conflicts. We also present a new DPT-aware objective for the SMD problem to minimize the difference between the original and migrated layouts while considering the DPT effects. In addition, we present an approach to generate DPT-aware standard cells by considering the DPT effects on the cell boundaries; this technique improves the layout printability and facilitates EDA tools to consider DPT. Experimental results show that our algorithms can effectively generate conflict-free migrated layouts with 14% smaller layout areas and 28% smaller layout changes, compared with the traditional method of layout decomposition followed by layout migration. In particular, our reduction technique can reduce the runtimes for the test cases from more than one day for the basic ILP formulation to only seconds. can reduce the runtimes for the test cases from more than one day to only seconds.

The flip-chip package is introduced for modern IC designs with higher integration density and larger I/O counts. In this paper, we consider the pre-assignment flip-chip routing problem with predefined connections between driver pads and bump pads. This problem has been shown to be much more difficult than the free-assignment one, but is more popular in real-world designs because the connections between driver pads and bump pads are typically pre-determined by IC or packaging designers. Based on the concept of routing sequence exchange, we propose a very efficient global routing algorithm by computing the weighted longest common subsequence (WLCS) and the maximum planar subset of chords (MPSC) for pre-assignment flip-chips. We observe that the existing work over constrains the capacity of a routing tile, which might miss some critical solution space with a better routing solution (e.g., smaller wirelength), and provide a remedy for this insufficiency to identify a better solution in a more complete solution space. We also develop a constant-time routability analyzer to check if a given set of wires can pass through a tile. Experimental results show that our router can achieve a 122X speedup with even better solution quality (same routability with slightly smaller wire-length), compared with a state-of-the-art flip-chip router based on integer linear programming (ILP).

The multiple-supply voltage (MSV) design style has been extensively applied to mitigate dynamic-power consumption. The MSV design paradigm, however, brings many crucial challenges, especially in the power-ring synthesis. Unlike the previous works that form the power rings as the enclosing bounding boxes of voltage islands, we enable power rings alignment to the outer boundaries of voltage islands. With this new formulation, the power-ring estimation becomes more accurate during floorplanning, and the power-ring synthesis is more practical after floorplanning. In this paper, we first propose a linear-time voltage-island power-ring search algorithm to identify the power rings of voltage islands and then present a linear-time optimal power-ring corner-patching algorithm to minimize the number of corners in the power rings by using post-floorplanning whitespaces. Experimental results first demonstrate that reducing corners in power rings significantly mitigates IR drop, and then show that the proposed algorithm can reduce the number of corners by 33% on average for the GSRC floorplan benchmarks. In particular, the total running time for the 16 GSRC benchmarks is less than one second on an AMD-64 machine with a 2.2 GHz CPU and 8 GB memory.

As nanometer technology advances, the post chemical-mechanical polishing (CMP) topography variation control becomes crucial for manufacturing closure. To improve the CMP quality, dummy-feature filling is typically performed by foundries after the routing stage. However, filling dummy features may greatly degrade the interconnect performance and significantly increase the input data in the following time-consuming reticle enhancement techniques. It is, thus, desirable to consider wire-density uniformity during routing to minimize the side effects from aggressive post-layout dummy filling. In this paper, we present a new full-chip grid-based routing system considering wire density for reticle planarization enhancement. To fully consider a wire distribution, the router applies a novel two-pass top-down planarity-driven routing framework, which employs new density critical area analysis based on Voronoi diagrams and incorporates an intermediate stage of a density-driven layer/track assignment based on incremental Delaunay triangulation. Experimental results show that our methods can achieve a more balanced wire distribution than state-of-the-art works.

The flip-chip package provides a high chip-density solution to the demand for more input-output pads of very large scale integration designs. In this paper, we present the first routing algorithm in the literature for the preassignment flip-chip routing problem with a predefined netlist among pads and wire-width and signal-skew considerations. Our algorithm is based on integer linear programming (ILP) and guarantees to find an optimal solution for the addressed problem. It adopts a two-stage technique of global routing followed by detailed routing. In global routing, it first uses three reduction techniques to prune redundant solutions and create a global-routing path for each net. Without loss of the solution optimality, our reduction techniques can further prune the ILP variables (constraints) by 85.5% (98.0%) on average over a recent reduction technique. The detailed routing applies passing-point assignment, net-ordering determination, and X-based gridless routing to complete the routing. Experimental results based on five real industry designs show that our router can achieve 100% routability and the optimal global-routing wirelength, and satisfy all signal-skew constraints, under reasonable central-processing-unit times, whereas recent related work has resulted in much inferior solution quality.

Power consumption is a crucial concern in nanometer chip design. Researchers have shown that multiple supply voltage (MSV) is an effective method for power consumption reduction. The underlying idea behind MSV is the tradeoff between power saving and performance. In this paper, we present an effective voltage-assignment technique based on dynamic programming. For circuits without reconvergent fan-outs, an optimal solution for the voltage assignment is guaranteed; for circuits with reconvergent fan-outs, a near-optimal solution is obtained. We then generate a level shifter for each net that connects two blocks in different voltage domains and perform power-network-aware floorplanning for the MSV design. Experimental results show that our floorplanner is very effective in optimizing power consumption under timing constraints.

To reduce the effect of parasitic mismatches and circuit sensitivity to thermal gradients or process variations for analog circuits, some pairs of modules need to be placed symmetrically with respect to a common axis, and the symmetric modules are preferred to be placed at closest proximity for better electrical properties. Most previous works handle the problem with symmetry constraints by imposing symmetric-feasible conditions in floorplan representations and using cost functions to minimize the distance between symmetric modules. Such approaches are inefficient due to the large search space and cannot guarantee the closest proximity of symmetry modules. In this paper, we present the first linear-time-packing algorithm for the placement with symmetry constraints using the topological floorplan representations. We first introduce the concept of a symmetry island which is formed by modules of the same symmetry group in a single connected placement. Based on this concept and the B*-tree representation, we propose automatically symmetric-feasible (ASF) B*-trees to directly model the placement of a symmetry island. We then present hierarchical B*-trees (HB*-trees) which can simultaneously optimize the placement with both symmetry islands and nonsymmetric modules. Unlike the previous works, our approach can place the symmetry modules in a symmetry group in close proximity and significantly reduce the search space based on the symmetry-island formulation. In particular, the packing time for an ASF-B*-tree or an HB*-tree is the same as that for a plain B*-tree (only linear) and much faster than previous works. Experimental results show that our approach achieves the best-published quality and runtime efficiency for analog placement.

Due to recent advances in microfluidics technology, digital microfluidic biochips and their associated computer-aided-design problems have gained much attention, most of which has been devoted to direct-addressing biochips. In this paper, we solve the droplet routing problem under the more scalable cross-referencing biochip paradigm. We propose the first droplet routing algorithm that directly solves the problem of routing. We first present an optimal basic integer-linear-programming (ILP) formulation. Due to its complexity, we also propose a progressive-ILP scheme to determine the locations of droplets at each time step. Simulation results demonstrate the efficiency and effectiveness of our algorithm.

Improving logic capacity by time-sharing, dynamically reconfigurable FPGAs are employed to handle designs of high complexity and functionality. In this article, we model each task as a 3D-box and deal with the temporal floorplanning/placement problem for dynamically reconfigurable FPGA architectures. We present a tree-based data structure, called T-trees , to represent the spatial and temporal relations among tasks. Each node in a T-tree has at most three children which represent the dimensional relationship among tasks. For the T-tree, we develop an efficient packing method and derive the condition to ensure the satisfaction of precedence constraints which model the temporal ordering among tasks induced by the execution of dynamically reconfigurable FPGAs. Experimental results show that our tree-based formulation can obtain significantly better solution quality with less execution time than the most recent state-of-the-art work.

Due to the sub-wavelength lithography, manufacturing sub-90 nm feature sizes require intensive use of resolution-enhancement techniques, among which optical proximity correction (OPC) is the most popular technique in industry. Considering the OPC effects during routing can significantly alleviate the cost of post-layout OPC operations. In this paper, we present an efficient, accurate, and economical analytical formula for intensity computation and develop the first modeling of post-layout OPC based on a quasi-inverse lithography technique. Extensive simulations with SPLAT, the golden lithography simulator in academia and industry, show that our intensity formula has high fidelity. Incorporating the OPC costs computed by the quasi-inverse lithography technique for our post-layout OPC modeling into a router, the router can be guided to maximize the effects of the correction. Compared with a rule-based OPC method, the experimental results show that our approach can achieve 14% and 16% reductions in the maximum and average layout distortions, respectively.

Routability is a challenging cost metric for modern large-scale mixed-size placement. Most existing routability-driven placement algorithms apply whitespace allocation to relieve the routing congestion. Nevertheless, we observe that whitespace allocation might worsen the routability of a placement. To remedy this deficiency, we propose in this paper a new direction/technique, called net overlapping removal, to optimize the routability during placement. Unlike most previous works that allocate whitespace among blocks, our approach moves nets apart from congested regions to improve the chip routability. To apply the net overlapping removal technique, we generalize a net bounding-box based congestion evaluation model to handle practical routing constraints and speed up the routability optimization during placement. We further propose a Gaussian smoothing technique to handle the challenging macro porosity issue, arising in modern mixed-size designs with large macros that require to preserve routing resources for inner routing of the macros. Experimental results show that our approaches lead to significantly better routability and running time than previous works for mixed-size placement.

Due to recent advances in microfluidics technology, digital microfluidic biochips and their associated CAD problems have gained much attention, most of which has been devoted to direct-addressing biochips. In this paper, we solve the droplet routing problem under the more scalable cross-referencing biochip paradigm, which uses row/column addressing scheme to activate electrodes. We propose the first droplet routing algorithm that directly solves the problem of routing in cross-referencing biochips. The main challenge of this type of biochips is the electrode interference which prevents simultaneous movement of multiple droplets. We first present a basic integer linear programming (ILP) formulation to optimally solve the droplet routing problem. Due to its complexity, we also propose a progressive ILP scheme to determine the locations of droplets at each time step. Experimental results demonstrate the efficiency and effectiveness of our progressive ILP scheme on a set of practical bioassays.

In this paper, we propose a constraint graph-based macro placement algorithm that removes macro overlaps and optimizes macro positions for modern mixed-size circuit designs. Improving over the constraint graph by working only on its essential edges without loss of the solution quality, our algorithm can search for high-quality macro placement solutions effectively and efficiently. Instead of packing macros along chip boundaries like most recent previous work, our placer can determine a non-compacted macro placement by linear programming and placement region cost evaluation and handle various placement constraints/objectives. Compared with various leading academic macro placers, our algorithm can consistently and significantly reduce the wirelengths for designs with different utilization rates, implying that our macro placer is robust and has very high quality.

The area-I/O flip-chip package provides a high chip-density solution to the demand of more I/O’s in VLSI designs; it can achieve smaller package size, shorter wirelength, and better signal and power integrity. In this paper, we introduce the routing problem for chip and package co-design and present the first work in the literature to handle the multiple Re-Distribution Layer (RDL) routing problem for flip-chip designs, considering pin and layer assignment, total wirelength minimization, and chip-package co-design. Our router adopts a two-stage technique of global routing followed by RDL routing. The global routing assigns each block port to a unique bump pad via an I/O pad and decides the RDL routing among I/O pads and bump pads. Based on the minimum-cost maximum-flow algorithm, we can guarantee 100% RDL routing completion after the assignment and the optimal solution with the minimum wirelength. The RDL routing efficiently distributes the routing points between two adjacent bump pads and then generates a 100% routable sequence to complete the routing. Experimental results based on 10 industry designs demonstrate that our router can achieve 100% routability and the optimal routing wirelength under reasonable CPU times, while related works cannot.

Nanometer effects have complicated the designs of chips as well as packages and printed circuit boards (PCB’s). In order to improve the performance, convergence, and signal integrity of the design, chip-package-board co-design is strongly recommended by industry. In this paper, we present the first routing algorithm in the literature for chip-package-board co-design with differential-pair considerations. Our algorithm is based on linear programming and integer linear programming and guarantees to find an optimal solution for the addressed problem. It first creates global-routing paths among chips, packages, and a PCB. Without loss of the solution optimality, our routing formulation can reduce the numbers of integer variables (constraints) by 95% (99%) on average. Then, any-angle routing is applied to complete the routing. Experimental results based on five real industry designs show that our router can achieve 100% routability and the optimal global-routing wirelength and satisfy all differential-pair constraints, under reasonable CPU times, whereas recent related work results in much inferior solution quality.

Global routing for modern large-scale circuit designs has attracted much attention in the recent literature. Most of the state-of-the-art academic global routers just work on a simplified routing congestion model that ignores the essential via capacity for routing through multiple metal layers. Such a simplified model would easily cause fatal routability problems in subsequent detailed routing. To remedy this deficiency, we present in this paper a more effective congestion metric that considers both the in-tile nets and the residual via capacity for global routing. With this congestion metric, we develop a new global router that features two novel routing algorithms for congestion optimization, namely least-flexibility-first routing and multi-source multi-sink escaping-point routing. The least-flexibility-first routing processes the nets with the least flexibility first, facilitating a quick prediction of congestion hot spots for the subsequent nets. Enjoying lower time complexity than traditional maze and A*-search routing, in particular, the linear-time escaping-point routing guarantees to find the optimal solution and achieves the theoretical lower-bound time complexity. Experimental results show that our global router can achieve very high-quality routing solutions with more reasonable via usage, which can benefit and correctly guide subsequent detailed routing.

In this paper, we propose the first metal-density driven placement algorithm to reduce CMP variation and achieve higher routability. Based on an analytical placement framework, we use a probabilistic routing model to estimate the wire density during the placement. Then, the metal density and thickness are predicted by a predictive CMP model. The spreading forces are adjusted according to the metal density map to reduce the metal density variation. Experimental results show that our method reduces the topography variation by 12% and the number of dummy fills by 6% and achieves much better routability, compared with wirelength-driven placement

In this paper, we derive the X-half-perimeter wirelength (XHPWL) model for X-architecture placement and explore the effects of three different wire models on X-architecture placement, including the Manhattan-half-perimeter wirelength (MHPWL) model, the XHPWL model, and the X-Steiner wirelength (XStWL) model. For min-cut partitioning placement, we apply the XHPWL and XStWL models to the generalized net-weighting method that can exactly model the wirelength after partitioning by net weighting. For analytical placement, we smooth the XHPWL function using log-sum-exp functions to facilitate analytical placement. This paper shows that both the XHPWL and XStWL models can reduce the X wirelength effectively. In particular, our results reveal the effectiveness of the X architecture on wirelength reduction during placement and, thus, the importance of the study on the X-placement algorithms, which is different from the results given in the work of Ono et al. which suggests that the X-architecture placement might not improve the X-routing wirelength over the Manhattan-architecture placement.

As the technology node advances into the nanometer era, via-open defects are one of the dominant failures due to the copper cladding process. To improve via yield and reliability, redundant-via insertion is a highly recommended technique proposed by foundries. Traditionally, double-via insertion is performed at the postlayout stage. The increasing design complexity, however, leaves very limited space for postlayout optimization. It is thus desirable to consider the double-via insertion at both the routing and postrouting stages. In this paper, we present a new full-chip gridless routing system considering double-via insertion for yield enhancement. To fully consider double vias, the router applies a novel two-pass, bottom-up routability-driven routing framework and features a new redundant-via aware detailed maze routing algorithm (which could be applied to both gridless and grid-based routing). We also propose a graph-matching based post-layout double-via insertion algorithm to achieve a higher insertion rate. In particular, the algorithm is optimal for grid-based routing with up to three routing layers and the stacked-via structure. Experiments show that our methods significantly improve the via count, number of dead vias, double-via insertion rates, and running times.

We present in this paper a new interconnect-driven multilevel floorplanner, called interconnect-driven multilevel-floorplanning framework (IMF), to handle large-scale building-module designs. Unlike the traditional multilevel framework that adopts the ldquoLambda-shapedrdquo framework (inaccurately called the ldquoV-cyclerdquo framework in the literature): bottom-up coarsening followed by top-down uncoarsening, the IMF, in contrast, works in the ldquoV-shapedrdquo manner: top-down uncoarsening (partitioning) followed by bottom-up coarsening (merging). The top-down partitioning stage iteratively partitions the floorplan region based on min-cut bipartitioning with exact net-weight modeling to reduce the number of global interconnections and, thus, the total wirelength. Then, the bottom-up merging stage iteratively applies fixed-outline floorplanning using simulated annealing for all regions and merges two neighboring regions recursively. Experimental results show that the IMF obtains the best published fixed-outline floorplanning results with the smallest average wirelength for the Microelectronics Center of North Carolina/Gigascale Systems Research Center benchmarks. In particular, IMF scales very well as the circuit size increases. The V-shaped multilevel framework outperforms the Lambda-shaped one in the optimization of global circuit effects, such as interconnection and crosstalk optimization, since the V-shaped framework considers the global configuration first and then processes down to local ones level by level, and thus, the global effects can be handled at earlier stages. The V-shaped multilevel framework is general and, thus, can be readily applied to other problems.

In this paper, we propose the first metal-density-driven (MDD) placement algorithm to reduce chemical-mechanical planarization/polishing (CMP) variation and achieve higher routability. To efficiently estimate metal density and thickness, we first apply a probabilistic routing model and then a predictive CMP model to obtain the metal-density map. Based on the metal-density map, we use an analytical placement framework to spread blocks to reduce metal-density variation. Experimental results based on BoxRouter and NTUgr show that our method can effectively reduce the CMP variation. By using our MDD placement, for example, the topography variation can be reduced by up to 38% (23%) and the number of dummy fills can be reduced by up to 14% (8%), compared with those using wirelength-driven (cell-density-driven) placement. The results of our MDD placement can also lead to better routability.

In addition to wirelength, modern placers need to consider various constraints such as preplaced blocks and density. We propose a high-quality analytical placement algorithm considering wirelength, preplaced blocks, and density based on the log-sum-exp wirelength model proposed by Naylor and the multilevel framework. To handle preplaced blocks, we use a two-stage smoothing technique, i.e., Gaussian smoothing followed by level smoothing, to facilitate block spreading during global placement (GP). The density is controlled by white-space reallocation using partitioning and cut-line shifting during GP and cell sliding during detailed placement. We further use the conjugate gradient method with dynamic step-size control to speed up the GP and macro shifting to find better macro positions. Experimental results show that our placer obtains very high-quality results.

In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placements with various constraints. Given a global placement that already considers the areas and the interconnections among standard cells and macros, our MP-tree-based macro placer optimizes macro positions, minimizes the macro displacement from the initial macro positions, and maximizes the area of the chip center for standard-cell placement and routing. Experiments based on the Proceedings of the 2006 International Symposium on Physical Design placement contest benchmarks and Faraday benchmarks show that our macro placer combined with APlace 2.0, Capo 10.2, mPL6, or NTUplace3 for a standard-cell placement outperforms these state-of-the-art academic mixed-size placers alone by large margins in robustness and quality. In addition to wirelength, experiments on four real industrial designs with large macros and high utilization rates show that our method significantly reduces the average half-perimeter wirelength by 35 %, the average routed wirelength by 55 %, and the routing overflows by 13 times compared with Capo 10.2, implying that our macro placer leads to much higher routability.

As technology enters the nanometer territory, the antenna effect plays an important role in determining the yield and reliability of a VLSI circuit. Diode and jumper insertions are the most effective techniques to fix the antenna effect. However, due to the increasing design complexity and the limited routing resource, applying diode or jumper insertion alone cannot achieve a high antenna fixing rate. In this paper, we give a polynomial-time antenna violation detection/fixing algorithm by simultaneous diode and jumper insertion with minimum cost, which is based on a minimum-cost network-flow formulation. Experimental results show that our algorithm consistently achieves much higher antenna fixing rates than the state-of-the-art jumper and diode insertion algorithms alone.

Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called the Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, antenna jumpers for reliability enhancement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Nevertheless, considering obstacles significantly increases the problem complexity, and thus, most previous works suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph, this paper presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction. Unlike previous heuristics, our algorithm guarantees to find an optimal OARSMT for any two-pin net and many higher pin nets. Extensive experiments show that our algorithm results in significantly shorter wirelengths than all state-of-the-art works.

Given a set of pins and a set of obstacles on routing layers, a multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) connects these pins by rectilinear edges within layers and vias between layers and avoids running through any obstacle to construct a Steiner tree with a minimal total cost. The ML-OARSMT problem is very important for many very large scale integration designs with pins being located in multiple routing layers that contain numerous routing obstacles incurred from IP blocks, power networks, prerouted nets, etc. As a fundamental problem with extensive practical applications to routing and wirelength/congestion/timing estimations in early design stages, it is desired to develop an effective algorithm for the ML-OARSMT problem to facilitate the design flow. However, there is no existing work on this ML-OARSMT problem. In this paper, we first formulate the ML-OARSMT problem with rectangular obstacles and then identify key different properties of this problem from its single-layer counterpart. Based on the multilayer obstacle-avoiding spanning graph, we present the first algorithm to solve the ML-OARSMT problem. Our algorithm can guarantee an optimal solution for any two-pin net and many multiple-pin nets. Experiments show that our algorithm results in 33% smaller total costs on average than a construction-by-correction heuristic which is widely used for Steiner-tree construction in the recent literature.

The electrostatic discharge (ESD) problem has become a challenging reliability issue in nanometer-circuit design. High voltages that resulted from ESD might cause high current densities in a small device and burn it out, so on-chip protection circuits for IC pads are required. To reduce the design cost, the protection circuit should be added only for the IC pads with an ESD current path, which causes the ESD current path analysis problem. In this paper, we first introduce the analysis problem for ESD protection in circuit design. We then model the circuit as a constraint graph, decompose the ESD connected components (ECCs) linked with the pads, and apply breadth-first search (BFS) to identify the ECCs in each constraint graph and, thus, the current paths. Experimental results show that our algorithm can very efficiently and economically detect all ESD paths. For example, our algorithm can detect all ESD paths in a circuit with more than 1.3 million vertices in 1.39 s and consume only 44-MB memory on a 3.0-GHz Intel Pentium 4 PC. To the best of our knowledge, our algorithm is thefirstpointtoolavailable to the public for the ESD analysis.

Due to recent advances in microfluidics, digital microfluidic biochips are expected to revolutionize laboratory procedures. One critical problem for biochip synthesis is the droplet routing problem. Unlike traditional very large scale integration routing problems, in addition to routing path selection, the biochip routing problem needs to address the issue of scheduling droplets under practical constraints imposed by the fluidic property and timing restriction of synthesis results. In this paper, we present the first network-flow-based routing algorithm that can concurrently route a set of noninterfering nets for the droplet routing problem on biochips. We adopt a two-stage technique of global routing followed by detailed routing. In global routing, we first identify a set of noninterfering nets and then adopt the network-flow approach to generate optimal global-routing paths for nets. In detailed routing, we present thefirstpolynomial-time algorithm for simultaneous routing and scheduling using the global-routing paths with a negotiation-based routing scheme. Our algorithm targets at both the minimization of cells used for routing for better fault tolerance and minimization of droplet transportation time for better reliability and faster bioassay execution. Experimental results show the robustness and efficiency of our algorithm.

As IC process geometries scale down to the nanometer territory, the industry faces severe challenges of manufacturing limitations. To guarantee yield and reliability, physical design for manufacturability and reliability has played a pivotal role in resolution and thus yield enhancement for the imperfect manufacturing process. In this paper, we introduce major challenges arising from nanometer process technology, survey key existing techniques for handling the challenges, and provide some future research directions in physical design for manufacturability and reliability.

In this paper, we present a new multi-packing tree (MP-tree) representation for macro placement to handle mixed-size designs. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placement with various constraints. Given a global placement, our MP-tree-based macro placer optimizes macro positions, minimizes the macro displacement from the initial macro positions, and maximizes the area of the chip center for standard-cell placement and routing. Experiments based on the eight ISPD'06 placement contest benchmarks show that our macro placer combined with Capo 10.2, NTUplace3, or mPL6 for standard-cell placement outperforms these state-of-the-art academic mixed-size placers alone by large margins in both robustness and quality. In addition to wirelength, experimented on five real industrial designs show that our method significantly reduce the average HPWL by 35%, the average routed wirelength by 55%, and the routing overflows than the counterpart with Capo 10.2, implying that our macro placer leads to much higher routability.

The flip-chip package provides a high chip-density solution to the demand for more I/O pads of VLSI designs. In this paper, we present the first routing algorithm in the literature for the pre-assignment flip-chip routing problem with a pre-defined netlist among pads and wire-width and signal-skew considerations. Our algorithm is based on integer linear programming (ILP) and guarantees to find an optimal solution for the addressed problem. It adopts a two-stage technique of global routing followed by detailed routing. In global routing, it first uses two reduction techniques to prune redundant solutions and create a global-routing path for each net. Without loss of the solution optimality, our reduction techniques can further prune the ILP variables (constraints) by 85.5% (98.0%) on average over a recent reduction technique. The detailed routing applies X-based grid-less routing to complete the routing. Experimental results based on five real industry designs show that our router can achieve 100% routability and the optimal global-routing wirelength and satisfy all signal-skew constraints, under reasonable CPU times, while recent related work results in much inferior solution quality.

Multiple supply voltages (MSV's) provide an effective technique for power optimization. This paper addresses a voltage partitioning problem arising in MSV design during high-level synthesis. We point out a theoretical mistake in a recent publication and prove that the partitioning problem is NP-hard. Despite its NP-hardness, we propose an efficient α2-approximation algorithm for the problem, where α is the constant ratio of the maximum to the minimum voltages. Compared with the previous work that runs in O(dn2) time, the time complexity of our algorithm is only O(dkn), where d, k, and n are respectively the numbers of voltages employed in the final designs (i.e., voltage domains), available supply voltages in the technology library, and functional units. Note that both d and k can be considered as small constants for practical applications. Experimental results show that our algorithm can achieve 36--255X run-time speedups than the recent work, with the same power reduction.

As nanometer technology advances, the post-CMP dielectric thickness variation control becomes crucial for manufacturing closure. To improve CMP quality, dummy feature filling is typically performed by foundries after the routing stage. However, tilling dummy features may greatly degrade the interconnect performance and lead to explosion of mask data. It is thus desirable to consider wire-density uniformity during routing to minimize the side effects from aggressive post-layout dummy filling. In this paper, we present a new full-chip grid-based routing system considering wire density for reticle planarization enhancement. To fully consider wire distribution, the router applies a novel two-pass, top-down planarity-driven routing framework, which employs a new density critical area analysis based on Voronoi diagrams and incorporates an intermediate stage of density-driven layer/track assignment based on incremental Delaunay triangulation. Experimental results show that our methods can achieve more balanced wire distribution than state-of-the-art works.

We introduce in this paper a new problem of ECO timing optimization using spare-cell rewiring and present the first work for this problem. Spare-cell rewiring is a popular technique for incremental timing optimization and/or functional change after the placement stage. The spare-cell rewiring problem is very challenging because of its dynamic wiring cost nature for selecting a spare cell, while the existing related problems consider only static wiring cost. For the addressed problem, we present a framework of buffer insertion and gate sizing to handle it. In this framework, we present a dynamic programming algorithm considering the dynamic cost, called dynamic cost programming (DCP), for the ECO timing optimization with spare cells. Without loss of solution optimality, we further present an effective pruning method by selecting spare cells only inside an essential bounding polygon to reduce the solution space. The whole framework is integrated into a commercial design flow. Experimental results based on five industry benchmarks show that our method is very effective and efficient in fixing the timing violations of ECO paths.

Power optimization is a crucial concern for modem circuit designs. Multiple supply voltages (MSV's) provide an effective technique for the power optimization. This paper addresses the voltage-island generation problem for MSV designs at the post-floorplanning stage. We first present a general formulation of this problem that considers level-shifter planning and power-network routing resources. Without loss of solution quality, we propose an economical graph-based representation that needs only a linear number of nodes to the block number to model the block adjacency in a floorplan for the voltage-island generation. In contrast, previous works need a quadratic number of nodes. To tackle the addressed problem, we employ an ILP formulation which consists of (1) level-shifter aware wirelength estimation to capture the timing overhead, (2) voltage-island-clustering inequalities to avoid complicated constraint transformations, and (3) inequalities to capture the power-network routing-resource usage. Compared with previous works, our algorithm can produce better voltage islands in terms of power-network routing resources. Experimental results show that our algorithm can effectively reduce the power-network routing resource by up to 19.46% with a reasonable overhead of 4.03% more power consumption and using reasonable running time.

Due to the technology scaling down, process variation has become a crucial challenge on both interconnect delay and reliability. To handle the process variation, statistical optimization has emerged as a popular technique for yield improvement. As a relatively new technique, second-order conic programming (SOCP) has recently attracted very much attention in the literature for statistical circuit optimization. However, we observe significant limitations of SOCP in its flexibility, accuracy, and scalability for statistical circuit optimization, especially when interconnects are considered. We thus present in this paper an effective and efficient alternative for multi-constrained statistical circuit optimization by both gate and wire sizing using Lagrangian relaxation (LR). Compared with SOCP, experimental results show that our LRbased algorithm can achieve much better solution quality by reducing 21% area and obtain 560X speed-up over SOCP.

Given a set of pins and a set of obstacles on routing layers, a multi-layer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) connects these pins by rectilinear edges within layers and vias between layers, and avoids running through any obstacle to construct a Steiner tree with a minimal total cost. The ML-OARSMT problem is very important for many VLSI designs with pins being located in multiple routing layers that contain numerous routing obstacles incurred from IP blocks, power networks, prerouted nets, etc. Therefore, it is desired to develop an effective algorithm for the ML-OARSMT problem. However, there is no existing work on this ML-OARSMT problem. In this paper, we first formulate the ML-OARSMT problem and identify key different properties of the problem from its single-layer counterpart. Based on the multilayer obstacle-avoiding spanning graph (ML-OASG), we present the first algorithm to solve the ML-OARSMT problem. Our algorithm can guarantee an optimal solution for any 2-pin net and many higher-pin nets. Experiments show that our algorithm results in 33% smaller total costs on average than a construction-by-correction heuristic which is widely used for Steiner-tree construction in the recent literature.

Due to the recent advances in microfluidics, digital microfluidic biochips are expected to revolutionize laboratory procedures. One critical problem for biochip synthesis is the droplet routing problem. Unlike traditional VLSI routing problems, in addition to routing path selection, the biochip routing problem needs to address the issue of scheduling droplets under the practical constraints imposed by the fluidic property and the timing restriction of the synthesis result. In this paper, we present the first network-flow based routing algorithm that can concurrently route a set of non-interfering nets for the droplet routing problem on biochips. We adopt a two-stage technique of global routing followed by detailed routing. In global routing, we first identify a set of non-interfering nets and then adopt the network-flow approach to generate optimal global-routing paths for the nets. In detailed routing, we present the first polynomialtime algorithm for simultaneous routing and scheduling using the global-routing paths with a negotiation-based routing scheme. The experimental results show the robustness and efficiency of our algorithm.

In this demonstration, the core processing engines of two video applications, 3D video and intelligent video surveillance, are demonstrated. The developed algorithms and its VLSI design results are shown with hardware prototypes processing input video on-the-fly. In addition to the processing engine design, the development tools for efficiently designing these chips are also demonstrated.

As technology continues to shrink, leakage power becomes animportant issue for modern FPGAs. In this paper, we address the leakage issue of partially dynamical reconfigurable FPGAs. We focus on eliminating leakage waste due to the delay between reconfiguration and task execution. We propose a post-placement leakage-aware scheduling algorithm that refines a placement generated by a performance-driven scheduler such that leakage waste is minimized and performance is not sacrificed. Experimental results on real and synthetic designs demonstrate the effectiveness and efficiency of our algorithm on leakage optimization.

In this paper, we derive the X-half-perimeter wirelength (XHPWL) model for X-architecture placement and explore the effects of three different wire models on X-architecture placement, including the Manhattan-half-perimeter wirelength (MHPWL) model, the XHPWL model, and the X-Steiner wirelength (XStWL) model. For min-cut partitioning placement, we propose a generalized net-weighting method that can exactly model the wirelength after partitioning by the net weight. The net-weighting method is general and can be incorporated into any wire models such as the XHPWL and XStWL models. For analytical placement, we smooth the XHPWL function using log-sum-exp functions to facilitate analytical placement. Our study shows that both the XHPWL model and the XStWL model can reduce the X wirelength. In particular, our results reveal the effectiveness of the X architecture on wirelength reduction during placement and thus the importance of the study on the Xplacement algorithms, which is different from the results given in the previous work that the X-architecture placement might not improve the X-routing wirelength over the Manhattan-architecture placement.

Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, antenna jumpers for reliability enhancement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Nevertheless, considering obstacles significantly increases the problem complexity, and thus most previous works suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph (OASG), this paper presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction. Unlike previous heuristics, our algorithm guarantees to find an optimal OARSMT for any 2-pin net and many higher-pin nets. Extensive experiments show that our algorithm results in significantly shorter wirelengths than all state-of-the-art works.

Droplet-based microfluidic biochips have recently gained much attention and are expected to revolutionize the biological laboratory procedures. As biochips are adopted for the complex procedures in molecular biology, its complexity is expected to increase due to the need of multiple and concurrent assays on a chip. In this article, we formulate the placement problem of digital microfluidic biochips with a tree-based topological representation, called T-tree . To the best knowledge of the authors, this is the first work that adopts a topological representation to solve the placement problem of digital microfluidic biochips. We also consider the defect tolerant issue to avoid to use defective cells due to fabrication. Experimental results demonstrate that our approach is more efficient and effective than the previous unified synthesis and placement framework.

To handle modern routing with nanometer effects, we need to consider designs with variable wire/via widths and spacings, for which gridless-routing approaches are desirable due to its great flexibility. In this paper, we introduce a gridless-routing model that can obtain design-rule-correct paths and avoid redundant wires. Besides, we propose an enhanced model for the gridless-routing model to reduce the solution space and the runtime. Based on the enhanced gridless-routing model, we present the first multilevel full-chip gridless detailed router (called MGR). The router integrates global routing, detailed routing, and congestion estimation together at each level of multilevel routing. It can handle designs with nonuniform wire/via widths and spacings and consider routability and optical-proximity correction. Experimental results show that MGR achieves the best routing solutions in smaller running times than previous works, based on a set of commonly used benchmarks (with uniform and nonuniform wire widths) and a set of real industrial benchmarks (with a versatile set of design rules)

The flip-chip package gives the highest chip density of any packaging method to support the pad-limited application-specific integrated circuit designs. In this paper, we propose the first router for the flip-chip package in the literature. The router can redistribute nets from wire-bonding pads to bump pads and then route each of them. The router adopts a two-stage technique of global routing followed by detailed routing. In global routing, we use the network flow algorithm to solve the assignment problem from the wire-bonding pads to the bump pads and then create the global path for each net. The detailed routing consists of three stages, namely: 1) cross-point assignment; 2) net ordering determination; and 3) track assignment, to complete the routing. Experimental results based on seven real designs from the industry demonstrate that the router can reduce the total wirelength by 10.2%, the critical wirelength by 13.4%, and the signal skews by 13.9%, as compared with a heuristic algorithm currently used in industry.

In this paper, we present an agglomeratively multilevel floorplanning/placement framework based on the B -tree representation called MB- tree to handle the floorplanning and packing for large-scale building modules. The MB-tree adopts a two-stage technique, i.e., clustering followed by declustering. The clustering stage iteratively groups a set of modules based on a cost metric guided by area utilization and module connectivity and at the same time establishes the geometric relations for the newly clustered modules by constructing a corresponding B -tree for them. The declustering stage iteratively ungroups a set of the previously clustered modules (i.e., perform tree expansion) and then refines the floorplanning/placement solution by using a simulated annealing scheme. In particular, the MB-tree preserves the geometric relations among modules during declustering, which makes the MB-tree an ideal data structure for the multilevel floorplanning/placement framework. Experimental results show that the MB-tree obtains significantly better silicon area and wirelength than previous works. Further, unlike previous works, the MB-tree scales very well as the circuit size increases.

We propose a multilevel full-chip routing algorithm that improves testability and diagnosability, manufacturability, and signal integrity for yield enhancement. Two major issues are addressed. 1) The oscillation ring test (ORT) and its diagnosis scheme for interconnects based on the popular IEEE Standard 1500 are integrated into the multilevel routing framework to achieve testability enhancement. We augment the traditional multilevel framework of coarsening and uncoarsening by introducing a preprocessing stage that analyzes the interconnect structure for better resource estimation before the coarsening stage, and a final stage after uncoarsening that improves testability to achieve 100% interconnect fault coverage and maximal diagnosability. 2) We present a heuristic to reduce routing congestion to optimize the multiple-fault probability, chemical-mechanical polishing- and optical proximity correction-induced manufacturability, and crosstalk effects, for yield improvement. Experimental results on the Microelectronics Center for North Carolina benchmark circuits show that the proposed ORT method achieves 100% fault coverage and the optimal diagnosis resolution for interconnects. Further, the multilevel routing algorithm effectively balances the routing density to achieve 100% routing completion.

As technology advances, the metal width decreases while the global wire length increases. This trend makes the resistance of the power wire increase substantially. Furthermore, the threshold voltage scales nonlinearly, raising the ratio of the threshold voltage to the supply voltage and making the voltage (IR) drop in the power/ground (P/G) network a serious problem in modern IC design. Traditional P/G network-analysis methods are often very computationally expensive, and it is, thus, not feasible to cosynthesize P/G network with floorplan. To make the cosynthesis feasible, we need not only an efficient, effective, and flexible floorplanning algorithm but also a very efficient yet sufficiently accurate P/G network-analysis method. In this paper, we present a method for floorplan and P/G network cosynthesis based on an efficient P/G network-analysis scheme and the$B^{\ast}$-tree floorplan representation. We integrate the cosynthesis into a commercial design flow to develop an effective power-integrity (IR drop)-driven design methodology. Experimental results based on a real-world circuit design and the MCNC benchmarks show that our design methodology successfully fixes the IR-drop errors earlier at the floorplanning stage and, thus, enables the single-pass design convergence.

As the process technology enters the nanometer era, reliability has become a major concern in the design and manufacturing of very large-scale integration circuits. In this paper, we focus on one reliability issue-jumper insertion in routing trees for avoiding/fixing antenna-effect violations at the routing/postlayout stages. We formulate the jumper insertion for antenna avoidance/fixing as a tree-cutting problem and present the first optimal algorithm for the tree-cutting problem. We show that the tree-cutting problem exhibits the properties of optimal substructures and greedy choices. With these properties, we present an O(V)-time optimal jumper-insertion algorithm that uses the minimum number of jumpers to avoid/fix the antenna violations in a routing tree with vertices. Experimental results show the superior effectiveness and efficiency of our algorithm.

We study in this paper the problem of jumper insertion on general routing (Steiner/spanning) trees with obstacles for antenna avoidance/fixing at the routing and/or postlayout stages. We formulate the jumper insertion for antenna avoidance/fixing as a tree-cutting problem and present the first optimal algorithm for the general tree-cutting problem. We show that the tree-cutting problem exhibits the properties of optimal substructures and greedy choices. With these properties, we present an O((V+D)lgD)-time optimal jumper-insertion algorithm that uses the least number of jumpers to avoid/fix the antenna violations on a Steiner/spanning tree with V vertices and D obstacles. Experimental results show the superior effectiveness and efficiency of our algorithm

Improving logic capacity by time-sharing, dynamically reconfigurable Field Gate Programmable Arrays (FPGAs) are employed to handle designs of high complexity and functionality. In this paper, we use a novel graph-based topological floorplan representation, named 3D-subTCG (3-Dimensional Transitive Closure subGraph), to deal with the 3-dimensional (temporal) floorplanning/placement problem, arising from dynamically reconfigurable FPGAs. The 3D-subTCG uses three transitive closure graphs to model the temporal and spatial relations between modules. We derive the feasibility conditions for the precedence constraints induced by the execution of the dynamically reconfigurable FPGAs. Because the geometric relationship is transparent to the 3D-subTCG and its induced operations (i.e., we can directly detect the relationship between any two tasks from the representation), we can easily detect any violation of the temporal precedence constraints on 3D-subTCG. We also derive important properties of the 3D-subTCG to reduce the solution space and shorten the running time for 3D (temporal) foorplanning/placement. Experimental results show that our 3D-subTCG-based algorithm is very effective and efficient.

Due to its great flexibility, gridless routing is desirable for nanometer circuit designs that use variable wire widths and spacings. Nevertheless, it is much more difficult than grid-based routing because of its larger solution space. In this paper, we present a novel "V-shaped" multilevel framework (called VMF) for full-chip gridless routing. Unlike the traditional "A-shaped" multilevel framework (inaccurately called the "Vcycle" framework in the literature), our VMF works in the V-shaped manner: top-down uncoarsening followed by bottom-up coarsening. Based on the novel framework, we develop a multilevel full-chip gridless router (called VMGR) for large-scale circuit designs. The top-down uncoarsening stage of VMGR starts from the coarsest regions and then processes down to finest ones level by level; at each level, it performs global pattern routing and detailed routing for local nets and then estimate the routing resource for the next level. Then, the bottom-up coarsening stage performs global maze routing and detailed routing to reroute failed connections and refine the solution level by level from the finest level to the coarsest one. We employ a dynamic congestion map to guide the global routing at all stages and propose a new cost function for congestion control. Experimental results show that VMGR achieves the best routability among all published gridless routers based on a set of commonly used MCNC benchmarks. Besides, VMGR can obtain significantly less wire-length, smaller critical path delay, and smaller average net delay than the previous works. In particular, VMF is general and thus can readily apply to other problems.

We propose an interconnect diagnosis scheme based on oscillation ring test methodology for SOC design with heterogeneous cores. The target fault models are delay faults and crosstalk glitches. We analyze the diagnosability of an interconnect structure and propose a fast diagnosability checking algorithm and an efficient diagnosis ring generation algorithm which achieves the optimal diagnosability. Two optimization techniques improve the efficiency and effectiveness of interconnect diagnosis. In all experiments, our method achieves 100% fault coverage and the optimal diagnosis resolution.

The flip-chip package gives the highest chip density of any packaging method to support the pad-limited ASIC design. One of the most important characteristics of flip-chip designs is that the input/output buffers could be placed anywhere inside a chip. In this paper, we first introduce the floorplanning problem for the flip-chip design and formulate it as assigning the positions of input/output buffers and first-stage/last-stage blocks so that the path length between blocks and bump balls as well as the delay skew of the paths are simultaneously minimized. We then present a hierarchical method to solve the problem. We first cluster a block and its corresponding buffers to reduce the problem size. Then, we go into iterations of the alternating and interacting global optimization step and the partitioning step. The global optimization step places blocks based on simulated annealing using the B*-tree representation to minimize a given cost function. The partitioning step dissects the chip into two subregions, and the blocks are divided into two groups and are placed in respective subregions. The two steps repeat until each subregion contains at most a given number of blocks, defined by the ratio of the total block area to the chip area. At last, we refine the floorplan by perturbing blocks inside a subregion as well as in different subregions. Compared with the B*-tree based floorplanner alone, our method is more efficient and obtains significantly better results, with an average cost of only 51.8% of that obtained by using the B*-tree alone, based on a set of real industrial flip-chip designs provided by leading companies

As the technology node advances into the nanometer era, via-open defects are one of the dominant failures. To improve via yield and reliability, redundant-via insertion is a highly recommended technique proposed by foundries. Traditionally, double-via insertion is performed at the post-layout stage. The increasing design complexity, however, leaves very limited space for post-layout optimization. It is thus desirable to consider the double-via insertion at both routing and post-routing stages. In this paper, we present a new full-chip gridless routing system considering double-via insertion for yield enhancement. To fully consider double vias, the router applies a novel two-pass, bottom-up routability-driven routing framework. We also propose a new post-layout double-via insertion algorithm to achieve a higher insertion rate. Based on a bipartite graph matching formulation, we develop an optimal double-via insertion algorithm for the cases with up to three routing layers and the stack-via structure, and then extend the algorithm to handle the general cases. Experiments show that our methods significantly improve the via count, the number of dead vias, double-via insertion rates, and running times.

Droplet-based microfluidic biochips have recently gained much attention and are expected to revolutionize the biological laboratory procedure. As biochips are adopted for the complex procedures in molecular biology, its complexity is expected to increase due to the need of multiple and concurrent assays on a chip. In this paper, we formulate the placement problem of digital microfluidic biochips with a tree-based topological representation, called T-tree. To the best knowledge of the authors, this is the first work that adopts a topological representation to solve the placement problem of digital microfluidic biochips. Experimental results demonstrate that our approach is much more efficient and effective, compared with the previous unified synthesis and placement framework.

In addition to wirelength, modern placers need to consider various constraints such as preplaced blocks and density. We propose a high-quality analytical placement algorithm considering wirelength, preplaced blocks, and density based on the log-sum-exp wirelength model proposed by Naylor et al. [20] and the multilevel framework. To handle preplaced blocks, we use a two-stage smoothing technique, Gaussian smoothing followed by level smoothing, to facilitate block spreading during global placement. The density is controlled by white-space re-allocation using partitioning and cut-line shifting during global placement and cell sliding during detailed placement. We further use the conjugate gradient method with dynamic step-size control to speed up the global placement and macro shifting to and better macro positions. Experimental results show that our placer obtains the best published results.

As technology enters the nanometer territory, the antenna effect plays an important role in determining the yield and reliability of a VLSI circuit. Diode insertion and jumper insertion are the most effective techniques to fix the antenna effect. However, due to the increasing design complexity and the limited routing resource, applying diode or jumper insertion alone cannot achieve a high antenna fixing rate. In this paper, we give a polynomial-time antenna violation detection/fixing algorithm by simultaneous diode/jumper insertion with minimum cost, based on a minimum-cost networkflow formulation. Experimental results show that our algorithm consistently achieves much higher antenna fixing rates than the state-of-the-art jumper insertion and diode insertion algorithms alone.

Power consumption is a crucial concern in nanometer chip design. Researchers have shown that multiple supply voltage (MSV) is an effective method for power consumption reduction. The underlying idea behind MSV is the trade-off between power saving and performance. In this paper, we present an effective voltage assignment technique based on dynamic programming. Given a netlist without reconvergent fanouts, the dynamic programming can guarantee an optimal solution for the voltage assignment. We then generate a level shifter for each net that connects two blocks in different voltage domains, and perform power-network aware floorplanning for the MSV design. Experimental results show that our floorplanner is very effective in optimizing power consumption under timing constraints.

The electrostatic discharge (ESD) problem has become a challenging reliability issue in nanometer circuit design. High voltages resulted from ESD might cause high current densities in a small device and burn it out, so on-chip protection circuits for IC pads are required. To reduce the design cost, the protection circuit should be added only for the IC pads with an ESD current path, which arises the ESD current path analysis problem. In this paper, we first introduce the analysis problem for ESD protection in circuit design. We then model the circuit as a constrained graph, decompose ESD connected components linked with the pads, and apply the breadth-first search (BFS) to identify the ESD connected components in each constrained graph and thus the current paths. Experimental results show that our algorithm can detect all ESD paths very efficiently and economically. To our best knowledge, our algorithm is the first point tool available to the public for the ESD analysis.

As the operation frequency reaches gigahertz in very deep-submicron designs, the effect of on-chip inductance on circuit performance can no longer be neglected. Therefore, it is desired to extract interconnect impedance and inductance accurately. Most previous works on impedance and inductance extraction are based on rectangular discretization which has been shown effective for the classical Manhattan based IC interconnect structures. As technology advances, however, more general IC interconnect structures, such as the X-based interconnect structure, have been in production. Those general interconnect structures allow wires to be routed with non-Manhattan shapes. For the non-Manhattan interconnect structures, rectangular discretization is obviously not sufficient. In this paper, we propose to use the surface integral formulation with triangular discretization to extract impedance and inductance for the general IC interconnect structures. Comparative studies with the well-known FastImp and IE3D show that our approach is flexible and effective.

In this paper, we present a hybrid placer, called NTUplace2, which integrates both the partitioning and the analytical (quadratic programming) placement techniques for large-scale mixed-size designs. Unlike most existing placers that minimize wirelength alone, we also control the cell density to optimize routability while minimizing the total wirelength. NTUplace2 consists of three major stages: multilevel global placement, legalization, and detailed placement. To handle mixed-size designs, in particular, we present a linear programming based legalization algorithm to remove overlaps between macros during global placement. Various other techniques are integrated to improve the solution quality at every stage.

As technology advances, the metal width decreases while the global wire length increases. This trend makes the resistance of the power wire increase substantially. Further, the threshold voltage scales nonlinearly, raising the ratio of the threshold voltage to the supply voltage and making the voltage (IR) drop in the power/ground (P/G) network a serious problem in modern IC design. Traditional P/G network analysis methods are often very computationally expensive, and it is thus not feasible to co-synthesize P/G network with floorplan. To make the co-synthesis feasible, we need not only an efficient, effective, and flexible floorplanning algorithm, but also a very efficient, yet sufficiently accurate P/G network analysis method. In this paper, we present a method for floorplan and P/G network co-synthesis based on an efficient P/G network analysis scheme and the B*-tree floorplan representation. We integrate the co-synthesis into a commercial design flow to develop an effective power integrity (IR-drop) driven design methodology. Experimental results based on a real-world circuit design and the MCNC benchmarks show that our design methodology successfully fixes the IR-drop errors earlier at the floorplanning stage and thus enables the single-pass design convergence.

We study in this paper the problem of jumper insertion on general routing (Steiner/spanning) trees with obstacles for antenna avoidance/fixing at the routing and/or post-layout stages. We formulate the jumper insertion for antenna avoidance/fixing as a tree-cutting problem and present the firstoptimal algorithm for the general tree-cutting problem. We show that the tree-cutting problem exhibits the properties of optimal substructures and greedy choices. With these properties, we present an O((V+D) lg D)-time optimal jumper insertion algorithm that uses the least number of jumpers to avoid/fix the antenna violations on a Steiner/spanning tree with V vertices and D obstacles. Experimental results show the superior effectiveness and efficiency of our algorithm.

Unlike classical floorplanning that usually handles only block packing to minimize silicon area, modern very large scale integration (VLSI) floorplanning typically needs to pack blocks within a fixed die (outline), and additionally considers the packing with block positions and interconnect constraints. Floorplanning with bus planning is one of the most challenging modern floorplanning problems because it needs to consider the constraints with interconnect and block positions simultaneously. In this paper, the authors study two types of modern floorplanning problems: 1) fixed-outline floorplanning and 2) bus-driven floorplanning (BDF). This floorplanner uses B/sup */-tree floorplan representation based on fast three-stage simulated annealing (SA) scheme called Fast-SA. For fixed-outline floorplanning, the authors present an adaptive Fast-SA that can dynamically change the weights in the cost function to optimize the wirelength under the outline constraint. Experimental results show that this floorplanner can achieve 100% success rates efficiently for fixed-outline floorplanning with various aspect ratios. For the BDF, the authors explore the feasibility conditions of the B/sup */-tree with the bus constraints, and develop a BDF algorithm based on the conditions and Fast-SA. Experimental results show that this floorplanner obtains much smaller dead space for the floorplanning with hard/soft macro blocks, compared with the most recent work. In particular, this floorplanner is more efficient than the previous works.

An interconnect diagnosis scheme based on the oscillation ring (OR) test methodology for systems-on-chip (SOC) design with heterogeneous cores is proposed. In addition to traditional stuck-at and open faults, the OR test can also detect and diagnose important interconnect faults such as delay faults and crosstalk glitches. The large number of test rings in the SOC design, however, significantly complicates the interconnect diagnosis problem. In this paper, the diagnosability of an interconnect structure is first analyzed then a fast diagnosability checking algorithm and an efficient diagnosis ring generation algorithm are proposed. It is shown in this paper that the generation algorithm achieves the maximum diagnosability for any interconnect. Two optimization techniques are also proposed, an adaptive and a concurrent diagnosis method, to improve the efficiency and effectiveness of interconnect diagnosis. Experiments on the MCNC benchmark circuits show the effectiveness of the proposed diagnosis algorithms. In all experiments, the method achieves 100% fault detection coverage and the optimal interconnect diagnosis resolution

This paper shows that the worst case switching pattern that incurs the longest bus delay while considering the RLC effect is quite different from that while considering the RC effect alone. It implies that the existing encoding schemes based on the RC model may not improve or possibly worsen the delay when the inductance effects become dominant. A bus-invert method is also proposed to reduce the on-chip bus delay based on the RLC model. Simulation results show that the proposed encoding scheme significantly reduces the worst case coupling delay of the inductance-dominated buses

As technology advances apace, crosstalk becomes a design metric of comparable importance to area and delay. This article focuses mainly on the crosstalk issue, specifically on the impacts of physical design and process variation on crosstalk. While the feature size shrinks below 0.25μ m , the impact of process variation on crosstalk increases rapidly. Hence, a crosstalk insensitive design is desirable in the deep submicron regime. In this article, crosstalk sensitivity is referred to as the influence of process variation on crosstalk in a circuit. We show that the lower bound of crosstalk sensitivity grows quadratically, while that of crosstalk increases linearly. Therefore, designers should also consider crosstalk sensitivity, when optimizing other design objectives such as crosstalk, area, and delay. According to our modeling, these objectives are all in posynomial forms, and thus the multi-objective optimization problem can optimally be solved by Lagrangian relaxation. Experimental results show that our method is effective and efficient. For instance, a circuit of 2856 gates and 5272 wires is optimized using 13-minute runtime and 2.8-MB memory on a Pentium III 1.0 GHz PC with 256-MB memory. In particular, by relaxing Lagrange multipliers to the critical paths, it takes only two iterations for all solutions to converge to the global optimal, which is much more efficient than related previous work. This relaxation scheme provides a key insight into the rapid convergence in Lagrangian relaxation.

To handle modern routing with nanometer effects, we need to consider designs of variable wire widths and spacings, for which gridless routers are desirable due to their great flexibility. The gridless routing is much more difficult than the grid-based one because the solution space of gridless routing is significantly larger than that of grid-based one. In this paper, we present the first multilevel, full-chip gridless detailed router. The router integrates global routing, detailed routing, and congestion estimation together at each level of the multilevel routing. It can handle non-uniform wire widths and consider routability and optical proximity correction (OPC). Experimental results show that our approach obtains significantly better routing solutions than previous works. For example, for a set of 11 commonly used benchmark circuits, our approach achieves 100% routing completion for all circuits while the famous state-of-the-art three-level routing and multilevel routing (multilevel global routing + flat detailed routing) cannot complete routing for any of the circuits. Besides, experimental results show that our multilevel gridless router can handle non-uniform wire widths efficiently and effectively (still maintain 100% routing completion for all circuits). In particular, our OPC-aware multilevel gridless router archives an average reduction of 11.3% pattern features and still maintains 100% routability for the 11 benchmark circuits.

In order to handle device matching for analog circuits, some pairs of modules need to be placed symmetrically with respect to a common axis. In this paper, we deal with the module placement with symmetry constraints for analog design using the Transitive Closure Graph-Sequence (TCG-S) representation. Since the geometric relationships of modules are transparent to TCG-S and its induced operations, TCG-S has better flexibility than previous works in dealing with symmetry constraints. We first propose the necessary and sufficient conditions of TCG-S for symmetry modules. Then, we propose a polynomial-time packing algorithm for a TCG-S with symmetry constraints. Experimental results show that the TCG-S based algorithm results in the best area utilization.

We present in this paper a new algorithm to co-optimize the problems of test scheduling and core wrapper design under power constraints for core-based SoC (System on Chip) designs. The problem of test scheduling is first transformed into a floorplanning problem with a given maximum height (test access mechanism width) constraint. Then, we apply the B*-tree based floorplanning technique to solve the SoC test scheduling problem. Experimental results based on the ITC'02 benchmarks show that our method is very effective and efficient---our method obtains the best results ever reported for SoC test scheduling with power constraint in every efficient running time. Compared with recent works, our method achieves average improvements of 4.7% to 20.1%.

As technology advances into the nanometer territory, the interconnect delay has become a first-order effect on chip performance. To handle this effect, the X-architecture has been proposed for high-performance integrated circuits. The X-architecture presents a new way of orienting a chip's microscopic interconnect wires with the pervasive use of diagonal routes. It can reduce the wirelength and via count, and thus improve performance and routability. Furthermore, the continuous increase of the problem size of IC routing is also a great challenge to existing routing algorithms. In this paper, we present the first multilevel framework for full-chip routing using the X-architecture. To take full advantage of the X-architecture, we explore the optimal routing for three-terminal nets on the X-architecture and develop a general X-Steiner tree algorithm based on the delaunay triangulation approach for the X-architecture. The multilevel routing framework adopts a two-stage technique of coarsening followed by uncoarsening, with a trapezoid-shaped track assignment embedded between the two stages to assign long, straight diagonal segments for wirelength reduction. Compared with the state-of-the-art multilevel routing for the Manhattan architecture, experimental results show that our approach reduced wirelength by 18.7% and average delay by 8.8% with similar routing completion rates and via counts.

As the process technology enters the nanometer era, reliability has become a major concern in the design and manufacturing of VLSI circuits. In this paper we focus on one reliability issue-jumper insertion in routing trees for avoiding/fixing antenna effect violations at the routing/post-layout stages. We formulate the jumper insertion for antenna avoidance/fixing as a tree-cutting problem. We show that the tree-cutting problem exhibits the properties of optimal substructures and greedy choices. With these properties, we present an O(V lg V)-time exact jumper insertion algorithm that uses the optimum number of jumpers to avoid/fix the antenna violations in a routing tree with V vertices. Experimental results show the superior effectiveness and efficiency of our algorithm.

We present in this paper, a new interconnect-driven multilevel floorplanning, called IMF, to handle large-scale building-module designs. Unlike the traditional multilevel framework that adopts the "V-cycle" framework: bottom-up coarsening followed by top-down uncoarsening, in contrast, IMF works in the "/spl Lambda/-cycle" manner: top-down uncoarsening (partitioning) followed by bottom-up coarsening (merging). The top-down partitioning stage iteratively partitions the floorplan region based on mm-cut bipartitioning with exact net-weight modeling to reduce the number of global interconnections and thus the total wirelength. Then, the bottom-up merging stage iteratively applies fixed-outline floorplanning using simulated annealing for all regions and merges two neighboring regions recursively. We also propose an accelerative fixed-outline floorplanning (AFF) to speed up wirelength minimization under the outline constraint. Experimental results show that IMF consistently obtains the best floorplanning results with the smallest wirelength for large-scale building-module designs, compared with all publicly available floorplanners. In particular, IMF scales very well as the circuit size increases. The /spl Lambda/-cycle multilevel framework outperforms the V-cycle one in the optimization of global circuit effects, such as interconnection and crosstalk optimization, since the /spl Lambda/-cycle framework considers the global configuration first and then processes down to local ones level by level and thus the global effects can be handled at earlier stages. The /spl Lambda/-cycle multilevel framework is general and thus can be readily applied to other problems.

The flip-chip package gives the highest chip density of any packaging method to support the pad-limited Application-Specific Integrated Circuit (ASIC) designs. In this paper, we propose the first router for the flip-chip package in the literature. The router can redistribute nets from wire-bonding pads to bump pads and then route each of them. The router adopts a two-stage technique of global routing followed by detailed routing. In global routing, we use the network flow algorithm to solve the assignment problem from the wire-bonding pads to the bump pads, and then create the global routing path for each net. The detailed routing consists of three stages, cross point assignment, net ordering determination, and track assignment, to complete the routing. Experimental results based on seven real designs from the industry demonstrate that the router can reduce the total wirelength by 10.2%, the critical wirelength by 13.4%, and the signal skews by 13.9%, compared with a heuristic algorithm currently used in industry.

Heat is a main concern for processors in deep sub-micron technologies. The chip temperature is affected by both the power consumption of processor components and the chip layout. Therefore, for thermal-aware design it is crucial to consider the thermal effects of different floorplans during micro-architectural design space exploration. In this paper, we propose a thermal-aware architectural floorplanning framework. With the aid of this framework, an architect can explore both physical and architectural design spaces simultaneously to find an architecture and the corresponding chip layout that maximizes performance under a thermal limitation

Unlike classical floorplanning that usually handles only block packing to minimize silicon area, modern VLSI floorplanning typically needs to pack blocks within a fixed die (outline) and additionally considers the packing with block positions and interconnect constraints. Floorplanning with bus planning is one of the most challenging modern floorplanning problems because it needs to consider the constraints with interconnect and block positions simultaneously. We study in this paper two types of modern floorplanning problems: (1) fixed-outline floorplanning and (2) bus-driven floorplanning. Our floorplanner uses the B*-tree floorplan representation and is based on a fast three-stage simulated annealing scheme, called Fast-SA. For fixed-outline floorplanning, we present an adaptive Fast-SA that can dynamically change

In this paper, we present a hierarchical ratio partitioning based placement algorithm for large-scale mixed-size designs. The placement algorithm consists of three steps: global placement, legalization,and detailed placement; it works in a hierarchical manner and integrates net-weighting partitioning, whitespace management, look-ahead bipartitioning, and fast legalization to handle the large-scale mixed-size placement problems. Unlike the traditional partitioning-based technique that is based on balanced partitioning, we apply ratio partitioning in each level. Further, applying the look-ahead bipartitioning technique in each level, we can evaluate the feasibility of the placement for sub-partitions more accurately. Therefore, we can find better ratios for the partitions, leading to easier legalization for the global placement result and finally a better detailed placement solution. Experimental results show the efficiency and effectiveness of our algorithm.

The College of Electrical Engineering and Computer Science at the National Taiwan University has identified the area of content science for media-rich life, broadly construed, as one of core areas for the college's future directions. One major aspect of this project is to develop the enabling technology for reconfigurable platforms for multimedia applications. Specifically, the goal is to develop reconfigurable platforms of system-on-a-chip (SoC) components for the applications to support the needs of multi-modal multimedia contents and to provide rapid system prototyping. The faculties in the College of Electrical Engineering and Computer Science have formed a multi-discipline team to develop such technology. Our team includes seven faculties and more than thirty students from the college. This short report describes the reconfigurable platform for content science research activities currently underway by our team. Our current activities include to develop the technology to analyze the critical path for avoiding hardware contention, to minimize the use of logic components, to design the multimedia IPs, to optimally route the bus and place the logic units, to design energy efficient cache, to evaluate the performance and power consumption, to design the algorithm for temporal floor-planning/placement.

In this paper, we propose a novel framework for fast multilevel routing considering crosstalk and performance optimization. To handle the crosstalk minimization problem, we incorporate an intermediate stage of layer/track assignment into the multilevel routing framework. For performance-driven routing, we propose a novel minimum-radius minimum-cost spanning tree heuristic for global routing. Compared with the state-of-the-art multilevel routing with the routability mode, the experimental results show that our router achieved a 6.7X runtime speedup, reduced the respective maximum and average crosstalk (coupling length) by about 30% and 24%, reduced the respective maximum and average delay by about 15% and 5%. Compared with the timing-driven mode, the experimental results show that our router still achieved a 5.9X runtime speedup, reduced the respective maximum and average crosstalk by about 35% and 23%, reduced the respective maximum and average delay by about 7% and 10% in comparable routability, and resulted in fewer failed nets.

In this brief, we introduce the concept of the P*-admissible representation and propose a P*-admissible, transitive closure graph-based representation for general floorplans, called transitive closure graph (TCG), and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P*-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying a faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operation, facilitating the convergence to a desired solution. All of these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.

As technology advances, the metal width is decreasing with the length increasing, making the resistance along the power line increase substantially. Together with the nonlinear scaling of the threshold voltage that makes the ratio of the threshold voltage to the supply voltage rise, the voltage (IR) drop become a serious problem in modern VLSI design. Traditional power/ground (P/G) network analysis methods are typically very computationally expensive and thus not feasible to be integrated into floorplanning. To make the integration of the P/G analysis with floorplanning feasible, we need a very efficient, yet sufficiently accurate analysis method. In this paper, we present the methods for the fast analysis of the P/G networks at the floorplanning stage and integrate our analyzer into a commercial tool to develop a power integrity (IR drop) driven design methodology. Experimental results based on three real-world circuit designs show that our P/G network analyzer is accurate enough and very efficient.

Improving logic capacity by time-sharing, dynamically reconfigurable FPGAs are employed to handle designs of high complexity and functionality. We model each task as a 3D-box and deal with the temporal floorplanning/placement problem for dynamically reconfigurable FPGA architectures. We present a tree-based data structure, called T-trees, to represent the spatial and temporal relations among tasks. Each node in a T-tree has at most three children which represent the dimensional relationship among tasks. For the T-tree, we develop an efficient packing method and derive the condition to ensure the satisfaction of precedence constraints which model the temporal ordering among tasks induced by the execution of dynamically reconfigurable FPGAs. Experimental results show that our tree-based formulation can achieve significantly better solution quality with less execution time than the most recent state-of-the-art work.

To facilitate sequential data transfer (e.g., bus or pipeline signals) and reduce bounded net delay (as well as total wirelength), it is desired to align circuit blocks one by one and constrain the blocks within a certain bounding box. In this paper, we handle the placement with alignment and performance (delay) constraints using the B*-tree representation. We first explore the feasibility conditions with the alignment and performance constraints, and then propose algorithms that can guarantee a feasible placement with alignment constraints and generate a good placement with performance constraints during each operation. In particular, our method is the first algorithm to achieve the amortized linear-time complexity for evaluating a placement with the alignment and performance constraints. Experimental results based on the MCNC benchmark with the constraints show that our method significantly outperforms the previous work.

As technology advances into the nanometer territory, the antenna problem has caused significant impact on routing tools. The antenna effect is a phenomenon of plasma-induced gate oxide degradation caused by charge accumulation on conductors. It directly influences manufacturability and yield of VLSI circuits, especially in deep-submicron technology using high density plasma. Furthermore, the continuous increase of the problem size of IC routing is also a great challenge to existing routing algorithms. In this paper, we propose a novel framework for multilevel full-chip routing with antenna avoidance using a built-in jumper insertion approach. Experimental results show that our approach re-duced antenna-violated gates by about 98 % and also achieved

In this paper, we propose a novel framework for multilevel full-chip routing considering both routability and performance called MR. The two-stage multilevel framework consists of coarsening, followed by uncoarsening. Unlike the previous multilevel routing, MR integrates global routing, detailed routing, and resource estimation, together at each level of the framework, leading to more accurate routing resource estimation during coarsening and thus facilitating the solution refinement during uncoarsening. Further, the exact routing information obtained at each level makes MR more flexible in dealing with various routing objectives (such as crosstalk, power, etc.). Experimental results show that MR obtains significantly better routing solutions than previous works. For example, for a set of 11 commonly used benchmark circuits, MR achieves 100% routing completion for all circuits, while the previous multilevel routing, the three-level routing, and the hierarchical routing can complete routing for only 2, 0, 2 circuits, respectively. In particular, the number of routing layers used by MR is even smaller. We also have performed experiments on timing-driven routing. The results are also very promising.

As technology advances and the number of interconnections among modules rapidly increases, timing closure, and design convergence are the most important concerns. Hence, it is desirable to consider interconnect optimization as early as possible. Previous work for this issue can be classified into two directions: wire planning and buffer-block planning for interconnect-driven floorplanning. Wire planning for interconnect-driven floorplanning does not consider buffer insertion, and buffer-block planning for interconnect-driven floorplanning cannot overcome the limitation of a bad initial floorplan. In this paper, we first address simultaneous floorplanning and buffer-block planning (i.e., integrating buffer-block planning into floorplanning) for interconnect optimization. We adopt simulated annealing to refine a floorplan so that buffers can be inserted more effectively. In each iteration, we construct a routing tree for each net, allocate buffers for all nets, introduce corresponding buffer blocks into the intermediate floorplan, and invoke Lagrangian relaxation to optimize area and satisfy timing requirements. Further, in order to reduce the problem size, we present supermodule partitioning which partitions modules into supermodules. Experimental results show that our method of integrating buffer-block planning into floorplanning can significantly improve the interconnect delay and reduce the number of buffers needed. Based on a set of MCNC benchmark circuits, our approach achieves an average success rate of 86.1% of nets meeting timing constraints, inserts only 272 buffers on average, and consumes an average extra area of only 0.28% over the given floorplan, compared with the average success rate of 62.6%, 1123 buffers, and extra area of 1.05% resulted from a famous recent work presented at ICCAD'99.

In this paper, we extend the concept of the P-admissible floorplan representation to that of the P/sup */-admissible one. A P/sup */-admissible representation can model the most general floorplans. Each of the currently existing P/sup */-admissible representations, sequence pair (SP), bounded-slicing grid, and transitive closure graph (TCG), has its strengths as well as weaknesses. We show the equivalence of the two most promising P/sup */-admissible representations, TCG and SP, and integrate TCG with a packing sequence (part of SP) into a representation, called TCG-S. TCG-S combines the advantages of SP and TCG and at the same time eliminates their disadvantages. With the property of SP, a fast packing scheme is possible. Inherited nice properties from TCG, the geometric relations among modules are transparent to TCG-S (implying faster convergence to a desired solution), placement with position constraints becomes much easier, and incremental update for cost evaluation can be realized. These nice properties make TCG-S a superior representation which exhibits an elegant solution structure to facilitate the search for a desired floorplan/placement. Extensive experiments show that TCG-S results in the best area utilization, wirelength optimization, convergence speed, and stability among existing works and is very flexible in handling placement with special constraints.

As the operating frequency increases to gigahertz and the rise time of a signal is less than or comparable to the time-of-flight delay of a wire, it is necessary to consider the transmission line behavior for delay computation. We present in this paper, an analytical formula for the delay computation under the transmission line model. Extensive simulations with SPICE show the high fidelity of the formula. Compared with previous works, our model leads to smaller average errors in delay estimation. Based on this formula, we show the property that the minimum delay for a transmission line with reflection occurs when the number of round trips is minimized (i.e., equals one). Besides, we show that the delay of a circuit path is a posynomial function in wire and buffer sizes, implying that a local optimum is equal to the global optimum. Thus, we can apply any efficient search algorithm such as the well-known gradient search procedure to compute the globally optimal solution. Experimental results show that simultaneous wire and buffer sizing is very effective for performance optimization under the transmission line model.

As technology advances and the number of interconnections among modules rapidly increases, timing closure and design convergence are the most important concerns. Hence, it is desirable to consider interconnect optimization as early as possible. In this paper, we first address simultaneous floorplanning and buffer block planning (i.e., integrating buffer block planning into floorplanning) for interconnect optimization. Experimental results show that our method can significantly improve the interconnect delay and reduce the number of buffers needed.

Crosstalk-induced noise has become a key problem in interconnect optimization when technology improves, spacing diminishes, and coupling capacitance/inductance increases. Buffer insertion/sizing is one of the most effective and popular techniques to reduce interconnect delay and decouple coupling effects. It is traditionally applied to post-layout optimization. However it is obviously infeasible to insert/size hundreds of thousands buffers during the post-layout stage when most routing regions are occupied. Therefore, it is desirable to incorporate buffer planning into floorplanning to ensure timing closure and design convergence. In this paper we first derive formulae of buffer insertion for timing and noise optimization, and then apply the formulae to compute the feasible regions for inserting buffers to meet both timing and noise constraints. Experimental results show that our approach achieves an average success rate of 80.9% (78.2%) of nets meeting timing constraints alone (both timing and noise constraints) and consumes an average extra area of only 0.49% (0.66%) over the given floorplan, compared with the average success rate of 75.6% of nets meeting timing constraints alone and an extra area of 1.33% by the BBP method [3].

Architecture and CAD are closely related issues in FPGA design. Routing architecture design shall optimize routability and facilitate router development; on the other hand, router design shall consider the specific properties of routing architectures to optimize the performance of the router. In this paper, we propose effective and efficient unified matching-based algorithms for array-based FPGA routing and segmentation design. For the segmentation design, we consider the similarity of input routing instances and formulate a net-matching problem to construct the optimal segmentation architecture. For the router design, we present a matching-based timing-driven routing algorithm which can consider a versatile set of routing segments. Experimental results show that our designed segmentations significantly outperform those used in commercially available FPGAs. For example, our designed segmentations achieve, on average, 14.6% and 19.7% improvements in routability, compared with those used in the Lucent Technologies ORCA 2C-series and the Xilinx XC4000E-series FPGAs, respectively.

We present in this paper a multilevel floorplanning/placement framework based on the B*-tree representation, called MB*-tree, to handle the floorplanning and packing for large-scale building modules. The MB*-tree adopts a two-stage technique, clustering followed by declustering. The clustering stage iteratively groups a set of modules based on a cost metric guided by area utilization and module connectivity, and at the same time establishes the geometric relations for the newly clustered modules by constructing a corresponding B*-tree for them. The declustering stage iteratively ungroups a set of the previously clustered modules (i.e., perform tree expansion) and then refines the floorplanning/placement solution by using a simulated annealing scheme. In particular, the MB*-tree preserves the geometric relations among modules during declustering, which makes the MB*-tree an ideal data structure for the multilevel floorplanning/placement framework. Experimental results show that the MB*-tree obtains significantly better silicon area and wirelength than previous works. Further, unlike previous works, MB*-tree scales very well as the circuit size increases.

Switch modules are the most important component of the routing resources in FPGAs/FPICs. Previous works have shown that switch modules with higher routability result in better area performance for practical applications. We consider in this paper an FPGA/FPIC switch-module analysis problem: the inputs consist of a switch-module description and the number of nets required to be routed through the switch module; the question is to determine if there exists a feasible routing for the routing requirements on the switch module. As a fundamental problem for the analysis of switch modules, this problem is applicable to the design and routability evaluation of FPGA/FPIC switch modules and FPGA/FPIC routing. We present a network-flow-based approximation algorithm for this problem. Based on mathematical analyses, we show that this algorithm has provably good performance with the bounds 5 and 5/4 away from the optima for two types of switch modules, respectively. Extensive experiments show that this algorithm is highly accurate and runs very efficiently.

Due to the layout complexity in modern VLSI designs, integrated circuit blocks may not be rectangular. However, literature on general rectilinear block placement is still quite limited. In this article, we present approaches for handling the placement for arbitrarily shaped rectilinear blocks using B*-trees [Chang et al. 2000]. We derive the feasibility conditions of B*-trees to guide the placement of rectilinear blocks. Experimental results show that our algorithm achieves optimal or near-optimal block placement for benchmarks with various shaped blocks.

Floorplanning/placement allocates a set of modules into a chip so that no two modules overlap and some specified objective is optimized. To facilitate floorplanning/placement, we need to develop an efficient and effective representation to model the geometric relationship among modules. In this paper, we present a P-admissible representation, called corner sequence (CS), for nonslicing floorplans. CS consists of two tuples that denote the packing sequence of modules and the corners to which the modules are placed. CS is very effective and simple for implementation. Also, it supports incremental update during packing. In particular, it induces a generic worst case linear-time packing scheme that can also be applied to other representations. Experimental results show that CS achieves very promising results for a set of commonly used MCNC benchmark circuits.

We extend in this paper the concept of the P-admissible floorplan representation to that of the P*-admissible one. A P*-admissible representation can model the most general floorplans. Each of the currently existing P*-admissible representations, SP, BSG, and TCG, has its strengths as well as weaknesses. We show the equivalence of the two most promising P*-admissible representations, TCG and SP, and integrate TCG with a packing sequence (part of SP) into a new representation, called TCG-S. TCG-S combines the advantages of SP and TCG and at the same time eliminates their disadvantages. With the property of SP, faster packing and perturbation schemes are possible. Inherited nice properties from TCG, the geometric relations among modules are transparent to TCG-S (implying faster convergence to a desired solution), placement with position constraints becomes much easier, and incremental update for cost evaluation can be realized. These nice properties make TCG-S a superior representation which exhibits an elegant solution structure to facilitate the search for a desired floorplan/placement. Extensive experiments show that TCG-S results in the best area utilization, wirelength optimization, convergence speed, and stability among existing works and is very flexible in handling placement with special constraints.

Deals with arbitrary convex and concave rectilinear module packing using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG and its induced operations, which makes TCG an ideal representation for floor-planning/placement with arbitrary rectilinear modules. We first partition a rectilinear module into a set of submodules and then derive necessary and sufficient conditions of feasible TCG for the submodules. Unlike most previous works that process each submodule individually and thus need post processing to fix deformed rectilinear modules, our algorithm treats a set of submodules as a whole and thus not only can guarantee the feasibility of each perturbed solution but also can eliminate the need of the post processing on deformed modules, implying better solution quality and running time. Experimental results show that our TCG-based algorithm is capable of handling very complex instances; further, it is very efficient and results in better area utilization than previous work.

We propose in this paper a novel framework for multilevel routing considering both routability and performance. The two-stage multilevel framework consists of coarsening followed by uncoarsening. Unlike the previous multilevel routing, we integrate global routing, detailed routing, and resource estimation together at each level of the framework, leading to more accurate routing resource estimation during coarsening and thus facilitating the solution refinement during uncoarsening. Further, the exact routing information obtained at each level makes our framework more flexible in dealing with various routing objectives (such as crosstalk, power, etc). Experimental results show that our approach obtains significantly better routing solutions than previous works. For example, for a set of 11 commonly used benchmark circuits, our approach achieves 100% routing completion for all circuits while the previous multilevel routing, the three-level routing, and the hierarchical routing can complete routing for only 3, 0, 3 circuits, respectively. In particular, the number of routing layers used by our router is even smaller. We also have performed experiments on timing-driven routing. The results are also very promising.

M. Shyu et al. (2000) defined the well-structured symmetric switch block M/sub N,W/ and showed that M/sub N,W/ is universal for any pair of positive integers N and W. However, we find that this result is partially correct. In this paper, we show that, when N/spl ges/7, M/sub N,W/ is not universal for odd Ws (/spl ges/3) and it is universal for any even W.

In this article, we introduce a new placement problem motivated by the Dynamically Reconfigurable FPGA (DRFPGA) architectures. Unlike traditional placement, the problem for DRFPGAs must consider the precedence constraints among logic components. For the placement, we develop an effective metric that can consider wirelength, register requirement, and power consumption simultaneously. With the considerations of the new metric and the precedence constraints, we then present a three-stage scheme of partitioning, initial placement generation, and placement refinement to solve the new placement problem. Experimental results show that our placement scheme with the new metric achieves respective improvements of 17.2, 27.0, and 35.9% in wirelength, the number of registers, and power consumption requirements, compared with the list scheduling method.

In this paper, we deal with arbitrarily shaped rectilinear module placement using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG as well as its induced operations, which makes TCG an ideal representation for floorplanning/placement with arbitrary rectilinear modules. We first partition a rectilinear module into a set of submodules and then derive necessary and sufficient conditions of feasible TCG for the submodules. Unlike most previous works that process each submodule individually and thus need to perform post processing to fix deformed rectilinear modules, our algorithm treats a set of submodules as a whole and thus not only can guarantee the feasibility of each perturbed solution but also can eliminate the need for the postprocessing on deformed modules, implying better solution quality and running time. Experimental results show that our TCG-based algorithm is capable of handling very complex instances; further, it is very efficient and results in better area utilization than previous work.

In this paper, we propose a transitive closure graph-based representation for general floorplans, called TCG, and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operations, facilitating the convergence to a desired solution. All these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.

As the operating frequency increases to giga hertz and the rise time of a signal is less than or comparable to the time-of-flight delay of a line, it is necessary to consider the transmission line behavior for delay computation. We present an analytical formula for the delay computation under the transmission line model. Extensive simulations with SPICE show the high fidelity of the formula. Compared with previous works of Elmore (1948) and Ismaul et al. (2000), our model leads to smaller average errors in delay estimation. Based on this formula, we show the property that the minimum delay for a transmission line with reflection occurs when the number of round trips is minimized. Besides, we show that the delay of a circuit path is a posynomial function in wire and buffer sizes, implying that a local optimum is equal to the global optimum. Thus, we can apply any efficient search algorithm such as the well-known gradient search procedure to compute the globally optimal solution. Experimental results show that simultaneous wire and buffer sizing is very effective for performance optimization under the transmission line model.

In this paper, we introduce a new placement problem motivated by the Dynamically Reconfigurable FPGA (DRFPGA) architectures. Unlike traditional placement, the problem for DRFPGAs must consider the precedence constraints among logic components. For the placement, we develop an effective metric that can consider wirelength, register requirement, and power consumption simultaneously. With the considerations of the new metric and the precedence constraints, we then present a three-stage scheme of partitioning, initial placement generation, and placement refinement to solve the new placement problem. Experimental results show that our placement scheme with the new metric achieves respective improvements of 17.2%, 27.0%, and 35.9% in wirelength, the number of registers, and power consumption requirements, compared with the list scheduling method.

Due to the precedence constraints among vertices, the partitioning problem for dynamically reconfigurable FPGAs (DRFPGAs) is different from the traditional one. In this paper, we first derive logic formulations for the precedence constrained partitioning problems, and then transform the formulations into integer linear programs (ILPs). The ILPs can handle the precedence constraints and minimize cut sizes simultaneously. To enhance performance, we also propose a clustering method to reduce the problem size. Experimental results based on the Xilinx DRFPGA architecture show that our approach outperforms the list scheduling, the network flow based, and the probability based methods by respective average improvements of 46.6%, 32.3%, and 21.5% in cut sizes. Our approach is practical and scales well to larger problems; the empirical runtime grows close to linearly in the circuit size. More importantly, our approach is very flexible and can readily extend to the partitioning problems with various objectives and constraints, which makes the ILP formulations superior alternatives to the DRFPGA partitioning problems.

Process technology advances have made multimillion gate field programmable gate arrays (FPGAs) a reality. A key issue that needs to be solved in order for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures. Channel segmentation designs have been studied to some degree in much of the literature; the previous methods are based on experimental studies, stochastic models, or analytical analysis. In this paper, we address a new direction for studying segmentation architectures. Our method is based on graph-theoretic formulation. We first formulate a problem of finding the optimal segmentation architecture for two input routing instances and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient multi-level matching-based algorithm for general channel segmentation designs. Experimental results show that our method significantly outperforms the previous work. For example, our method achieves average improvements of 18.2% and 8.9% in routability in comparison with other work.

Due to the precedence constraints among vertices, the partitioning problem for time-multiplexed field-programmable gate arrays (TMFPGAs) is different from the traditional one. In this paper, we first derive logic formulations for the precedence-constrained partitioning problems and then transform the formulations into integer linear programs (ILPs). The ILPs can handle the precedence constraints and minimize cut sizes simultaneously. To enhance performance, we also propose a clustering method to reduce the problem size. Experimental results based on the Xilinx TMFPGA architecture show that our approach outperforms the list-scheduling (List), the network-flow-based (FBB-m) (Liu and Wong, 1998), and the probability-based (PAT) (Chao, 1999) methods by respective average improvements of 46.6%, 32.3% and 21.5% in cut sizes. Our approach is practical and scales well to larger problems; the empirical runtime grows close to linearly in the circuit size. More importantly, our approach is very flexible and can readily extend to the partitioning problems with various objectives and constraints, which makes the ILP formulations superior alternatives to the TMFPGA partitioning problems.

FPGA routing resources typically consist of segments of various lengths. Due to the segmented routing architectures, the traditional measure of wiring cost (wirelength, delay, congestion, etc) based on geometric distance and/or channel density is no longer accurate for FPGAs. Researchers have shown that the number of segments, instead of geometric (Manhattan) distance, traveled by a net is the most crucial factor in controlling the routing delay and cost in an FPGA. Further, the congestion information of a routing channel shall be measured by the available segments of specific lengths, instead of the density in a channel alone. In this paper, we propose an architecture-driven metric for simultaneous FPGA placement and global routing. The new metric considers the available segments and their lengths to optimize the wiring cost for placement and global routing. Experiments by employing a cluster growth placement and maze routing to demonstrate the new metric show respective average reductions of 8%, 20%, and 19% in the number of tracks used (area), maximum net delay, and average net delay based on the Lucent Technologies ORCA2C-like and the Xilinx XC4000EX-like architectures, compared with the traditional metric of geometric distance and channel density.

We present in this paper an efficient, flexible, and effective data structure, B*-trees for non-slicing floorplans. B*-trees are based on ordered binary trees and the admissible placement presented in [1]. Inheriting from the nice properties of ordered binary trees, B*-trees are very easy for implementation and can perform the respective primitive tree, operations search, insertion, and deletion in only O(1), O(1), and O(n) times while existing representations for non-slicing floorplans need at least O(n) time for each of these operations, where n is the number of modules. The correspondence between an admissible placement and its induced B*-tree is 1-to-1 (i.e., no redundancy); further, the transformation between them takes only linear time. Unlike other representations for non-slicing floorplans that need to construct constraint graphs for cost evaluation, in particular, the evaluation can be performed on B*-trees and their corresponding placements directly and incrementally. We further show the flexibility of B*-trees by exploring how to handle rotated, pre-placed, soft, and rectilinear modules. Experimental results on MCNC benchmarks show that the B*-tree representation runs about 4.5 times faster, consumes about 60% less memory, and results in smaller silicon area than the O-tree one [1]. We also develop a B*-tree based simulated annealing scheme for floorplan design; the scheme achieves near optimum area utilization even for rectilinear modules.

In this paper, we propose a unified wire sizing and perturbation algorithm for crosstalk-constrained performance optimization that is applicable to general routing structures. Our algorithm is based on a two-stage iterative technique: we first perturb all wires to the positions with the minimum delay, then we adjust the wire sizes to further optimize delay under crosstalk constraints. The unified wire sizing and perturbation technique has the property of unimodality, implying that there is a unique position resulting in the optimal delay and crosstalk. Applying these properties can dramatically reduce the search space and thus lead to a very efficient method to determine the best wire position and the optimal wire size. Experimental results show that our algorithm can achieve average improvements of 44.5% and 40.2% in delay without sacrificing area and crosstalk for the 0.18 /spl mu/m and 0.25 /spl mu/m process technologies, respectively. Further, we develop an effective incremental update technique that can substantially speed up the runtime. Empirically, this technique can reduce runtime by 10 times.

Due to the layout complexity in deep sub-micron technology, integrated circuit blocks are often not rectangular. However, literature on general rectilinear block placement is still quite limited. In this paper, we present approaches for handling the placement for arbitrarily shaped rectilinear blocks, based on a newly developed data structure called B*-trees. Experimental results show that our algorithm achieves optimal or near optimal block placement for benchmarks with multiple shaped blocks.

Article Optimal reliable crosstalk-driven interconnect optimization Share on Authors: Iris Hui-Ru Jiang Department of Electronics Engineering, National Chiao Tung University, Hsinchu 30010, Taiwan Department of Electronics Engineering, National Chiao Tung University, Hsinchu 30010, TaiwanView Profile , Song-Ra Pan Department of Computer and Information Science, National Chiao Tung University, Hsinchu 30010, Taiwan Department of Computer and Information Science, National Chiao Tung University, Hsinchu 30010, TaiwanView Profile , Yao-Wen Chang Department of Computer and Information Science, National Chiao Tung University, Hsinchu 30010, Taiwan Department of Computer and Information Science, National Chiao Tung University, Hsinchu 30010, TaiwanView Profile , Jing-Yang Jou Department of Electronics Engineering, National Chiao Tung University, Hsinchu 30010, Taiwan Department of Electronics Engineering, National Chiao Tung University, Hsinchu 30010, TaiwanView Profile Authors Info & Claims ISPD '00: Proceedings of the 2000 international symposium on Physical designMay 2000 Pages 128–133https://doi.org/10.1145/332357.332388Online:01 May 2000Publication History 6citation191DownloadsMetricsTotal Citations6Total Downloads191Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A switch block M with W terminals on each side is said to be universal if every set of nets satisfying the dimension constraint (i.e., the number of nets on each side of M is at most W) is simultaneously routable through M. In this paper, we present an algorithm to construct N-sided universal switch blocks with W terminals on each side. Each of our universal switch blocks has (/sub 2//sup N/) W switches and switch-block flexibility N-1 (i.e., F/sub S/=N-1). We prove that no switch block with less than (/sub 2//sup N/)W switches can be universal. We also compare our universal switch blocks with others of the topology associated with Xilinx XC4000-type FPGAs. To explore the area performance of the universal switch blocks, we develop a detailed router for hierarchical FPGAs (HFPGAs) with 5-sided switch blocks. Experimental results demonstrate that our universal switch blocks improve routability at the chip level. Based on extensive experiments, we also provide key insights into the interactions between switch-block architectures and routing.

Noise, as well as area, delay, and power, is one of the most important concerns in the design of deep submicrometer integrated circuits. Currently existing algorithms do not handle simultaneous switching conditions of signals for noise minimization. In this paper, we model not only physical coupling capacitance, but also simultaneous switching behavior for noise optimization. Based on Lagrangian relaxation, we present an algorithm which can optimally solve the simultaneous noise, area, delay, and power optimization problem by sizing circuit components. Our algorithm, with linear memory requirement and linear runtime, is very effective and efficient. For example, for a circuit of 6144 wires and 3512 gates, our algorithm solves the simultaneous optimization problem using only 2.1-MB memory and 19.4-min runtime to achieve the precision of within 1% error on a SUN Spare Ultra-I workstation.

In this paper we present a timing-driven router for symmetrical array-based FPGAs. The routing resources in the FPGAs consist of segments of various lengths. Researchers have shown that the number of segments, instead of wirelength, used by a net is the most critical factor in controlling routing delay in an FPGA. Thus, the traditional measure of routing delay on the basis of geometric distance of a signal is not accurate. To consider wirelength and delay simultaneously, we study a model of timing-driven routing rees, arising from the special properties of FPGA routing architectures. Based on the solutions to the routing-tree problem, we present a routing algorithm that is able to utilize various routing segments with global considerations to meet timing constraints. Experimental results show that our approach is very effective in reducing timing violations.

Noise, as well as area, delay, and power, is one of the most important concerns in the design of deep sub-micron ICs. Currently existing algorithms do not handle simultaneous switching conditions of signals for noise minimization. In this paper, we model not only physical coupling capacitance, but also simultaneous switching behavior for noise optimization. Based on Lagrangian relaxation, we present an algorithm which can optimally solve the simultaneous noise, area, delay, and power optimization problem by sizing circuit components. Our algorithm, with linear memory requirement overall and linear runtime per iteration, is very effective and efficient. For example, for a circuit of 6144 wires and 3512 gates, our algorithm solves the simultaneous optimization problem using only 1.8 MB memory and 47 minute runtime to achieve the precision of within 1% error on a SUN Sparc Ultra-I workstation. 1 Introduction With decreasing feature sizes, higher clock rates, and increasing interconnect...

No abstract available.

Improving logic density by time-sharing, time-multiplexed FPGAs (TMFPGAs) has become an important research topic for reconfigurable computing. Due to the precedence and capacity constraints in TMFPGAs, the clustering and partitioning problems for TMFPGAs are different from the traditional ones. We propose a two-phase hierarchical approach to solve the partitioning problem for TMFPGAs. With the precedence and capacity considerations for both phases, the first phase clusters nodes to reduce the problem size, and the second phase applies a probability-based iterative improvement approach to minimize cut cost. Experimental results based on the Xilinx TMFPGA architecture show that our algorithm significantly outperforms previous works.

A switch block M with W terminals on each side is said to be universal if every set of nets satisfying the dimension constraint (i.e., the number of nets on each side of M is at most W) is simultaneously routable through M (Y.W. Chang et al., 1996). We present an algorithm to construct N-sided universal switch blocks with W terminals on each side. Each of our universal switch blocks has (/sub 2//sup N/)W switches and switch-block flexibility N-1 (i.e., F/sub S/=N-1). We prove that no switch block with less than (/sub 2//sup N/)W switches can be universal. Further, the decomposition property of a universal switch block provides a key insight into its layout implementation with a smaller silicon area. We also compare our universal switch blocks with others of the topology associated with Xilinx XC4000-type FPGAs. Experimental results demonstrate that our universal switch blocks improve routability at the chip level.

An FPD switch module M with /spl omega/ terminals on each side is said to be universal if every set of nets satisfying the dimension constraint (i.e., the number of nets on each side of EA is at most /spl omega/) is simultaneously routable through M. Chang et al. (1996) have identified a class of universal switch blocks. In this paper, we consider the design and routing problems for another popular model of switch modules called switch matrices. Unlike switch blocks, we prove that there exist no universal switch matrices. Nevertheless, we present quasi-universal switch matrices which have the maximum possible routing capacities among all switch matrices of the same size and show that their routing capacities converge to those of universal switch blocks. Each of the quasi-universal switch matrices of size /spl omega/ has a total of only 14/spl omega/-20 (14/spl omega/-21) switches if /spl omega/ is even (odd), /spl omega/>1, compared to a fully populated one which has 3/spl omega//sup 2/-2/spl omega/ switches. We prove that no switch matrix with less than 14/spl omega/-20 (14/spl omega/-21) switches can be quasi-universal. Experimental results demonstrate that the quasi-universal switch matrices improve routability at the chip level.

Process technology advances will soon make the one-miilion gate FPGA a reality.A key issue that needs to be solved for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures [10].Onedimensional segmentation designs have been studied to some degree in much of the literature; most of the previously proposed methods are based on stochastic or analytical analysis.In this paper, we address a new direction for studying segmentation architwtures.Our method is based on graph-theoretic formulation.tire first formulate a net matching problem and present a polynomial-time optimal algorithm to solve the problem.Based on the solution to the problem, we develop an effective and eficient matching-based a!gonthm for FPGA segmentation designs.Eqem.mental results show that our method significantly outperforms previous work. For uample,our method achieves averagw of 18.2% and 8.9% improvements m routability, compared with the work in [lJ] and the most recent work in [7], respectively.More importantly, our approaches are vey flm.ble and can Teadi[y utend to higherorder segmentation designs (e.g., two-or three-dimensional segmentation design, etc), which aTe crucial to the design of large-scale FPGAs.

In this paper, we present a timing-driven global router for symmetrical-array-based FPGAs. The routing resources in the symmetrical-array-based FPGAs consist of segments of various lengths. Researchers have shown that the number of segments, instead of wirelength, used by a net is the most critical factor in controlling routing delay in an FPGA. Thus, traditional measure of routing delay based on the geometric distance of a signal is not accurate. To consider wirelength and delay simultaneously, we study a model of timing-driven routing trees, arising from the special properties of FPGA routing architectures. We explore the complexity of the routing-tree problem and present efficient and effective approximation algorithms for the problem. Based on the solutions to the routing-tree problem, we present a global-routing algorithm which is able to utilize various routing segments with global consideration to meet the timing constraints. Experimental results on benchmark circuits show that our approach is promising.

An FPD switch module M with w terminals on each side is said to be universal if every set of nets satisfying the dimensional constraint (i.e., the number of nets on each side of M is at most w) is simultaneously routable through M [8]. Chang, Wong, and Wong have identified a class of universal switch blocks [8]. In this paper, we consider the design and routing problems for another popular model of switch modules called switch matrices. Unlike switch blocks, we prove that there exist no universal switch matrices. Nevertheless, we present quasi-universal switch matrices which have the maximum possible routing capacities among all switch matrices of the same size, and show that their routing capacities converge to those of universal switch blocks. Each of the quasi-universal switch matrices of size w has a total of only 14w - 20 (14w - 21) switches if w is even (odd), w > 1, compared to a fully populated one which has 3w2 - 2w switches. We prove that no switch matrix with less than 14w - 20 (14w - 21) switches can be quasi-universal. Experimental results demonstrate that the quasi-universal switch matrices improve routabilty at the chip level.

Abstract — We consider a switch module routing problem for symmetrical-array field-programmable gate arrays (FPGA’s). This problem was first introduced in [21]. They used it to evaluate the routability properties of switch modules which they proposed. Only an approximation algorithm for the problem was proposed by them. We give an optimal algorithm for the problem based on integer linear programming (ILP). Experiments show that this formulation leads to fast and efficient solutions to practical-sized problems. We then propose a precomputation that eliminates the need to use ILP on-line. We also identify special cases of this problem that reduce to problems for whom efficient algorithms are known. Thus, the switch module routing problem can be solved in polynomial time for these special cases. Using our solution to the switch module routing problem, we propose a new metric to estimate the congestion in each switch module in the FPGA. We demonstrate the use of this metric in a global router. A comparison with a global router guided by the density of the routing channels shows that our metric leads to far superior global and detailed routing solutions. Index Terms—Field-programmable gate array, global routing. I.

Delay, power, skew, area, and sensitivity are the most important concerns in current clock-tree design.We present in this paper an algorithm for simultaneously optimizing the above objectives by sizing wires and buers in clock trees.Our algorithm, based o n L agrangian relaxation method, can optimally minimize delay, power, and area simultaneously with very low skew and sensitivity.With linear storage overall and linear runtime per iteration, our algorithm is extremely economical, fast, and accurate; for example, our algorithm can solve a 6201-wire-segment clock-tree p r oblem using about 1-minute runtime and 1.3-MB memory and still achieve pico-second precision on an IBM RS/6000 workstation.

No abstract available.

A switch module M with W terminals on each side is said to be universal if every set of nets satisfying the dimensional constraint (i.e., the number of nets on each side of M is at most W ) is simultaneously rout able through M . In this article, we present a class of universal switch modules. Each of our switch modules has 6 W switches and switch-module flexibility three (i.e, F s =3). We prove that no switch module with less than 6 W switches can be universal. We also compare our switch modules with those used in the Xilinx XC4000 family FPGAs and the antisymmetric switch modules (with F S =3) suggested by Rose and Brown [1991]. Although these two kinds of switch modules also have F S =3 and 6 W switches, we show that they are not universal. Based on combinatorial counting techniques, we show that each of our universal switch modules can accommodate up to 25% more routing instances, compared with the XC4000-type switch module of the same size. Experimental results demonstrate that our universal switch modules improve routability at the chip level. Finally, our work also provides a theoretical insight into the important observation by Rose and Brown [1991] (based on extensive experiments) that F S =3 is often sufficient to provide high routability.

Unlike traditional ASIC routing, the feasibility of routing in FPGAs is constrained not only by the available space within a routing region, but also by the routing capacity of a switch block. Recent work has established the switch-block capacity as a superior congestion-control metric for FPGA global routing. However, the work has two deficiencies: (1) its algorithm for computing the switch-block capacity is not efficient, and (2) it, as well as the other recent works only modeled one type of routing segments-single-length lines. To remedy the deficiencies, we present in this paper efficient algorithms for obtaining the switch-block capacity and a graph modeling for routing on the new generation FPGAs with a versatile set of segment lengths. Experiments show that our algorithms dramatically reduce the run times for obtaining the switch-block capacities. Experiments with a global router based on the switch-block and channel densities for congestion control show a significant improvement in the area performance, compared with one based on the traditional congestion metric.

Switch modules are the most important component of the routing resources in FPGAs and FPICs. The quality of switch modules greatly affects FPGA/FPIC routing solutions. The switch-module design problem was studied by K. Zhu et al. (1993). In order to analyze the routability of designed switch modules, a heuristic algorithm based on network-flow techniques was proposed. In this paper, we mathematically show that the network-flow based algorithm has provably good performance with the bounds 5 and 5/4 away from the optima for two types of switch modules, respectively. Based on the analyses, we developed a new method for designing switch modules. Experimental results show that our designed switch modules significantly improve routability, compared with those by K. Zhu et al. Extensive experiments also show that the network-flow based algorithm is highly accurate and runs very efficiently.

We address the problem of designing switch modules for FPGAs and FPICs to maximize routability under area and delay constraints. The switch module design problem is closely related to two-dimensional segmentation design for FPGAs and FPICs. We study the properties of switch modules and present an algorithm for switch module design. We also present an algorithm to analyze the routability of a given switch module.