In advanced technology nodes, it is becoming common to mix standard cells with different heights in the same design to optimize timing, power, and routability simultaneously. In this paper, we explore the placement problem of mixed-cell-height designs that include half-row-extended (HRE) cells and conventional single-row-height cells. An HRE cell is like a conventional single-row-height cell extended by half a row both upward and downward, resulting in a double-row-height cell. The advantage of an HRE cell is its superior driving strength compared to a conventional double-row-height cell, where both the top and bottom cell boundaries are aligned with power or ground rails. But mixing HRE cells with conventional single-row height cells may result in a less compact placement, which adversely affects the wirelength and/or the chip size. To address the placement challenges introduced by HRE cells, we propose a two-level placement framework: (1) HRE cell-aware global placement and (2) half-row-fragment-aware legalization. During the global placement, we estimate the potential area overhead caused by the HRE cells and identify groups of HRE cells that should be placed close to one another to control the whitespace distribution while minimizing the wirelength. Then, we invoke FragmentSaver, a legalizer that leverages deadspace cost curves to reduce row fragmentation with minimal displacement. Experimental results show that, compared to the state-of-the-art mixed-cell-height placer RePIAce [8], our method resulted in significant reductions in routed wirelength and cell displacement.

Trapped-ion quantum computers offer high-fidelity operations, long coherence times, and all-to-all connectivity within a single trap. However, scaling to large circuits is limited by the trap's ion capacity. The QCCD architecture addresses this by enabling ion shuttling across multiple traps, but excessive shuttling increases execution time and degrades fidelity. This paper presents an improved ion-shuttling approach targeting linear QCCD architectures. Building on a state-of-the-art approach [27] for linear trapped-ion devices, our approach introduces a front-layer-based scheduling method that dynamically prioritizes executable gates, along with a novel destination trap selection method for ion-shuttling, effectively reducing unnecessary ion movements. We also present a look-ahead gate selection strategy based on the gate dependency graph, avoiding the high runtime of the gate proximity approach used in the state-of-the-art approach, especially in circuits with all-to-all communication. Our approach achieves up to a 37.67% reduction in shuttle count and up to a 74.91% reduction in compilation time compared to the state-of-the-art approach for linear trapped-ion devices on actual NISQ benchmarks and synthetic circuits. On average, our approach achieves a 16.44% reduction in shuttle count and a 30.77% reduction in compilation time across all test cases. These improvements highlight the effectiveness of our approach, particularly for actual circuits.

Very large scale integration (VLSI) circuits typically consist of millions of nets, posing significant challenges for efficient physical design. Interconnect delay has become a critical factor for timing performance in technology nodes at 5nm and beyond. Additionally, the coupling effect among the wires increases the complexity of delay optimization. Moreover, tapering constraints are essential in advanced technology nodes to ensure manufacturability. Furthermore, the ever-increasing scale of modern designs necessitates a high-performance computing (HPC) framework to accelerate delay-driven layer assignment in advanced technology nodes. To address these challenges, we propose ParDelay, a parallel delay-driven layer assignment leveraging hierarchical task graph modeling while considering tapering constraints for advanced technology nodes, which includes the following five key techniques: 1) A general deterministic parallel framework is proposed for delay-driven layer assignment, leveraging a hierarchical task graph to enable both internet and inter-node parallelism. 2) A delay- and overflow-driven tapering repairing strategy is proposed to eliminate tapering violations while further optimizing net delay. 3) A local delay-critical net filtering method is proposed to analyze local delay criticality to guide layer assignment, thereby minimizing delay while eliminating overflow. 4) To mitigate the coupling effect, we propose a net shielding algorithm that reduces wire density for maximum delay candidate nets to optimize maximum delay. 5) A delay-aware refinement strategy is proposed to classify nets by their delay rank and assign distinct non-default-rule (NDR) wire permissions and refinement objectives, thereby reducing delay. Experimental results demonstrate that, compared to existing layer assignment algorithms and parallel routing frameworks, our approach effectively reduces delay, via count, and runtime under the tapering constraints.

This article introduces GenPart 2.0, an enhanced version of the hypergraph partitioner GenPart. While GenPart was limited to handling only unit vertex weights, GenPart 2.0 extends capabilities to include varying vertex weights. This extension is achieved through a variational graph neural network-based generative model and new feature preparation techniques. GenPart 2.0 addresses hypergraph partitioning challenges by establishing an embedding space that adheres to normalized cut and balance constraints. The generative model in GenPart 2.0 is designed to explore various partitioning configurations within this embedding space. Further, it enhances partitioning solutions using the V-cycle method. Testing on VLSI circuit benchmarks, including ISPD98, ISPD2005, and Titan23, under various balance constraints, has demonstrated improved performance by GenPart 2.0.

This paper introduces GPart, a scalable multilevel framework for graph partitioning that integrates GNN embeddings with efficient coarsening and refinement techniques. On the Titan23 benchmarks, GPart achieves a cut size reduction of 34.13% to 42.92% over METIS and improves cut size by 9.30% on selected DIMACS benchmarks compared to G-kway. Furthermore, experiments on the Titan23 benchmarks show that GPart reduces normalized memory usage by 24.6x compared to GAP and 12.4x compared to GenPart. Unlike existing GNN-based methods, which require large hidden layers and substantial memory, GPart’s multilevel architecture reduces hidden layer sizes, significantly optimizing memory efficiency.

In the physical design flow, detailed placement is critical for wirelength optimization and routability enhancement. While many CPU-based approaches emphasize wirelength reduction, GPU-based approaches primarily focus on accelerating detailed placement without sacrificing quality. However, leveraging GPU parallelism to further improve placement quality remains largely underexplored. As existing optimization steps have approached the practical limits of wirelength optimization, achieving further improvements has become increasingly challenging. In this work, we propose a GPU-based detailed placement flow featuring Simultaneous Row and Order Assignment (SROA) step, a novel step that integrates dynamic programming-based row assignment with heuristic-based cell position adjustment. SROA enables efficient exploration of a significantly larger solution space on GPUs. Experimental results show that our approach preserves routability while reducing detailed routing wirelength and via count by 1.35% and 1.03%, respectively, compared to the ABCDPlace solutions.

Vision Transformer models have become a powerful class of deep learning models, excelling in various computer vision tasks. Their integration into safety-critical systems necessitates a robust understanding of their reliability. This is particularly crucial due to the rising vulnerability of modern computing systems to transient faults, namely soft errors. In this paper, we analyze the reliability of Vision Transformer models in the presence of soft errors by employing parameter fault injection. We also propose a simple yet highly effective technique against soft errors, which can enhance the reliability by restoring the Top-1 accuracy of Vision Transformer models on the ImageNet-1K dataset to nearly original levels.

The Steiner minimum tree (SMT) serves as an optimal connection model for multiterminal nets in very large scale integration (VLSI). Constructing both rectilinear SMT (RSMT) and octilinear SMT (OSMT) are known to be NP-hard problems. Simultaneously, constructing multiple topologies of SMTs for a given net holds significant importance in alleviating routing constraints such as alleviating congestion and ensuring timing convergence. However, existing efforts predominantly focus on designing specialized methods to construct a specifically structured SMT for a given net, making it challenging to extend to different structures or topologies of SMTs, while also exhibiting insufficient optimization capabilities. In this work, we propose a unified approach based on deep reinforcement learning (DRL) to address both RSMT and OSMT problems while generating diverse routing topologies. First, we design an edge point sequence (EPS) that leverages the structural characteristics of SMT to connect the output of the deep learning model with the SMT structure. Second, we propose a deep learning model tailored for EPS, employing the negative wirelength of SMT as a reward to train the model using DRL. Third, we provide a corresponding rapid and accurate wirelength computation algorithm for evaluating the quality of the construction solution to expedite model training. Finally, we leverage the stochastic nature of machine learning to construct diverse SMT construction solutions. To the best of our knowledge, this is the first unified approach capable of simultaneously addressing both RSMT and OSMT problems while generating diverse solutions. The proposed unified approach demonstrates superior solution quality and higher efficiency compared to specifically designed algorithms.

Routability has always been a significant challenge in Very Large Scale Integration (VLSI) design. To overcome the potential mismatch between the global routing results and the detailed routing requirements, track assignment is introduced to achieve an efficient routability estimation. Moreover, with the increasing scale of circuits, the intricate interconnections among the components on the chip lead to increased timing delay in signal transmission, thereby significantly impacting the performance and reliability of the circuit. Thus, to further improve the routability of the circuit, it is also critical to realize an accurate estimation of the timing delay within the track assignment stage. Existing heuristic track assignment algorithms, however, are prone to local optimality, and thus fail to provide accurate routability estimations. In this article, we propose an enhanced scalable parallel track assignment algorithm called SPTA 2.0 for VLSI design, employing a two-stage partition strategy and considering timing delay. First, the proposed algorithm achieves efficient assignment of all wires by considering the routing information from both the global and local nets. Second, the overlap cost, the blockage cost, and the wirelength cost can be minimized to significantly improve the routability. Third, a critical wire controlling strategy is proposed to optimize signal timing delays inside nets. Finally, a two-stage partition strategy and a panel-subpanel-level parallelism are designed to further reduce the runtime, improving the scalability of the proposed methodology. Experimental results on multiple benchmarks demonstrate that the proposed method provides better routability estimations, and leads to superior track assignment solutions compared with existing algorithms.

While GPU-based placers have demonstrated significant speed advantages over their CPU-based counterparts, hyperparameter tuning remains a bottleneck, often requiring substantial human intervention and expert knowledge. This challenge is particularly critical given the urgent need for rapid time-to-market solutions. Recently, Large Language Models (LLMs) have exhibited remarkable capabilities in zero-shot learning, context understanding, logical reasoning, and answer generation. In this work, we introduce HyperPlace, an innovative paradigm that leverages an off-the-shelf LLM to automate hyperparameter optimization using in-context learning techniques. Our approach transcends single-output black-box optimization methods by incorporating a batch optimization mechanism that evaluates multiple hyperparameter configurations simultaneously across several GPU computing platforms. We validated the effectiveness of our approach in placement quality, measured by Half-Perimeter Wire Length (HPWL), using DREAMPlace 2.0. To further demonstrate the capability of integrating our framework with other placers, we conducted additional experiments using Xplace 2.0. By employing the ISPD2005 benchmarks for our evaluation, HyperPlace enhances the placement tools with up to a 1.66% reduction in HPWL compared to their published results. Additionally, we evaluated HyperPlace on the ISPD2015 benchmarks, which incorporate fence region constraints not present in ISPD2005 benchmarks. Under these more complex constraints, HyperPlace achieves up to a 22.24% reduction in HPWL compared to the default settings of the placement tools, further demonstrating its adaptability across diverse placement scenarios and benchmark suites.

As design rules become more complex in new technology nodes, signal routing presents increasing challenges. In order to reduce the complexity, routing is typically divided into global routing (GR) and detailed routing (DR). However, a feasible GR solution may not always translate to a feasible DR solution due to resource mismatches between the two stages. In this work, we propose capacity reduction techniques that are applied in GR while aiming to enhance detailed-routability and bridge the mismatches between GR and DR. Encouraging experimental results demonstrate that after including the proposed capacity reduction techniques, the outdated open-source global router NTHU-Route 2.0 is revitalized and outperforms the state-of-the-art global router of TritonRoute-WXL. We achieve all DRC-clean solutions with 7.8% less via usage, 29% less non-preferred usage, and 2% DR quality score improvement while only increasing wirelength by 0.4%. Additionally, our GR runtime and DR runtime are respectively 44% and 31% shorter.

Separating the power delivery network (PDN) from the front-side metal stack and using the back-side metal stack primarily for the PDN has been proposed to improve the PDN performance. To well utilize the surplus routing resources left on the back side after the PDN is built, we study in this paper how to route signal nets on both front and back sides (i.e. double-sided signal routing). To this end, we present a netlist planning approach that is able to well distribute a set of signal nets to two sides and properly insert a set of bridging cells such that after performing placement legalization and signal routing on each side separately, a high-quality double-sided routing solution can be produced. Our netlist planning approach has been combined with a commercial place and route tool, and our experimental results show that compared to traditional single-sided routing without back-side PDN, double-sided routing achieves 9.1% reduction in wirelength and 1.8% decrease in via count. Additionally, for critical nets, the percentage of the total length of their wire segments routed on preferred metal layers were improved by 13.6%.

Reverse engineering is a process that converts low-level description to high-level one. In this paper, we propose a hybrid approach consisting of structural analysis and black-box testing to reverse engineering on combinational circuits. Our approach is able to convert combinational circuits from gate-level netlist to Register-Transfer Level (RT-level) design accurately and efficiently. We developed our approach and participated in Problem A of the 2022 CAD Contest @ ICCAD. The revised version of our program successfully converted most cases and achieved higher scores than the 1stplace team in the contest.

To improve the power delivery network (PDN) efficiency under the consideration of scaling trends, back-side PDN has been proposed. To well utilize the remaining routing resources on the back side after constructing the PDN, a pioneering work [4] introduced a netlist planning flow capable of distributing a set of signal nets to both sides for routing. However, it failed to consider the routing blockages of the PG network, and the overlapping regions between bounding boxes of pins assigned to the front side and back side, respectively, leading to sub-optimal wirelength. To mitigate these drawbacks, we propose a PG-aware capacity calculation to adjust the bridging cell capacities and the routing capacities for accurate back-side routing resource estimation and a bounding box-based netlist planning approach. Compared to [4], our method resulted in 2% reduction in the average wirelength and 6.4% improvement in the average timing score for the critical nets. Compared to a netlist planning method that leveraged a commercial tool, our approach reduced the average wirelength by 7.4% and improved the average timing score for the critical nets by 22.2%.

This paper introduces GenPart, a novel hypergraph partitioner that utilizes a variational graph convolutional network-based generative model to significantly enhance partitioning performance. Traditional partitioning approaches, including multi-level and spectral partitioning, often struggle to preserve the intrinsic structure of hypergraphs, resulting in suboptimal cut performance. GenPart addresses these challenges by creating a sophisticated embedding space, compliant with normalized cut and balance constraints, and further refined by incorporating the V-cycle method. Through generative modeling, GenPart explores a variety of new and diverse partitioning configurations within this embedding space, demonstrating superiority on several VLSI circuit benchmarks and notably outperforming well-established partitioners. Rigorous testing on ISPD98, Titan23, and ISPD2005 benchmarks under varied balance constraints has proven GenPart's efficacy. Notably, on the ISPD98 benchmarks, GenPart has demonstrated the best records on 16 out of 18 instances for a balance factor of 2% and on all 18 instances for a balance factor of 10%, outperforming other state-of-the-art methods such as hMETIS, SpecPart, K-SpecPart, and MedPart. These impressive gains not only confirm GenPart's effectiveness but also suggest that it may serve as a pioneering approach in hypergraph partitioning.

In response to the continuous scaling of technology nodes, a dedicated back-side metal stack for the power delivery network (PDN) has been proposed to enhance performance. To fully utilize the remaining routing resources left after the back-side PDN construction, netlist planning has been introduced to transform single-sided netlists into double-sided ones, thus enabling double-sided signal routing. However, since netlist planning precedes routing, it may overlook certain elements, leading to design rule violations (DRVs) on the back side. Addressing these DRVs during the implementation of engineering change orders (ECOs) requires designers to correct all violations remaining after place-and-route (P&R), a process that demands substantial manual effort. It has been observed that back-side DRVs mainly stem from excessive competition among back-side nets for limited routing resources. These DRVs cannot be easily resolved by merely refining P&R on the back side; adjustments to the netlists on both sides are crucial as well. Therefore, this work introduces an innovative ECO methodology that integrates netlist adjustments with P&R refinement on both sides to effectively reduce back-side DRVs in double-sided signal routing while preventing the creation of new front-side DRVs. This marks a pioneering effort in tackling this issue. Experiments show that our methodology resolves 100% back-side DRVs from various netlist planning strategies across 14 test cases while keeping similar routing quality.

The physical qubits in current quantum computers do not all interact with each other. Therefore, in executing a quantum algorithm on an actual quantum computer, layout synthesis is a crucial step that ensures that the synthesized circuit of the quantum algorithm can run smoothly on the quantum computer. In this paper, we focus on a layout synthesis problem for quantum circuits and improve a prior work, TB-OLSQ, which adopts a transition-based satisfiability modulo theories (SMT) formulation. We present how to modify TB-OLSQ to obtain an accelerated version for runtime reduction. In addition, we extend the accelerated version by considering gate absorption for better solution quality. Our experimental results show that compared with TB-OLSQ, the accelerated version achieves 121X speedup for a set of SWAP-free circuits and 6X speedup for the other set of circuits with no increase in SWAP gates. In addition, the accelerated version with gate absorption helps reduce the number of SWAP gates by 38.9% for the circuits requiring SWAP gates, while it is also 3X faster.

Professor Martin D. F. Wong is well recognized as a distinguished figure in the community of physical design, owing to his numerous and noteworthy contributions. This talk aims to highlight his pioneering works in the field of automatic floorplan design. Professor Wong's profound insights and innovative approaches have not only propelled advancements in the field but also served as an inspirational source for other researchers.

Macro legalization is an important physical design problem for mixed-size circuits. Unlike previous studies that mainly focus on obtaining a non-overlapping macro placement with minimal total displacement, this work considers the minimization of the total macro displacement and the total standard-cell non-placeable area subject to the minimum channel spacing constraint and the buffer area reservation constraint. An effective approach is proposed to tackle the addressed problem. Encouraging experimental results are shown to support the robustness of our approach.

A new cell-based design paradigm that mixes short rows and tall rows in a layout has emerged to better optimize power, performance and area. We present an effective approach to tackle the placement legalization problem for such hybrid-row-height designs. It takes advantage of the availability of multiple versions of the same cell with different heights and widths to incorporate a cell version change mechanism in the legalization process. Considering cell variants can reduce the required cell displacement from the initial global placement solution and ensure that there is no unlegalizable cell due to the overuse of either kind of resources (short rows or tall rows). Promising experimental results showed the effectiveness of our legalization approach under different row configurations.

Neural networks have become an attractive choice for audio applications, but they are known to suffer from adversarial examples. In this work, we propose a method for detecting adversarial examples of a keyword spotting system. We design convolutional neural networks for metric learning to map the internal representation of each layer of an input audio to a low-dimensional feature space. We then extract the distance information from the feature space of each layer and feed it into an LSTM network to determine whether the input audio is clean or adversarial. Promising experimental results are shown to support our detector.

Conventional global placement algorithms typically assume that all cell rows in a design have the same height. Nevertheless, a design making use of standard cells with short-row height, tall-row height, and double-row (short plus tall) height can provide a better sweet spot for performance and area co-optimization in advanced nodes. In this paper, we assume for a hybrid-row-height design, its placement region is composed of both tall rows and short rows, and a cell library containing multiple versions of each cell in the design is provided. We present a new analytical global placer, HybridGP, for such hybrid-row-height designs. Furthermore, we assume that a subset of cells with sufficient timing slacks is given so that we may change their versions without overall timing degradation if desired. Our approach considers the usage of short-row and tall-row resources and exploits the flexibility of cell version change to facilitate the subsequent legalization stage. Augmented with an identical legalizer for final placement legalization, we compared HybridGP with a conventional global placer. The experimental results show that legalized placement solutions of much better quality can be obtained in less run time with HybridGP.

Multi-bit flip-flops (MBFFs) are often used to reduce the number of clock sinks, resulting in a low-power design. A traditional MBFF is composed of individual FFs of uniform driving strength. However, if some but not all of the bits of an MBFF violate timing constraints, the MBFF has to be sized up or decomposed into smaller bit-width combinations to satisfy timing, which reduces the power saving. In this paper, we present a new MBFF generation approach considering mixed-driving MBFFs whose certain bits have a higher driving strength than the other bits. To maximize the FF merging rate (and hence to minimize the final amount of clock sinks), our approach will first perform aggressive FF merging subject to timing constraints. Our merging is aggressive in the sense that we are willing to possibly oversize some FFs and allow the presence of empty bits in an MBFF to merge FFs into MBFFs of uniform driving strengths as much as possible. The oversized individual FFs of an MBFF will be later downsized subject to timing constraints by our approach, which results in a mixed-driving MBFF. Our MBFF generation approach has been combined with a commercial place and route tool, and our experimental results show the superiority of our approach over a prior work that considers uniform-driving MBFFs only in terms of the clock sink count, the FF power, the clock buffer count, and the routed clock wirelength.

Timing optimization has always been a key issue affecting the chip performance. Most of the previous layer assignment algorithms mainly optimize timing from the perspective of interconnect delay, and often ignore the impact of slew on signal integrity. Therefore, this paper proposes LA-SVR, a high-performance layer assignment algorithm with slew violations reduction. The proposed algorithm mainly includes three key techniques: 1) an effective classified reassignment strategy is proposed to re-assign nets in terms of different optimization priorities for overflow avoidance; 2) an effective net adjustment method is adopted to reduce the potential slew violations; 3) a layer restricting strategy is proposed to optimize delay of nets and slew violations simultaneously by restricting the candidate better routing layers of different nets. Experimental results show that the proposed algorithm has a significant effect on slew violations reduction.

Routability has always been a very challenging issue in Very Large Scale Integrated (VLSI) circuit design. The routability is considered in track assignment so that the global routing results can better match the requirements of detailed routing. However, existing heuristic track assignment algorithms are prone to local optimality, which cannot provide the accurate routability estimation. To overcome this limitation, we propose a scalable parallel Integer Linear Programming (ILP)-based track assignment algorithm, called SPTA, which employs a two-stage partition strategy. First, by taking into account both the global and local nets, all wires are assigned to tracks, making full use of the information from the global routing results. Second, an efficient ILP model for track assignment is proposed to minimize the overlap between iroutes1, thus significantly improving routability. Third, a two-stage partition strategy is designed to reduce the runtime. Finally, a panel-subpanel-level parallelism is proposed to further speed up the algorithm without sacrificing the quality of the solutions. Experimental results show that SPTA has a better routability estimation compared with the existing algorithms.

Deep Neural Network (DNN) is gaining popularity thanks to its ability to attain high accuracy and performance in various security-crucial scenarios. However, recent research shows that DNN-based Automatic Speech Recognition (ASR) systems are vulnerable to adversarial attacks. Specifically, these attacks mainly focus on formulating a process of adversarial example generation as iterative, optimization-based attacks. Although these attacks make significant progress, they still take large generation time to produce adversarial examples, which makes them difficult to be launched in real-world scenarios. In this article, we propose a real-time attack framework that utilizes the neural network trained by the gradient approximation method to generate adversarial examples on Keyword Spotting (KWS) systems. The experimental results show that these generated adversarial examples can easily fool a black-box KWS system to output incorrect results with only one inference. In comparison to previous works, our attack can achieve a higher success rate with less than 0.004 s. We also extend our work by presenting a novel ensemble audio adversarial attack and testing the attack on KWS systems equipped with existing defense mechanisms. The efficacy of the proposed attack is well supported by promising experimental results.

Interconnect delay is a key factor that affects the chip performance in layer assignment. Particularly in the advanced process technologies of 5 nm and beyond, interconnect delay has grown significantly due to the increase of circuit scale. Moreover, coupling effect existed in wires reduces the accuracy of delay evaluation. On the other hand, the size of vias is often ignored in layer assignment, which enlarges the mismatch between global routing and detailed routing. To solve these problems, we proposeVPT, a timing-aware layer assignment algorithm considering via pillars, which includes the following five key techniques: 1) via pillar structure combined with nondefault-rule (NDR) wires is adopted to form a net delay optimization system for advanced process technologies; 2) a synthetical model that can adapt to varying types and sizes of both vias and wires is designed to evaluate overflow effectively; 3) a sorting strategy is devised to reduce uncertainty of layer assignment flow and improve stability of the proposed algorithm; 4) an awareness strategy based on multiaspect congestion assessment is designed to reduce overflow significantly; and 5) a net scalpel algorithm is devised to minimize the maximum delay of nets, so that the timing behaviors can be improved systematically. The experimental results on multiple benchmarks confirm that the proposed algorithm leads to lower delay and less overflow, while achieving the best solution quality among the existing algorithms with the shortest runtime.

Conventional lithography techniques are unable to achieve the resolution required by advance technology nodes. Multiple patterning lithography (MPL) has been introduced as a viable solution. Besides, new standard cell structure with multiple middle-of-line (MOL) layers is adopted to improve intra-cell routability. A mixed-cell-height standard cell library, consisting of cells of single-row and multiple-row heights, is also used in designs for power, performance and area concerns. As a result, it becomes increasingly difficult to get a feasible placement for a mixed-cell-height design where multiple cell layers require MPL. In this paper, we present a methodology to refine a given mixed-cell-height standard cell placement for satisfying MPL requirements on multiple cell layers as much as possible, while minimizing the total cell displacement. We introduce the concept of uncolored cell group (UCG) to facilitate the effective removal of coloring conflicts. By eliminating UCGs without generating any new coloring conflict around them, the number of UCGs is effectively reduced in the local and global refinement stages of our methodology. We report promising experimental results to demonstrate the efficacy of our methodology.

Previous methods of performing adversarial attacks against speech recognition systems often treat this problem as a solely optimization problem and require iterative updates to generate optimal solutions. Although they can achieve high success rate, the process is too computational heavy even with the help of GPU. In this paper, we introduce a new type of real-time adversarial attack methodology, which applies Recurrent Neural Networks (RNN) with a two-step training process to generate adversarial examples targeting a Keyword Spotting (KWS) system. We extend our attack to physical world by adding extra constraints in order to eliminate the distortions in real world. In the experiment, we launch a real-time adversarial attack on the KWS system both in digital and physical world. The experimental results of digital world show that the execution time of our attack is more than 400 times faster than the state-of-the-art attack (i.e., C&W attack) with the comparable attack success rate. In physical world, after adding extra constraints, the perturbation becomes more robust such that the average attack success rate increases from 40.3% to 84.3%.

Layer assignment, a major step in global routing of integrated circuits, is usually performed to assign segments of nets to multiple layers. Besides the traditional optimization goals such as overflow and via count, interconnect delay plays an important role in determining chip performance and has been attracting much attention in recent years. Accordingly, in this paper, we propose MiniDelay, a timing-aware layer assignment algorithm to minimize delay for advanced technology nodes, taking both wire congestion and coupling effect into account. MiniDelay consists of the following three key techniques: 1) a non-default-rule routing technique is adopted to reduce the delay of timing critical nets, 2) an effective congestion assessment method is proposed to optimize delay of nets and via count simultaneously, and 3) a net scalpel technique is proposed to further reduce the maximum delay of nets, so that the chip performance can be improved in a global manner. Experimental results on multiple benchmarks confirm that the proposed algorithm leads to lower delay and few vias, while achieving the best solution quality among the existing algorithms with the shortest runtime.

As feature size continues to shrink and design complexity continues to increase, a circuit layout has become more difficult to verify than before. Rule-based pattern matching is considered as a practical approach for layout verification, but unlike traditional ones, this paper focuses on three kinds of rules and presents an efficient pattern matching algorithm. Given a layout and a set of rules, our algorithm first adopts a line sweep method to scan the layout twice such that for each given rule, it collects all pairs of polygons satisfying that rule. It then bases on the collected polygon pairs to find all layout patterns each of which meets the given set of all rules. Experimental results show that our algorithm is able to find the correct set of matched patterns efficiently for each test case.

In this paper, we present a mixed-height standard cell placement flow for digital circuit blocks. To our best knowledge, commercial tools currently do not support this type of flow in a fully automated manner. In our placement flow, we leverage a commercial placement tool and integrate it with several new point tools. Promising experimental results are reported to demonstrate the efficacy of our placement flow.

This paper presents a routability-driven track assignment algorithm (RDTA) to efficiently estimate routability. Routability has become a very challenging issue in modern IC design and it can be effectively estimated by routing congestion. Track assignment is a stage towards bridging the gap between global routing and detailed routing. And track assignment can also analyze routing congestion more accurate than other routing stages like global routing. Some works have used track assignment to estimate routability. In this work, wire segments extracted from a global routing solution are assigned to proper tracks considering local nets, via locations and pin access. The overlap between wire segments extracted from a global routing solution can be effectively reduced by the algorithm so that the solution of RDTA can effectively estimate the routability.

Multi-cell spacing constraints arise due to aggressive scaling and manufacturing issues. For example, we can incorporate multi-cell spacing constraints due to pin accessibility problem in sub-10nm nodes. This work studies detailed placement considering multi-cell spacing constraints. A naive approach is to model each multi-cell spacing constraint as a set of 2-cell spacing constraints, but the resulting total cell displacement would be much larger than necessary. Thus, we aim to tackle this problem and propose a practical multi-cell method by first analyzing the initial layout to determine which cell pair in each multi-cell spacing constraint is the easiest to break apart. Secondly, we apply a single-row dynamic programming (SRDP)-based method one row at a time, called Intra-Row Move (IRM) to resolve a majority of violations while minimizing the total cell displacement or wirelength increase. With cell virtualization and movable region computation techniques, our IRM can be easily extended to handle mixed cell-height designs with only a slight modification of the cost computation in the SRDP method. Finally, we apply an integer linear programming-based method called Global Move (GM) to resolve the remaining violations. Experimental results indicate that our multi-cell method is much better than a 2-cell method both in solution quality and runtime.

This paper addresses a delay-driven layer assignment problem with consideration of via delay and coupling effect in the global routing stage. A negotiation-based framework is proposed to balance delay, congestion, and via count. Coupling capacitance is considered using a probabilistic look-up table. Finally, the proposed algorithm uses both parallel wires and wide wires to reduce wire delay. The effectiveness of our layer assignment algorithm is supported by extensive experimental results.

In this paper, we study the problem of refining a standard cell placement for self-aligned double patterning (SADP), which asks to simultaneously refine a detailed placement and find a valid SADP layout decomposition such that both overlay violation and wirelength are as small as possible. We first present an algorithm that adopts the technique of white space insertion for an SADP-aware single-row cell placement problem. Based on the single-row algorithm, we then describe an approach to the addressed placement refinement problem. Finally, we report encouraging experimental results to support the efficacy of our approach.

Routability has become a very challenging issue in a modern VLSI design flow. Many works use global routing to estimate the routability in the early design stages. However, global routing cannot accurately capture local congestion, so it is hard to detect the detailed routability issue. To more accurately estimate the detailed-routing routability, this paper presents a track-assignment-based routability estimator. In this work, wire segments called iroutes are extracted from a global routing result, and then the proposed negotiation-based algorithm assigns these iroutes to proper tracks and minimizes the overlaps between the iroutes. Based on the assignment result, we can judge which regions may have critical routability issues by seeing where more overlaps reside.

In today's multi-die ICs, the die-to-die interconnects are often complicated and susceptible to various kinds of manufacturing defects and stress-induced performance degradation in the field. This phenomenon has prompted a need to perform online monitoring of the signal integrity over the die-to-die interconnects for reliability critical applications. In this work, we present a slack-time binning scheme so that one can constantly quantify the margin of a timing failure threat (TFT) occurring to a registered die-to-die interconnect. The proposed scheme attaches a Slack-Time Monitor (ST-monitor) to each Flip-Flop (FF) that receives a signal transmitted through a die-to-die interconnect under monitoring. Two techniques are introduced to enhance the traditional “Timing-Violation Checker”, namely (1) a tunable guard-band technique, and (2) an offset compensation technique. With these two techniques, one can perform online slack-time binning. Experimental results using a 90nm CMOS process show that the proposed scheme has a low area overhead of only approximately 2.35 times the area of a boundary scan cell.

In this paper, we study a cell-based row-structure layout decomposition problem for triple patterning lithography (TPL) which asks to minimize a weighted sum of coloring conflicts and stitches. We show how to extend a prior graph-based approach to solve the problem optimally under certain assumptions. Furthermore, several methods to substantially reduce the graph size and hence to accelerate the extended approach are presented. Experimental results show that our decomposer can significantly outperform a state-of-the-art work in terms of both solution quality and run time.

In this paper, we study row-based detailed placement refinement for triple patterning lithography (TPL), which asks to find a refined detailed placement solution as well as a valid TPL layout decomposition under the objective of minimizing the number of stitches and the half-perimeter wirelength. Our problem does not have precoloring solutions of cells as the input, and it allows using techniques, including white space insertion, cell flipping, adjacent-cell swapping, and vertical cell movement, to optimize the solution quality. We first present (resource-constrained) shortest-path-based algorithms for several TPL-aware single-row placement problems that allow or disallow perturbing a given cell ordering. Based on these algorithms, we then propose an approach to our TPL-aware detailed placement refinement problem, which first minimizes the number of stitches and then minimizes the wirelength. Finally, we report extensive experimental results to demonstrate the effectiveness and efficiency of our approach.

To avoid producing unroutable placement solutions, many state-of-the-art routability-driven placers iteratively invoke global routers to evaluate their placement solutions, and then perform routability optimization. However, using a global router to evaluate hard-to-route placement solutions may spend considerable runtime and it cannot guarantee that a placement is truly unroutable to any router. This paper presents an unroutable placement recognizer based on a window-based unroutable region recognition algorithm and a length-bounded unroutable panel recognition (UPR) algorithm, which can confirm some placements that are exactly unroutable among a set of hard-to-route placements. In addition, if a placement is recognized to be unroutable, the recognizer can report a lower bound of total overflow for the placement. The experimental results reveal that the unroutable region recognition algorithm can find out 16 placements that are definitely unroutable among 23 widely used hard-to-route global routing benchmarks. Moreover, when a scenic constraint is considered, the UPR algorithm can find out a few more placements that are also unroutable.

Redundant via insertion (RVI) has become an inevitable means adopted in the routing or post-routing stage to enhance chip reliability and yield as feature size shrinks down to nanometer scale. The remaining routing resources, however, could become so limited after RVI, and make engineering change order (ECO) routing during a pre-mask stage or even a post-mask stage difficult to complete. In this paper, we study an ECO routing problem where redundant vias are present in the given layout but can be considered for replacement or removal to increase the routability and improve the routing quality. To find an ECO routing path, we construct only the necessary part of the routing graph on-the-fly, and develop an A* search based algorithm for achieving efficient path finding. We also take redundant via replacement, removal, and insertion into account when formulating the routing cost, and apply a state-of-the-art method to perform redundant via replacement and insertion. Experiments show that our algorithm not only successfully routes all test cases but also efficiently produces high-quality solutions.

Interposer-based 3D ICs (or known as 2.5D ICs) have been seen as an alternative approach to true 3D stacked ICs, which mount multiple dies on a silicon interposer and route signals between dies by the interconnects in the interposer. However, the floorplan of dies on the interposer and the signal assignment for macro-bumps and TSVs will largely impact the wirelength of the interconnects in a 2.5D IC. Because long interconnects would degrade the performance of 2.5D ICs, the multi-die floorplanning problem and signal assignment problem for 2.5D ICs are critical. This paper presents an enumeration-based algorithm and a network-flow-based algorithm to solve the multi-die floorplanning and signal assignment problems in a 2.5D IC, respectively. Also, to speed up the floorplanning and signal assignment algorithms, several acceleration techniques are proposed. The experimental results reveal that this work can effectively reduce the total wirelength in a 2.5D IC and the acceleration techniques can significantly speed up the proposed algorithms.

Placement consists of three stages: global placement, legalization, and detailed placement (DP). Recently, most research works have concentrated on improving global placement and legalization, but innovations in DP have been rarely seen. ICCAD13 held a DP contest that formulates the emerging placement issues into a bin-utilization metric and maximum cell displacement constraint. This paper presents a detailed placer that can effectively reduce both half-perimeter wirelength and the peak bin-utilization under the displacement constraint. The proposed lazy-update based incremental density profit function supports efficient cell swapping. Combination of lazy-update density profit function and Density-Driven Swap lets our placer achieve AOFP of 0 for the majority of the ICCAD13 test cases. The placer presented produces the best placement results among the top3 teams in the ICCAD13 contest.

In this paper, we study a mask-cost-aware routing problem for engineering change order (ECO). By taking into account old routes for possible reuse, we present an approach for the problem. Encouraging experimental results are reported to demonstrate the effectiveness of our approach.

A 2.5D IC provides a silicon interposer to integrate multiple dies into a package, which not only offers better performance than 2D ICs but also has lower manufacturing complexity than true 3D ICs. In an interposer, routing wires connect signals between dies or route signals from dies to the package substrate. The number of metal layers in an interposer is one of the critical factors to affect the routability and manufacturing cost of the 2.5D IC. Thus, how to achieve 100% routing completion rate in an interposer using a minimum number of metal layers plays a key role for the success of a 2.5D IC. This paper presents a global-routing-based metal layer planner called VGR to identify a minimal number of metal layers for an interposer with consideration of routability and manufacturing cost. Also, VGR can identify a good stacking order of the horizontal and vertical layers in an interposer such that the routing solution in the interposer costs fewer vias. To our best knowledge, this paper is the first study to solve the metal layer planning problem for silicon interposers.

Wire sizing can be used to reduce the delays of critical nets. However, because of the forbidden pitch issue in sub-20nm designs, wide wires may no longer be an attractive solution because of the restrictive wire spacing requirement from advanced lithography. In this work, we investigate the suitability of the parallel wiring technique, in which multiple parallel wires are used to route the same net, as an alternative to routing a net using a single wide wire. In particular, we study the trade offs between parasitics, timing, power, and routing resources. Our study reveals that wire sizing using both parallel wires and wide wires can be advantageous. Moreover, if high layout densities are required, parallel wiring can be a viable approach in solving timing problems for sub-20nm designs.

Routability has become a challenging issue with designs scaling down. Recently, global-routing-based routing congestion estimators (GRCEs) are widely used to detect the routability problems in the early VLSI design stages. To make GRCEs fast, using parallel routing approaches to speed up GRCEs is a promising direction. However, integrating existing parallel routing approaches into a GRCE may degrade the accuracy of the GRCE, because the routing kernel of the GRCE has to be modified such that its routing behavior changes. This paper presents a resource-level parallel approach (RPA) to accelerate GRCEs. RPA is easy to implement and has no need to change the routing kernels of GRCEs. Thus, GRCEs accelerated by RPA can keep its routing behavior and the estimation accuracy. Moreover, this paper presents an analytical method to quantify the estimation accuracy of a GRCE. Traditionally, the accuracy of a GRCE is manually measured by how they look like between the congestion maps generated by the GRCE and a real router, which may be inaccurate and time-consuming. In contrast, using the proposed quantifying method to evaluate the accuracy of a GRCE is more precise and faster.

To avoid producing unroutable placement solutions, many state-of-the-art routability-driven placers iteratively invoke global routers to evaluate their placement solutions and then perform routability optimization. However, using a global router to evaluate hard-to-route placement solutions may spend considerable runtime and it cannot guarantee that a placement is truly unroutable to any router. This paper presents an unroutable placement recognizer based on a window-based layout scanning algorithm, which can confirm some placements that are exactly unroutable among a set of hard-to-route placements. In addition, if a placement is recognized to be unroutable, the recognizer can point out unroutable regions and report a lower bound of total overflow for the placement. The experimental results reveal that the proposed recognizer can find out 16 placements that are definitely unroutable among 23 widely used hard-to-route global routing benchmarks.

Given a set of pin-vertices, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects all the pin-vertices possibly through Steiner points using vertical and horizontal segments with the minimal wirelength and without intersecting any obstacle. To deal with multiple routing layers and preferred routing orientations, we consider the multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) problem and the obstacle-avoiding preferred direction Steiner tree (OAPD-ST) problem. First, we prove that the multilayer case is theoretically different from the 2D one, and propose a reduction to transform a multilayer instance into a 3D instance. Based on the reduction, we apply computational geometry techniques to develop an efficient algorithm, utilizing existing OARSMT heuristics, for the ML-OARSMT problem and the OAPD-ST problem. Furthermore, we develop an advanced Steiner point selection to avoid inferior Steiner points and to improve the solution quality. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results.

Multi-core system simulation techniques have been especially essential to system development in recent years. Although these techniques have been studied extensively, we have found that both conventional polling and collaborative timing synchronization approaches all encounter a severe scalability issue when the number of target cores is more than that of the host cores. To resolve this issue, we propose an effective hybrid technique that combines the advantage of the two approaches. According to the experimental results, the proposed technique effectively resolves the scalability issue and shows one to four orders of improvement compared to conventional approaches.

Through-silicon vias (TSVs) are used to connect inter-die signals in a 3-D IC. Unlike conventional vias, TSVs occupy device area and are very large compared to logic gates. However, most previous 3-D floorplanners only view TSVs as points. As a result, whitespace redistribution is necessary for TSV insertion after the initial floorplan is computed, which leads to suboptimal layouts. In this paper, we propose a very efficient 3-D floorplanner to simultaneously floorplan the functional modules and place the TSVs and to optimize the total wirelength under fixed-outline constraint. Compared to the state-of-the-art 3-D floorplanner with TSV planning, our design consistently produces better floorplans with 15% shorter wirelength and 31% fewer TSVs on average. Our algorithm is extremely fast and only takes a few seconds to floorplan benchmarks with hundreds of modules compared to hours as required by the previous state-of-the-art floorplanner.

Wire bonding is currently the most popular method for connecting signals between dies in system-in-package (SiP) design. Pad assignment, which assigns inter-die signals to die pads so as to facilitate wire bonding, is an important physical design problem for SiP design because the quality of a pad assignment solution affects both the cost and the performance of an SiP design. In this paper, we study a pad assignment problem, which prohibits the generation of illegal crossings and aims to minimize the total signal wirelength, for die-stacking SiP design. We first consider the two-die cases and die-stacks with a bridging die, and present a minimum-cost flow-based approach to optimally solve them in polynomial time. We then describe an approach, which uses a modified left-edge algorithm and an integer linear programming technique, for pyramid die-stacks with no bridging die. Finally, we discuss extensions of the two approaches to handle additional design constraints. Encouraging experimental results are shown to support our approaches.

In this paper, we formulate a problem of simultaneous redundant via insertion and line end extension for via yield optimization. Our problem is more general than previous works in the sense that more than one type of line end extension is considered and the objective function to be optimized directly accounts for via yield. We present a zero-one integer linear program based approach, that is equipped with two speedup techniques, to solve the addressed problem optimally. In addition, we describe how to modify our approach to exactly solve a previous work. Extensive experimental results are shown to demonstrate the effectiveness and efficiency of our approaches.

In this paper we study a global routing problem that considers not only overflow and wirelength but also layer directives. A layer directive is often given to a timing-critical net for meeting target performance, and it specifies a range of consecutive layers on which the net should be routed. Unlike a previous work that focuses only on a restricted set of layer ranges, our problem allows arbitrary layer ranges to be specified. We present a global router which enhances an academic router by employing techniques to take general layer directives into account during two-dimensional (2D) routing and layer assignment. The experiment results show that our global router can produce encouraging solutions for all test cases.

In this paper, we will study floorplanning in 3-D integrated circuits (3D-ICs). Although literature is abundant on 3D-IC floorplanning, none of them consider the areas and positions of signal through-silicon vias (TSVs). In previous research, signal TSVs are viewed as points during the floorplanning stage. Ignoring the areas, positions and connections of signal TSVs, previous research estimates wirelength by measuring the half-perimeter wirelength of pins in a net only. Experimental results reveal that 29.7% of nets possess signal TSVs that cannot be put into the white space within the bounding boxes of pins. Moreover, the total wirelength is underestimated by 26.8% without considering the positions of signal TSVs. The considerable error in wirelength estimation severely degrades the optimality of the floorplan result. Therefore, in this paper, we will propose a two-stage 3-D fixed-outline floorplaning algorithm. Stage one simultaneously plans hard macros and TSV-blocks for wirelength reduction. Stage two improves the wirelength by reassigning signal TSVs. Experimental results show that stage one outperforms a post-processing TSV planning algorithm in successful rate by 57%. Compared to the post-processing TSV planning algorithm, the average wirelength of our result is shorter by 22.3%. In addition, stage two further reduces the wirelength by 3.45% without any area overhead.

In this paper, we study a floorplanning problem for die-stacking System-in-Package (SiP) design in which the wire bonding method is used to connect signals between different dies. We present an approach which sequentially determines a floorplan for each die such that the generated floorplan has minimal on-chip wirelength and satisfies given fixed-outline and temperature constraints. The experimental results indicate that our approach has 100% successful rate in producing a feasible floorplan for each test case.

Global routing is a very crucial stage in a design cycle, because it physically plans the routes of nets on a chip. In order to boost the research and development of global routing techniques, ISPD held contests and released benchmarks in 2007 and 2008, respectively. However, the contests may lead researchers away from facing other real problems in practice. In this paper we study a new global routing problem that not only considers traditional routing objectives such as overflow and wirelength but also focuses on honoring layer directives that are usually specified for timing-critical nets to alleviate performance degrading. Based on novel extensions of an academic router, we present a new global router called GLADE for the addressed problem. The experimental results show that GLADE can effectively generate a high-quality solution, which balances the metrics under consideration, for each test case from the set of recently released ICCAD 2009 benchmarks.

Antenna effect is an important issue that needs to be considered in the routing stage for modern design. In this paper, we study a layer assignment problem that arises during multi-layer global routing and takes antenna avoidance into account. The problem asks to transform a given 2-dimensional global routing result into a 3-dimensional one (i.e., a multi-layer one) and to minimize the amount of antenna violations and the via count subject to given wire congestion constraints. We present an algorithm that tackles the addressed layer assignment problem in a net-by-net manner. An existing dynamic-programming-based single-net layer assignment method that can only consider the via count is judiciously modified and adopted by our algorithm to handle both antenna avoidance and via count minimization for each net. To further reduce the via count but without increasing the amount of antenna violations, a refinement procedure based on min-cost max-flow is developed and added to our algorithm. The experiment results show that when compared with the layer assignment approach adopted by a state-of-the-art academic global router, our algorithm not only can improve the via count slightly but also can significantly reduce the amount of antenna violations.

This paper presents a robust global router called NTHU-Route 2.0 that improves the solution quality and runtime of NTHU-Route by the following enhancements: 1) a new history based cost function; 2) new ordering methods for congested region identification and rip-up and reroute; and 3) two implementation techniques. We report convincing experimental results to show the effectiveness of each individual enhancement. With all these enhancements together, NTHU-Route 2.0 solves all ISPD98 benchmarks with very good quality. Moreover, NTHU-Route 2.0 routes 7 of 8 ISPD07 benchmarks and 12 of 16 ISPD08 benchmarks without any overflow. Compared with other state-of-the-art global routers, NTHU-Route 2.0 is able to produce better solution quality and/or run more efficiently.

Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we studied the problem ofsimultaneous double via insertion and wire bending(DVI/WB) in a postrouting stage, where a single via can have at most one redundant via inserted next to it. Aside from this, we are allowed to bend existing signal wires for enhancing the insertion rate of double vias. The primary goal of the DVI/WB problem is to insert as many double vias as possible; the secondary objective is to minimize the amount of layout perturbation. We formulate the DVI/WB problem as that of finding a minimum-weight maximum independent set (mWMIS) on an enhanced conflict graph. We proposed algorithms to perform wire bending and to construct the enhanced conflict graph from a given design. We also proposed a zero-one integer linear program (0–1 ILP)-based approach to solve the mWMIS problem. Moreover, we studied the problem of DVI/WB with the consideration of via density and extended our 0–1 ILP-based approach to solve it. Experimental results show that our approaches can improve the insertion rate by up to 6.34% at the expense of up to 1.29% wirelength increase when compared with the state-of-the-art double via insertion methods that do not consider wire bending. Moreover, when compared with an existing method that considers wire bending, our DVI/WB approach can insert 2% more double vias and produce 32% less wirelength increase rate on average.

As on-track double vias take less routing resources and have better electrical characteristics, we study in this paper the problem of double via insertion with a preference for on-track double vias (DVI/ON) in a postrouting stage. The primary goal is to insert as many double vias as possible, and maximizing the number of on-track double vias is a secondary objective. We present a zero-one integer linear program-based approach to optimally solve the DVI/ON problem. Moreover, we also discuss a special case of the DVI/ON problem and present a maximum-weighted bipartite matching-based optimal approach. Experimental results indicate that our approaches outperform existing algorithms in terms of solution quality.

Wire bonding is the most popular method to connect signals between dies in System-in-Package (SiP) design nowadays. Pad assignment, which assigns inter-die signals to die pads so as to facilitate wire bonding, is an important physical design problem for SiP design because the quality of a pad assignment solution affects both the cost and performance of a SiP design. In this paper, we study a pad assignment problem, which prohibits the generation of illegal crossings and aims to minimize the total signal wirelength, for die-stacking SiP design. We first consider a variety of special cases and present a minimum-cost maximum-flow based approach to optimally solve them in polynomial time. We then describe an approach, which uses a modified left edge algorithm and an integer linear programming technique, to solve the general case. Encouraging experimental results are shown to support our approaches.

Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we study the problem of double via insertion with wire bending (DVI/WB) in a post-routing stage, where a single via can have at most one redundant via inserted next to it. Aside from this, we are allowed to bend existing signal wires for enhancing the insertion rate of double vias. The goal of DVI/WB is to primarily insert as many double vias as possible and to minimize the amount of layout perturbation as the secondary objective. We formulate the DVI/WB problem as that of finding a minimum-weight maximum independent set (mWMIS) on an enhanced conflict graph. We propose algorithms to perform wire bending and to construct the enhanced conflict graph from a given design. Moreover, we also propose a zero-one integer linear program (0-1 ILP) based approach to solve mWMIS. Experimental results show that our approach can improve the insertion rate by up to 5.58% at the expense of up to 0.37% wirelengh increase when compared with a state-of-the-art double via insertion method that does not consider wire bending.

In this paper, we study a layer assignment problem which arises during multi-layer global routing. Our layer assignment problem takes the total wire overflow and the maximum wire overflow of a given 2D global routing solution to form the wire congestion constraints, and asks to find a 3D counterpart through layer assignment such that the total via overflow and the total via count of the 3D result are both as small as possible while the wire congestion constraints are satisfied. To solve this layer assignment problem, we present an algorithm which first determines a net order, then applies a dynamic programming technique to perform layer assignment in a net-by-net manner according to the net order, and finally refines the solution iteratively until convergence. Our algorithm is guaranteed to always generate a layer assignment solution satisfying the wire congestion constraints. We tested our layer assignment algorithm on the ISPD'07 and ISPD'08 benchmarks and the results are very encouraging.

In this paper, we present a new global router, NTHU-Route, for modern designs. NTHU-Route is based on iterative rip-ups and reroutes, and several techniques are proposed to enhance our global router. These techniques include (1) a history based cost function which helps to distribute overflow during iterative rip-ups and reroutes, (2) an adaptive multi-source multi-sink maze routing method to improve the wirelength of maze routing, (3) a congested region identification method to specify the order for nets to be ripped up and rerouted, and (4) a refinement process to further reduce overflow when iterative history based rip-ups and reroutes reach bottleneck. Compared with two state-of-the-art works on ISPD98 benchmarks, NTHU-Route outperforms them in both overflow and wirelength. For the much larger designs from the ISPD07 benchmark suite, our solution quality is better than or comparable to the best results reported in the ISPD07 routing contest.

Phase shifting mask (PSM) is a promising resolution enhancement technique, which is used in the deep sub-wavelength lithography of the VLSI fabrication process. However, applying the PSM technique requires the layout to be free of phase conflicts. In this paper, we present a mixed integer linear programming (MILP) based layout modification algorithm which solves the phase conflict problem by wire spreading. Unlike existing layout modification methods which first solve the phase conflict problem by removing edges from the layout-associated conflict graphs and then try to revise the layout to match the resultant conflict graphs, our algorithm simultaneously considers the phase conflict problem and the feasibility of modifying the layout. The experimental results indicate that without increasing the chip size, the phase conflict problem can be well tackled with minimal perturbation to the layout.

In this paper, we present a generalized network flow based algorithm for power-aware FPGA memory mapping. Our algorithm not only maps user-defined logical memories to physical embedded memory blocks under the memory resource constraint but also achieves minimum power consumption. The experimental results show that our algorithm was always able to efficiently generate optimal solutions for all test cases while an existing greedy method could do so only for about one third of the test cases.

We present in this paper a fast and stable global router called NTHU-Route 2.0 that improves the solution quality and runtime of a state-of-the-art router, NTHU-Route, by the following enhancements: (1) a new history based cost function, (2) new ordering methods for congested region identification and rip-up and reroute, and (3) two implementation techniques. The experimental results show that NTHU-Router 2.0 solves all ISPD98 benchmarks with very good quality. Moreover, it routes 7 of 8 ISPD07 benchmarks without any overflow. In particular, for one of the ISPD07 benchmarks which are thought to be difficult cases previously, NTHU-Route 2.0 can completely eliminate its total overflow. NTHU-Route 2.0 also successfully solves 12 of 16 ISPD08 benchmarks without causing any overflow.

Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we study the problem of double-cut via insertion (DVI) in a post-routing stage, where a single via can have at most one redundant via inserted next to it and the goal is to insert as many redundant vias as possible. The DVI problem can be naturally formulated as a zero-one integer linear program (0-1 ILP). Our main contributions are acceleration methods for reducing the problem size and the number of constraints. Moreover, we extend the 0-1 ILP formulation to handle via density constraints. Experimental results show that our 0-1 ILP is very efficient in computing optimal DVI solution, with up to 35.3 times speedup over existing heuristic algorithms.

Redundant via insertion is highly effective in improving chip yield and reliability. In this paper, we study the problem ofdouble-cutviainsertion(DVI) in a post-routing stage, where a single via can have, at most, one redundant via inserted next to it and the goal is to insert as many redundant vias as possible. The DVI problem can be naturally formulated as a zero-one integer linear program (0-1 ILP). Our main contributions are acceleration methods for reducing the problem size and the number of constraints. Moreover, we extend the 0-1 ILP formulation to handle via density constraints. Experimental results show that our 0-1 ILP is very efficient in computing an optimal DVI solution, with up to 73.98 times speedup over existing heuristic algorithms.

In this paper, we study the problem of layer assignment for via minimization, which arises during multilayer global routing. In addressing this problem, we take the total overflow and the maximum overflow as the congestion constraints from a given one-layer global routing solution and aim to find a layer assignment result for each net such that the via cost is minimized while the given congestion constraints are satisfied. To solve the problem, we propose a polynomial-time algorithm which first generates a net order and then performs layer assignment one net at a time according to the order using dynamic programming. Our algorithm is guaranteed to generate a layer assignment solution satisfying the given congestion constraints. We used the six-layer benchmarks released from the ISPD'07 global routing contest to test our algorithm. The experimental results show that our algorithm was able to improve the contest results of the top three winners MaizeRouter, BoxRouter, and FGR on each benchmark. As compared to BoxRouter 2.0 and FGR 1.1, which are newer versions of BoxRouter and FGR, our algorithm respectively produced smaller via costs on all benchmarks and half the benchmarks. Our algorithm can also be adapted to refine a given multilayer global routing solution in a net-by-net manner, and the experimental results show that this refinement approach improved the via costs on all benchmarks for FGR 1.1.

Advanced process technologies impose more significant challenges especially when manufactured circuits exhibit substantial process variations. Consideration of process variations becomes critical to ensure high parametric timing yield. During the design stage, fast estimation of the achievable buffered delay can navigate more accurate and efficient wire planning and timing analysis in floorplanning or global routing. In this paper, we derive approximated first-order canonical forms for buffered delay estimation which considers the effect of process variations and the presence of buffer blockages. We empirically show that an existing deterministic delay estimation method is over-pessimistic and thus result in unnecessary design rollback. The experimental results also show that our method can estimate buffered delay with 4% average error but achieve up to 149 times speedup when compared to a state-of-the-art statistical buffer insertion method.

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 routing, finding a rectilinear Steiner minimal tree (RSMT) is a fundamental problem. Today's design often contains rectilinear obstacles, like macro cells, IP blocks, and pre-routed nets. Therefore obstacle-avoiding RSMT (OARSMT) construction becomes a very practical problem. In this paper we present a fast and stable algorithm for this problem. We use a partitioning based method and an ant colony optimization based method to construct obstacle-avoiding Steiner minimal tree (OASMT). Besides, two heuristics are proposed to do the rectilinearization and refinement to further improve wirelegnth. The experimental results show our algorithm achieves the best wirelength results in most of the test cases and the runtime is very small even for the larger cases each of which has both the number of terminals and the number of obstacles more than 100.

Reducing the yield loss due to via failure is one of the important problems in design for manufacturability. A well known and highly recommended method to improve via yield/reliability is to add redundant vias. In this paper, we study the problem of post-routing redundant via insertion and formulate it as a maximum independent set (MIS) problem. We present an efficient graph construction algorithm to model the problem, and an effective MIS heuristic to solve the problem. The experimental results show that our MIS heuristic inserts more redundant vias and distributes them more uniformly among via layers than a commercial tool and an existing method. The number of inserted redundant vias can be increased by up to 21.24%. Besides, since redundant vias can be classified into on-track and off-track ones, and on-track ones have better electrical properties, we also present two methods (one is modified from the MIS heuristic, and the other is applied as a post processor) to increase the amount of on-track redundant vias. The experimental results indicate that both methods perform very well.

Redundant via insertion and line end extension employed in the post-routing stage are two well known and highly recommended techniques to reduce yield loss due to via failure. However, if the amount of inserted redundant vias is not well controlled, it could violate via density rules and adversely worsen the yield and reliability of the design. In this paper, we first study the problem of redundant via insertion, and present two methods to accelerate a state-of-the-art approach (which is based on a maximum independent set (MIS) formulation) to solve it. We then consider the problem of simultaneous redundant via insertion and line end extension. We formulate the problem as a maximum weighted independent set (MWIS) problem and modify the accelerated MIS-based approach to solve it. Lastly, we investigate the problem of simultaneous redundant via insertion and line end extension subject to the maximum via density rule, and present a two-stage approach for it. In the first stage, we ignore the maximum via density rule, and enhance the MWIS-based approach to find the set of regions which violate the maximum via density rule after performing simultaneous redundant via insertion and line end extension. In the second stage, excess redundant vias are removed from those violating regions such that after the removal, the maximum via density rule is met while the total amount of redundant vias removed is minimized. This density-aware redundant via removal problem is formulated as a set of zero-one integer linear programming (0-1 ILP) problems each of which can be solved independently without sacrificing the optimality. The superiorities of our approaches are all demonstrated through promising experimental results.

Given a routing tree for a multi-pin net, two algorithms extending the van Ginneken algorithm [3] for concurrent flip-flop and buffer insertion were presented in [5]. One algorithm called MiLa targets at minimizing the latency, and the other algorithm called GiLa aims to find a feasible solution subject to given latency constraints imposed on sinks. However, they both do not consider the case where buffer/flip-flop blockages are present. In this paper, we enhance the MiLa algorithm and GiLa algorithm to consider blockage avoidance by finding alternative registered-buffered paths between each internal node inside a blockage and its parent node. The experimental results show that in comparison to the MiLa algorithm, our approach is able to find a solution with the same latency (for about half of the test cases) or even better latency (for the remaining test cases) and the same wirelength, while the buffer/flip-flop usage and CPU time are comparable or acceptable. In comparison to the GiLa algorithm, our approach is able to find a feasible solution for each test case while the Gila algorithm fails to do so for several test cases.

As the technology of manufacturing process continues to advance, the process variation becomes more and more serious in nanometer designs. Optical proximity correction (OPC) is employed to correct the process variation of the diffraction effect. To obtain the desired layout as early as possible, routers must have some changes to handle the optical effects to speed up the OPC time and to avoid the routing result that cannot be corrected by the OPC process. In this paper, we propose two practical OPC-aware maze routing problems and present how to enhance an existing maze routing algorithm to get an optimal algorithm for each problem. The experimental results are also given to demonstrate the effectiveness of these two enhanced algorithms.

In this paper, an effective algorithm is presented for multilevel circuit clustering for delay minimization, and is applicable to hierarchical field programmable gate arrays. With a novel graph contraction technique, which allows some crucial delay information of a lower-level clustering to be maintained in the contracted graph, our algorithm recursively divides the lower-level clustering into the next higher-level one in a way that each recursive clustering step is accomplished by applying a modified single-level circuit clustering algorithm based on . We test our algorithm on the two-level clustering problem and compare it with the latest algorithm in . Experimental results show that our algorithm achieves, on average, 12% more delay reduction when compared to the best results (from TLC with full node-duplication) in . In fact, our algorithm is the first one for the general multilevel circuit clustering problem with more than two levels.

Abstract | In this paper, an eective algorithm is pre-sented for performance driven multi-level clustering for com-binational circuits, and is applicable to hierarchical FPGAs. With a novel graph contraction technique, which allows some crucial delay information of a lower-level clustering to be maintained in the contracted graph, our algorithm recur-sively divides the lower-level clustering into the next higher-level one in a way that each recursive clustering step is ac-complished by applying a modied single-level circuit clus-tering algorithm based on [1]. We test our algorithm on the two-level clustering problem and compare it with the latest algorithm in [2]. Experimental results show that our algorithm achieves, on average, 12 % more delay reduction when compared to the best results (from TLC with full node-duplication) in [2]. In fact, our algorithm is the rst one for the general multi-level circuit clustering problem with more than two levels. I.

This paper considers the area-constrained clustering of combinational circuits for delay minimization under a more general delay model, which practically takes variable interconnect delay into account. Our delay model is particularly applicable when allowing the back-annotation of actual delay information to drive the clustering process. We present a vertex grouping technique and integrate it with the algorithm (Rajaraman and Wong, 1995) such that our algorithm can be proved to solve the problem optimally in polynomial time.

In VLSI module placement, it is very practical to consider placing some modules along the pre-specified boundaries of the chip so that the modules are easier to be connected to certain I/O pads. In this paper, we study the module placement problem where some modules have the boundary constraints, and present a simulated annealing based algorithm that represents each placement topology by a sequence-pair. The major contribution of our algorithm is that a feasible placement is always obtainable. Our algorithm has been implemented, and its effectiveness is supported by the encouraging experimental results.

In this paper, we consider the problem of lookup table (LUT) based FPGA technology mapping for power minimization in combinational circuits. The problem has been previously proved to be NP-hard, and hence we present an efficient heuristic algorithm for it. The main idea of our algorithm is to exploit the "cut enumeration" technique to generate possible mapping solutions for the sub-circuit rooted at each node. However, for the consideration of both run time and memory space, only a fixed-number of solutions are selected and stored by our algorithm. To facilitate the selection process, a method that correctly calculates the estimated power consumption for each mapped sub-circuit is developed. The experimental results indicate that our algorithm reduces the average power consumption by up to 14.18%, and the average number of LUTs by up to 6.99% over an existing method.

using minimum amount of area overhead. And we show that our algorithm can be applied to improve the solution produced by any area-constrained functional replication partitioning heuristic.

Article Free Access Share on Feasible two-way circuit partitioning with complex resource constraints Authors: Hsun-Cheng Lee Department of Information and Computer Engineering, Chung Yuan Christian University, Chungli, Taiwan Department of Information and Computer Engineering, Chung Yuan Christian University, Chungli, TaiwanView Profile , Ting-Chi Wang Department of Information and Computer Engineering, Chung Yuan Christian University, Chungli, Taiwan Department of Information and Computer Engineering, Chung Yuan Christian University, Chungli, TaiwanView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 435–440https://doi.org/10.1145/368434.368731Published:28 January 2000Publication History 0citation93DownloadsMetricsTotal Citations0Total Downloads93Last 12 Months4Last 6 weeks1 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 SiteeReaderPDF

Uses data collected from benchmark circuit simulations to examine the relationship between the tests which detect stuck-at faults and those which detect bridging surrogates. We show that the coefficient of correlation between these tests approaches zero as the stuck-at fault coverage approaches 100%. An enhanced version of the MPG-D model, which is based upon the number of detections of each site in a logic circuit, is shown to be superior to stuck-at fault coverage-based defective part level prediction. We then compare the accuracy of both predictors for an industrial circuit tested using two different test pattern sequences.

Recently Young and Wong extended the well-known simulated annealing based Wong-Liu algorithm [1986] to solve the problem of slicing floorplan design with boundary constraints. The main idea behind the Young-Wong algorithm [1999] is to determine the boundary information of each module in a floorplan by traversing the corresponding normalized Polish expression from right to left once. By carefully examining each of the three types of moves adopted by the Young-Wong algorithm for generating a new normalized Polish expression, we observe that it is very likely that only a subset of modules might have the boundary information changed in the new normalized Polish expression, and hence only the boundary information for those modules needs to be recomputed. Based on the observation, we improve the Young-Wong algorithm by providing methods to accelerate the boundary information computation.

In this paper two faster and better spectral algorithms are presented for the multi-way circuit partitioning problem with the objective of minimizing the scaled cost. The problem can be approximately transformed into the vector partitioning problem by mapping each circuit component to a multi-dimensional vector. The common key idea of our two algorithms for solving the vector partitioning problem is to first treat the set of vectors as a cluster; and then repeatedly select a cluster which gives the maximum cost improvement among all the current clusters, and partition it into two new clusters. The bipartitioning process is continued until the number of clusters is equal to the required number of partitions. The experimental results indicate that the two algorithms significantly outperform MELO+DP-RP [3] in both the run time and partitioning result.

A new class of routing structures with fixed orthogonal wire segments and field programmable switches at the intersections of the wire segments is proposed. In comparison with the conventional two-dimensional field-programmable gate array (FPGA) routing structure, this class of routing structures has the advantage of using a smaller number of active programmable switches. An existing field-programmable interconnect chip (FPIC) routing structure can be included as a special case in our class of routing structures. Using a probabilistic model, we prove that complete routing can be achieved with a high degree of probability in a routing structure of this class in which the number of tracks in each channel approaches the lower bound asymptotically. We present a sequential routing algorithm based on the solution of the single net routing problem. We take into account the delay introduced by the active programmable switches on a routing path and formulate the single net routing problem as a node-weighted Steiner minimum tree (NWSMT) problem in a bipartite graph G. Since our single net routing problem is NP-complete, a polynomial time approximate algorithm is proposed. We prove that our single net routing algorithm produces an optimal solution for some special classes of bipartite graphs. In general, the solution obtained by our algorithm bas a performance bound of min{/spl Delta/(V/Z), |Z|-1}. Experimental results for several industrial circuits show a reduction of up to 41% in the number of active programmable switches when compared with corresponding results for the conventional FPGA routing structure.

In this paper we consider two channel pin assignment problems which take circuit performance into account. The first one is the module implementation selection problem. We are given a net span bound for each critical net and each module has several possible placements of its pins. Our objective is to minimize channel density while satisfying net span constraints. We proved that this problem is NP-complete. For the case when each module has at most 2 pin placements, the problem can be transformed to the 2-SAT problem and hence is polynomial time solvable. We present a heuristic based on this algorithm to solve the general case. The second problem we consider is the module shifting problem. We are given a set of modules whose relative ordering is fixed on each side of the channel but their exact positions are not fixed. We present a polynomial time algorithm to test the feasibility of satisfying the net span constraints by shifting the modules. The algorithm is based on formulating the problem as a special integer linear programming problem which is solvable in polynomial time. We also extend our algorithms to handle multiple channels.>

We study in this paper the net assignment problem subject to the capacity constraint, selection constraint and routing constraint. Given two adjacent channels separated by a cell row, and a set of nets in each of the two channels, this problem is to assign to the cell row a subset of nets in each channel such that without violating any given constraint, the sum of the remaining densities of the two channels is minimized. The capacity constraint requires the density caused by the nets, which are assigned to the cell row, to be no more than a user-specified number k, where k is no more than the number of tracks available for routing over that cell row. The selection constraint specifies in each channel the subset of nets which are candidates to be assigned to the cell row. The routing constraint requires each net to be either completely assigned to the cell row or to stay in its channel. This problem can find its application in modeling a practical over-the-cell routing problem in which the whole region over the cell row is two-layer routable for the nets in the two adjacent channels. We present an optimal algorithm to solve this problem and provide experimental results to support our algorithm.

A new class of routing structures with fixed orthogonal wire segments and field programmable switches at the intersections of the wire segments is proposed. In comparison with the conventional two dimensional field-programmable gate array (FPGA) routing structure, this class of routing structures has the advantage of using a smaller number of programmable switches. Using a probabilistic model, we prove that complete routing can be achieved with a high degree of probability in a routing structure of this class in which the number of tracks in each channel approaches the lower bound asymptotically. A sequential routing algorithm which is based on the solution of the single net routing problem is presented. We take into account the delay introduced by the programmable switches on a routing path and formulate the single net routing problem as a Node-Weighted Steiner Minimum Tree (NWSMT) problem in a bipartite graph G. Since our single net routing algorithm is proposed. We prove that our single net routing algorithm produces an optimal solution for some special classes of bipartite graphs. In general, the solution obtained by our algorithm has a performance bound of min{/spl Delta/(VZ), |Z|-1}. On the other hand, we also prove that it is NP-complete to determine a solution which approximates the optimal solution without any constant bound. Experimental results show a reduction of up to 41% in the number of programmable switches when compared with corresponding results for the conventional FPGA routing structure.

An optimal algorithm for the floorplan area optimization problem is presented. The algorithm is based on an extension of the technique of L. Stockmeyer (1983). Experimental results indicate that the authors' algorithm is efficient and capable of successfully handling large floor plans. The algorithm is compared with the branch-and-bound optimal algorithm of S. Wimer et al. (ibid., vol.8, no.2, p.139-45, 1989). The running time of the present algorithm is substantially less than that of the Wimer algorithm. For several examples where the Wimer algorithm ran for days and did not terminate, the present algorithm produced optimal solutions in a few seconds.>

In this paper we present an optimal algorithm for the floorplan area optimization problem. Our algorithm is based on an extension of the technique in [5]. Experimental results indicate that our algorithm is efficient and capable of successfully handling large floorplans. We compare our algorithm with the branch-and-bound optimal algorithm in [6]. The running time of our algorithm is substantially less than that of [6]. For several examples where the algorithm in [6] ran for days and did not terminate, our algorithm produced optimal solutions in a few seconds.