Advanced neutral atom quantum systems are being developed by the industry due to its unique hardware features that enable efficient quantum circuit execution. In fact, neutral atom quantum systems are the only platforms that simultaneously support both long-range qubit interactions and native multi-qubit gates. However, the unique characteristics of neutral atom devices limit the applicability of existing qubit mapping methods developed for other quantum devices, and the state-of-the-art mapping approach [13] for neutral atom devices suffers from long runtime and low shuttle scheduling parallelism. We introduce a novel mapping and shuttling framework for neutral atom devices. We first partition the input circuit into a sequence of subcircuits, each associated with a mapping that enables the execution of all gates in the subcircuit. To find these mappings efficiently, we adopt a flexible strategy that dynamically switches between two mapping search methods. Then, for each pair of consecutive mappings, we schedule the shuttling operations required to transition between them and prioritize timing-critical operations to improve parallelism. We performed experiments on three benchmark sets, including circuits with up to 1617 qubits and more than $\mathbf{1 0 0, 0 0 0}$ gates. Our proposed framework resulted in high-quality routing solutions and consistently achieves higher fidelity with shorter runtime compared to existing approaches.

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.

To address the scalability challenges of quantum computing, the industry is shifting from monolithic architectures to modular quantum systems. By interconnecting multiple quantum processing units (QPUs) through communication links, modular quantum systems can scale to much higher number of qubits. However, the delay of inter-QPU operations is an order of magnitude greater than that of intra-QPU operations. To minimize the final circuit latency, a well-considered initial assignment of logical qubits in the circuit to QPUs in the system and careful insertion of inter-QPU operations are required. In this paper, we propose a timing-aware end-to-end circuit compilation framework for modular quantum systems. In the placement stage, a dependency- and interaction-aware assignment strategy is developed to assign logical qubits that interact early and frequently to nearby QPUs. In the routing stage, we optimize the insertion of inter-QPU operations and multiple intra-QPU operations to enable the execution of the gates. The selection of both inter- and intra-QPU operations is based on their circuit latency overhead, which is estimated using the operation delay and the available idle time of operand qubits that can cover the delay, as well as their benefit to subsequent gates. Our experiments assumed a realistic modular quantum system consisting of three interconnected QPUs with a total of 1,386 physical qubits. We evaluated our framework using two benchmark sets consisting of reversible arithmetic circuits and algorithmic circuits, with up to 1,300 qubits and over 800,000 two-qubit gates. Experimental results demonstrate that our approach outperformed the state-of-the-art compilation approach for modular quantum systems with over 73.8% and 46.9% reduction in final circuit latency and number of inserted inter-QPU operations, respectively. In addition, this advantage is preserved on a larger modular quantum system with four QPUs arranged in a square topology.

Adiabatic quantum-flux parametron (AQFP) is a superconducting technology with extremely low power consumption compared to traditional CMOS structures. Since AQFP logic gates are all clocked by AC current, extra buffer cells are required to balance the length of data paths. Furthermore, since the output current of an AQFP logic gate is too weak to drive more than one gate, splitter cells are needed to branch the output signals of multi-fanout gates. For an AQFP circuit, the total number of additional buffers and splitters may be much more than the number of logic gates, significantly impacting the circuit’s power, performance, and area. In this work, we propose several techniques to (i) reduce the total number of required buffers and splitters and (ii) perturb the levels of logic gates to seek more opportunities for optimization. Experimental results show that, compared to state-of-the-art methods, our approach can obtain optimized results with less additional inserted buffers/splitters in shorter run times, especially in larger circuits.

Advanced silicon-based spin-qubit chips are being developed by the industry because of its promising scalability for large-scale quantum computing. The silicon-based fabrication of spin-qubit devices allows them to scale to thousands of qubits while maintaining a relatively small area compared to other quantum technologies such as superconducting or neutral atom. However, the unique characteristics of spin-qubit devices limit the applicability of existing qubit routing methods developed for other quantum devices, and the state-of-the-art routing approach for spin-qubit devices overlooks some key factors, leading to suboptimal solution quality. We introduce a novel routing method for spin-qubit devices that leverages Dijkstra’s algorithm and breadth-first search to determine the routing path for the operand qubit(s) of each gate. To avoid redundant computations for routing paths, we determine the routing region for each gate and represent it as a bit vector, which enables efficient overlap checking between routing regions. We performed experiments on four benchmark sets, including circuits with up to 1617 qubits and more than 700,000 gates. These benchmark sets cover a wide range of quantum circuits, including reversible arithmetic, algorithmic, synthesized, and random circuits. Our proposed method resulted in high-quality routing solutions and outperformed the state-of-the-art qubit routing approach on spin-qubit devices with over 29% and 7% reduction in operation overhead and depth overhead, respectively.

To execute a quantum program, it has to be compiled for execution on the target quantum processor. The program is first converted into a logical circuit composed of elementary gates supported by the target processor. Most often the logical circuit cannot be executed directly on the quantum processor due to the limited connectivity between the physical qubits of the processor. So, a quantum compiler needs to perform qubit routing by inserting auxiliary gates to execute operations like SWAP, MOVE, and BRIDGE in order to satisfy the connectivity constraint. Qubit routing yields a physical circuit that can be executed on the target processor. Finally, the physical circuit still has to be scheduled considering the gate delays and the control constraints imposed by the shared classical control electronics of the quantum processor. For noisy intermediate-scale quantum processors, it is important to minimize the latency of the final scheduled physical circuit. However, solving qubit routing without considering gate delays and control constraints will inevitably lead to suboptimal final results. Here we propose a control and timing-aware qubit routing algorithm, CTQr, considering gate delays and control constraints. Moreover, CTQr performs gate merging on the fly in order to minimize the final circuit latency. The experimental results show that CTQr outperforms the state-of-art approach with 11.2%, 8.8%, and 54.6% average reduction in the circuit latency, number of additional gates, and execution time, respectively.

Traditionally, a standard cell library is composed of pre-designed cells all of which have identical height so that the cells can be placed in rows of uniform height on a chip. The desire to integrate more logic gates onto a single chip has led to a continuous reduction of row height with reduced number of routing tracks over the years. It has reached a point that not all cells can be designed with the minimum row height due to internal routability issue. Hybrid-row-height IC design with placement rows of different heights has emerged which offers a better sweet spot for performance and area optimization. [7] proposed the first row planning algorithm for hybrid-row-height design based on k-means clustering to determine the row configuration so that the cells in an initial placement can be moved to rows with matching height with as little cell displacement as possible. The biggest limitation of the k-means clustering method is that it only works for designs without any macros. Here we propose an effective and highly flexible dynamic programming approach to determine an optimized row configuration for designs with or without macros. The experimental results show that for designs without any macros, our approach resulted in 30.7% reduction in total cell displacement and 7.4% reduction in the final routed wirelength on average compared to the k-means clustering approach while satisfying the timing constraints. Additional experimental results show that our approach can comfortably handle designs with macros while satisfying the timing constraints.

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%.

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%.

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.

Adiabatic quantum-flux parametron (AQFP) is a superconducting technology with extremely low power consumption compared to traditional CMOS structure. Since AQFP logic gates are all clocked by AC current, extra buffer cells are required for balancing the length of data paths. Furthermore, since the output current of an AQFP logic gate is too weak to drive more than one gate, splitter cells are needed for branching the output signals of multi-fanout gates. For an AQFP circuit, the total number of additional buffers and splitters may be much more than the number of logic gates (up to 9 times in the benchmark circuits after optimization), which would greatly impact the power, performance, and area of the circuit. In this paper, we propose several techniques to (i) reduce the total number of required buffers and splitters, and (ii) perturb the levels of logic gates in order to seek more optimization opportunities for buffer and splitter reduction. Experimental results shows that our approach has better quality with comparable runtime compared to a retiming-based method from ASP-DAC'23. Moreover, our approach has quality which is on equal footing with the integer linear programming-based method also from ASP-DAC'23.

In current quantum devices, physical qubits are not fully connected so that two-qubit interaction can only be performed between specific pairs of physical qubits. To execute a quantum circuit, it is necessary to transform it into a functionally equivalent one that respects the constraints imposed by the target architecture. Quantum circuit transformation inevitably introduces additional gates which reduces the fidelity of the circuit. Therefore, it is important that the transformation method completes the transformation with minimal overheads. Quantum circuit transformation consists of two steps, initial mapping and qubit routing, and here we propose a DEAR (Dynamically-Extract-and-Route) framework to solve the qubit routing problem. A key insight of DEAR is that by maintaining a sufficient lookahead ability all the time, we can make much better routing decisions while effectively controlling the runtime. In our DEAR framework, we periodically extract a subcircuit by identifying a set of remaining gates that should be executed earlier than the others, and then applies A* search to determine how to insert a sequence of additional SWAP and BRIDGE operations into the subcircuit to obtain a high quality routing solution with minimum number of additional gates. In this work, we consider the insertion of both SWAP and BRIDGE operations while most previous works deal with SWAP insertion only. We evaluate our approach with four benchmark sets with different characterization on IBM Tokyo. The experimental results show that our approach outperforms the state-of-the-art work utilizing SWAP and BRIDGE insertion with 19.1% and 77.5% average reduction in the number of additional gates and runtime, respectively, starting from the same initial mapping. We also performed experiments on larger quantum devices such as Google Sycamore and IBM Rochester both with 53 physical qubits that have largely different architectures from one another and from IBM Tokyo. Again, DEAR was much faster and required significantly less amount of additional gates.

At the 3 nm node, a hybrid-row-height design paradigm has emerged for better power efficiency and performance optimization. A diverse cell library that includes multiple variants of a cell with different fin counts is available. Instead of using cells with the same fin count for the entire chip, a design may combine cells with two different fin counts. Cells with the same fin count can be laid down in the same row resulting in a chip with hybrid row heights. With this brand-new design paradigm, revisiting and revamping the conventional VLSI placement flow becomes necessary. There were attempts that addressed the placement problem associated with hybrid-row-height design at the global placement stage or the placement legalization stage. In this work, we first propose an effective detailed placement approach suitable for hybrid-row-height designs and then conduct a comprehensive study to evaluate the different options of forming a complete hybrid-row-height design placement flow. For the first time, the advantage of considering the row configuration early on in the global placement stage is confirmed. Besides, our proposed detailed placement approach can improve the final half-perimeter wirelength by over 7% on average which more than double the improvement obtainable by a basic detailed placement algorithm similar to the well-known FastDP.

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.

Power staple insertion is an effective means to mitigate IR drop in the advanced technology process. Previous works have shown that detailed placement refinement can greatly enhance the power staple insertion rate. However, with FinFET, it is necessary to consider the drain-to-drain abutment (DDA) constraints. We note that extra source node insertion for resolving DDA violations can interfere with power staple insertion. To handle DDA constraints and optimize power staple insertion at the same time, we formulate and solve a new DDA-aware placement refinement problem in this work. Given an initial nonoverlapping placement optimized for other conventional objectives, we compute a refined placement with cell shifting subject to DDA constraints such that the number of staple insertion slots can be maximized. An effective approach is proposed that supports a nonrestricted cell displacement range during placement refinement. It provides the flexibility to adjust the displacement bound of each cell dynamically in order to resolve all DDA violations. As a result, our algorithm guarantees that a placement solution with no DDA violation can always be computed without using a large displacement range for each cell which would require much longer runtime and larger average cell displacement. In addition to cell shifting, we incorporate concurrent cell flipping to reduce the required cell displacement to satisfy the DDA constraints and to facilitate power staple insertion. The experimental results showed the effectiveness of the proposed approach.

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.

Quantum computing is gaining more and more attention due to its huge potential and the constant progress in quantum computer development. IBM and Google have released quantum architectures with more than 50 qubits. However, in these machines, the physical qubits are not fully connected so that two-qubit interaction can only be performed between specific pairs of the physical qubits. To execute a quantum circuit, it is necessary to transform it into a functionally equivalent one that respects the constraints imposed by the target architecture. Quantum circuit transformation inevitably introduces additional gates which reduces the fidelity of the circuit. Therefore, it is important that the transformation method completes the transformation with minimal overheads. It consists of two steps, initial mapping and qubit routing. Here we propose a reinforcement learning-based model to solve the initial mapping problem. Initial mapping is formulated as sequence-to-sequence learning and self-attention network is used to extract features from a circuit. For qubit routing, a DEAR (Dynamically-Extract-and-Route) framework is proposed. The framework iteratively extracts a subcircuit and uses A* search to determine when and where to insert additional gates. It helps to preserve the lookahead ability dynamically and to provide more accurate cost estimation efficiently during A* search. The experimental results show that our RL-model generates better initial mappings than the best known algorithms with 12% fewer additional gates in the qubit routing stage. Furthermore, our DEAR-framework outperforms the state-of-the-art qubit routing approach with 8.4% and 36.3% average reduction in the number of additional gates and execution time starting from the same initial mapping.

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.

Due to the aggressive scaling of advanced technology nodes, multiple-row-height cells have become more and more common in VLSI design. Consequently, the placement of cells is no longer independent among different rows, which makes the traditional row-based legalization techniques obsolete. In this work, we present a highly efficient linear-time mixed-cell-height legalization approach that optimizes both the total cell displacement and the maximum cell displacement. First, a fast window-based cell insertion technique introduced in [4] is applied to obtain a feasible initial row assignment and cell ordering which is known to be good for total displacement consideration. In the second stage, we use an iterative cell swapping algorithm to change the row assignment and the cell order of the critical cells for maximum displacement reduction. Then we develop an optimal linear time DAG-based fixed row and fixed order legalization algorithm to minimize the maximum cell displacement. Finally, we propose a cell shifting heuristic to reduce the total cell displacement without increasing the maximum cell displacement. Using the proposed approach, the quality provided by the global placement can be preserved as much as possible. Compared with the state-of-the-art work [4], experimental results show that our proposed algorithm can reduce the maximum cell displacement by more than 11% on average with similar average cell displacement.

Power staple insertion is a new methodology for IR drop mitigation in advanced technology nodes. Detailed placement refinement which perturbs an initial placement slightly is an effective strategy to increase the success rate of power staple insertion. We are the first to address the manufacturing-aware power staple insertion optimization problem by triple-row placement refinement. We present a correct-by-construction approach based on dynamic programming to maximize the total number of legal power staples inserted subject to the design rule for 1D patterning. Instead of using a multidimensional array which incurs huge space overhead, we show how to construct a directed acyclic graph (DAG) on the fly efficiently to implement the dynamic program for multi-row optimization in order to conserve memory usage. The memory usage can thus be reduced by a few orders of magnitude in practice.

In a single-flux-quantum (SFQ) circuit, almost all cells need to receive the clock signal which incurs a high clock routing overhead. Besides, the clock tree of an SFQ circuit requires the insertion of a clock splitter cell at every tree branching point which renders the conventional design flow of placement followed by clock tree synthesis ineffective to obtain a high quality clock tree with low clock skew. To address these issues, we propose a two-stage global placement methodology and a placement refinement algorithm after placement legalization. Our two-stage global placement methodology first applies a conventional global placement algorithm to place the cells in the given SFQ circuit evenly, which is followed by clock tree synthesis and clock splitter insertion, and then performs a second stage of global placement to re-place both the original cells and clock splitters at the same time. In the second global placement stage, the look-ahead legalization technique is used to spread out the original cells and the clock splitters, and the clock tree is re-synthesized several times to obtain an optimized clock tree topology such that there are little overlaps of the clock splitters with the original circuit cells. In addition, the total wirelength of data signals and clock signal is optimized concurrently. After legalizing the placement of all cells, our placement refinement method can be run to further reduce the clock skew. Compared with the previous state-of-the-art work, on average we can reduce the total half-perimeter wirelength and clock skew by 9% and 31%. respectively.

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.

As 2.5-D field-programmable gate arrays (FPGAs) have larger logic capacity and higher pin counts compared to conventional FPGAs, they are already deployed in some multi-FPGA systems. 2.5-D FPGA consists of multiple dies connected through an interposer. Since the interposer provides only a fraction of the amount of interconnect resources with an increased delay compared to that within individual dies, it is important to reduce the number of signal crossings between dies both for routability and timing consideration when a circuit is mapped to a 2.5-D FPGA. In a multi-2.5D FPGA system with time-multiplexed hardwired inter-FPGA connections, there can be tens of thousands of inter-FPGA signals incident with each FPGA and their pin assignment can greatly affect the amount of die-crossing signals within the FPGAs. In this article, we formulate the pin assignment problem for such systems with the objective of minimizing signal crossings between dies within the individual FPGAs. Taking into consideration of the multi-die structure of 2.5-D FPGA, we propose two different iterative refinement approaches to the problem, one based on integer linear programming (ILP) and the other algorithm C-2MCF based on clustering optimization and minimum cost flow optimization. Compared to a greedy pin assignment heuristic for minimization of signal crossings between dies, C-2MCF produced 27.1% less crossings on average. While the ILP-based algorithm has up to 1% quality advantage over C-2MCF for moderate-sized instances, C-2MCF is orders of magnitude faster and can comfortably handle very large problem instances. In addition, the proposed minimum cost flow techniques within C-2MCF can also be used in conjunction with any other possible pin assignment method to enhance the final result.

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.

Advanced 2.5D FPGAs with larger logic capacity and higher pin counts compared to conventional FPGAs are commercially available. Some multi-FPGA systems have already utilized 2.5D FPGAs. Commercial 2.5D FPGA consists of multiple dies connected through an interposer. The interposer provides a fraction of the amount of interconnect resources with increased delay compared to that within individual dies. A recent study has shown the benefits of reducing signal crossings between dies on routability and timing when a circuit is mapped to a 2.5D FPGA. In a multi-2.5D FPGA system with multiplexed hardwired inter-FPGA connections, there can be tens of thousands of inter-FPGA signals incident with each FPGA and their pin assignment can greatly affect the amount of signal crossings between dies. In this paper, we formulate the pin assignment problem for such system with the objective of minimizing signal crossings between dies within the individual FPGAs. Taking into consideration of the multi-die structure of 2.5D FPGA, we propose an effective and efficient iterative improvement algorithm based on integer linear programming to the pin assignment problem. Experimental results show that our algorithm can reduce signal crossings between dies in the individual FPGAs by over 30% on average compared to two heuristic approaches.

In 10nm technology node, self-aligned double patterning (SADP) and triple patterning lithography (TPL) allow us to achieve minimum wiring pitch of around 45nm. While metal layers can be printed by SADP, via layer manufacturing requires TPL to maintain design rules. SADP-aware detailed routing is proposed to ensure decomposability of metal layer patterns. However, its routing solution does not automatically guarantee TPL decomposable via layers. Vias have an inherently low reliability and via failure causes a great yield loss. Double via insertion (DVI) is an effective means to increase yield by reducing via failures. With the restriction of SADP design rules and consideration of TPL decomposability for via layers, DVI becomes a more challenging problem. In this paper, we consider DVI and via layer TPL manufacturability simultaneously in SADP-aware detailed routing. Both spacer-is-metal and spacer-is-dielectric types of SADP are considered. Furthermore, we tackle the TPL-aware DVI in postrouting stage. Both ILP and high-performance heuristic solutions are proposed. The experimental results demonstrate our router can obtain 100% routability and TPL decomposable via layers with reduced dead via count. Meanwhile, compared with the ILP approach to solve TPL-aware DVI problem, the heuristic approach can achieve similar solution quality and significant speedup.

Block copolymer directed self-assembly (DSA) has emerged as an economical complementary technology in the midst of next generation lithography. In particular, DSA has a strong potential for contact hole and via patterning. However, high via density in sub-10nm technology node makes it very hard to manufacture all the vias using DSA only. Complementing DSA with multiple patterning (MP) is an option such that multiple masks are used to print the DSA guiding templates for guiding the self-assembly of the block copolymer. Besides, redundant via insertion is desirable because it is an effective means to reduce yield loss due to via defect and improve reliability. To the best of our knowledge, we are the first work to consider DSA-MP decomposition and redundant via insertion with dummy via consideration to enhance manufacturability. Experimental results shows the effectiveness and efficiency of our method compared with previous works and resulted in 0 unmanufacturable vias for all benchmarks.

A traditional standard cell library consists of various functional cells with the same height, which could speed up VLSI design flow since designers could align cells to placement sites in rows. However, in advanced nodes, cells are designed with different heights. With mixed cell heights, we can design simple cells (e.g. inverters) as single-row-height cells, and complex cells (e.g. flip-flops) as multiple-row-height cells. Nevertheless, placement legalization becomes more difficult with mixed-cell-height libraries. In this paper, we propose a parallel legalization method for mixed-cell-height standard cell libraries to minimize total displacement. Experimental results show that our method has a 19\% improvement on average in displacement compared with the state-of-the-art work [9].

Split fabrication is a promising approach to security against attacks by untrusted foundries. While existing split fabrication methods consider the overhead of conventional objectives such as wirelength and timing, they mostly neglect manufacturability - an unavoidable challenge in nanometer technologies. Observing that security and manufacturability can be addressed in a synergistic manner, this work introduces routing techniques that can simultaneously improve both security and manufacturability in terms of either Chemical Mechanical Planarization (CMP) uniformity or Self-Aligned Double Patterning (SADP) compliance. The effectiveness of these techniques is confirmed by experiments on benchmark circuits.

Split fabrication is a promising approach to security against attacks by untrusted foundries. While existing split fabrication methods consider the overhead of conventional objectives such as wirelength and timing, they mostly neglect manufacturability - an unavoidable challenge in nanometer technologies. Observing that security and manufacturability can be addressed in a synergistic manner, this work introduces routing techniques that can simultaneously improve both security and manufacturability in terms of either Chemical Mechanical Planarization (CMP) uniformity or Self-Aligned Double Patterning (SADP) compliance. The effectiveness of these techniques is confirmed by experiments on benchmark circuits.

The significantly increased number of routing design rules at sub-20nm nodes has made pin access one of the most critical challenges in detailed routing. Resolving pin access issues in detailed routing stage may be too late due to the fixed pin locations, especially in the area with high pin density. In placement stage when cell movement is allowed, the consideration of pin access has more flexibility. We propose a refinement stage after detailed placement to improve pin access. To respect the given placement solution, the refinement techniques are restricted to cell flipping, same-row adjacent cell swap, and cell shifting. A cost function is presented to model pin access for each pin-to-pin connection. Based on the cost function, two phases are proposed to improve pin access for all the connections simultaneously. In the first phase, we refine the placement by cell flipping and same-row adjacent cell swap. The problem is solved by dynamic programming row by row. In the second phase, only cell shifting is used, and a linear program is formulated to further refine the placement. Experimental results demonstrate that the proposed detailed placement refinement can improve pin access and reduce unroutable nets by about 33% in the detailed routing stage.

As the technology nodes scale down to sub-22 nm, double patterning lithography has been considered as a practical solution for layout manufacturing. Compared with litho-etch-litho-etch, self-aligned double patterning (SADP) has better overlay control. To have a better SADP layout decomposability of routing patterns, we consider SADP during detailed routing stage. Two major types of SADP processes are considered: 1) spacer-is-dielectric type and 2) spacer-is-metal type. Different from previous works, the idea of color preassignment is adopted for SADP-aware detailed routing. An elegant graph model is proposed to capture both routing and SADP manufacturing cost. They greatly simplify the problem to maintain SADP design rules in detailed routing. We apply a negotiated congestion based rip-up and reroute scheme to achieve better routability while maintaining SADP design rules. Compared with other state-of-the-art academic works, our approach does not produce any side overlay error and no SADP design rules violation is reported. Meanwhile, a better solution in terms of total wirelength, routability, and runtime is achieved.

Threshold voltage assignment is a very effective technique to reduce leakage power consumption in modern integrated circuit design. As feature size continues to decrease, the layout constraints [called minimum implant area (MinIA) constraints] on the implant area, which determines the threshold voltage of a device, are becoming increasingly difficult to satisfy. It is necessary to take these constraints into consideration during the placement stage. In this paper, we propose to resolve the MinIA constraint violations of a given placement by performing simultaneous detailed placement and threshold voltage refinement. We first present an optimal and efficient mixed integer-linear programming (MILP)-based algorithm to handle intrarow MinIA constraints. We then extend the MILP-based algorithm to handle both inter-row and intrarow MinIA constraints. Both of our algorithms guarantee to fix all MinIA constraint violations. Experimental results demonstrate that our algorithms only perturb the original placement and threshold voltage assignment solutions minimally to eliminate all violations and are fast in practice.

Threshold voltage assignment is a very effective technique to reduce leakage power consumption in modern integrated circuit (IC) design. As feature size continues to decrease, the layout constraints (called MinIA constraints) on the implant area, which determines the threshold voltage of a device, are becoming increasingly difficult to satisfy. It is necessary to take these constraints into consideration during the layout stage. In this paper, we propose to resolve the MinIA constraint violations by a simultaneous detailed placement and threshold voltage refinement approach. We present an optimal and efficient mixed integer-linear programming (MILP)-based algorithm which guarantees to fix all MinIA constraint violations. Experimental results demonstrate that our algorithm only perturbs the original placement and threshold voltage assignment solutions minimally to eliminate all violations and is fast in practice.

In 10nm technology node, self-aligned double patterning (SA DP) and triple patterning lithography (TPL) allow us to achieve minimum wiring pitch of around 45nm. While metal layers can be printed by SADP, via layer manufacturing requires TPL to maintain design rules. SADP-aware detailed routing is proposed to ensure decomposability of metal layer patterns. However, its routing solution does not automatically guarantee TPL decomposable via layers. Vias have an inherently low reliability and via failure causes a great yield loss. Double via insertion (DVI) is an effective means to increase yield by reducing via failures. With the restriction of SADP design rules and consideration of TPL decomposability for via layers, DVI becomes a more challenging problem. In this paper, we consider DVI and via layer TPL manufacturability simultaneously in SADP-aware detailed routing. The experimental results demonstrate our router can obtain 100% routability and TPL decomposable via layers with reduced dead via count.

Pin assignment and escape routing are two closely related problems and it is desired to consider routability during pin assignment for package-board co-design. During pin assignment and escape routing, differential pairs and blind-via usage are two major factors to be considered in modern printed circuit board designs. However, most previous works only target on either differential pairs or blind-via usage but cannot handle both of them simultaneously. In this paper, we propose the first package-board co-design method to optimize the pin assignment and escape routing in the presence of differential pairs and blind-via usage for grid pin array. Experimental results show that our package-board co-design flow can achieve wirelength improvement and reduce the number of layers required compared with competitive baseline flows.

Static timing analysis has always been indispensable in integrated circuit design. In order to consider design and electrical complexities (e.g., crosstalk coupling, voltage drops) as well as manufacturing and environmental variations, timing analysis is typically done using an “early-late” split. The early-late split timing analysis enables timers to effectively account for any within-chip variation effects. However, this dual-mode analysis may introduce unnecessary pessimism, which can lead to an over-conservative design. Thus, common path pessimism removal (CPPR) is introduced to eliminate this pessimism during timing analysis. A naive approach would require the analysis of all paths in the design. For today's designs with millions of gates, enumerating all paths is impractical. In this paper, we propose a new approach to effectively prune the redundant paths and develop a multi-threaded timing analysis tool called MTimer for fast and accurate CPPR. The results show that our timer can achieve 3.53X speedup on average comparing with the winner of the TAU 2014 contest and maintain 100% accuracy on removing common path pessimism during timing analysis.

As the technology nodes scale down to 22nm and beyond, Double Patterning Lithography (DPL) has been considered as a practical solution for manufacturing process. Compared with Litho-Etch-Litho-Etch (LELE), Self-Aligned Double Patterning (SADP) has better overlay tolerance. Two types of SADP process are popularly used for the state-of-the-art lithography patterning: Spacer-Is-Dielectric (SID) and Spacer-Is-Metal (SIM). Meanwhile, Self-Aligned Quadruple Patterning (SAQP), as a natural extension of SADP, is expected to be one of the major solutions for future process requirement after the 16nm/14nm technology node. In order to have better decomposability of layout patterns, we consider SIM type SADP/SAQP during detailed routing stage. The idea of color pre-assignment is adopted and a graph model is proposed which greatly simplifies the problem and reduces design rule violation. Then, the negotiated congestion based scheme is applied for detailed routing based on our proposed graph model. Compared with other state-of-art works, our approach does not produce any side overlay error and no design rule violation is reported. Meanwhile, a better solution in terms of total wirelength, via count, routability, and runtime is achieved.

Multicore instruction-set simulation (MCISS) has become more and more important due to tremendous increase in number of multicore designs. To boost the speed of MCISS, one of the most effective and commonly used approaches is parallel simulation. However, timing synchronization must be applied to ensure accurate simulation results of parallel MCISS, and may induce huge synchronization overhead. In this paper, we propose a highly efficient and effective parallel MCISS approach by synchronizing timing before each synchronization function (SF) call. We improve the applicability of the state-of-the-art critical-section-level simulation approach with a generic blocking/nonblocking send/receive model covering all types of SFs. To further reduce synchronization overhead, we also introduce optimization methods such as a hybrid scheduling technique and provide an analysis algorithm that helps the designers to choose the host platform with the best simulation performance. Experiments show that the proposed approach attains a simulation speed of up to 285 MIPS, while producing accurate timing and functional results.

Electron-beam (e-beam) lithography has long been employed for mask writing but the write time is increasing due to the escalating mask pattern complexity. Besides, e-beam direct write is being pursued as an alternative solution for chip production in the sub-22 nm regime. To improve the throughput of e-beam lithography, character projection method is commonly employed and a critical problem is to pack as many useful characters as possible onto the stencil. In this paper, we consider three enhancements in packed stencil design over previous works. First, the fact that the pattern of a character can be located anywhere within its enclosing projection region is exploited to facilitate flexible blank space sharing. Second, the use of multiple shaping apertures with different sizes is explored. Third, the use of overlapping shots for printing some characters is investigated. For the packed stencil design problem with flexible blank space sharing and multiple shaping apertures, two dynamic programming-based algorithms are proposed, one allows overlapping shots and the other does not. Experimental results show that the proposed enhancement and the associated algorithms can significantly reduce the total shot count and hence improve the throughput of e-beam lithography.

Electron-beam direct write (EBDW) lithography is a promising solution for chip production in the sub-22nm regime. To improve the throughput of EBDW lithography, character projection method is commonly employed and a critical problem is to pack as many characters as possible onto the stencil. In this paper, we consider two enhancements in packed stencil design over previous works. First, the use of multiple shaping apertures with different sizes is explored. Second, the fact that the pattern of a character can be located anywhere within its enclosing projection region is exploited to facilitate flexible blank space sharing. For this packed stencil design problem with multiple shaping apertures and flexible blank space sharing, a dynamic programming based algorithm is proposed. Experimental results show that the proposed enhancement and the associated algorithm can significantly reduce the total shot count and hence improve the throughput of EBDW lithography.

Adaptive logic module (ALM) in modern field programmable gate array can serve as one 6-input lookup table (LUT) or two smaller lookup tables under certain constraints. In a typical design flow, a netlist of LUTs formed after technology mapping has to be merged into ALMs and then packed into coarse-grained logic blocks (CLBs) before placement and routing. How the LUTs are merged and the ALMs are packed has a significant impact on the quality of the placement. We propose a novel wirelength-driven algorithm to merge the LUTs and pack the ALMs to ensure that it will not adversely affect the final wire-length. Experimental results show that substituting AAPack [8] by our algorithm yields about 14.54% reduction in number of tracks required for routing and 17.97% wirelength improvement for ALM-based FPGA. Applying our algorithm to traditional FPGA, the minimum channel width and wirelength are reduced by 16.59% and 17.57%, respectively, compared to T-VPack.

Due to the resolution limitations of optical lithography equipment, 1D gridded layout design is gaining steam. Self-aligned double patterning (SADP) is a mature technology for printing 1D layouts. However, for 20nm and beyond, SADP using a single trim mask becomes insufficient for printing all 1D layouts. A viable solution is to complement SADP with e-beam lithography. In this paper, in order to increase the throughput of printing a 1D layout, we consider the problem of e-beam shot count minimization subject to bounded line end extension constraints. Two different approaches of utilizing the trim mask and e-beam to print a layout are considered. The first approach is under the assumption that the trim mask and e-beam are used for end cutting. The second is under the assumption that the trim mask and e-beam are used to rid of all unnecessary portions. We propose elegant ILP formulations for both approaches. Experimental results show that both ILP formulations can be solved efficiently. The pros and cons of the two approaches for manufacturing 1D layout are discussed.

Electron-beam maskless lithography is being actively explored by the semiconductor industry for chip production in the sub-22 nm regime. Character projection allows in one e-beam shot the printing of complex pattern rather than merely a single rectangle or triangle as in variable-shaped beam projection. However, those circuit patterns that do not match any character on the stencil still have to be written by variable-shaped beam projection. We investigate a new problem of character and stencil co-optimization with blank space sharing between characters so as to minimize the total number of shots required for printing a circuit. We exploit the fact that the blank spaces on the sides of a character can be adjusted by moving the pattern to be printed within its projection region to facilitate blank space sharing so as to pack more characters into the stencil. Even though the co-optimization problem is shown to be NP-complete, we are able to design an elegant approximation algorithm, CASCO. Experiments confirm that the solutions by CASCO are nearly optimal. Compared to the published state-of-the-art, CASCO reduces the shot count by 1.59 times, while it is also orders of magnitude faster.

Due to process limitations, wiring rules are imposed by foundries on chip layout. Under nanometer wiring rules, the required separation between two wire ends is dependent on their surrounding wires, and there is a limit on the minimum length of each wire segment. Yet, traditional maze routing algorithms are not designed to handle these rules, so rule violations are corrected by post-processing and the quality of result is seriously impacted. For this reason, we propose a new maze routing algorithm capable of handling these wiring rules. The proposed algorithm is proved to find a legal shortest path with time complexity of O(n), where n is the number of grid points. Experiments with seven tight industrial cases show that the runtime of a commercial router is reduced by 2.4 times and the total wire length is also reduced by 3% on average.

Due to process limitations, wiring rules are imposed on chip layout by foundries. Under nanometer wiring rules, the required separation between two wire ends is dependent on their surrounding wires, and there is a limit on the minimum length of each wire segment. However, traditional shortest path algorithms are not properly designed for these rules. In the paper, we propose a maze routing algorithm, called MANA, capable of finding legal shortest paths under these rules. Experiments with seven industrial cases show that by handling these rules during maze routing, 94% of the violations are prevented on average, and the overall runtime of a commercial router is reduced by 71%. In addition, the total wire length is also reduced by 3% on average.

With the increasing complexity of circuit design in recent years, the pin assignment and escape routing problems for field-programmable gate array (FPGA) on a printed circuit board (PCB) have become greatly difficult due to the fast increase in pin count and density. Most existing works only focus on either the FPGA pin assignment problem or the PCB escape routing problem independently, but cannot handle them simultaneously. In this paper, we propose an integer linear programming based method to simultaneously solve the problem of pin assignment and escape routing for FPGA-PCB co-design. Moreover, differential pairs and single-ended signals are handled together optimally to minimize the total wirelength in escape routing. Encouraging experimental results are shown to support our approach showing reduction in the number of PCB routing layers and/or wirelength.

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.

Modern field programmable gate arrays like Altera's Stratix Series have adopted the adaptive logic module (ALM) structure due to its potential performance and area advantages. An ALM can implement a single logic function or can be fractured into two smaller lookup tables (LUTs). In this paper, we propose an ALM mapping algorithm, ALMmap, for area minimization with bounded depth. We revamp the traditional iterative cut-based mapping flow and introduce a procedure for bounded depth mapping generation with dynamic area recovery that effectively combines cut selection, mapping, and area recovery together. In addition, we introduce a new procedure for computing cut set for ALM minimization under a depth constraint. The notion of area flow which has been used successfully for cut selection to reduce LUT count is revised for cut selection to reduce ALM count. ALMmap obtains depth optimal solutions that are 25.6% and 11.6% smaller, on average, than those produced by a classical mapper and WireMap, respectively.

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.

We propose a power-driven flip-flop (FF) merging and relocation approach that can be applied after conventional timing-driven placement and before clock network synthesis. It targets to reduce the clock network size and thus the clock power consumption while controlling the switching power of the nets connected to the FFs by selectively merging FFs into multibit FFs and relocating them under timing and placement density constraints. The experimental results are very encouraging. For a set of benchmarks, our approach reduced the switching capacitance of clock network by 36%-43% after gated clock tree synthesis. Finally, the total switching capacitance of clock network and nets connected to the FFs is reduced by 24%-29%.

To sustain the pace of integration density improvement, 3-D IC technology is hailed as a “Beyond Moore” driver. It has been demonstrated to have great potential to diminish footprint, reduce interconnect delay, promote system performance, decrease power consumption and facilitate integration of heterogeneous processes. Besides, it is commonly cited as a means of reducing lateral wirelength. Some early theoretical and experimental studies have also shown that 3-D IC can significantly reduce lateral wirelength. However, the effect of through-silicon via (TSV) area overhead on the wirelength has been largely overlooked. In this paper, we derive a mathematical upper bound on the wirelength benefit of placing a circuit in 3-D that takes the TSV area overhead into account. For a set of IBM placement benchmarks scaled to the 32 nm process, we show that 3-D integration cannot help to reduce the wirelength under current TSV technologies.

To successfully route a design, one essential requirement is to allocate sufficient routing resources. In this paper, we show that allocating routing resources based on horizontal and vertical (H/V) cut-demands can greatly improve routability especially for designs with thin areas. We then derive methods to predict the maximum H/V cut-demands and propose two cut-demand based approaches, one is to allocate routing resources considering the maximum H/V cut-demands and the other is to consolidate fragmented metal-1 routing resources for effective resource utilization. Experimental results demonstrate that the resource allocation method can precisely determine design areas and the resource consolidation method can significantly improve routability. With better routability, the routing time is about 5 times faster on average and the design area can be further reduced by 2-15%.

With the increasing complexity of circuit design in recent years, the pin assignment and escape routing problems for FPGA on a PCB have become greatly difficult due to the fast increase in pin count and density. Most existing works only focus on either the FPGA pin assignment problem or the PCB escape routing problem independently but cannot handle them simultaneously. In this paper, we propose an integer linear programming (ILP) based method to simultaneously solve the pin assignment and escape routing problems for FPGA-PCB code sign. Because of the underlying network structure of our formulation, we can solve the problem efficiently. Experimental results demonstrate that our method can achieve an average 54.5% wire length improvement over the common two-stage approach.

We propose a power-driven flip-flop merging and relocation approach that can be applied after conventional timing-driven placement and before clock network synthesis. It targets to reduce the clock network size and thus the clock power consumption, as well as the switching power of the nets connected to the flip-flops by selectively merging flip-flops into multi-bit flip-flops and relocating them under timing and placement density constraints. The experimental results are very encouraging. For a set of benchmarks, our approach reduced the clock wirelength by 30 to 50%. Meanwhile, the switching power of signal nets connected to the flip-flops were reduced by 2 to 43%.

In this paper, we present an algorithm called FOARS for obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction. FOARS applies a top-down approach which first partitions the set of pins into several subsets uncluttered by obstacles. Then an obstacle-avoiding Steiner tree is generated for each subset by an obstacle aware version of the rectilinear Steiner minimal tree algorithm FLUTE. Finally, the trees are merged and refined to form the OARSMT. To guide the partitioning of pins, we propose a novel algorithm to construct a linear-sized obstacle-avoiding spanning graph which guarantees to contain a rectilinear minimum spanning tree if there is no obstacle. Experimental results show that FOARS is among the best algorithms in terms of both wirelength and runtime for testcases both with and without obstacles.

This paper presents a completely new approach to the problem of hypergraph clustering for wirelength-driven placement. The novel algorithm we propose is called SafeChoice (SC). Different from all previous approaches, SC is proposed based on a fundamental theorem, safe condition which guarantees that clustering would not degrade the placement wirelength. To mathematically derive such a theorem, we first introduce the concept of safe clustering, i.e., do clustering without degrading the placement quality. To efficiently check the safe condition for pair-wise clustering, we propose a technique called selective enumeration. SafeChoice maintains a global priority queue based on the safeness and area of potential clusters. Using a simple heuristic, it automatically stops clustering when generating more clusters would degrade the placement wirelength. Moreover, we extend SafeChoice to do clustering while considering the object physical locations, i.e., physical clustering. Finally, we apply SafeChoice into a two-phase placement framework and propose a high-quality analytical placement algorithm called SCPlace. Comprehensive experimental results show that the clusters produced by SC consistently help the placer to achieve the best wirelength among all other clustering algorithms, and SCPlace generates the best half-perimeter wirelength compared with all other state-of-the-art placers.

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.

Obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is becoming one of the most sought after problems in modern design flow. In this paper we present FOARS, an algorithm to route a multi-terminal net in the presence of obstacles. FOARS is a top down approach which includes partitioning the initial solution into subproblems and using obstacle aware version of Fast Lookup Table based Wire-length Estimation (OA-FLUTE) at a lower level to generate an OAST followed by recombining them with some backend refinement. To construct an initial connectivity graph FOARS uses a novel obstacle-avoiding spanning graph (OASG) algorithm which is a generalization of Zhou's spanning graph algorithm without obstacle [1]. FOARS has a run time complexity of O(n log n). Our experimental results indicate that it outperforms Lin et al. [2] by 2.3% in wirelength. FOARS also has 20% faster run time as compared with Long et al. [3], which is the fastest solution till date.

This paper presents SafeChoice (SC), a novel clustering algorithm for wirelength-driven placement. Unlike all previous approaches, SC is proposed based on a fundamental theorem, safe condition which guarantees that clustering would not degrade the placement wirelength. To derive such a theorem, we first introduce the concept of safe clustering, i.e., do clustering without degrading the placement quality. To check the safe condition for pair-wise clustering, we propose selective enumeration technique. SC maintains a global priority queue (PQ) based on the safeness and area of potential clusters. Iteratively the cluster at the top of the PQ is formed. SC automatically stops clustering when generating more clusters would degrade the placement wirelength. To achieve other clustering objectives, e.g., any target clustering ratio, SC is able to perform under three different modes. Comprehensive experimental results show that the clusters produced by SC consistently help the placer to achieve the best wirelength among all other clustering algorithms.

Flip-chip is a solution for designs requiring more I/O pins and higher speed. However, the higher speed demand also brings the issue of signal skew. In this paper, we propose a new 3-stage design layout methodology for flip-chip considering signal skew. Firstly, we produce an initial bumper signal assignment, and then solve the flip-chip floorplanning problem using a partitioning-based technique to spread the modules across the flip-chip as the distribution of its bumpers. With an anchoring and relocation strategy, we can effectively place I/O buffers at desirable locations. Finally, we further reduce signal skew and monotonic routing density by refining the bumper signal assignment. Experimental results show that signal skew of traditional floorplanners range from 4% to 280% higher than ours. And the total wirelength of other floorplanners is as much as 100% higher than ours. Moreover, our signal refinement method can further decrease monotonic routing density by up to 8% and signal skew by up to 11%.

This paper accurately considers wire short defects and proposes an algorithm to guarantee IC chip yield rate improvement for redundant wire insertion. Without considering yield rate degradation caused by shorts, traditional methods may even lead to yield rate loss. However, shorts are more complicated to analyze than opens. Moreover, since any two points of a routed net can be connected by a redundant wire, the number of possible insertion patterns for a chip is un-tractable. To maximize yield rate improvement and to make the problem tractable, we identify a key insight, tolerance-ratio, as an effective guide for choosing insertion patterns and insertion order. Finally, to guarantee yield rate improvement, only positive gain redundant wires are committed. Experimental results show that, compared with unprocessed cases, all yield rate improvements in the proposed algorithm are positive, and the defect rates are reduced by up to 65% and by 24% on average. On the other hand, without considering shorts, the defect rate can increase as much as 7%.

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.

We propose an efficient algorithm to construct a low-power zero-skew gated clock network, given the module locations and activity information. Unlike previous works, we consider masking logic insertion and buffer insertion simultaneously, and guarantee to yield a zero-skew clock tree. Both the logical and physical information of the modules are carefully taken into consideration when determining where masking logic should be inserted. We also account for the power overhead of the control signals so that the total average power consumption of the constructed zero-skew gated clock network can be minimized. To this end, we present a recursive approach to compute the effective switched capacitance of a general gated and buffered clock network, accounting for both the clock tree's and controller tree's switched capacitance. The power consumptions of the gated clock networks constructed by our algorithm are 20 to 36% lower than those reported in the best previous work in the literature.

Using multiple supply voltages on a SoC design is an efficient way to achieve low power. However, it may lead to a complex power network and a huge number of level shifters if we just set the cores to operate at their respective lowest voltage levels. We present two formulations for the voltage level assignment problem. The first is exact but takes longer time to compute a solution. The second can be solved much faster with virtually no loss on optimality. In addition, we propose a modification to the traditional floorplanning framework. Unlike previous works (Jingcao Hu et al., 2004) and (Hung et al., 2005), we can optimize the total power consumption, the level shifter overhead, and the power network complexity without compromising the wirelength and the chip area. In the experiments, we obtained 17- 53% power savings with voltage island generation.

The designers of field-programmable gate arrays (FPGAs) always devote to optimize the chip performance. The interconnect delay is a crucial determining factor of circuit performance in FPGA based design. In FPGAs, signals passing through a long wire do not always exit at the end of the wire. Therefore, the expected delay other than end to end delay of the long wire should be optimized. This paper is the first work that addresses expected delay optimization for FPGA interconnect. We present an optimal dynamic programming based approach to insert and size buffers to minimize the expected delay. The experimental results showed that the expected delay of the interconnect buffered with consideration of expected delay optimization sometimes can be significantly smaller than the interconnect buffered for end-to-end delay minimization.

As the VLSI manufacturing technology advances into the deep sub-micron (DSM) era, the mask cost can reach one or two million dollars. Multiple project wafers (MPW) which put different dies onto the same set of masks is a good cost-sharing approach. Every design needs to be produced by its desired technology process, such as 1 poly with 4 metal layers (1P4M), or 1 poly with 5 metal layers (1P5M). Dies with different desired manufacturing processes cannot be produced from the same wafer, but they can be put onto the same set of masks in order to reduce the total cost of the used masks and wafers. In this paper, we propose a novel integer linear programming (ILP)-based floorplanner for shuttle runs consisting of projects requiring different desired processes. Two simulated annealing-based side-to-side wafer dicing planners are also presented. Experimental results show that our approach achieves 28% wafer reduction on average compared to a previous simulated annealing-based reticle floorplanner.

We consider the placement of FPGA designs with multiple I/O standards on modern FPGAs that support multiple I/O standards. We propose an efficient approach to solve the constrained I/O placement problem by 0-1 integer linear programming within a high performance placement flow. We derive an elegant 0-1 integer linear program formulation which is applicable not only for devices with symmetric I/O banks but also for devices with asymmetric I/O banks (i.e., different banks may have different sizes and/or support different subsets of I/O standards). Moreover, it is capable of handling user's pre-locked I/Os. We also show that additional restrictions such as conditional usage of Vref pins can be easily incorporated. Our formulation involves only a small number of 0-1 integer variables independent of the device size or the number of I/O objects, hence our approach can comfortably handle very large problem instances. Extensive experimentation showed that the 0-1 integer linear program corresponding to a feasible instance of the constrained I/O placement problem can be solved in seconds.

In this paper, we present the first exact approach to solve the constrained input/output (I/O) placement problem for field programmable gate arrays (FPGAs) that support multiple I/O standards. We derive a compact integer linear program formulation for the constrained I/O placement problem. The size of the integer linear program derived is independent of the number of I/O objects to be placed and, hence, is scalable to very large design instances. For example, for a Xilinx Virtex-E FPGA, the number of integer variables required is never more than 32 and is much smaller for practical design instances. Extensive experimental results using a noncommercial integer linear program solver shows that it only takes seconds to solve the resultant integer linear program in practice. In addition, we also propose a new overall placement flow to place both core logic and I/Os.

We study the technology mapping problem for LUT-based FPGAs targeting at power minimization. The problem has been proved to be NP-hard previously. Therefore, we present an efficient heuristic algorithm to generate low-power mapping solutions. The key idea is to compute and select low-power K -feasible cuts by an efficient incremental network flow computation method. Experimental results show that our algorithm reduces power consumption as well as area over the best algorithms reported in the literature. In addition, we present an extension to compute depth-optimal low-power mappings. Compared with Cutmap, a depth-optimal mapper with simultaneous area minimization, we achieve a 14% power savings on average without any depth penalty.

We study the technology mapping problem for LUT-based FPGAs targeting at power minimization. The problem has been proved to be NP-hard previously. Hence, we present an efficient heuristic to compute low-power mapping solutions. The major distinction of our work from previous ones is that while generating a LUT, we look ahead at the impact of the mapping selection of this LUT on the power consumption of the remaining network. We choose the mapping that results in the least estimated overall power consumption. The key idea is to compute low-power K-feasible cuts by an efficient incremental network flow computation method. Experimental results show that our algorithm reduces both power consumption and area over the previous algorithms reported in the literature.

In this paper, we present the first exact algorithm to solve the constrained I/O placement problem for FPGAs that support multiple I/O standards. We derive a compact integer linear programming formulation for the constrained I/O placement problem. The size of the integer linear program derived is independent of the number of I/O objects to be placed and hence is scalable to very large design instances. For example, for a Xilinx Virtex-E FPGA, the number of integer variables required is never more than 32 and is much smaller for practical design instances. Extensive experimental results using a non-commercial integer linear program solver shows that it only takes seconds to solve the resultant integer linear program in practice.

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

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

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

Logic replication is known to be an effective technique to reduce the number of cut nets in partitioned circuits. A new replication model called functional replication is particularly useful for partitioning technology-mapped circuits. Functional replication differs from traditional replication because it considers the functional dependency of the different output signals of a logic cell on its input signals. Functional replication can lead to a higher reduction in the number of cut nets than traditional replication. In this paper, we give the first theoretical treatment of the min-cut partitioning problem with functional replication. We present a novel two-phase algorithm to compute a min-cut bipartition of a technology-mapped circuit with functional replication using a minimum amount of area overhead. Additionally, we show that our algorithm can be applied to improve the solution produced by any area-constrained functional replication partitioning heuristic.

#%$& (' ) * + , . /'0* 1 2 * 34 657 8* 2 8* 9 /':; : 6 * ?6@8AB *1 1 0* %* C= 8 0 ?D':1 ? E3F * +G'H ?D'0* IJ ?6@ K'0? ?L > M 2 4 0NO ? 8 (P> Q -A : A )7R-SJ$& *F+='T'Q?U'V : > M 2 4 0N * A : AXW-S0YM$(A2!> , [Z \* :MC= 8 '0?D:6* + F M ?D'0* / ]'0 ?D':^3F+ (+] E* % Z 'K' ?D'0 :H > `_ 2 [ . 0NTC 8 ?U'0 )a* + K [ /':% > M 2 -NT * M+ 'M K' 8* * _b 8* 9C 8 ?U'0 D :c *(''-? ?6@]IJ @d Z>_ 2 IJ Ae#1 0 VIJ /)F* + 1 D 9'0?D \*9 G \@ \* K'V* D H3f' @;* ? IJ .* + ` : \* d ? g (+c K'0: * M -N4 > `_ 2 [ h 0NO [* T ^'M: IJ 9C= 8 ?D'LAi H* + F ='0 2 /) 34 E 8*T' ?D E@8 [*h [57 * IJ E D /'.* :6 ('K'0* 4 0I 8*r Q 8* AOx 0 '.y y0_b ?D 8 (Pcz/R0Y,_b [*F ? ) 3X , / / K 8* hNu { 0I W0y`+ 4* `? F* +='0 ^R-SM D > * A 1. INTRODUCTION n| * +H},qr! a* -?D -:-@H 8* :Q* + E 1 c ! #%$ [ (' )r I> E'V . /'0? / c /3F * 9 K'-? ? E ~ = % ?D'/ c'V* '0 ^ IJ h ':9 /Z * @8Af#1 '83F+ ? )73F 6* + * + /'0 0No h ~ ) fNu [* D f'V h 8* :0 ('0* / K >* T D tAih? ? * + E : [ G},qr! , +>@ /'0?4 [_ : %v6z/S>) „0wAak /34 IJ /)J3F 6* +`* & 0 X+> / a -N7* + 'i -N 8* [*f H \*('0 = 'V ( _b ? ?2 0 4Np ?D?6_b \*  : H'0Nu* [ F 6 _ * L ='V * * : ) 8* *r ?D':F L* _b : A # '8@cC= 8 '-? : 0 6* + )i ? = :% ? D D : '= G _ ? : )7+ '/IJ E 2 2 / ^ ='\*k /' Mv6z-z )Oz  )tW>)2‘>)7’>) RVw)> *a* + @` D ` 0*&*('0PJ F >* [ *& ?D'0 :E D 8* Q'>* Z *9v W/wA € ;v WVw)&ƒX+ d *M'-? A1 8* :0 ('0* C= 8 0 ?D':%'0 = “ D >*M 8* [*. ?U'0 D : Ac!> D IJ [ @d3F 6 :% I-'-? ='V_ * 9 \* K X'Q ?D [_ :[* @`: ? ='-?2 * /)1v W/w7 /'9 ?6@ 8 f > ('V* _b ~ / * ? \* , A : ATz S S-SM [* [$a *X3F ? ?7 -* 2 “ D >*Q* -?DI 9 ?D 6* +]IJ [ @c?D'V : K * ? \* 1 -A : A z/S0Y” [* [$(A,x * + 0 )ˆv WVwa 'K+ \* M:-?D ='0?o * [ * K /m8 8* D'-? ?6@^ * M:-? ='0?O >* [ * )7* + Q 2 [ Np K'0 -NO3F+ [+1 2 f 1* + , 0 ( : -NO * f* . 2 , * / tA c [Z \* :]C 8 ?D'0 :;'0? : 6* + . ?D'V* / Š'_ '-? :h3F+ [+ / r* T Z '&'F?D'0 :4 > . 2 [ r 0N C 8 ?D'0 ) * + f /':E . 2 o -N7 [* i+ 'i K' 4 >* [ * _b >* C= 8 0 ?D': *(''-? ?6@ IJ @. Z 2 IJ Ao € `* + i ='0 2 /) 34 c >*1'‰ D ? %@J * 57 * IJ c D /'G* ˆ :6 c 8* Š'Œ :-? ˆ */A•…X Nu ‰::|* + G * ) . ?6* _* '-?o * E'0 M * 9*€3X -_* ='0? [* A …X = / _ :M+8@ 2 [ :('+ _* -_b:0 ('+%* ('\Np 0 K'0* . / d* % I K* + K \* ('8*.Np 0 _ ? 6*Q D ‰'^ ?D 8 (P2A l4+ E *, / * %* (+ Um8 . ,IJ @% [57 * IJ A.! 2 M34 '0 h: IJ H' ? ‹3F 6* +1R-S ? 8 [P> f'0 = 9W-S0YŽ [* AiTNu* [ f * / * t)834 , 'K+='/IJ h'0*f \*,zVW-R-SQ * h p3F+ [+9 X* + h /'3F+ `34 F+ 'VI f * i 2 *€3X K'-? ? ='6 i -Nt ? 8 (P> [$(Aal4+ Q'H :6 * )-Np 0 F', _ ? •3F * +Œy y ? 8 [P> '0 = ŠzVRVY† * )&* + HC 8 ?U'0 D :G'0?D:-_ 6* +  D cv WVwr* 8 -PH 0 k* +='0 ^W0y.+ f* M 1 H* + , 0 D:='-? * ? \*/)& ** 8 Pc? M* + '‰R0S% > * '0Nu* [ ` [*M / * LA #1 '83F+ ? )k3X c 8*H'] %'('V* c:-?D ='0?, * [ HNu 3F 6 :^ I '0?D '0* d D * + E ='0 2 /A nG . qL'-:('0 :U'0 G ?D'0Z>_ 'V* .* (+ Dm> &* h \@ \* K'0* /'-? ?6@Q * X: ? '-? D 8* * ) * @ :,* E D ~ 4* + f K'0Z . ŽI> D -?D'0* 9'-: '\*&* + 4 * _ :k Ail4+ D q'%: IJ ‰C 8 ?U'0 LA‰l4+ H 7 'V* H 0N,qL'-:('0 :U'0 b2 b5

Logic replication is known to be an effective technique to reduce the number of cut nets in partitioned circuits. A new replication model calledfunctional replicationis particularly useful for partitioning technology mapped circuits [7]. Functional replication differs from traditional replication because it considers the functional dependency of the different output signals of a logic cell on its input signals. Functional replication can lead to a higher reduction in the number of cut nets than traditional replication. In this paper, we give the first theoretical treatment of the min-cut partitioning problem with functional replication. We present a novel two-phase algorithm to compute a min-cut bipartition of a technology mapped circuit with functional replication 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.

No abstract available.

Previously, two algorithms for the board-level routing problem in FPGA-based logic emulators that use crossbars for interconnection were proposed. However, the performance issue was not considered in the previous algorithms. And they cannot handle routing constraints that may arise from certain timing requirement. So, in this paper we propose a performance-driven routing algorithm for the board-level routing problem that can handle additional routing constraints and reduce the delay of the routing solutions.

The channel segmentation design problem for symmetrical FPGAs is the problem of designing segmented tracks in the interconnection channels that provides good net routability and delay performance at the same time. In this paper, we show how to separate the problem into the segmentation design problems of the vertical and horizontal channels by a statistical analysis of the net distribution on a symmetrical FPGA. And we propose an effective approach for segmented channel design when the allowed number of tracks in a channel is fixed and limited.

In this paper, we consider a board-level routing problem which is applicable to field-programmable gate arrays (FPGA)-based logic emulation systems such as the Realizer System and the Enterprise Emulation System manufactured by Quickturn Design Systems. For the case where all nets are two-terminal nets, we present an O(n/sup 2/)-time optimal algorithm where n is the number of nets. Our algorithm guarantees 100% routing completion if the number of interchip signal pins on each FPGA chip in the logic emulation system is less than or equal to the number of I/O pins on the chip. Our algorithm is based on iterative computation of Euler circuits in graphs. We also prove that the routing problem with multiterminal nets is NP-complete. Also we suggest one way to handle multiterminal nets using some additional resources.

Logic replication has been shown to be very effective in reducing the number of cut nets in partitioned circuits. Liu et al. (see IEEE Trans. Computer-Aided Design, vol. 14, p. 623-30, May 1995) considered the circuit partitioning problem with logic replication for separating two given nodes and presented an algorithm to determine a partitioning of the minimum possible cut size. In general, there are many possible partitioning solutions with the minimum cut size and the difference in the required amount of replication by these solutions can be significant. Since there is a size constraint on each component of the partitioning in practice, it is desirable to also minimize the amount of replication. In this paper, we present a network-flow based algorithm to determine an optimum replication min-cut partitioning that requires minimum replication. We show that the algorithm can be generalized to separate two given subsets of nodes giving an optimum partitioning of the minimum possible cut size using the least possible amount of replication. We also show that our algorithm can be used to improve the solutions produced by any existing size-constrained replication min-cut partitioning algorithm by reducing the cut size and shrinking the replication set.

We consider a board-level routing problem applicable to FPGA-based logic emulation systems such as the Realizer System [Varghese et al. 1993] and the Enterprise Emulation System [Maliniak 1992] manufactured by Quickturn Design Systems. Optimal algorithms have been proposed for the case where all nets are two-terminal nets [Chan and Schlag 1993; Mak and Wong 1995]. We show how multiterminal nets can be handled by decomposition into two-terminal nets. We show that the multiterminal net decomposition problem can be modeled as a bounded-degree hypergraph-to-graph transformation problem where hyperedges are transformed to spanning trees. A network flow-based algorithm that solves both problems is proposed. It determines if there is a feasible decomposition and gives one whenever such a decomposition exists.

Logic replication has been shown to be very effective in reducing the number of cut nets in partitioned circuits. L.T. Liu et al. (1995) considered the circuit partitioning problem with logic replication for separating two given nodes and presented an algorithm to determine a partitioning of the minimum possible cut size. In general, there are many possible partitioning solutions with the minimum cut size and the difference of their required amounts of replication can be significant. Since there is a size constraint on each component of the partitioning in practice, it is desirable to also minimize the amount of replication. In this paper, we present a network-flow based algorithm to determine an optimum replication min-cut partitioning that requires minimum replication. We show that the algorithm can be generalized to separate two given subsets of nodes and determine an optimum partitioning of the minimum possible cut size using the least possible amount of replication. We also show that our algorithm can be used to improve the solutions produced by any heuristic replication min-cut partitioning algorithm by reducing the cut size and shrinking the replication set.

In this paper, we consider a board-level routing problem which is applicable to FPGA-based logic emulation systems such as the Realizer system [5] and the Enterprise Emulation System [3] manufactured by Quickturn Systems. For the case where all nets are two-terminal nets, we present an O(n 2 )-time optimal algorithm where n is the number of nets. Our algorithm guarantees 100% routing completion if the number of inter-chip signal pins on each FPGA chip in the logic emulation system is less than or equal to the number of I/O pins on the chip. Our algorithm is based on iteratively finding Euler circuits in graphs. We also prove that the routing problem with multiterminal nets is NP-complete. 1 Introduction Introduced in the mid-1980's, FPGAs [1,2] combine the programmability of programmable logic devices and the scalable interconnection structure of traditional gate arrays. This combination results in programmable devices with much higher logic density. Compared with tradition...

We consider a board-level routing problem applicable to FPGA-based logic emulation systems such as the Realizer System (Varghese et al., (1993)) and the Enterprise Emulation System (Maliniak (1992)) manufactured by Quickturn Systems. Optimal algorithms have been proposed for the case where all nets are two-terminal nets. In this paper, we show how multi-terminal nets can be handled by decomposition into two-terminal nets. We show that the multi-terminal net decomposition problem can be modelled as a bounded-degree hypergraph-to-graph transformation problem where hyper-edges are transformed to spanning trees. A network flow-based algorithm that solves both problems is proposed. It determines if there is a feasible decomposition and gives one whenever such a decomposition exists.