We provide an improved assessment of Google Brain’s deep reinforcement learning approach to macro placement [29] and its updated Circuit Training (CT) implementation in GitHub [53]. A stronger simulated annealing (SA) baseline leverages the “go-with-the-winners” metaheuristic [3] and a multi-threading implementation. We develop and release new public benchmarks in sub-10nm technology: LEF/DEF for Google’s 7nm TSMC Ariane protobuf and scaled variants, as well as testcases implemented in the open-source ASAP7 7nm research enablement. We evaluate from-scratch training and fine-tuning results for the latest “AlphaChip” release of Circuit Training, alongside multiple alternative macro placers. We also study the recently-published pre-training guidance in [53]. A commercial place-and-route tool is used to provide “true reward” post-route power, performance and area metrics. All data, evaluation flows and related scripts are publicly available in theMacroPlacementGitHub repository [63]. Our study affords insights into reproducibility and reporting in the research literature, and points out still-missing confirmations (e.g., of CT’s scalability and pre-training methodology) that remain open questions for the research community.

With the growing demand for VLSI scaling, standard cell library generation becomes crucial process to enhance performance via design technology co-optimization (DTCO) and system technology co-optimization (STCO) exploration. In this work, we review existing methodologies and algorithms used for standard cell layout automation for sub-10nm nodes, categorized by their algorithmic approaches for transistor placement and internal cell routing.

The "CAD Contest at ICCAD" is a challenging, multi-month, research and development competition, focusing on advanced, real-world problems in the field of electronic design automation (EDA). Since 2012, the contest has been publishing many sophisticated circuit design problems, from system-level design to physical design, together with industrial benchmarks and solution evaluators. Contestants can participate in one or more problems provided by EDA/IC industry. The winners will be awarded at an ICCAD special session dedicated to this contest. Every year, the contest attracts more than a hundred teams, fosters productive industry-academia collaborations, and leads to hundreds of publications in top-tier conferences and journals. The 2025 CAD Contest has 247 teams from all over the world, which generates the highest participation record. Moreover, the problems of this year cover state-of-the-art EDA research trends such as hardware trojan detection, design optimization with multibit flip-flops, and performance-driven incremental placement optimization from well-known EDA/IC companies. We believe the contest keeps enhancing impact and boosting EDA researches.

We propose SO3-Cell, the first automatic standard cell layout generation framework that optimizes three key steps simultaneously using Mixed-Integer Linear Programming (MILP). SO3-Cell simultaneously performs circuit topology optimization, transistor placement, and internal cell routing to achieve an optimized layout solution. Our optimization objective is to minimize metal usage while enhancing cell layout flexibility within a given area.We introduce design space pruning techniques to mitigate the complexity of larger designs, such as a full adder, a reset flip-flop (FF), and a 2-bit FF. We successfully generate a layout for a 44-transistor 2-bit FF within 25,862 seconds, demonstrating the scalability and robustness of the SO3-Cell framework. We evaluate the block-level PPA impact of the proposed cell-layout improvements, demonstrating a 35.0% reduction in power, a 2.2% increase in frequency, and a 31.1% reduction in area.

Moore's law scaling is approaching physical limits, as indicated by the technology roadmap. Recent standard cell layout reductions rely on track height compression, which increases pin density and routing congestion. To address these challenges, design technology co-optimization (DTCO) was introduced. This paper explores how much track height can be compressed and how DTCO features can sustain layout scaling. To support this exploration, we developed an SMT-based cell synthesis tool that integrates gear ratio, M1 metal grid offset, local-interconnect source-drain (LISD) merging, adjustable gate cut lengths, and double-height architecture with pass-throughs, and various power delivery options.

As physical pitch scaling slows, efforts to match its pace by reducing standard cell height and sacrificing horizontal routing tracks have introduced placement and routing challenges, making the design of high-quality standard cell layouts increasingly crucial. However, existing cell metrics only focus on pin accessibility and are insufficient to address issues in advanced nodes (e.g., Power Delivery Networks (PDN), increased routing blockages, etc.). We propose Cell Layout Flexibility(Cell-Flex) metrics, novel metrics that evaluate flexibility of standard cell layouts. flexibility reflects the versatility of cell layouts to placement and routing demands, which influences optimizing block design. By using Cell-Flex metrics as objectives in designing cell layout, we achieve a 13.2% reduction in block area without increasing total Design Rule Violations (DRVs). We develop a Machine Learning (ML) model using Kolmogorov-Arnold Networks (KAN) that utilizes the Cell-Flex metrics as features to make DRV prediction. By adding Cell-Flex features, we improve accuracy from 0.65 to 0.79 and F1 score from 0.52 to 0.78, demonstrating that our metrics are important for DRV prediction and serve as robust indicators of cell layout quality.

The "CAD Contest at ICCAD" is a challenging, multi-month, research and development competition, focusing on advanced, real-world problems in the field of electronic design automation (EDA). Since 2012, the contest has been publishing many sophisticated circuit design problems, from system-level design to physical design, together with industrial benchmarks and solution evaluators. Contestants can participate in one or more problems provided by EDA/IC industry. The winners will be awarded at an ICCAD special session dedicated to this contest. Every year, the contest attracts more than a hundred teams, fosters productive industry-academia collaborations, and leads to hundreds of publications in top-tier conferences and journals. The 2024 CAD Contest has 221 teams from all over the world, which generates the highest participation record. Moreover, the problems of this year cover state-of-the-art EDA research trends such as logic optimization, multibit flip-flop, and Machine Learning (ML) for EDA from well-known EDA/IC companies. We believe the contest keeps enhancing impact and boosting EDA researches.

With the announcement of the most advanced silicon spin quantum-bit (qubit) chip by Intel, silicon-based quantum circuit manufacturing technology has shown the superior potential to realize quantum computing to other technologies because of the mature semiconductor manufacturing technologies and the compatibility with electronics. Due to the bottleneck in scalability caused by interconnections in silicon-based quantum circuits, crossbar architectures serve as one of the most promising solutions for circuitry implementation. This paper proposes the first satisfiability modulo theories (SMT) formulation to optimally solve the layout synthesis problem by simultaneously performing scheduling, mapping, and routing for silicon-based quantum systems with a specific crossbar architecture. The experiments demonstrate that the proposed method can effectively generate layout synthesis results with minimal usage of swap and shuttle gates within the shortest circuit depths, and the solutions greatly outperform those derived from a state-of-the-art work.

Laplace learning algorithms for graph-based semi-supervised learning have been shown to produce degenerate predictions at low label rates and in imbalanced class regimes, particularly near class boundaries. We propose CutSSL: a framework for graph-based semi-supervised learning based on continuous nonconvex quadratic programming, which provably obtains \emph{integer} solutions. Our framework is naturally motivated by an \emph{exact} quadratic relaxation of a cardinality-constrained minimum-cut graph partitioning problem. Furthermore, we show our formulation is related to an optimization problem whose approximate solution is the mean-shifted Laplace learning heuristic, thus providing new insight into the performance of this heuristic. We demonstrate that CutSSL significantly surpasses the current state-of-the-art on k-nearest neighbor graphs and large real-world graph benchmarks across a variety of label rates, class imbalance, and label imbalance regimes. Our implementation is available on Colab\footnote{\url{https://colab.research.google.com/drive/1tGU5rxE1N5d0KGcNzlvZ0BgRc7_vob7b?usp=sharing}}.

State-of-the-art analytical placement algorithms for VLSI designs rely on solving nonlinear programs to minimize wirelength and cell congestion. As a consequence, the quality of solutions produced using these algorithms crucially depends on the initial cell coordinates. In this work, we reduce the problem of finding wirelength-minimal initial layouts subject to density and fixed-macro constraints to a Quadratically Constrained Quadratic Program (QCQP). We additionally propose an efficient sequential quadratic programming algorithm to recover a block-globally optimal solution and a subspace method to reduce the complexity of problem. We extend our formulation to facilitate direct minimization of the Half-Perimeter Wirelength (HPWL) by showing that a corresponding solution can be derived by solving a sequence of reweighted quadratic programs. Critically, our method is parameter-free, i.e. involves no hyperparameters to tune. We demonstrate that incorporating initial layouts produced by our algorithm with a global analytical placer results in improvements of up to 4.76% in post-detailed-placement wirelength on the ISPD'05 benchmark suite. Our code is available on github. https://github.com/choltz95/laplacian-eigenmaps-revisited.

We provide open, transparent implementation and assessment of Google Brain's deep reinforcement learning approach to macro placement (Nature) and its Circuit Training (CT) implementation in GitHub. We implement in open-source key "blackbox" elements of CT, and clarify discrepancies between CT and Nature. New testcases on open enablements are developed and released. We assess CT alongside multiple alternative macro placers, with all evaluation flows and related scripts public in GitHub. Our experiments also encompass academic mixed-size placement benchmarks, as well as ablation and stability studies. We comment on the impact of Nature and CT, as well as directions for future research.

The objective of a leakage recovery step is to make use of positive slack and reduce power by performing appropriate standard-cell swaps such as threshold-voltage ( V th ) or channel-length reassignments. The resulting engineering change order netlist needs to be timing clean. Because this recovery step is performed several times in a physical design flow and involves long runtimes and high tool-license usage, previous works have proposed graph neural network–based frameworks that restrict feature aggregation to three-hop neighborhoods and do not fully consider the directed nature of netlist graphs. As a result, the intermediate node embeddings do not capture the complete structure of the timing graph. In this article, we propose DAGSizer , a framework that exploits the directed acyclic nature of timing graphs to predict cell reassignments in the discrete gate sizing task. Our DAGSizer (Sizer for DAGs) framework is based on a node ordering-aware recurrent message-passing scheme for generating the latent node embeddings. The generated node embeddings absorb the complete information from the fanin cone (predecessors) of the node. To capture the fanout information into the node embeddings, we enable a bidirectional message-passing mechanism. The concatenated latent node embeddings from the forward and reverse graphs are then translated to nodewise delta-delay predictions using a teacher sampling mechanism. With eight possible cell-assignments, the experimental results demonstrate that our model can accurately estimate design-level leakage recovery with an absolute relative error ε model under 5.4%. As compared to our previous work, GRA-LPO, we also demonstrate a significant improvement in the model mean squared error.

Packaging has become a crucial process due to the paradigm shift of More than Moore. Addressing manufacturing and yield issues is a significant challenge for modern layout algorithms. We propose to use printed circuit board (PCB) placement as a benchmark for the packaging problem. A maximum-margin formulation is devised to improve the separation between nets. Our framework includes seed layout proposals, a coordinate descent-based procedure to optimize routability, and a mixed-integer linear programming method to legalize the layout. We perform an extensive study with 14 PCB designs and an open-source router. We show that the placements produced by NS-place improve routed wirelength by up to 25%, reduce the number of vias by up to 50%, and reduce the number of DRVs by 79% compared to manual and wirelength-minimal placements.

Canonical methods for analytical placement of VLSI designs rely on solving nonlinear programs to minimize wirelength and cell overlap. We focus on producing initial layouts such that a global analytical placer performs better compared to existing heuristics for initialization. We reduce the problem of initialization to a quadratically constrained quadratic program. Our formulation is aware of fixed macros. We propose an efficient algorithm which can quickly generate initializations for testcases with millions of cells. We show that the our method for parameter initialization results in superior performance with respect to post-detailed placement wirelength.

SMART NoCs achieve ultra-low latency by enabling single-cycle multiple-hop transmission via bypass channels. However, contention along bypass channels can seriously degrade the performance of SMART NoCs by breaking the bypass paths. Therefore, contention-free task mapping and scheduling are essential for optimal system performance. In this article, we propose an SMT (Satisfiability Modulo Theories)-based framework to find optimal contention-free task mappings with minimum application schedule lengths on 2D/3D SMART NoCs with mixed dimension-order routing. On top of SMT’s fast reasoning capability for conditional constraints, we develop efficient search-space reduction techniques to achieve practical scalability. Experiments demonstrate that our SMT framework achieves 10× higher scalability than ILP (Integer Linear Programming) with 931.1× (ranges from 2.2× to 1532.1×) and 1237.1× (ranges from 4× to 4373.8×) faster average runtimes for finding optimum solutions on 2D and 3D SMART NoCs and our 2D and 3D extensions of the SMT framework with mixed dimension-order routing also maintain the improved scalability with the extended and diversified routing paths, resulting in reduced application schedule lengths throughout various application benchmarks.

In advanced nodes, scaling of critical dimension and pitch has not progressed at historical Moore’s Law rates. Thus,scaling boostersare explored to improve achievable power, performance, area, and cost (PPAC) in new technologies. However, scaling boosters increase complexity of standard-cell architectures, power delivery, design rules, and other aspects of the design enablement, and may not result in design-level benefits. Therefore, design-technology co-optimization (DTCO) methodologies are required to evaluate design-level benefits of scaling boosters. The key challenge for DTCO is that large engineering efforts and long timelines are needed to develop design enablements (e.g., cell libraries) and perform implementation studies in order to assess technology options. We describe a new framework that can systematically evaluate a measure of intrinsic routability,$K_{\mathrm{ th}}$, across both technology and design choices. We focus on routability since it is a critical factor in the scaling of area and cost. Our framework includes realistic standard-cell libraries that are automatically generated using satisfiability modulo theory (SMT) methods, and a new pin shape selection method. Routability assessments are based on the PROBE approach and an improved construction of underlying netlist topologies. Our experimental studies demonstrate the assessment of routability impacts for advanced-node technology and design options. We demonstrate learning-based$K_{\mathrm{ th}}$prediction to reduce runtime, disk space and commercial tool licenses needed to implement our framework. Our work enables faster and more comprehensive evaluation of technology options early in the technology development process.

As technology nodes continue to advance relentlessly, geometric pitch scaling starts to slow down. In order to retain the trend of Moore’s law, design technology co-optimization (DTCO) and system technology co-optimization (STCO) are introduced together to continue scaling beyond 5 nm using pitch scaling, patterning, and novel 3-D cell structures [i.e., complementary-FET (CFET)]. However, numerous DTCO and STCO iterations are needed to continue block-level area scaling with considerations of physical layout factors: 1) various standard cell (SDC) library sets (i.e., different cell heights and conventional FET); 2) design rules (DRs); 3) back end of line (BEOL) settings; and 4) power delivery network (PDN) configurations. The growing turnaround time (TAT) among SDC design, DR optimization, and block-level area evaluation becomes one of the major bottlenecks in DTCO and STCO explorations. In this work, we develop a machine learning model that combines bootstrap aggregation and gradient boosting techniques to predict the sensitivity of minimum valid block-level area of various physical layout factors. We first demonstrate that the proposed model achieves 16.3% less mean absolute error (MAE) than the previous work for testing sets. Then, we show that the proposed model successfully captures the block-level area sensitivity of new SDC library sets, new BEOL settings, and new PDN settings with 0.013, 0.004, and 0.027 MAE, respectively. Finally, compared to the previous work, the proposed approach improves the robustness of predicting new circuit designs by up to 6.76%. The proposed framework provides more than$100\times $speedup compared to conventional DTCO and STCO exploration flows.

The printed circuit board (PCB) routing problem has been studied extensively in recent years. Due to continually growing net/pin counts, extremely high pin density, and unique physical constraints, the manual routing of PCBs has become a time-consuming task to reach design closure. Previous works break down the problem into escape routing and area routing and focus on these problems separately. However, there is always a gap between these two problems requiring a massive amount of human efforts to fine-tune the algorithms back and forth. Besides, previous works of area routing mainly focus on routing between escaping routed ball-grid-array (BGA) packages. Nevertheless, in practice, many components are not in the form of BGA packages, such as passive devices, decoupling capacitors, and through-hole pin arrays. To mitigate the deficiencies of previous works, we propose a full-board routing algorithm that can handle multiple real-world complicated constraints to facilitate the printed circuit board routing and produce high-quality manufacturable layouts. Experimental results show that our algorithm is effective and efficient. Specifically, for all given test cases, our router can achieve 100% routability without any design rule violation while the other two state-of-the-art routers fail to complete the routing for some test cases and incur design rule violations.

Static power consumption is a critical challenge for IC designs, particularly for mobile and IoT applications. A final post-layout step in modern design flows involves a leakage recovery step that is embedded in signoff static timing analysis tools. The goal of such recovery is to make use of the positive slack (if any) and recover the leakage power by performing cell swaps with footprint compatible variants. Though such swaps result in unaltered routing, the hard constraint is not to introduce any new timing violations. This process can require up to tens of hours of runtime, just before the tapeout, when schedule and resource constraints are tightest. The physical design teams can benefit greatly from a fast predictor of the leakage recovery step: if the eventual recovery will be too small, the entire step can be skipped, and the resources can be allocated elsewhere. If we represent the circuit netlist as a graph with cells as vertices and nets connecting these cells as edges, the leakage recovery step is an optimization step, on this graph. If we can learn these optimizations over several graphs with various logic-cone structures, we can generalize the learning to unseen graphs. Using graph convolution neural networks, we develop a learning-based model, that predicts per-cell recoverable slack, and translate these slack values to equivalent power savings. For designs up to 1.6M instances, our inference step takes less than 12 seconds on a Tesla P100 GPU, and an additional feature extraction, post-processing steps consuming 420 seconds. The model is accurate with relative error under 6.2%, for the design-specific context.

With the relentless scaling of technology nodes, physical design engineers encounter non-trivial challenges caused by rapidly increasing design complexity, particularly in the routing stage. Back-end designers must manually stitch/modify all of the design rule violations (DRVs) that remain after automatic place-and-route (P&R), during the implementation of engineering change orders (ECOs). In this paper, we propose CoRe-ECO, a concurrent refinement framework for efficient automation of the ECO process. Our framework efficiently resolves pin accessibility-induced DRVs by simultaneously performing detailed placement, detailed routing, and cell replacement. In addition to perturbation-minimized solutions, our proposed SMT-based optimization framework also suggests the adoption of alternative master cells to better achieve DRV-clean layouts. We demonstrate that our framework successfully resolves from 33.3% to 100.0% (58.6% on average) of remaining DRVs on M1-M3 layers, across a range of benchmark circuits with various cell architectures, while also providing average total wirelength reduction of 0.003%.

In this article, we propose an automated standard cell synthesis framework, SP&R, which simultaneously solves P&R without deploying any sequential/separate operations, by a novel dynamic pin allocation scheme. The proposed SP&R utilizes the multiobjective optimization feature of satisfiability modulo theories (SMT) to obtain optimal cell layouts. To achieve practical scalability of the framework, we develop various search-space reduction techniques, including breaking symmetry, conditional assignment/localization, and cell/objective function partitioning. Compared to the previous work, SP&R achieves 20.8× to 131.7× runtime improvements on average across the design-rule sets. As a result, SP&R successfully produces cell layouts up to 36 field-effect transistors (FETs) and 27 nets within 1.75 h by orchestrating all innovative tactics together, resulting in the generation of a whole 7-nm standard cell library. Compared to the known layouts, our work improves cell size and # M2 tracks by 0.1 contacted poly pitch and 0.3 tracks, respectively.

In modern integrated circuit design, bus routing is a challenge because of complex design rules and wiring constraints. Despite extensive research, state-of-the-art in bus routing is not effective when nonuniform tracks, various obstacles, wire width constraints, and multiple spacing rules should be handled simultaneously. A new bus routing framework proposed in this article is based on maze routing and Boolean satisfiability. It produces high-quality results quickly and allows for additional optimizations, such as minimizing wire length on the critical paths. A number of challenging bus routing benchmarks appeared in 2018 ICCAD Contest. Experiments on these benchmarks not only show that the framework is faster than the winners of the competition and previous work but also produces better results, improving the overall cost by 12% while at the same time minimizing the number of spacing violations.

With the relentless scaling of technology nodes, design technology co-optimization (DTCO) for the conventional (Conv.) cell structure is starting to reach its limitations due to limited routing resources, lateral p-n separations, and performance requirements. As a result, system technology co-optimization (STCO) has been proposed to exploit the benefits of 3-D architectures. Complementary-FET (CFET) technology, which stacks p-FET on n-FET or vice versa, can release the restriction of p-n separation and reduce in-cell routing congestion by enabling p-n direct connections. However, CFET standard cell (SDC) synthesis demands holistic considerations to maximize the area benefit of scaling at the block level due to the extremely limited routability that comes from the stacked structure and reduced cell height. In this article, we propose a satisfiability modulo theory (SMT)-based CFET SDC synthesis framework that simultaneously solves place-and-route to generate optimized layouts. We first demonstrate that the CFET structure achieves 10.94% and 21.27% reduction on average cell area and metal length, respectively, and 15.10% smaller block-level area compared to Conv. structure as scaling down to 3.5T architecture. For routability, the proposed constraint-based minimum pin length/minimum pin opening and objective-based edge-based pin-separation/M2 track use reduce up to 48% #DRVs at the block level compared to the previous work. Then, through extensive DTCO explorations on ground design rules and #BEOLs, 3.5T CFET SDCs achieve up to 6.50% smaller block-level areas than 4.5T CFET SDCs. Finally, with the assistance of STCO and DTCO, 3.5T CFET SDCs achieve 21.0% on average reduced block-level areas compared to 4.5T Conv. SDCs.

Standard cell synthesis requires careful engineering approaches to ensure routability across various digital IC designs since physical design (PD) for sub-7nm technology nodes demands holistic efforts to address urgent and nontrivial design challenges. The smaller number of routing tracks and more complex design rules due to the sophisticated multi-patterning technology make place-and-route (P&R) for designing a standard cell extremely hard and time-consuming. Many conventional approaches have been suggested for improving transistor-level P&R and pin accessibility, nonetheless insufficient because of the heuristic/divide-and-conquer manners. In this paper, we propose a novel framework, SP&R, which simultaneously solves P&R for designing standard cell's layout without deploying any sequential procedures (between place and route steps) by using dynamic pin allocation-based cell synthesis. The proposed SP&R utilizes the Optimization Modulo Theories (OMT), an extension of the Satisfiability modulo theories (SMT), to obtain optimal standard cell layout by virtue of SAT (Boolean Satisfiability)-based fast reasoning ability. We validate that our SP&R framework achieves 10.5% of reduction on average in terms of metal length compared to the sequential approach, through practical standard cell designs targeting sub-7nm technology nodes.

As the technology node is evolving, standard cell (SDC) design scaling is obstructed by design constraints such as limited routing resources, lateral P-N separation, and performance requirements. Complimentary-FET (CFET) technology, which stacks the P-FET on N-FET or vice versa, is able to release the restriction of P-N connection for SDC layout scaling. However, (both in-cell and block-level) routable CFET SDC design, while maintaining the scaling advantages, is a non-trivial problem because of the extremely limited routability (including pin-accessibility) comes from the intrinsic stacked FET structure.

With the scaling of VLSI technologies, the design-technology co-optimization (DTCO) requires prompt development of standard cell libraries to explore scaling effects of various cell architectures. However, standard cell layout design demands holistic efforts for processing transistor placement and in-cell routing due to the limited routing tracks and complicated design rules. Thus, an automatic design framework of standard cell layout became essential in the advanced scaling. Conventional heuristic/divide-and-conquer approaches lack the optimality of solutions because of the limited solution space. In this paper, we propose a novel standard cell scaling framework that simultaneously finds an optimal solution in placement and routing with the pin-accessibility. To ensure the minimum number of pin-access points, we devise strict Boolean counter-based design constraints. We validate our framework using scaling parameters and cell architectures across sub-7nm technology nodes.

Abstract We focus on the all‐pairs minimum cut (APMC) problem, a graph partitioning problem whose solution requires finding the minimum cut for every pair of nodes in a given graph. While it is solved for undirected graphs, a solution for APMC in directed graphs still requires an O(n2) brute force approach. We show that the empirical number of distinct minimum cuts in randomly generated strongly connected directed graphs is proportional to n rather than the theoretical value of n2, suggesting the possibility of an algorithm which finds all minimum cuts in less than O(n2) time. We also provide an example of the strict upper bound on the number of cuts in graphs with three nodes. We model the distributions with the Generalized extreme value (GEV) distribution and enable the possibility of using a GEV distribution to predict the probability of achieving a certain number of minimum cuts, given the number of nodes and edges. Finally, we contribute to the notion of symmetric cuts by showing that there can be O(n2) symmetric cuts in graphs when node replication is allowed.

Pin accessibility encounters nontrivial challenges due to the smaller number of routing tracks, higher pin density, and more complex design rules. Consequently, securing design rule-correct routability has become a critical bottleneck for sub-10-nm IC designs (particularly in the detailed routing stage) costing days of runtime. To reduce turnaround time, IC designers demand new design methodologies to analyze the routing feasibility of a given layout architecture (e.g., conditional design rules, pin assignment patterns, etc). There are several conventional methods capable of assessing routability that consider pin accessibility. However, precise diagnosis of unroutable layouts remains an open problem for IC design practitioners. In this article, we propose two novel frameworks that: 1) efficiently analyzes design rule-correct routability via an integer linear programming (ILP)-derived Boolean satisfiability (SAT) formulation written in light-weight conjunctive normal form, on top of multicommodity flow theory and 2) precisely diagnose explicit reasons for design-rule violations (DRVs) in the form of human-interpretable explanations, while specifying conflicting design rules with a physical location. While covering a variety of conditional design rules, we have refined our formulation by using SAT encoding techniques, supernode simplification, Boolean constraint propagation-based preprocessing, etc. We demonstrate that our routability analysis framework produces design rule-correct routability assessment within 0.02% of ILP runtime on average. Also, our routability diagnosis framework precisely examines DRVs, revealing design-rule conflicts for a variety of pin layouts and switchboxes. We show our frameworks scalability by utilizing practical benchmarks ranging up to 40000 grid-size layouts (i.e., 200 Htrack × 200 Vtrack), producing results within an hour.

We propose a stability preserved Arnoldi algorithm for matrix exponential in the time domain simulation of large-scale power delivery networks (PDNs), which are formulated as semi-explicit differential-algebraic equations (DAEs). The matrix exponential and vector products (MEVPs) compose the solution of DAEs in multistep integration methods and can be efficiently approximated with the rational Krylov subspace. To produce stable simulation results for the ill-conditioned system from semi-explicit DAEs, the revised Arnoldi algorithm introduces a new structured orthogonalization process to construct the Krylov subspace. We demonstrate the performance of the new algorithm with theoretical proof and experiments. In the computation of MEVPs, we utilize the exponential related φ functions to improve the numerical accuracy. We further explore the optimal ratio to confine the spectrum in the rational Krylov subspace. Finally, the transient framework is tested on a group of system-level PDNs, showing that matrix exponential-based algorithms could achieve high efficiency and accuracy.

Routability diagnosis has increasingly become the bottleneck in detailed routing for sub-10nm technology due to the limited tracks, high density, and complex design rules. The conventional ways to examine the routability of detailed routing are ILP- and SAT-based techniques. However, once we identify the routability, the diagnosis remains an open problem for physical designers. In this paper, we propose a novel framework, called ROAD, which diagnoses explicit reasons for routing failures. The proposed ROAD framework utilizes a diagnosis-friendly SAT formulation to represent design's layout and diagnoses the routability with SAT solving techniques. Based on the diagnosis, ROAD provides human-interpretable explanations for conflicted routing conditions. To show the practical value of our framework, we also generate comprehensive test-sets that enable exhaustive exploration of layouts based on Rent's rule. We demonstrate that ROAD successfully examines conflict causes for diverse pin layouts. Throughout extensive diagnosis, we also present several key findings for design failure. ROAD performs routability diagnosis within 2 minutes on average for 90 grids testsets, while diagnosing the exact causes of routing failures in terms of congestion and conditional design rules.

The Nesterov's method approach to analytic placement has recently demonstrated strong solution quality and scalability. We dissect the previous implementation strategy and show that solution quality can be significantly improved using two levers: 1) constraint-oriented local smoothing and 2) dynamic step size adaptation. We propose a new density function that comprehends local overflow of area resources; this enables a constraint-oriented local smoothing at per-bin granularity. Our improved dynamic step size adaptation automatically determines step size and effectively allocates optimization effort to significantly improve solution quality without undue runtime impact. Our resulting global placement tool, RePlAce, achieves an average of 2.00% half-perimeter wirelength (HPWL) reduction over all best known ISPD-2005 and ISPD-2006 benchmark results, and an average of 2.73% over all best known modern mixed-size (MMS) benchmark results, without any benchmark-specific code or tuning. We further extend our global placer to address routability, and achieve on average 8.50%-9.59% scaled HPWL reduction over previous leading academic placers for the DAC-2012 and ICCAD-2012 benchmark suites. To our knowledge, RePlAce is the first work to achieve superior solution quality across all the ISPD-2005, ISPD-2006, MMS, DAC-2012, and ICCAD-2012 benchmark suites with a single global placement engine.

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

Transient simulation becomes a bottleneck for modern IC designs due to large numbers of transistors, interconnects and tight design margins. For modified nodal analysis (MNA) formulation, we could have differential algebraic equations (DAEs) which consist ordinary differential equations (ODEs) and algebraic equations. Study of solving DAEs with conventional multi-step integration methods has been a research topic in the last few decades. We adopt matrix exponential based integration method for circuit transient analysis, its stability and accuracy with DAEs remain an open problem. We identify that potential stability issues in the calculation of matrix exponential and vector product (MEVP) with rational Krylov method are originated from the singular system matrix in DAEs. We then devise a robust algorithm to implicitly regularize the system matrix while maintaining its sparsity. With the new approach, $\varphi$ functions are applied for MEVP to improve the accuracy of results. Moreover our framework no longer suffers from the limitation on step sizes thus a large leap step is adopted to skip many simulation steps in between. Features of the algorithm are validated on large-scale power delivery networks which achieve high efficiency and accuracy.

Tree structures and algorithms provide a fundamental and powerful data abstraction and methods for computer science and operations research. In particular, they enable significant advancement of IC physical design techniques and design optimization. For the last half century, Prof. T. C. Hu has areas in computer science, including network flows, integer programming, shortest paths, binary trees, global routing, etc. In this article, we select and summarize three important and interesting tree-related topics (ancestor trees, column generation, and alphabetical trees) in the highlights of Prof. T. C. Hu's contributions to physical design.

No abstract available.

We explore Krylov subspace algorithms to calculate φ functions of exponential integrators for circuit simulation. Higham [1] pointed out the potential numerical stability risk of φ functions computation. However, for the applications to circuit analysis, the choice of methods remains open. This work inspects the accuracy of matrix exponential and vector product with Krylov subspace methods, and identifies the proper approach to achieving numerically stable solutions for nonlinear circuits. Empirial results verify the quality of the proposed methods using various orders of φ functions. Furthermore, instead of Newton-Raphson (NR) iterations in conventional methods, an iterative residue correction algorithm is devised for nonlinear system analysis. The stability and efficiency of our methods are illustrated with experiments.

Innovations and advancements on physical design (PD) in the past half century significantly contribute to the progresses of modern VLSI designs. While ``Moore's Law'' and ``Dennard Scaling'' have become slowing down recently, physical design society encountered a set of challenges and opportunities. This article is presented at the event of the Life Time Achievement Award for Dr. Satoshi Goto by ISPD 2017. Dr. Goto's career in VLSI designs sets an exemplar role model for young engineers. Thus, we use his contributions as a thread to describe our personal view of physical layout from early back-board ordering to recent multi-dimensional placement and the future.

We propose a flat, analytic, mixed-size placement algorithm ePlace-3D for three-dimension integrated circuits (3D-ICs) using nonlinear optimization. Our contributions are (1) electrostatics based 3D density function with globally uniform smoothness (2) 3D numerical solution with improved spectral formulation (3) 3D nonlinear pre-conditioner for convergence acceleration (4) interleaved 2D-3D placement for efficiency enhancement. Our placer outperforms the leading work mPL6-3D and NTUplace3-3D with 6.44% and 37.15% shorter wirelength, 9.11% and 10.27% fewer 3D vertical interconnects (VI) on average of IBM-PLACE circuits. Validation on the large-scale modern mixed-size (MMS) 3D circuits shows high performance and scalability.

This paper presents a new transient electro-thermal simulation method for fast 3-D chip-level analysis of power electronics with field solver accuracy. The metallization stack and substrate are meshed and solved with 3-D field solver using nonlinear temperature-dependent electrical and thermal parameters, and the active transistors are modeled with table models to avoid time-consuming technology computer-aided design simulation. Two contributions are made to enhance the physical relevance and the computational performance: 1) the capacitive effects, including interconnect parasitic capacitance and gate capacitance of power devices with nonlinear dependence on bias and temperature, are explicitly accounted for and 2) a specialized nonlinear exponential integrator (EI) method is developed to address the considerably different time scales between electrical and thermal sectors. The EI-based transient solver allows the electrical system to step with much larger time steps than in conventional methods, thus the time step gap between the electrical and the thermal simulation is largely reduced.

We design an algorithmic framework using matrix exponentials for time-domain simulation of power delivery network (PDN). Our framework can reuse factorized matrices to simulate the large-scale linear PDN system with variable stepsizes. In contrast, current conventional PDN simulation solvers have to use fixed step-size approach in order to reuse factorized matrices generated by the expensive matrix decomposition. Based on the proposed exponential integration framework, we design a PDN solver R-MATEX with the flexible time-stepping capability. The key operation of matrix exponential and vector product is computed by the rational Krylov subspace method. To further improve the runtime, we also propose a distributed computing framework DR-MATEX. DR-MATEX reduces Krylov subspace generations caused by frequent breakpoints from a large number of current sources during simulation. By virtue of the superposition property of linear system and scaling invariance property of Krylov subspace, DR-MATEX can divide the whole simulation task into subtasks based on the alignments of breakpoints among those sources. The subtasks are processed in parallel at different computing nodes without any communication during the computation of transient simulation. The final result is obtained by summing up the partial results among all the computing nodes after they finish the assigned subtasks. Therefore, our computation model belongs to the category known as embarrassingly parallel model. Experimental results show R-MATEX and DR-MATEX can achieve up to around 14.4× and 98.0× runtime speedups over traditional trapezoidal integration-based solver with fixed time-step approach.

We propose an efficient algorithmic framework for time-domain circuit simulation using exponential integrators. This work addresses several critical issues exposed by previous matrix exponential based circuit simulation research, and makes it capable of simulating stiff nonlinear circuit system at a large scale. In this framework, the system's nonlinearity is treated with exponential Rosenbrock-Euler formulation. The matrix exponential and vector product is computed using invert Krylov subspace method. Our proposed method has several distinguished advantages over conventional formulations (e.g., the well-known backward Euler with Newton-Raphson method). The matrix factorization is performed only for the conductance/resistance matrix G, without being performed for the combinations of the capacitance/inductance matrix C and matrix G, which are used in traditional implicit formulations. Furthermore, due to the explicit nature of our formulation, we do not need to repeat LU decompositions when adjusting the length of time steps for error controls. Our algorithm is better suited to solving tightly coupled post-layout circuits in the pursuit for full-chip simulation. Our experimental results validate the advantages of our framework.

We propose an electrostatics-based placement algorithm for large-scale mixed-size circuits (ePlace-MS). ePlace-MS is generalized, flat, analytic and nonlinear. The density modeling method eDensity is extended to handle the mixed-size placement. We conduct detailed analysis on the correctness of the gradient formulation and the numerical solution, as well as the rationale of dc removal and the advantages over prior density functions. Nesterov's method is used as the nonlinear solver, which shows high yet stable performance over mixed-size circuits. The steplength is set as the inverse of Lipschitz constant of the gradient function, while we develop a backtracking method to prevent overestimation. An approximated nonlinear preconditioner is developed to minimize the topological and physical differences between large macros and standard cells. Besides, we devise a simulated annealer to legalize the layout of macros and use a second-phase global placement to reoptimize the standard cell layout. All the above innovations are integrated into our mixed-size placement prototype ePlace-MS, which outperforms all the related works in literature with better quality and efficiency. Compared to the leading-edge mixed-size placer NTUplace3, ePlace-MS produces up to 22.98% and on average 8.22% shorter wirelength over all the 16 modern mixed-size benchmark circuits with the same runtime.

We develop a flat, analytic, and nonlinear placement algorithm, ePlace , which is more effective, generalized, simpler, and faster than previous works. Based on the analogy between placement instance and electrostatic system, we develop a novel placement density function eDensity , which models every object as positive charge and the density cost as the potential energy of the electrostatic system. The electric potential and field distribution are coupled with density using a well-defined Poisson's equation, which is numerically solved by spectral methods based on fast Fourier transform (FFT). Instead of using the conjugate gradient (CG) nonlinear solver in previous placers, we propose to use Nesterov's method which achieves faster convergence. The efficiency bottleneck on line search is resolved by predicting the steplength using a closed-form equation of Lipschitz constant. The placement performance is validated through experiments on the ISPD 2005 and ISPD 2006 benchmark suites, where ePlace outperforms all state-of-the-art placers (Capo10.5, FastPlace3.0, RQL, MAPLE, ComPLx, BonnPlace, POLAR, APlace3, NTUPlace3, mPL6) with much shorter wirelength and shorter or comparable runtime. On average, of all the ISPD 2005 benchmarks, ePlace outperforms the leading placer BonnPlace with 2.83% shorter wirelength and runs 3.05× faster; and on average, of all the ISPD 2006 benchmarks, ePlace outperforms the leading placer MAPLE with 4.59% shorter wirelength and runs 2.84× faster.

ePlace is a generalized analytic algorithm to handle large-scale standard-cell and mixed-size placement. We use a novel density function based on electrostatics to remove overlap and Nesterov's method to minimize the nonlinear cost. Steplength is estimated as the inverse of Lipschitz constant, which is determined by our dynamic prediction and backtracking method. An approximated preconditioner is proposed to resolve the difference between large macros and standard cells, while an annealing engine is devised to handle macro legalization followed by placement of standard cells. The above innovations are integrated into our placement prototype ePlace, which outperforms the leading-edge placers on respective standard-cell and mixed-size benchmark suites. Specifically, ePlace produces 2.83%, 4.59% and 7.13% shorter wirelength while runs 3.05×, 2.84× and 1.05× faster than BonnPlace, MAPLE and NTUplace3-unified in average of ISPD 2005, ISPD 2006 and MMS circuits, respectively.

We proposed MATEX, a distributed framework for transient simulation of power distribution networks (PDNs). MATEX utilizes matrix exponential kernel with Krylov subspace approximations to solve differential equations of linear circuit. First, the whole simulation task is divided into subtasks based on decompositions of current sources, in order to reduce the computational overheads. Then these subtasks are distributed to different computing nodes and processed in parallel. Within each node, after the matrix factorization at the beginning of simulation, the adaptive time stepping solver is performed without extra matrix re-factorizations. MATEX overcomes the stiffness hinder of previous matrix exponential-based circuit simulator by rational Krylov subspace method, which leads to larger step sizes with smaller dimensions of Krylov subspace bases and highly accelerates the whole computation. MATEX outperforms both traditional fixed and adaptive time stepping methods, e.g., achieving around 13X over the trapezoidal framework with fixed time step for the IBM power grid benchmarks.

In this paper, we propose a novel method for power distribution network verification at early design stages. This approach predicts the worst case noise of on-chip power grids with multiple current sources subjected to a set of hierarchical constraints. The current constraints not only define bounds for current magnitudes, but also consider nonzero current transition times that makes the prediction of worst case noise more realistic. Under the novel current constraints, a dynamic programming algorithm is introduced to generate the worst case current sources based on the impulse responses of the power grid. The algorithm is accelerated by a modified Knuth-Yao quadrangle inequality speedup method, which reduces the time complexity from O(s2m) to O(smlogs), where s is the number of discretized current values and m is the total number of zero-crossing points of the current sources. Experimental results show that our approach not only efficiently predicts realistic worst case noise of on-chip power grids, but also correlates the frequency-domain resonance effects with the time-domain noise behavior.

A novel equalized global link architecture and driver-receiver codesign flow are proposed for high-speed and low-energy on-chip communication by utilizing a continuous-time linear equalizer (CTLE). The proposed global link is analyzed using a linear system method, and the formula of CTLE eye opening is derived to provide high-level design guidelines and insights. Compared with the separate driver-receiver design flow, over 50% energy reduction is observed. The final optimal solution achieves 20-Gb/s signaling over 10 mm, 2.6- μm pitch on-chip transmission line with 15.5-ps/mm latency and 0.196-pJ/b energy using 45-nm technology. Monte Carlo simulation also shows that 3 σ/μ for power and delay variation in the proposed global link are 13.1% and 4.6%, respectively.

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

This paper addresses the modeling and analysis problems for power distribution networks (PDNs) in 3-D ICs. An on-chip distributed model is proposed for 3-D power grids, in which the details of metal layers are considered. The distributed model is demonstrated to be essential to identifying the unique noise behavior of 3-D PDNs. A lumped model is proposed based on the distributed model. The lumped model features the connection impedance between tiers and is proven to be useful for designers to understand the global effects of 3-D PDNs. Based on the models, an analysis flow is designed for 3-D PDNs in both frequency domain and time domain. With the analysis flow, the electrical characteristics of 3-D PDNs are studied systematically for the first time. The frequency-domain analysis identifies the global and local resonance phenomena in 3-D PDNs that are distinct from those in 2-D PDNs. The physical mechanisms behind the resonance phenomena are investigated. The time-domain analysis predicts the worst-case supply noise based on distributed current constraints. The “Rogue Wave” concept is introduced to explain the spatial and temporal relations of the worst-case on-chip noise responses in 3-D PDNs.

In this paper, we propose a series of methods, including character design, stencil compaction and layout matching for Character Projection (CP) Electron-Beam Lithography. We solve the problems with emphasis on inter-cell routing including wires and vias. For wire layout, we design a small set of regular characters after layout normalization. Then we partition the layout into several rows and adopt a greedy algorithm for layout matching in each row. For via layout, we utilize a minimum path covering algorithm to group vias into paths, which are contained in characters with bounded length. We devise an efficient method to compact all characters into a stencil with much less area than the total area of characters. Experimental results show that our algorithms achieve up to 83.42% and 67.29% of the maximum improved-throughput by CP against to Variable Shaped Beam (VSB) technology for wire and via layouts, respectively. Our characters can apply for general purpose layouts to save the high cost of generating different stencils for different layouts.

We present a fast time-domain multiphysics simulation framework that combines full-wave electromagnetism (EM) and carrier transport in semiconductor devices (TCAD). The proposed framework features a division of linear and nonlinear components in the EM-TCAD coupled system. The former is extracted and handled independently with high efficiency by a matrix exponential approach assisted with Krylov subspace method. The latter is treated by ordinary Newton's method yet with a much sparser Jacobian matrix that leads to substantial speedup in solving the linear system of equations. More convenient error management and adaptive control are also available through the linear and nonlinear decoupling.

We propose an advanced matrix exponential method (MEXP) to handle the transient simulation of stiff circuits and enable parallel simulation. We analyze the rapid decaying of fast transition elements in Krylov subspace approximation of matrix exponential and leverage such scaling effect to leap larger steps in the later stage of time marching. Moreover, matrix-vector multiplication and restarting scheme in our method provide better scalability and parallelizability than implicit methods. The performance of ordinary MEXP can be improved up to 4.8 times for stiff cases, and the parallel implementation leads to another 11 times speedup. Our approach is demonstrated to be a viable tool for ultra-large circuit simulations (with 1.6M ~ 12M nodes) that are not feasible with existing implicit methods.

In this paper, we propose a new approach for gated bus synthesis [16] with minimum wire capacitance per transaction in three-dimensional (3D) ICs. The 3D IC technology connects different device layers with through-silicon vias (TSV), which need to be considered differently from metal wire due to reliability issues and a larger footprint. Practically, the number of TSVs is bounded between layers; thus, we first devise dynamic programming and local search techniques to determine the optimal TSV locations. We then employ two approximation algorithms to generate a rectilinear shortest-path Steiner graph in each device layer. One algorithm extends the well-known greedy heuristic for the Rectilinear Steiner Arborescence problem and handles large cases with high efficiency. The other algorithm utilizes a linear programming relaxation and rounding technique which costs more time and generates a nearly-optimal Steiner graph. Experimental results show that our algorithms can construct shortest-path Steiner graphs with 22% less total wire length than the previous method of Wang et al. [16].

Fast full-chip time-domain simulation calls for advanced numerical integration techniques with capability to handle the systems with (tens of) millions of variables resulting from the modified nodal analysis (MNA). General MNA formulation, however, leads to a differential algebraic equation (DAE) system with singular coefficient matrix, for which most of explicit methods, which usually offer better scalability than implicit methods, are not readily available. In this paper, we develop a practical two-stage strategy to remove the singularity in MNA equations of large-scale circuit networks. A topological index reduction is first applied to reduce the DAE index of the MNA equation to one. The index-1 system is then fed into a systematic process to eliminate excess variables in one run, which leads to a nonsingular system. The whole regularization process is devised with emphasis on exact equivalence, low complexity, and sparsity preservation, and is thus well suited to handle extremely large circuits.

Power grid verification has become an indispensable step to guarantee a functional and robust chip design. Vectorless power grid verification methods, by solving linear programming (LP) problems under current constraints, enable worst-case voltage drop predictions at an early stage of design when the specific waveforms of current drains are unknown. In this paper, a novel power grid verification algorithm based on hierarchical constraints is proposed. By introducing novel power constraints, the proposed algorithm generates more realistic current patterns and provides less pessimistic voltage drop predictions. The model order reduction-based coefficient computation algorithm reduces the complexity of formulating the LP problems from being proportional to steps to being independent of steps. Utilizing the special hierarchical constraint structure, the submodular polyhedron greedy algorithm dramatically reduces the complexity of solving the LP problems from overO(km3) to roughlyO(kmlogkm), wherekmis the number of variables. Numerical results have shown that the proposed algorithm provides less pessimistic voltage drop prediction while at the same time achieves dramatic speedup.

The authors for the above titled paper were incorrectly listed. The correct list of authors is presented here.

We propose an explicit numerical integration method based on matrix exponential operator for transient analysis of large-scale circuits. Solving the differential equation analytically, the limiting factor of maximum time step changes largely from the stability and Taylor truncation error to the error in computing the matrix exponential operator. We utilize Krylov subspace projection to reduce the computation complexity of matrix exponential operator. We also devise a prediction-correction scheme tailored for the matrix exponential approach to dynamically adjust the step size and the order of Krylov subspace approximation. Numerical experiments show the advantages of the proposed method compared with the implicit trapezoidal method.

We propose a block-diagonal structured model order reduction (BDSM) scheme for fast power grid analysis. Compared with existing power grid model order reduction (MOR) methods, BDSM has several advantages. First, unlike many power grid reductions that are based on terminal reduction and thus error-prone, BDSM utilizes an exact column-by-column moment matching to provide higher numerical accuracy. Second, with similar accuracy and macromodel size, BDSM generates very sparse block-diagonal reduced-order models (ROMs) for massive-port systems at a lower cost, whereas traditional algorithms such as PRIMA produce full dense models inefficient for the subsequent simulation. Third, different from those MOR schemes based on extended Krylov subspace (EKS) technique, BDSM is input-signal independent, so the resulting ROM is reusable under different excitations. Finally, due to its blockdiagonal structure, the obtained ROM can be simulated very fast. The accuracy and efficiency of BDSM are verified by industrial power grid benchmarks.

In this paper, we present a fast and stable explicit numerical integration method. Our method utilizes matrix exponential operator to compute numerical solution of the ordinary differential equations of circuits to avoid the stability issue. A matrix partition algorithm and a numerical approximation are proposed to reduce the complexity of matrix exponential and matrix inverse operation. Experimental results show that our method is stable and efficient. Our method is over two times faster than backward Euler on average.

Professor Kuh is a pioneer and giant in physical layout. In this talk, we will describe his influence in placement. His pioneering work from interval graph for one dimensional gate assignment, BBL (Building-Block Layout System for Custom Chip IC Design) [2, 3, 6, 8], BEAR [7] layout system, BAGEL (Gate Array Layout) [17], RAMP (Resistive Analog Module Placement) [5], PROUD (Sea of Gates Placement) [28] to congestion, timing, and low power driven placement, Prof. Kuh always starts with innovative theoretical construction, software system building, and applications with impact on productivity.

Vectorless power grid verification algorithms, by solving linear programming (LP) problems under current constraints, enable worst-case voltage drop predictions at an early design stage. However, worst-case current patterns obtained by many existing vectorless algorithms are time-invariant (i.e., are constant throughout the simulation time), which may result in an overly pessimistic voltage drop prediction. In this paper, a more realistic power grid verification algorithm based on hierarchical current and power constraints is proposed. The proposed algorithm naturally handles general RCL power grid models. Currents at different time steps are treated as independent variables and additional power constraints are introduced; this results in more realistic time-varying worst-case current patterns and less pessimistic worst-case voltage drop predictions. Moreover, a sorting-deletion algorithm is proposed to speed up solving LP problems by utilizing the hierarchical constraint structure. Experimental results confirm that worst-case current patterns and voltage drops obtained by the proposed algorithm are more realistic, and that the sorting-deletion algorithm reduces runtime needed to solve LP problems by 85%.

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

As process technology scales, numerous interconnect schemes have been proposed to mitigate the performance degradation caused by the scaling of on-chip global wires. In this paper, we review current on-chip global interconnect structures and develop simple models to analyze their architecture-level performance. We propose a general framework to design and optimize a new category of global interconnect based on on-chip transmission line (T-line) technology. We perform a group of experiments using six different global interconnection structures to discover their differences in terms of latency, energy per bit, throughput, area, and signal integrity over several technology nodes. Our results show that T-line structures have the potential to outperform conventional repeated RC wires at future technology nodes to achieve higher performance while using less power and improving the reliability of wire communication. Our results also show that on-chip equalization is helpful to improve throughput, signal integrity, and power efficiency.

As semiconductor process technology scales down, interconnect planning presents ever-greater challenges to designers. In this paper, we analyze, evaluate, and compare various metrics with optimized wire configurations in the contexts of different design criteria: delay minimization, delay-power minimization, and delay2-power minimization. We show how various design criteria influence the configuration, performance, and power consumption of repeated wires.

A frequency-time-domain co-simulation flow using discrete Fourier transform (DFT) is introduced in this paper to analyze large power distribution networks (PDN's). The flow not only allows designers to gain an insight to the frequency-domain characteristics of the PDN but also to obtain accurate time-domain voltage responses according to different load current profiles. An adaptive method achieves accurate results within even shorter time compared to the basic DFT flow. In addition, parallel processing is incorporated which leads to a significant reduction in simulation time. Error bounds of the DFT flow are derived to assure the accuracy of simulation results. Experimental results show that the proposed flow has a relative error of 0.093% and a speedup of 10× compared to SPICE transient simulation with a single processor.

In this paper, we propose an efficient approach to minimize the noise on power networks via the allocation of decoupling capacitors (decap) and controlled equivalent series resistors (ESR). The controlled-ESR is introduced to reduce the on-chip power voltage fluctuation, including both voltage drop and overshoot. We formulate an optimization problem of noise minimization with the constraint of decap budget. A revised sensitivity calculation method is derived to consider both voltage drop and overshoot. The sequential quadratic programming (SQP) algorithm is adopted to solve the optimization problem where the revised sensitivity is regarded as the gradient. Experimental results show that considering voltage drop without overshoot leads to underestimating noise by 4.8%. We also demonstrate that the controlled-ESR is able to reduce the noise by 25% with the same decap budget.

As a global interconnection, bus is critical for chip performance in deep submicron technology. Reducing bus routing vias will facilitate the lithography and give bus routing a higher yield and also a higher performance. In this paper, we present a floorplan revising method to minimize the number of reducible routing vias with a controllable loss on the chip area and wirelength. Therefore, it is easy to make a proper tradeoff between via reduction and revising loss. Experiments show that our method reaches a 96.2% and 93.5% reduction of routing vias, which is close to 100% and runs fast. Besides, our revising is friendly to all third-party floorplanners, which can be applied to any existing floorplans to reduce vias. It is also scalable to larger benchmarks.

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

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

We present an integer linear programming (ILP) method that optimizes generalized prefix Ling adders in terms of area, delay, and power. The contribution is listed in the following. (1) We devise an ILP formulation based on logical effort models so that we can use ILP solver, CPLEX, to produce minimum power solutions with given structural, area and timing constraints. The formulation allows the adjustment of parameters and constraints, e.g. the radix numbers and the ratio of static and dynamic power. We implement the flow for the users to automatically synthesize the adders. (2) We engineer sets of integer decision variables and linear constraints to depict the prefix topology, signal delay, and power characterization. Since the design space of prefix adders is large, optimal solutions are usually hard to generate without good formulations. We generate redundant constraints to prune the search space. The approach significantly reduces the execution time. (3) We explore mixed radices for prefix topologies, i.e. GP cells have radices 2, 3, or 4, and a prefix network can contain cells of different radices. This mixed-radix feature expands the design space for better solutions. High-radix adders reduce logic levels and thus can serve for high performance applications. On the other hand, high-radix cells take more logical effort, longer parasitic delay, and more power consumption. These factors are all taken care of in the devised ILP formulation. (4) We adopt the structure of Ling adders to produce faster sum and carry responses. The experiments show that Ling adders achieve better results than normal prefix adders. (5) We apply hierarchical design methods to handle high bit-width modules. One weakness of ILP solver is the scaleability of computational time with the bit-width. We use a divide-and-conquer strategy to synthesize 64-bit adders.

This paper presents an efficient parallel transistor level full-chip circuit simulation tool with SPICE-accuracy. The new approach partitions the circuit into a linear domain and several non-linear domains based on circuit non-linearity and connectivity. The linear domain is solved by parallel fast linear solver while nonlinear domains are parallelly distributed into different processors and solved by direct solver. Parallel domain decomposition technique is used to iteratively solve the different partitions of the circuit and ensure convergence. Different domain decomposition techniques are discussed. Orders of magnitude speedup over SPICE is observed for sets of large-scale VLSI circuits.

To address the performance limitation brought by the scaling issues of on-chip global wires, a new configuration for global wiring using on-chip lossy transmission lines is proposed and optimized. We propose a signaling structure to compensate the distortion and attenuation of on-chip transmission lines, which uses passive compensation and inserts repeated transceivers composing sense amplifiers and inverter chains. An optimization flow for designing this scheme based on eye-diagram prediction and sequential quadratic programming (SQP) is devised. This flow is used to study the latency, power dissipation and throughput performance of the new global wiring scheme as the technology scales from 90 nm to 22 nm. Comparing to repeated RC wire, experimental results demonstrate that at 22 nm technology node, the new scheme can reduce the normalized delay by 80%-95%, the normalized energy consumption by 50%-94%. The normalized latency is 10 ps/mm, the energy per bit is 20 pJ/m, and the throughput is 15 Gbps/mum. All performance metrics are scalable with technology, which makes this approach a potential candidate to break the "interconnect wall" of digital system performance.

With the popularity of multiple power domain (MPD) design, the multi-domain power network noise analysis and minimization is becoming important. This paper describes an efficient heuristic algorithm to arrange the power-up sequence in a multi-domain power network in order to minimize the noise. We present a formulation of this problem and show it is NP-complete. Therefore, we propose a simulated annealing (SA) based algorithm with preprocessing. Experimental results show that the proposed algorithm can minimize the noise close to the minimal values. In terms of efficiency, the SA algorithm is more than hundreds of times faster than the enumerating method and the running time scales well for these cases with the number of domains. In addition, we discuss the trade off between power-up efficiency and noise.

Power consumption of system-level on-chip communications is becoming more significant in the overall system-on-chip (SoC) power as technology scales down. In this paper, we propose a low power design technique of gated bus which can greatly reduce power consumption on state-of-the-art bus architectures. By adding demultiplxers and adopting a novel shortest-path Steiner graph, we achieve a flexible tradeoff between large power reduction versus small wire-length increment. According to our experiments, using the gated bus we can reduce on average 93.2% of wire capacitance per transaction, nearly half of bus dynamic power and on a scale of 5%~10% of total system power.

This work proposes reliability aware through silicon via (TSV) planning for the 3D stacked silicon integrated circuits (ICs). The 3D power distribution network is modeled and extracted in frequency domain which includes the impact of skin effect. The worst case power noise of the 3D power delivery networks (PDN) with local TSV failures resulting from fabrication process or circuit operation is identified in both frequency and time domain. From the experimental results, it is observed that a single TSV failure could increase the maximum voltage variation up to 70% which should be considered in nanoscale ICs. The parameters of the 3D PDN are designed such that the power distribution is reliable under local TSV failures. The spatial distribution of the power noise, reliability and block out area is analyzed to enhance the reliability of the 3D PDN under local TSV failure.

In this paper, we present a fully parallel transistor level full-chip circuit simulation tool with SPICE-accuracy for general circuit designs. The proposed overlapping domain decomposition approach partitions the circuit into a linear subdomain and multiple non-linear subdomains based on circuit non-linearity and connectivity. Parallel iterative matrix solver is used to solve the linear domain while non-linear subdomains are parallelly distributed into different processors topologically and solved by direct solver. To achieve maximum parallelism, device model evaluation is done parallelly. Parallel domain decomposition technique is used to iteratively solve the different partitions of the circuit and ensure convergence. Orders of magnitude speedup over SPICE is observed for sets of largescale circuit designs on up to 64 processors.

This paper proposes a scheme for automatic re-distribution layer (RDL) routing, which is used in chip-package connections. Traditional RDL routing designs are mostly performed manually because the wire geometries are more flexible and therefore more difficult to handle on RDL than on chip. For example, octilinear routing is manufacturable in RDL and is widely adopted due to its higher efficiency than Manhattan routing. In this paper we devise a polynomial time octilinear RDL routing algorithm based on a grid network embedded in the bump array. The grid network is constructed to fully utilize the routing space as well as avoid any spacing violation. Detailed routing solution can be obtained following the min-cost max-flow in the network. Experimental results show the effectiveness of our router.

This paper discusses the impact of migrating from 2-D to 3-D on floorplanning and placement. By looking at a basic formulation of graph cuboidal dual problem, we show that the 3-D case and the 3-layer 2.5-D case are fundamentally more difficult than the 2-D case in terms of computational complexity. By comparison among these cases, the intrinsic complexity in 3-D floorplan structures is revealed in the hard-deciding relations between topological connections and geometrical contacts. The results show future challenges for physical design and CAD of 3-D integrated circuits.

Reliable design of power distribution network for stacked integrated circuits introduces new challenges i.e., substrate coupling among through silicon vias (TSVs) and tiers grid in addition to reliability issues such as electromigration and thermo-mechanical stress, compared to conventional system on chip (SoC). In this paper a comprehensive modeling of the TSV and stacked power grid with frequency dependent parasitic is proposed. The analytical model considers the impact of the substrate coupling between the TSVs and layers grid. A frequency domain based analysis flow is introduced to incorporate frequency dependent parasitics. The design of a reliable power distribution network is formulated as an optimization problem to minimize power noise under reliability and electro-migration constraints. Experimental results demonstrate the efficacy of the problem formulation and solution technique.

As the feature size of VLSI circuits scales down and clock rates increases, circuit performance is becoming more sensitive to process variations. This paper proposes an algorithm of symmetrical buffer placement in symmetrical clock trees to achieve zero-skew in theory, as well as robust low skew under process or environment variations. With the completely symmetrical structure, we can eliminate many factors of clock skew such as model inaccuracy, environment temperature and intra-die process variations. We devise a new dynamic programming scheme to handle buffer placement and wire sizing under the constraint of symmetry. By classifying the wires by tree levels and defining the level-dependent blockages, the potential candidate points in the gaps of circuit blocks can be fully explored. The algorithm is efficient for minimizing source-sink delay as well as other linear cost functions. Experiments show that our method helps to obtain a balanced design of clock tree with low delay, skew and power.

In this paper, an efficient framework is proposed to analyze the worst case of voltage variation of power network considering multidomain clock gating. First, a frequency-domain-based simulation method is proposed to obtain the time-domain voltage response. With the vector fitting technique, the frequency-domain responses are approximated by a partial fraction expression, which can be easily converted to a time-domain waveform. Then, an algorithm is proposed to find the worst-case voltage variation and corresponding clock gating patterns, through superimposing the voltage responses caused by all domains working separately. The major computation of the whole framework is solving the frequency-domain equation system, whose complexity is about$O(N^{\alpha}D\log f_{\max})$, where$\alpha$is between one and two if using an iterative solver from the PETSc library.$N$is the node number,$f_{\max}$is the upper bound of frequency, and$D$is the number of clock domains. Numerical results show that the proposed simulation method is up to several hundred times faster than commercial fast simulators, like HSPICE and MSPICE. In addition, the proposed method is able to analyze large-scale power networks that the commercial tools are not able to afford.

Low energy and small switch area usage are two important design objectives in FPGA global routing architecture design. This article presents an improved MCF model based CAD flow that performs aggressive optimizations, such as topology and wire style optimization, to reduce the energy and switch area of FPGA global routing architectures. The experiments show that when compared to traditional mesh architecture, the optimized FPGA routing architectures achieve up to 10% to 15% energy savings and up to 20% switch area savings in average for a set of seven benchmark circuits.

This paper presents a new logic style, named Current-Mode Differential logic (CMDL), that achieves both high operating speed and low power consumption. Inspired by the low-voltage swing (LVS) logic, CMDL uses a shunt resistor at the differential output to obtain constant low swing signal without the need to reset low. Furthermore, conditional shunt transistors are used for the internal nodes to prevent high-voltage swing, thus entirely eliminate the power-hungry clocked reset network in LVS circuits. We show that the CMDL is suitable for high-end microprocessor integer core by providing three datapath modules implemented in CMDL. Our simulation results indicate that, operating at comparable speed with LVS logic, CMDL circuits can achieve up to 50% reduction of delay-power product compared to CMOS logic and LVS logic. In addition, CMDL reduces the power consumption of LVS by up to 40%.

This paper optimizes timing and power consumption of mixed-radix Ling adders with the physical area constraints using an integer linear programming formulation. Each cell in the prefix network is flexible to have different radix and size, and Ling carries are incorporated. Optimal solutions are obtained by solving the proposed formulation. The experiments show that the produced optimal structures have a large power saving compared with traditional designs. The ASIC implementation results are superior to those produced by Synopsys Module Compiler.

A low power passive equalizer using RL terminator is proposed and optimized in this work. The equalizer includes an inductor in series with the resistive terminator, which boosts high frequency components and therefore improves the interconnect bandwidth with little overhead on power consumption. An analytic estimation method for eye-opening and jitter based on tritonic step response is also introduced in this work, which enables the optimization procedure. Our experimental results show that our estimation method is accurate and a board level transmission line of 50cm wire length can achieve 15Gb/s data rate. With 15GHz frequency input, the power consumption of the equalizer is less than 2.5mW, and the total power is 5mW.

This paper proposes an efficient method to find the worst case of voltage violation by multi-domain clock gating in an on-chip power network. We first present a voltage response in an arbitrary multi-domain clock gating pattern, using a superposition technique. Then, an integer linear programming (ILP) formulation is proposed to identify the worst-case gating pattern and the maximum variation area. The ILP based method is significantly faster than a conventional method based on enumeration. The experimental results are also compared with a case where peak voltage variation is induced, which shows the latter technique largely underestimated the overall variation effect.

Fixed-outline floorplanning, which enables hierarchical design, is considered more and more important nowadays. In this paper, a novel SA-based Fixed-outline Floorplanner with the Optimal Area utilization named SAFFOA is introduced to improve the total wirelength. The basic idea is to build and solve a group of four quadratic equations in four variables iteratively, which can handle the fixed-outline constraint of any aspect ratio. A new topological representation called Ordered Quadtree is then custom-made for this basic idea to facilitate its integration into SA iterations. After the fixed-outline constraint with 100% area utilization is achieved, we will solve the tradeoff between the chip area and wirelength and thus concentrate on the latter in SA process. Experimental results show that the chip wirelength is decreased by about 16.8% and 8.6% on average, compared with two previous fixed-outline floorplanners on soft modules, which are both proved to be better than Parquet. Besides, our method is still competitive on the wirelength, even if compared with some leading-edge outline-free floorplanners. At last, Local Refinement is also adopted to guide the SA process and reshape soft modules to meet the constraint on their aspect ratios (ARs). With its help, SAFFOA can still generate feasible floorplans with no deadspace under a strict AR constraint such as [0.5,2].

This paper introduces an accumulative prediction method to predict the eye diagram for high speed signaling systems. We use the step responses of pull-up and pull-down to extract the worst-case eye diagram, including the eye height and jitter. Furthermore, the method produces the input patterns of the worst-case intersymbol interference. The algorithm handles signals of either symmetric or asymmetric rise/fall time. Experimental results demonstrate the accuracy and efficiency of the proposed method.

In today’s many-core era, the interconnection networks have been the key factor that dominates the performance of a computer system. In this paper, we propose a design flow to discover the best topology in terms of the communication latency and physical constraints. First a set of representative candidate topologies are generated for the interconnection networks among computing chips; then an efficient multi-commodity flow algorithm is devised to evaluate the performance. The experiments show that the best topologies identified by our algorithm can achieve better average latency compared to the existing networks.

To address the performance limitation brought by the scaling issues of on-chip global wires, a new configuration for global wiring using on-chip lossy transmission lines(T-lines) is proposed and optimized in this paper. Firstly, we use passive compensation and repeated transceivers composed by sense amplifier and inverter chain to compensate the distortion and attenuation of on-chip T-lines. Secondly, an optimization flow for designing this scheme based on eye-diagram prediction and sequential quadratic programming (SQP) is proposed. This flow is employed to study the latency, power dissipation and throughput performance of the new global wiring scheme as the technology scales from 90nm to 22nm. Compared with conventional repeater insertion methods, our experimental results demonstrate that, at 22nm technology node, this new scheme reduces the normalized delay by 85.1%, the normalized energy consumption by 98.8%. Furthermore, all the performance metrics are scalable as the technology advances, which makes this new signaling scheme a potential candidate to break the “interconnect wall” of digital system performance.

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

Parallel prefix adder is the most flexible and widely-used binary adder for ASIC designs. Many high-level synthesis techniques have been developed to find optimal prefix structures for specific applications. However, the gap between these techniques and back-end designs is increasingly large. In this paper, we propose an integer linear programming method to build minimal-power prefix adders within given timing and area constraints. It counts both gate and wire capacitances in the timing and power models, considers static and dynamic power consumptions, and can handle gate sizing and buffer insertion to improve the performance further. The proposed method is also adaptive for non-uniform arrival time and required time on each bit position. Therefore our method produces the optimum prefix adder for realistic constraints.

We extend the surfliner on-chip distortionless transmission line scheme and provide more details for the implementation issues. Surfliner seeks to approach distortionless transmission by intentionally adding shunt resistors between the signal line and the ground. In theory if we distributively make the shunt conductance G=RC/L, there is no distortion at the receiver end and the signal propagates at the speed of light. We show the feasibility and advantages of this shunt resistor scheme by a real design case of single-ended microstrip line in 0.10mum technology. The simulation results indicate we can achieve near perfect signaling of 10 Gbps data over a 10 mm serial link, yet no pre-emphasis/equalization or other special techniques are needed. Guidelines for determining the optimal value and spacing of the shunt resistors are also provided.

We propose two orthogonal approaches to logarithmic cyclic shifter design. The first method, called fanout splitting, replaces multiplexers in a conventional design with demultiplexers which have two fanouts driving the shifting and non-shifting paths separately. The use of demultiplexers has a two-fold effect; it cuts the accumulated wire load on the critical path from O(Nlog2(N)) to O(N), and reduces the switching probabilities on the inter-stage long wires from 1/4 to 3/16. We then perform cell order optimization to further improve the delay, and formulate it as an integer linear programming problem. For the 64-bit case, the two approaches together reduce the total delay by 67.1% and dynamic power consumption by 17.6%, respectively.

Heart activities are governed by the sympathetic and parasympathetic nervous system. Changes in these neural signals influence the development of arrhythmias, including ventricular tachyarrhythmias that often progress to sudden cardiac death (SDC). A simultaneous study of the cardioneural signals with the electrical heart activity can elucidate the mechanism of abnormal heart activity. In this work, we identify the locations to detect cardioneural signals. We first perform a 108 channel measurement to explore the cardioneural signals. We then focus on selected locations for longer period measurement. We monitor the changes in the heart rate following each sympathetic or vagal nerve activity. The neural signals are extracted from ECG by applying independent component analysis. The work provides a promising approach for studying the association of cardioneural signals with electrical heart activity.

Low energy and small switch area usage are two of the important design objectives in FPGA global routing architecture design. This paper presents an improved MCF model based CAD flow that performs aggressive optimizations, such as topology and wire style optimizations, to reduce the energy and switch area of FPGA global routing architectures. The experiments show that when compared to traditional mesh architecture, the optimized FPGA routing architectures achieve up to 10% to 15% energy savings and up to 20% switch area savings in average for a set of seven benchmark circuits.

This paper develops a novel high-speed inter-chip serial signaling scheme with leakage shunt resistors and termination resistors between the signal trace and the ground. For given abstract topology transmission line based on the data for IBM high-end AS/400 system[1] [2], we put termination resistors at the end of receiver and adjust the shunt and termination resistors value to get the optimal distortion-less transmission line. Analytical formulas are derived to predict the worst case jitter and eye-opening based on bitonic step Response Assumption[3]. Our schemes and the other two comparison cases are discussed.

This paper proposes an efficient analysis flow and an algorithm to identify the worst case noise for power networks with multiple clock domains. First, we apply the Laplace transform on the input current sources to derive the analytical formula. Then, we calculate the circuit frequency response with logarithmic scale frequency components. The frequency domain response is approximated by a rational function using vector fitting modeling. The rational function is used to derive the natural frequency of the power ground networks, and can be converted back into time domain easily. Based on the analysis results, we then present the worst case clock gating pattern algorithm to analyze the power networks with multiple clock domains. The most expensive part of the proposed algorithm is the matrix solving: O(F(N) ldr log f ldr D). Function F is the complexity of iterative solution of complex matrix with dimension N. We assume that there are D clock domains and the frequency spans from 0 to f Hz. Experimental results show that our method is up to 60X faster than HSPICE, and can analyze large circuits which are not affordable by HSPICE.

In this paper, an efficient approach is proposed for the problem of transient simulation of lossy transmission lines. The complexity of the conventional convolution approach for lossy transmission lines is reduced from O(N2) to O(Nlog2N) by utilizing a multilevel FFT convolution method, where N is the total number of time points. Numerical convolution formula that exploits both the analytical forms of the lossy transmission line impulse responses and adaptive time steps are developed for the multilevel FFT convolution method. A new breakpoint control scheme is also proposed to adaptively control simulation time step. Experimental results show that the proposed approach is over 100 times faster than Berkeley SPICE3 (Quarles, et al, 1993) while remains the same accuracy.

One effective way to reduce power ground network noise is to add decoupling capacitors, but this method changes the impedance and natural frequency. Traditional simulation requires re-simulating the whole circuit, which is time-consuming. This paper presents a fast impedance curve and natural frequency computation algorithm, based on vector fitting modeling with incremental value of decap. The new method fits several sampling data in an impedance curve with a rational function. Therefore, the impedance at other frequencies would be easily interpolated. Moreover, vector fitting computes poles accurately and thus finds natural frequencies. Experiments show that the results of this method are accurate and the algorithm complexity is much lower than with traditional method.

In this paper, we investigate thermal via (T-via) planning during three-dimensional (3-D) floorplanning. First, we consider the temperature constrained T-via planning (TVP) problem on a given 3-D floorplan. Second, we integrate dynamic TVP into 3-D floorplanning process. Our main contribution and results can be summarized as follows. We solve the temperature constrained TVP problem by solving a sequence of simplified interlayer and intralayer TVP subproblems. Each subproblem is formulated as convex programming problem and we derive nearly optimal solution for detailed T-via distribution. Based on the TVP solution, we implement the integrated TVP and 3-D floorplanning algorithm in a two-stage approach. Before floorplanning, blocks are assigned into different layers by solving a sequence of knapsack problems. During floorplanning, T-vias are allocated with white space redistribution to optimize T-via insertion. Experimental results show that our TVP approach can reduce T-vias by 12% compared with a recent published work (J. Cong and Y. Zhang, "Thermal via planning for 3-D ICs," in Proc. Int. Conf. Comput.-Aided Des., Nov. 2005, pp.745-752). Compared with the postfloorplanning optimization approach, integrating TVP into floorplanning process can reduce T-vias by 16% with 21% runtime overhead

We improve the efficiency of static timing analysis when false paths are considered. The efficiency of timing analysis is critical for the performance driven optimization program because timing analysis is invoked heavily in the inner loop. However, when false paths are dealt with in timing analysis, a large number of tags needs to be created and propagated, thus deteriorating efficiency. In this paper, weminimize the number of the tags through a biclique-covering approach, which iteratively removes a tag if the false path information in the tag is covered by the union of other tags.With the produced tags, we remove the false path timing and guarantee to cover the nonfalse path timing. Since the minimum biclique covering of the general bipartite graph is NP complete [Indag. Math., vol. 39, p. 211, 1977], [Discrete Math., vol. 149, no. 1–3, p. 159, 1996], we use a minimal degree ordering approach to perform the biclique-covering minimization. The experimental results show significant reduction on the number of tags.

In this paper, we introduce an efficient transistorlevel simulation tool with SPICE-accuracy for deepsubmicrometer very large-scale integration circuits with strong-coupling effects. The new approach uses multigrid for huge networks of power/ground, clock, and interconnect with strong coupling. Mutual inductance can be incorporated without error-prone matrix sparsification approximations or expensive matrix inversion. Transistor devices are integrated using a novel two-stage Newton–Raphson method to dynamically model the linear network and nonlinear devices boundary. Orders-ofmagnitude speedup over Berkeley SPICE3 is observed for sets of real deep-submicrometer design circuits.

We propose a framework to unify the process of false paths and multi-cycle paths in static timing analysis (STA). We use subgraphs attached with timing constraints to represent false paths and multi-cycle paths. The complexity of the subgraph representation is reduced to improve efficiency. Finally, we present theorems to show that the unified framework produces correct timings. The experimental results demonstrate that the minimization is effective for both artificial and industry test cases.

In this paper, we introduce a general operator splitting method for transient simulation of VLSI circuits. The proposed approach generates special partitions of the circuits and alternates the explicit and implicit integrations between the partitions. We prove that the method is unconditionally stable independent of the step size. The splitting scheme greatly reduces the nonzero fill-ins generated in direct methods like LU decomposition. Orders of magnitude speedup over Berkeley SPICE3 is observed for sets of circuits.

We have developed a new approach to studying human heart activity using independent component analysis. The electrocardiogram (ECG) is an important tool in diagnosis of heart disease. However, the normal 12-lead ECG can only record limited aspects of heart's electrical signals and mostly their interpretation relies on trained and experienced medical doctors. We have performed experiments in which heart signals were recorded in high spatial resolution. Independent component analysis was applied to the recorded signals to separate distinct temporal components of the recorded signals. The separated components were further analyzed by back-projecting their activities to the surface montage to examine each component's property. Experimental results show this to be a promising approach that can be extended to build more detailed heart activity simulations

Communication latency and power consumption are two competing objectives in Network-on-Chip (NoC) design. This paper proposes a novel method that unifies these two objectives in a multi-commodity flow (MCF) formulation. With an improved fully polynomial approximation algorithm, power efficient design of an 8 x 8 NoC can be found for given average latency constraints with certain communication bandwidth requirements. Experimental results suggest that (1) compared with mesh, torus and hypercube topologies, the optimized design can improve power latency product by up to 52.1%, 29.4% and 35.6%, respectively. (2) by sacrificing 2% latency, power consumption of the optimized design can be improved by up to 19.4%, which indicates the importance of power and latency co-optimization in NoC design.

The chip/package I/Os count has continuously been growing as the systems become more complicated. High density I/Os interconnection and efficient escape routing with high performance and low cost will greatly benefit the whole electronic system. We analyze the properties of the hexagonal array, which can hold about 15% more I/Os compared with the traditional square grid array. We propose three escape routing strategies for the hexagonal array: column-by-column horizontal escape routing, two-sided horizontal/vertical escape routing, and multi-direction hybrid channel escape routing. We can escape I/Os in the hexagonal array in the same or less number of routing layers compared with square grid array. The practical examples show the efficiency of our strategies. Using hexagonal array, we can reduce the number of escape routing layers as well as increase the density of I/Os.

Division is one of the most complicated and expensive arithmetic operations. Both clock frequency and operation delay are limited by the memory wall, even in LUT-based FPGA devices. To conquer the memory limitation, we propose a hybrid division algorithm which employs Prescaling, Series expansion and Taylor expansion (PST) algorithms. The proposed algorithm boosts very-high radix division efficiently. The algorithm is multiplicative, and feasible for the modern FPGA devices with build-in multipliers. The algorithm is implemented in Altera StratixII FPGA devices and compared with the division IP core generated by MegaWizard. The result shows that the PST algorithm has higher clock frequency, lower execution time and also lower power consumption.

We devise a central triangular sequence to minimize the escape routing layers in area array packaging. We use a network flow model to analyze the bottleneck of the routable pins. The triangular patterns are generated in a reverse order from the last to the first layer. We demonstrate that the triangular pin sequence maximizes the sum of escape pins in the accumulated layers and thus minimize the number of escape routing layers. A test case is presented to illustrate the approach.

In this paper, we propose a timing model reduction algorithm for hierarchical timing analysis based on a bicliquestar replacement technique. In hierarchical timing analysis, each functional block is characterized into an abstract timing model. The complexity of analysis is linear to the number of edges in the abstract timing model for timing propagation. We propose a biclique-star replacement technique to minimize the number of edges in the timing model. The experiments on industry test cases show that by allowing acceptable errors, the proposed algorithm can largely reduce the number of edges in the timing model.

Incorporating thermal vias into 3D ICs is a promising way to reduce circuit temperature by lowering down the thermal resistances between device layers. In this paper, we integrate dynamic thermal via planning into 3D floorplanning process. Our 3D floorplanning and thermal via planning approaches are implemented in a two-stage approach. Before floorplanning, the temperature-constrained vertical thermal via planning is formulated as a convex programming problem. Based on the analytical solution, blocks are assigned into different layers by solving a sequence of knapsack problems. Then a SA engine is used to generate floorplans of all these layers simultaneously. During floorplanning, thermal vias are distributed horizontally in each layer with white space redistribution to optimize thermal via insertion. Experimental results show that compared to a recent published result from [14], our method can reduce thermal vias by 15% with 38% runtime overhead.

A parallel prefix circuit has n inputs x 1 , x 2 , …, x n , and computes the n outputs y i = x i • x i −1 •…• x 1 , 1 ≤ i ≤ n , in parallel, where • is an arbitrary binary associative operator. Snir proved that the depth t and size s of any parallel prefix circuit satisfy the inequality t + s ≥2 n −2. Hence, a parallel prefix circuit is said to be of zero-deficiency if equality holds. In this article, we provide a different proof for Snir's theorem by capturing the structural information of zero-deficiency prefix circuits. Following our proof, we propose a new kind of zero-deficiency prefix circuit Z ( d ) by constructing a prefix circuit as wide as possible for a given depth d . It is proved that the Z ( d ) circuit has the minimal depth among all possible zero-deficiency prefix circuits.

In high performance systems, process variations and fluctuations of operating environments have significant impact on the clock skew. Recently, hybrid structures of H-tree and mesh [2,15,18,19] were proposed to distribute the clock signal with a balanced H-tree and lock the skew using the shunt effect of the mesh. However, in multi-giga hertz regime, the RC model [15] of the mesh is no longer valid. The inductance effect of the mesh can even make the skew worse. In this paper, we investigate the use of a novel architecture which incorporates multiple level transmission line shunts to distribute global clock signal. We derive the analytical expression of the skew reduction contributed by the shunt of a transmission line with the length of an integral multiple of clock wavelength. Based on the analytical skew expression, we adopt convex programming techniques to optimize the wire widths of the multi-level transmission line network. Simulation results show that the multilevel network achieves below 4ps skew for 10GHz clock rate.

The notion of design for manufacturability is blurring the separation between the tasks of design and manufacture. In the era of nano-technologies, the description of the design rules has retreated back to an early stage form of many conditional cases and even an art. Thus, it is important to set the metrics for the manufacturability. However, who is going to be held accountable for the final outcomes? Should the designer, the EDA developer, the manufacture engineer, or a new breed of experts take the lead to tackle the problem?

This paper presents an integrated methodology for high-performance integer multiplier design, which combines algorithmic partial product generation, logic synthesis, and physical layout into a unified process. The interconnect delay, which dominates the performance of a multiplier, is thoroughly considered in this integration. The special structures in the multiplier are utilized to reduce the high complexity of the holistic approach. Compared with multipliers generated by a state-of-the-art tool, the timing improvements of our results are 11% for a 16-bit multiplier, and 7.5% for a 32-bit multiplier.

Parallel prefix adder is a general technique for speeding up binary addition. In unit delay model, we denote the size and depth of an n-bit prefix adder C(n) as SC(n) and dC(n) respectively. Snir proved that sC(n) + dC(n) ≥ 2n - 2 holds for arbitrary prefix adders. Hence, a prefix adder is said to be of zero-deficiency if sC(n) + dC(n) = 2n - 2. In this paper, we first propose a new architecture of zero-deficiency prefix adder dubbed Z(d), which provably has the minimal depth among all kinds of zero-deficiency prefix adders. We then design a 64-bit prefix adder Z64, which is derived from Z(d)|d=8, and compare it against several classical prefix adders of the same bit width in terms of area and delay using logical effort method. The result shows that the proposed Z(d) adder is also promising in practical VLSI design.

In this paper, we introduce an efficient transistor level simulation tool with SPICE-accuracy for deep-submicron(DSM) VLSI circuits with strong coupling effects. The new approach uses multigrid for large networks of power/ground, clock and signal interconnect. Transistor devices are integrated using a novel two-stage Newton-Raphson method to dynamically model the linear network and nonlinear devices interface. Orders of magnitude speedup over Berkeley SPICE3 is observed for sets of DSM design circuits.

We improve the efficiency of static timing analysis when false paths are considered. The efficiency of timing analysis is critical for the performance driven optimization program because timing analysis is invoked heavily in the inner loop. However, when false paths are dealt in timing analysis, a large number of tags need to be created and propagated, and thus deteriorated the efficiency. In this paper, we minimize the number of the tags through a biclique covering approach, which iteratively removes a tag if the false path information in the tag is covered by the union of other tags. The produced tags remove the false path timing and guarantee to cover the true path timings. Since the minimum biclique covering of the general bipartite graph is NP complete, we use a minimal degree ordering approach to perform the biclique covering minimization. The experimental results show significant reduction on the number of tags.

We present a novel scheme to implement distortionless transmission lines for on-chip electrical signaling. By introducing intentional leakage conductance between the wires of a differential pair, the distortionless transmission line eliminates dispersion caused by the resistive nature of on-chip wires and achieves speed of light transmission. We show that it is feasible to construct distortionless transmission line with conventional silicon process. Simulation results show that using 65nm technology, the proposed scheme can achieve 15Gbits/s bandwidth over a 20mm on-chip serial link without any equalization. This approach offers a six times improvement in delay and 85% reduction in power consumption over a conventional RC wire with repeated buffers.

Power consumption has become one of the first order design considerations of the nano-scale VLSI designs. In this paper, we propose a methodology to synthesize energy-efficient networks-on-chip (NoCs). Our methodology features three key characters. First, we adopt a multi-commodity flow formulation to unify network topologies, physical embedding, and wire style optimizations. Second, we utilize a variety of interconnect wire styles to achieve high performance low power on-chip communication. Third, we heuristically explore a large design space of network topologies. Experiments on a homogeneous communication demand model demonstrate that for a 4 /spl times/ 4 NoC with torus topology, our methodology can achieve a power saving up to 35%.

A complete placement system, UPlace, for mixed mode designs is presented, which consists of a force-directed global placement, and a zone-refinement based detailed placement. For global placement, a unified objective function capturing both wire length and cell distribution is proposed; quadratic programming is formulated to optimize the unified object function efficiently; a discrete cosine transformation method is devised to calculate the uneven cell distribution cost. A dynamic approach for decomposing multi-pin nets into two-pin nets is also introduced for better wire length modeling. Zone refinement method is used for a unified legalization and detailed placement process. Experimental results show that the placement algorithm is very promising.

The Y architecture for on-chip interconnect is based on pervasive use of 0/spl deg/, 120/spl deg/, and 240/spl deg/ oriented semiglobal and global wiring. Its use of three uniform directions exploits on-chip routing resources more efficiently than traditional Manhattan wiring architecture. This paper gives in-depth analysis of deployment issues associated with the Y architecture. Our contributions are as follows. 1) We analyze communication capability (throughput of meshes) for different interconnect architectures using a multicommodity flow approach and a Rentian communication model. Throughput of the Y architecture is largely improved compared to the Manhattan architecture, and is close to the throughput of the X architecture. 2) We improve existing estimates for the wirelength reduction of various interconnect architectures by taking into account the effect of routing-geometry-aware placement. 3) We propose a symmetrical Y clock tree structure with better total wire length compared to both H and X clock tree structures, and better path length compared to the H tree. 4) We discuss power distribution under the Y architecture, and give analytical and SPICE simulation results showing that the power network in Y architecture can achieve (8.5%) less IR drop than an equally resourced power network in Manhattan architecture. 5) We propose the use of via tunnels and banks of via tunnels as a technique for improving routability for Manhattan and Y architectures.

The dominating contribution of interconnect to system performance has made it critical to plan the resources of the buffers and routes in the early stage of the layout. In this paper, we integrate floorplanning with buffer insertion for performance-driven design processes. We devise a two-step method to evaluate the feasible buffer insertion sites, which can improve the efficiency of the buffer-planning algorithm. By partitioning all empty spaces into blocks in the packing process, the buffer allocation is handled as an integral part of the floorplanning. Our buffer-planning algorithm maps the buffers into tiles with consideration of routing congestion. In this approach, we construct a distribution graph to model the possible routes. The buffer allocation method is performed on the updated distribution graph to find the buffer locations with their respective congestion costs. The method is based on a simulated annealing approach, which is composed of multiple phases to speed up the optimization. Since there is more freedom with floorplan optimization, the empirical results demonstrate better performance.

Binary addition is one of the most frequent operations in computation systems. Dedicated carry logic in modern FPGA devices allows ripple-carry adders to outperform other kinds of adders. However, a long carry chain is still time-consuming in a wide bit-width adder. We propose a new methodology to partition the long carry chain into short segments and organize these segments by applying carry-select or carry-skip schemes. Therefore, the resulting adder can take advantage of fast carry ripple locally, reduce the long signal delay globally, and produce high performance calculations.

The timing-convergence problem arises because estimations made during logic synthesis may not be met during physical design. In this paper, an efficient rewiring engine is proposed to explore maximal freedom after placement. The most important feature of this approach is that the existing placement solution is left intact throughout the optimization. A linear-time algorithm is proposed to detect functional symmetries in the Boolean network which are then used as the basis for rewiring. Integration with an existing gate-sizing algorithm further proves the effectiveness of our technique. Three applications are demonstrated: delay, power, and reliability optimization.

Timing performance and routability are two main goals of global routing. These two targets are mutually conflicting if we view and handle their effects independently. In this paper, we adopt a shadow price mechanism to incorporate the two issues into one unified objective function. We formulate global routing as a multicommodity flow problem. The objective function is the slack of congestion with the clock period as the delay limit from registers and inputs to registers and outputs. The multicommodity flow is expressed by a linear-programming formulation as a primal problem. We then convert the primal problem into a dual formulation using the shadow price as the variables. The shadow price of a net is the sum of its congestion price and timing price. The primal and dual formulation offers theoretical upper and lower bounds of the routing solution. Throughout the optimization process, the difference of the two bounds reduces, which provides the user's insight into the quality of the solutions. Based on the new formulation, this paper presents the UTACO algorithm for standard cell global routing.

This paper deals with area minimization of power network for very large-scale integration designs. A new algorithm based on efficient nonlinear programming techniques is presented to solve this problem. During the optimization, a penalty method, conjugate gradient method, circuit sensitivity analysis, and merging adjoint networks are applied, which enables the algorithm to optimize large circuits. The experiment results prove that this algorithm is robust and can achieve the objective of minimizing the area of power network in a short runtime.

Corner Block List (CBL) was recently proposed as an efficient representation for MOSAIC packing of rectangles. Although the original method is really innovative, there still remains room for improvement for our purpose. This article proposes a compact algorithm for placement based on corner block list. By introducing the dummy blocks in CBL, our algorithm can intellectively employ dummy blocks in the packing to represent the placement including empty rooms, which corner block list cannot represent. Our algorithm can obtain the fast convergence to an optimal solution. Based on the compact approach, we propose a new way to handle arbitrary shaped rectilinear modules. The experimental results are demonstrated by some benchmark data and the performance shows effectiveness of the proposed method.

This paper studies the buffer planning problem for interconnect-centric floorplanning for nanometer technologies. The dead-spaces are the spaces within a placement that are not held by any circuit block. In this paper, we proposed a buffer planning algorithm based on dead space redistribution to make good use of dead-spaces for buffer insertion. Associated with circuit blocks under topological representations, the dead space can be redistributed by freely moving some circuit blocks within their rooms in the placement. The total area and the topology of the placement keep unchanged while doing the dead space redistribution. The number of nets satisfying the delay constraint can be increased by redistributing the dead space all over the placement, which has been demonstrated by the experimental results. The increment of the number of nets that satisfy delay constraints is 9% on an average.

In this paper, we propose a new on-chip interconnect scheme called Y-architecture, which can utilize the on-chip routing resources more efficiently than traditional Manhattan interconnect architecture by allowing wires routed in three directions (0°, 60°, and 120°). To evaluate the efficiency of different interconnect architectures, we assume mesh structures with uniform communication demand and develop a multi-commodity flow (MCF) approach to model the on-chip communication traffic. We also extend the combinatorial MCF algorithm in [5] to compute the optimal routing resource allocations for different interconnect architectures. The experiments show that: (1) Compared with Manhattan architecture, the Y-architecture demonstrates a throughput improvement of 30.7% for square chip. The throughput of the Y-architecture is only 2.5% smaller than that of X-architecture. (2) A chip with the shape of a convex polygon produces better throughput than a rectangular chip: For Y-architecture, a hexagonal chip provides 41% more throughput than a squared chip using the Manhattan architecture. For Manhattan architecture, a diamond chip achieves a throughput improvement of 19.5% over the squared chip using the same interconnect architecture. (3) Compared with Manhattan architecture, the Y-architecture reduces the wire length of a randomly distributed two pin net by 13.4% and the average wire length of Y-architecture is only 4.3% more than that of the X-architecture.

Timing performance and routability are two main issues of global routing. In this paper, we adopt a shadow price mechanism to incorporate the two issues into one unified objective function. The shadow price of a net is the sum of its congestion price and timing price. Based on the new formulation, this paper presents the UTACO algorithm for standard cell (SC) global routing. The experimental results show that UTACO is efficient for both timing and congestion optimization.

We propose a new linear network reduction algorithm based on a generalized Y-Δ transformation technique in s-domain. Resultant admittance is kept as a rational function of s with a dramatically reduced order. Yet it preserves low-order terms of exact admittance evaluated with traditional symbolic analysis. Stability of transfer functions derived from reduced-order admittance is guaranteed via a Hurwitz polynomial approximation. Such low-order transfer functions are used in pole analysis and time domain waveform evaluation in response to any input signal.

An efficient matrix solver is critical to the analytical placement. As the size of the matrix becomes huge, the multilevel methods turn out to be more efficient and more scalable. Algebraic Multigrid (AMG) is a multilevel technique to speedup the iterative matrix solver [10]. We apply the algebraic multigrid method to solve the linear equations that arise from the analytical placement. A layout based clustering scheme is put forward to generate coarsening levels for the multigrid method. The experimental results show that the algebraic multigrid solver is promising for analytical placement.

By dividing the packing area into routing tiles, we can give the budget of the buffer insertion. And the detail locating of the blocks in their rooms can be implemented for each iterations during the annealing process to favor the later buffer planning. The buffer insertion will affect the possible routes as well the congestion of the packing. The congestion estimation in this paper takes the buffer insertion into account. So we devise a buffer planning algorithm to allocate the buffer into tiles with congestion information considered. The buffer allocation problem is formulated into a net flow problem and the buffer allocation can be handled as an integral part in the floorplanning process. Since there is more freedom for floorplan optimization, the floorplanning algorithm integrated with buffer planning can result in better performance and chip area.

We propose a realizable RCLK-in-RCLK-out parasitic reduction technique. The method employs generalized Y-Δ transformation. In our method, admittances are kept in their original rational forms of s, and their orders are reduced by truncating high-order terms. Therefore reduced admittances match the low-order terms in exact admittances. First-order realization of admittances is guaranteed, and higher-order realization is achieved by template optimization using Geometric Programming. The algorithm uniquely uses common-factor identification and cancelation operations to make Y-Δ transformation numerically stable. The experiment shows that our method can achieve higher reduction ratio than TICER and comparable simulation results with PRIMA.

In this paper, we introduce an efficient analysis method for the power network of general topology. The new approach is based on algebraic multigrid (AMG) method that can avoid the slow convergence of basic iterative methods. An innovative adaptive coarsening and error-smoothing scheme is employed to further speed up the performance, taking advantage of the spatial variation of power supply noise. Experimental results show that our method is more than 100 times faster than SPICE3.

Previous works on buffer planning are mainly based on fixed die placement. It is necessary to reduce the complexity of computing the feasible buffer insertion sites to integrate the buffer planning with the floorplanning process. In this paper, we give an efficient buffer planning algorithm with linear complexity by computing all the feasible buffer insertion sites in a 2-step method. By partitioning all the dead spaces into blocks while doing the packing, the buffer allocation can be handled as an integral part in the floorplanning process. Our method is based on a simulated annealing approach which is divided into two phases: timing optimization phase and buffer insertion phase. Since there is more freedom for floorplan optimization, the floorplanning algorithm integrated with buffer planning can result in better time performance and chip area.

Floorplan representation is a fundamental issue in designing a floorplanning algorithm. In this paper, we first present a twin binary trees structure for mosaic floorplans. It is a nonredundant representation. We then derive the exact number of configurations for mosaic floorplans and slicing floorplans. Finally, the relationships between various state-of-the-art floorplan representations are discussed and explored.

Interconnect architecture plays an important role in determining the throughput of meshed communication structures. We assume a mesh structure with uniform communication demand for communication. A multi-commodity flow (MCF) model is proposed to find the throughput for several different routing architectures. The experimental results reveal several trends: 1. The throughput is limited by the capacity of the middle row and column in the mesh, simply enlarging the congested channel cannot produce better throughput. A flexible chip shape provides around 30% throughput improvement over a square chip of equal area. 2. A 45-degree mesh allows 17% throughput improvement over 90-degree mesh and a 90-degree and 45-degree mixed mesh provides 30% throughput improvement. 3. To achieve maximum throughput on a mixed Manhattan and diagonal interconnect architecture, the best ratio of the capacity for diagonal routing layers and the capacity for Manhattan routing layers is 5.6. 4. Incorporating a simplified via model, interleaving diagonal routing layers and Manhattan routing layer is the best way to organize the wiring directions on different layers.

High performance SoC requires nonblocking interconnections between an array of processors built on one chip. With the advent of deep sub-micron technologies, switches are becoming much cheaper while wires are still expensive. Therefore, optimization efforts should focus on the wire resources. In this paper, we devise air objective function to balance the interconnect topology between routing area and power dissipation. Based on the objective function, we find the best one-dimensional and two-dimensional nonblocking interconnect architectures. Furthermore, we define a derivative benefit and devise a strategy for improving the performance of hierarchical nonblocking interconnect architectures and derive optimized results.

Wirelength estimation techniques typically contain a site density function that enumerates all possible path sites for each wirelength in an architecture and an occupation probability function that assigns a probability to each of these paths to be occupied by a wire. In this paper, we apply a generating polynomial technique to derive complete expressions for site density functions which take effects of layout region aspect ratio and the presence of obstacles into account. The effect of an obstacle is separated into two parts: the terminal redistribution effect and the blockage effect. The layout region aspect ratio and the obstacle area are observed to have a much larger effect on the wirelength distribution than the obstacle's aspect ratio and location. Accordingly, we suggest that these two parameters be included as indices of lookup tables in wireload models. Our results apply to a priori wirelength estimation schemes in chip planning tools to improve parasitic estimation accuracy and timing closure; this is particularly relevant for system-on-chip designs where IP blocks are combined with row-based layout.

Efficient and accurate interconnect estimation is crucial to design convergence. With System-on-Chip design, IP blocks form routing obstacles that cannot be accounted for by existing a priori wirelength estimations. In this paper, we identify two distinct effects of obstacles on interconnection length: (i) changes due to the redistribution of interconnect terminals and (ii) detours that have to be made around the obstacles. Theoretical expressions of both effects for point-to-point nets with a single obstacle are derived and compared to experimental observations. We also experimentally assess these effects for multi-terminal interconnections and in the presence of multiple obstacles. We single out cases where the effects are additive, which suggests the use of lookup tables and equivalent blockage relations. Our results are applicable in chip planning tools, where they enable improved accounting for obstacles in a priori wirelength estimation schemes.

In floorplanning of typical VLSI design, some modules are required to satisfy some placement constraints in the final packing. Boudary Constraint is one kind of those placement constraints to pack some modules along one of the four sides: on the left, on the right, at the bottom or at the top of the final floorplan. We implement the boundary constraint algorithm for general floorplan by extending the Corner Block List (CBL) - a new efficient topology representation for non-slicing floorplan. Our contribution is to find the necessary and sufficient characterization of the modules along the boundary represented by Corner Block List. So that we can check the boundary constraints by scanning the intermediate solutions in the linear time during the simulated annealing process and fix the corner block list in case the constraints are violated. The experiment results are demonstrated by several examples of MCNC benchmarks and the performance is remarkable.

The abutment constraint problem is one of the common constraints in practice to favor the transmission of data between blocks. Based on Corner Block List(CBL), a new algorithm to deal with abutment constraints is developed in this paper. We can obtain the abutment information by scanning the intermediate solutions represented by CBL in linear time during the simulated annealing process and fix the CBL in case the constraints are violated. Based on this algorithm, a new method to deal with L-shaped/T-shaped blocks is proposed. The shape flexibility of the soft blocks and the rotation and reflection of L-shaped/T-shaped blocks are exploited to obtain a tight packing. The experiment results are demonstrated by some benchmark data and the performance shows effectiveness of the proposed method.

This paper deals with area minimization of power distribution networks for VLSIs. A new algorithm based on efficient nonlinear programming techniques is presented to solve this problem. Experimental results prove that this algorithm has achieved the objectives of minimizing the area of power/ground networks with higher speeds.

In this paper we extend the O-tree approach to handle rectilinear blocks. First we explore the properties of L-shaped blocks, then decompose rectilinear blocks into a set of sub-L-shaped-blocks. The properties of L-shaped blocks can be applied to general recti?linear blocks. In order to explore the optimal search thoroughly, we generate four direction O-trees. A heuristic optimization algorithm based on the four direction O-trees produces very good experiment results.

Floorplan representations are a fundamental issue in designing floorplan algorithms. In this paper, we first derive the exact number of configurations of mosaic floorplans and slicing floorplans. We then present two non-redundant representations: a twin binary tree structure for mosaic floorplans and a slicing ordered tree for slicing floorplans. Finally, the relations between the state-of-the-art floorplan representations are discussed and their efficiency is explored.

A Non-Slicing floorplanning algorithm based on CBL[1], corner block list, was presented recently. It can represent non-slicing floorplans without empty rooms. In this paper, we propose an extended corner block list structure, ECBLl, to represent general non-slicing floorplans, which may include empty rooms. By setting l×[1..3], where l is the extending ratio, our algorithm can translate a topological floorplan to its corresponding placement in O(n) time, where n is the number of blocks. Also, based on the optimum solution theorem of bounded-sliceline grid in [2], we proved that the solution space of ECBLn contains the optimum block placement, which has the minimum area. Experimental results on MCNC benchmarks show promising performance with 7% improvement in wire length and 2% decrease in dead space over algorithms based on CBL. Meanwhile, compared with other algorithms, our algorithm can get better results with less runtime.

We present an ordered tree (O tree) structure to represent nonslicing floorplans. The O tree uses only n(2+[lg n]) bits for a floorplan of n rectangular blocks. We define an admissible placement as a compacted placement in both x and y directions. For each admissible placement, we can find an O-tree representation. We show that the number of possible O-tree combinations is O(n!2/sup 2n-2//n/sup l.5/). This is very concise compared to a sequence pair representation that has O((n!)/sup 2/) combinations. The approximate ratio of sequence pair and O-tree combinations is O(n/sup 2/(n/4e)/sup n/). The complexity of O tree is even smaller than a binary tree structure for slicing floorplan that has O(n!2/sup 5n-3//n/sup 1.5/) combinations. Given an O tree, it takes only linear time to construct the placement and its constraint graph. We have developed a deterministic floorplanning algorithm utilizing the structure of O tree. Empirical results on MCNC (www.mcnc.org) benchmarks show promising performance with average 16% improvement in wire length and 1% less dead space over previous central processing unit (CPU) intensive cluster refinement method.

In this paper we use a segmented Chebyshev orthongonal polynomial expansion approach to approximate amplitude and phase response for RLC interconnect simulation. This method has been shown to be efficient in reducing frequency sampling point number or expansion order. Experiments also show that the number of sampling points is not necessarily dependent on the interconnect circuit size, which makes possible large network simulation. Additionally, because of the smoothing-effect of the atan function in evaluation, the phase response, which has major impact on the transient edge of output response, can be easily approximated. Experiments show the proposed simulation approach achieves 30-50 times speed-up over spice3f4. 1.

Timing convergence problem arises when the estimations made during logic synthesis can not be met during physical design. In this paper, an efficient rewiring engine is proposed to explore maximal freedom after placement. The most important feature of this approach is that the existing placement solution is left intact throughout the optimization. A linear time algorithm is proposed to detect functional symmetries in the Boolean network and is used as the basis for rewiring. Integration with an existing gate sizing algorithm further proves the effectiveness of our technique. Experimental results are very promising.

The ordered tree (O-tree) representation has recently gained much interest in layout design automation. Different from previous topological representations of non-slicing floorplans, the O-tree representation is simpler, needs linear computation effort to generate a corresponding layout, and exhibits a smaller upper-bound of possible configurations. This paper addresses the problem of handling symmetry constraints in the context of the O-tree representation. This problem arises in analog placements, where symmetry is often used to match layout-induced parasitics and to balance thermal couplings in differential circuits. The good performance of our placement tool dealing with several analog designs taken from industry proves the effectiveness of our technique.

In this paper, a corner block list-a new efficient topological representation for non-slicing floorplan is proposed with applications to VLSI floorplan and building block placement. Given a corner block list, it takes only linear time to construct the floorplan. Unlike the O-tree structure, which determines the exact floorplan based on given block sizes, corner block list defines the floorplan independent of the block sizes. Thus, the structure is better suited for floorplan optimization with various size configurations of each block. Based on this new structure and the simulated annealing technique, an efficient floorplan algorithm is given. Soft blocks and the aspect ratio of the chip are taken into account in the simulated annealing process. The experimental results demonstrate the algorithm is quite promising.

We present a new realizable reduced order modeling technique for RLC interconnect trees. Both lumped and distributed wire models can be used with this technique. Provable stability is achieved by using Hurwitz polynomials. Moment computation process is avoided but moments can still be matched implicitly. In experiments, the proposed Hurwitz three-pole model can accurately and efficiently capture inductive effect for both near end and far end nodes.

Recently, a deterministic algorithm based on the O-tree repre-sentation has been proposed. This method generates excellent layout results on MCNC test cases with O(n3) complexity, where n is the number of blocks. In this paper, we reduce the complexity of the deterministic algorithm to O(n2). Experimental results indicate our algorithm maintains the high quality of the deterministic algorithm at a fraction of the CPU time. 1.

This paper presents a performance-driven I/O pin routing algorithm with special consideration of wire uniformity. First, a topological routing based on a min-cost max-flow algorithm is proposed. In this phase, an exponential weight function is used to guide the flow distribution which is very helpful in distributing wires, globally and uniformly, on the whole routing area. Then a physical routing phase is applied to implement one-to-one connection between chip pads and I/O pins, which focuses on the wire uniformity of the fanout area nearby the periphery of chip pads. Finally, a balanced position based wire polishing approach is proposed to further improve the local wire uniformity which tries to modify each wire into a smooth curve instead of broken line while satisfying the specified design rules such as wire-wire pitch and wire-pin pitch. A routing cost function is adequately defined to guide the whole routing process which leads to a good trade-off between wire uniformity and wire length. The algorithm has been implemented and tested on up to 10-ring 600-pin PGA and the experimental results are very promising.

We present an ordered tree, O-tree, structure to represent non-slicing floorplans. The O-tree uses only n (2 + ⎡lg n⎤) bits for a floorplan of n rectangular blocks. We define an admissible placement as a compacted placement in both x and y direction. For each admissible placement, we can find an O-tree representation. We show that the number of possible O-tree combinations is O(n! 2 2n- 2 / n 1.5). This is very concise compared to a sequence pair representation which has O((n!) 2) combinations. The approximate ratio of sequence pair and Otree combinations is O(n 2 (n /4e) n). The complexity of O-tree is even smaller than a binary tree structure for slicing floorplan which has O(n! 2 5n-3 /n 1.5) combinations. Given an O-tree, it takes only linear time to construct the placement and its constraint graph. We have developed a deterministic floorplanning algorithm utilizing the structure of O-tree. Empirical results on MCNC benchmarks show promising performance with average 16 % improvement in wire length, and 1 % less in dead space over previous CPU-intensive cluster refinement method. 1.

A new category of moments-Amplitude and Phase moments (AP moments) are introduced for RLC interconnect delay estimation. We show that there are tight relationships between AP moments, circuit moments and central moments. The first order AP moment represents the Elmore delay while the higher order AP moments can be used to represent the error between the Elmore delay and the exact 50% delay from the view of gain and phase-shift variation. With the help of the physical meaning revealed by the AP moments, a closed-form 50% delay model-AP delay model is proposed for RLC interconnect delay estimation in terms of the first four AP moments. We also propose a new two-pole model (AP two-pole model) by matching the first two phase moments of the transfer function. The AP two-pole model can be used for more generally timing parameters estimation. The input signal's impact on delay estimation can be incorporated into these two delay models by simply combining the input signal's AP moments with the transfer function's AP moments. In our experiments these two models show significant accuracy improvement over the Elmore delay model.

This paper presents new results in the area of timing optimization for multisource nets. The augmented RC-diameter (ARD) is suggested as a natural and practical performance measure and a linear time algorithm for computing the ARD of a multisource net is presented. Building on the ARD measure, we characterize the multisource optimization problem in terms of operations on piece-wise linear functions. This characterization is then used to develop an algorithm for optimal repeater insertion: for a given multisource topology the algorithm efficiently identifies an optimal assignment of repeaters to prescribed insertion points under the "min cost timing feasible" problem formulation. The algorithm has been implemented and computational results demonstrate the viability of the approach.

With the recent advent of deep sub-micron technology and new packaging schemes such as multichip modules, integrated circuit components are often not rectangular. Most existing block placement approaches, however, only deal with rectangular blocks, resulting in inefficient area utilization. New approaches which can handle arbitrarily shaped blocks are essential to achieve high-performance design. In this paper, we extend the sequence-pair approach for rectangular block placement to arbitrarily sized and shaped rectilinear blocks. Experimental results show that our algorithm achieves results with excellent area utilization.

In this paper, we present an extension of moment computation to 2-port circuits. Our formulas are applicable to both transfer function moments and driving-point admittance moments. Given the input admittances, output admittances, and transfer functions of two 2-ports, our formulas compute the input admittance, output admittance, and transfer function when these 2-ports are combined either in parallel or in series. A nice conclusion of our work is the discovery our formulas form an elegant framework integrating the results from two classical papers, Rubinstein et al. & O'Brien and Savarino, for computing the Elmore delay and driving-point admittance moments in RC trees.

With the recent advent of deep sub-micron technology and new packaging schemes such as Multi-Chip Modules(MCMs), integrated circuit components are often not rectangular. Most existing block placement approaches, however, only deal with rectangular blocks, resulting in inefficient area utilization. New approaches which can handle arbitrarily shaped blocks are essential to achieve high performance design. In this paper, we present an approach extending the sequence-pair approach for rectangular block placement to arbitrarily sized and shaped rectilinear blocks. Experimental results show that our algorithm achieves results with excellent area utilization.

We present a dynamic architecture for field programmable gate array (FPGA)-based computing systems with the introduction of dynamic field-programmable interconnection devices. The central principle of this new architecture is based on the concept of time-sharing, which we use to efficiently exploit the potential communication bandwidth of interconnection resources. This new architecture not only releases FPGA pin limitation to some degree, but also greatly increases the routability of interconnection networks, resulting in higher overall performance of FPGA-based systems.

When designing integrated circuits, sub-components rarely end up being perfectly rectangular. However, currently most block-placers only consider rectangular components, resulting in inefficient area utilization. We propose a placement tool that allows arbitrarily sized and shaped convex components. It extends the rectangle-packing method proposed by Kajitani. We describe the methods used to create the placement and give some performance results.

In this paper we present a new layout-driven timing model based on asymptotic waveform evaluation (AWE) for improved timing analysis during routing. Our model enables the bottom-up computation of interconnect tree moments, and can be easily integrated with such a global router. Such an integration achieves incremental layout optimization, i.e., timing analysis and routing are tightly coupled, with feedback between them. This achieved incremental layout optimization, through our innovative timing model, is the main contribution of this work.

Network flow approaches have been used for partitioning with successin the past. However, most of them can not deal with size constraintsdirectly in partitioning. Instead, they incorporate the sizeconstraints implicitly in the objective function. This paper presentsa new network flow approach for partitioning circuits into treehierarchies. We formulate a linear program for the hierarchicaltree partitioning problem by spreading metrics proposed in [Divide-and-conquer approximation algorithms via spreading metrics, Fast approximate graph partitioning algorithms].The size constraints in partitioning can be formulated directly aslinear constraints. Motivated by the duality between the linear programsfor partitioning and network flow problems, we devise aheuristic algorithm based on network flow and spreading metriccomputations. Experimental results demonstrate that the new algorithmcan generate better solutions for MCNC benchmarks.

This paper presents new results in the area of timingoptimization for multi-source nets. The Augmented RC-Diameter (ARD) is proposed as a natural and practical performance metric and a linear time algorithm for computingthe ARD of a multi-source net is presented. Building onthe ARD, an algorithm for optimal repeater insertion is presented: for a given multi-source topology the algorithm efficiently identifies an optimal assignment of repeaters to prescribed insertion points under the min cost timing feasibleproblem formulation. The algorithm has been implementedand preliminary experimental results are promising.

We propose an iterative optimization approach for mixedmacro-cell and standard-cell placement, which minimizes the chipsize and interconnection wire length at the same time. We present abranch-and-bound algorithm which efficiently searches for the optimalsolution by evaluating all of the possible configurations on theselected cluster to minimize the gap distance between the ceilingand the floor. A virtual grid and permutation order are generateddynamically to eliminate redundant branches, which was the causeof much higher complexity in other approaches. Experimentalresults on the MCNC benchmark circuits show that the algorithmachieves very competitive results to manual design.

In this paper, we propose an efficient timing-driven global router, TIGER, for gate array and standard cell layout design. Unlike other conventional global routing techniques, interconnection delays are modeled and included during the routing and rerouting process in order to minimize the maximum channel density for gate arrays or the total track number for standard cells, as well as to satisfy the timing constraints in TIGER. The timing-driven global routing problem is formulated as a multiterminal, multicommodity network flow problem with integer flows under additional timing constraints. Two novel performance-driven Steiner tree algorithms are proposed to generate the initial global routing trees. A critical-path-based timing analysis method is used to guarantee the satisfaction of timing constraints. Experimental results based on MCNC (ISCAS) benchmarks show that TIGER can obtain better results than or comparable results with TimberWolf 5.6.

This paper addresses the problem of partitioning a circuit into a tree hierarchy with an objective of minimizing a global interconnection cost.An efficient and effective algorithm is necessary when the circuit is huge and the tree has many levels of hierarchy.We propose a heuristic algorithm for improving a partition with respect to a given tree structure.The algorithm utilizes the tree hierarchy as an efficient mechanism for iterative improvement.We also extend the tree hierarchy to apply a multi-phase partitioning approach.Experimental results show that the algorithm significantly improves the initial partitions produced by multiway partitioning and by recursive partitioning.

This paper addresses the linear placement problem by using a spectral approach.It has been demonstrated that, by giving a more a c curate representation of the linear placement problem, a linear objective function yields better placement quality in terms of wire length than a quadratic objective function as in the eigenvector approach [4][11][6].On the other hand, the quadratic objective function has an advantage in that it tends to place c omponents more s p arsely than the linear objective function, resulting in a continuous solution closer to a physically feasible discrete solution.In this paper, we propose an -order objective function to capture the strengths of both the linear and quadratic objective functions.We demonstrate that our approach yields improved s p e ctral placements.We also present a bottom-up clustering algorithm which iteratively collapses pairs of nodes in a graph using local and global connectivity information, where the global connectivity information is derived f r om the clustering property of the eigenvector approach.The eect of our new spectral linear placement and clustering approach is demonstrated o n b enchmark circuits from MCNC.

We present new algorithms for construction of performance driven Rectilinear Steiner Trees under the Elmore delay model.Our algorithms represent a departure f r om previous approaches in that we derive an explicit area/delay tradeo curve.We achieve this goal by limiting the solution space to the set of topologies induced b y a p ermutation on the sinks of the net.This constraint allows ecient identi cation of optimal solutions while still providing a rich solution space.We also incorporate simultaneous wire sizing.Our technique consistently p r o duces topologies equalling the performance o f previous approaches with substantially less area overhead.

Pseudo-exhaustive testing (PET) offers a simple solution to testing complex circuits and systems [12].However, PET suffers long testing time for test generation and high area overhead of test hardware.The pipelined pseudo-exhaustive testing (PPET) achieves fast testing time with high fault coverage by pipelining test vectors and test responses among partitioned circuit segments [15].To reduce hardware overhead in PPET, a novel approach for implementing area-efficient PPET is presented.Circuit partitioning with retiming is used to convert designs for PPET.Experimental results show that this approach exhibits an average of 20% area reduction over non-retimed testable circuits.Our algorithm offers high utilization of existing flip-flops (FFs) and provides a framework for further performance optimization.

We present an algorithm for simultaneously finding a rectilinear Steiner tree T and buffer insertion points into T. The objective of the algorithm is to minimize a cost function (e.g., total area or power) subject to given timing constraints on the sinks of the net. An interesting side-effect of our approach is that we are able to derive an entire cost/delay tradeoff curve for added flexibility. The solutions produced by the algorithm are optimal subject to the constraint that the routing topology be induced by a permutation on the sinks of the net. We show that high quality sink permutations can be derived from a given routing structure such as the minimum spanning tree. This derivation provides an error bound on the minimum area solution induced by the permutation. The effectiveness of our algorithm is demonstrated experimentally.

The global routing problem is formulated as a multiterminal, multicommodity flow problem with integer flows, An E-optimal 2-terminal multicommodity flow algorithm with fractional flows is extended to handle multiterminal commodities, Our adaptation of this network flow algorithm seeks to maximize overall routability by minimizing edge congestion as opposed to conventional techniques which usually seek to minimize wire length. We show that under certain conditions, our approach derives an approximate optimal solution. We apply a randomized rounding procedure to derive an integer solution from the fractional multicommodity flow solution. Experimental results demonstrate that this network flow algorithm can be realistically used to route industrial sized circuits with reduced congestion.

In high-performance chip design, the problem of net matching is often critical for achieving correct circuit performance. We adopt a conservative design, to route all matched nets with identical topologies and equal wire lengths to achieve zero skew. The problem is formulated as a variant of the D-dimensional Steiner tree problem. We propose a two-stage solution. The first stage uses an iterative improvement strategy to generate the Steiner tree topology for all the nets. The second stage places the nodes using one of two methods. The first approach expresses the optimal Steiner node positions as a linear programming solution, with average computational complexity O(n/sup 2/m/sup 2/), where n is the number of nets and m is the number of pins. Improved efficiency is achieved under the other approach by transforming the Manhattan metric to an l/sub /spl infin// norm using a 45/spl deg/ rotation of the solution space. The norm is then approximated by either an l/sub /spl lambda// norm, for suitably large values of /spl lambda/, or an exponential "penalty" function. The solution space in both approaches becomes strictly convex, allowing us to apply a greedy approach which converges to an optimal solution with great efficiency, leading to a dramatic speed-up versus the linear programming approach.

This paper presents a new wire length estimation technique for row-based design. Noting that the local topological structure of the network is often reflected in the local structure of the placement, we present a technique of topological analysis of the network, in which the local structure of the network is characterized by a growing sequence of multilevel neighborhoods. By assuming a pointwise independent branching process, we derive equations for the probability density of multilevel neighborhoods. The wire length distribution is found by solving these equations. For thirteen industrial circuits tested, this technique gives an average of 15.1% estimation accuracy.

In this paper, we propose a heuristic algorithm for a given topology of a multisource multisink bus to reduce the signal delay time. The algorithm minimizes the delay by inserting buffers into the candidate locations and sizing the buffers. When compared with the traditional method of source driver sizing, experiments show up to 7.2%, 20.7%, and 29.6% improvement in delay for 2.0, 0.5, and 0.3 /spl mu/m technologies, respectively.

No abstract available.

Field programmable gate arrays (FPGAs) have formed the basis for high performance and affordable computing systems. FPGA based logic simulators can emulate complex logic designs at clock speeds of several orders of magnitude faster than even accelerated software simulators, while FPGA based prototyping systems provide great flexibility in rapid prototyping and system verification. However, besides FPGA pin limitation, existing FPGA based systems also meet the problem of improving the routability of interconnect networks in the architecture design. We present a dynamic architecture for FPGA based computing systems with field programmable gate arrays and dynamic field programmable interconnect devices. Our architecture has advantages on FPGA gate utilization as well as on routability of interconnect networks. The central principle of this new architecture as based on the concept of efficiently exploiting the potential communication bandwidth of interconnect resources. By dynamically reconfiguring the interconnect networks, FPGA pins and interconnect resources are efficiently reused. In this way, this new architecture not only overcomes FPGA pin limitations, but also greatly increases the routability of interconnect networks, resulting in higher overall performance of FPGA based systems.

We propose a unified solution to both linear placement and partitioning. Our approach combines the well-known eigenvector optimization method with the recursive max-flow min-cut method. A linearized eigenvector method is proposed to improve the linear placement. A hypergraph maxflow algorithm is then adopted to efficiently find the max-flow min-cut. In our unified approach, the max-flow min-cut provides an optimal ordered partition subject to the given seeds and the eigenvector placement provides heuristic information for seed selection. Experimental results on MCNC benchmarks show that our approach is superior to other methods for both linear placement and partitioning problems. On average, our approach yields an improvement of 45.1% over eigenvector approach in terms of total wire length, and yields an improvement of 26.9% over PARABOLI[6] in terms of cut size.

We present efficient, optimal algorithms for timing optimization by discrete wire sizing and buffer insertion. Our algorithms are able to minimize dynamic power dissipation subject to given timing constraints. In addition, we compute the complete power-delay tradeoff curve for added flexibility. We extend our algorithm to take into account the effect of signal slew on buffer delay which can contribute substantially to overall delay. The effectiveness of these methods is demonstrated experimentally.

In this paper, a Fiduccia-Mattheyses (FM) algorithm incorporating a novel initial partition generating method is proposed. The proposed algorithm applies to both bipartitioning and multi-way partitioning problems with or without replication. The initial partition generating method is based on a gradient descent algorithm. On partitioning without replication, our algorithm achieves an average of 17% improvement over the analytical method, PARABOLI, on bipartitioning, 10% better than Primal-Dual method on 4-way partitioning and 51% better than net-based method. On partitioning allowing replication, our algorithm achieves an average of 23% improvement over the directed Fiduccia-Mattheyses algorithm on Replication Graph (FMRG) method on bipartitioning.

We address in this paper the fanout tree problem introduced by Berman, et. al., that is using buffer fanout trees to reduce the fanout delay in a technology mapped network. We construct two basic types of fanout trees and provide simple techniques to manipulate them for further delay reduction. These trees are inserted along critical paths throughout the network. We also perform gate-transformation, that is substitution of a gates of equivalent logical functions, if the technology permits. Experimental results show improvement over Touati's LT-tree construction technique.

In this paper, we consider the problem of decomposing a Finite State Machine (FSM) into communicating FSMs to minimize the number of inputs/outputs. We propose an FSM decomposition procedure based on partitioning the set of transitions that describes the behavior of an FSM. An extended FM-based partitioning algorithm is applied for transition partitioning. We also devise a state output encoding technique to further reduce the number of interconnections between the FSMs required for communication. Experimental results for MCNC benchmarks show that our algorithm has favorable results over circuit partitioning algorithms on the netlist level.

Given a system represented at gate level, we propose an algorithm mapping the design into the minimum number of FPGA's for logic emulation. We first devise a Local Ratio-cut clustering scheme to reduce the circuit complexity. Then a Set Covering partitioning approach, utilizing the paradigm of Espresso II, is proposed as an alternative to the widely adopted recursive partitioning paradigm. Experimental results have shown that our approach achieved significant improvement with much shorter run times compared to the recursive Fiduccia-Mattheyses approach on large designs. For instance, on a benchmark of 160 K gates and 90 K nets, we reduced the number of FPGA's required and the run time by 41 and 86%, respectively.>

Graph partitioning is crucial in multiple-chip design, floorplanning and mapping large logic networks into multiple FPGA's. Replication logic can be used to improve the partitioning. Given a network G with only two-pin nets and a pair of nodes s and t to be separated, we introduce a replication graph and an O(mn log(n/sup 2//m)) algorithm for optimum partitioning with replication and without size constraints, where m and n denote the number of nets and the number of nodes in G, respectively. In VLSI designs, each partition has size constraints and the given network contains multiple-pin nets. A heuristic extension is adopted to construct replication graphs with multiple-pin nets. Then we use a directed Fiduccia-Mattheyses algorithm in the constructed replication graph to solve the replication cut problem with size constraints.>

We describe a new linear programming (LP)-based hierarchical pitchmatching method. With a simplified treatment of the intercell constraints, the size of the LP problems is significantly reduced as compared to the best known results. In particular, the pitchmatching problem is decomposed into independent subproblems by exploiting the layout slicing structure. Each subproblem is further "folded" to reduce the LP problem size. We prove that the new method generates smaller LP problem than the previously best known approach. Experimental data show that the LP problem size can be 10 times smaller.>

Recently, Johnson et al. [1989] presented an excellent comparison of simulated annealing and Kernighan-Lin algorithms. However, their test beds were limited to random and geometric graphs. We present a complete evaluation by adding real circuitry into the test beds. A two-level partitioning algorithm called the primal-dual algorithm is also incorporated for comparison. We show that at least 500 runs are necessary to demonstrate the performance of the Fiduccia-Mattheyses algorithm, whereas traditional way of evaluation tends to underestimate. Nevertheless, our new results show that for two-way partitioning on real circuits, the primal-dual algorithm is, in general, a better choice than both the Fiduccia-Mattheyses algorithm and the simulated annealing algorithm. This conclusion is more likely to hold when the primal-dual algorithm is switched to a simpler mode.>

We present a new clustering metric, based on a random graph model and a ratio cut concept. The minimization of the proposed clustering cost can be transformed to a uniform multicommodity flow problem by adding artificial weight functions, which can be solved by a multicommodity flow-based algorithm with high complexity. We devise a probabilistic flow injection approach which drastically reduces the complexity of the flow-based algorithm. Experimental results show that this algorithm generates promising results with respect to the proposed metric.>

We propose a simulated annealing based zero-skew clock net construction algorithm that works in any routing spaces, from Manhattan to Euclidean, with the added flexibility of optimizing either the wire length or the propagation delay. We first devise an O(log n) tree grafting perturbation function to construct a zero-skew clock tree under the Elmore delay model. This tree grafting scheme is able to explore the entire solution space asymptotically. A Gauss-Seidel iteration procedure is then applied to optimize the Steiner point positions. Experimental results have shown that our algorithm can achieve substantial delay reduction and encouraging wire length minimization compared to previous works.>

Future computers will need to incorporate the parallelism of optical interconnections in order to achieve projected performance within reasonable size, power and speed constraints. This is necessary since optical interconnections have advantages in size, power, and speed over "long" distance communication. These features make optical interconnects ideal for inter-module connections in multichip module systems. Free-space optical interconnection can be one form of optical interconnections. Computer generated holograms (CGHs) are extremely attractive optical components for use in free space optical interconnections due to their ability to be computer designed. We will show that the fabrication limitations of CGHs for general interconnection networks require the need for placement algorithms for large processing element (PEs) arrays. In this paper, we will demonstrate that these fundamental CGH fabrication limitations greatly influence the computer aided design of optoelectronic interconnect networks that utilize CGHs for optical interconnections. Specifically, we show that the minimum feature size directly affects the logical placement of processing elements. Various physical models for free-space optical interconnects in parallel optoelectronic MCM systems are then identified from which we derive several logical models for analysis. We then analyze these cases and present algorithms to solve the associated layout problems. Design examples are given to illustrate the benefits of utilizing these placement algorithms in real optoelectronic interconnection networks.>

Abstract|Given a huge system represented at gate level, we propose an algorithm mapping the design into the minimum number of FPGAs for logic emulation. We rst devise a Local Ratio-cut clustering scheme to reduce the circuit complexity. Then a Set Covering partitioning approach, utilizing the paradigm of Espresso II, is proposed to replace the widely adopted recursive partitioning paradigm. Experimental results show that our approach achieves signi cant improvement inamuch shorter run time compared to the recursive Fiduccia-Mattheyses approach on large designs. For example, on a benchmark of 160K gates and 90K nets, we reduced the number of FPGAs required by 29 % and reduced the run time by 78%. 1

Abstract| W e propose an ecient performancedriven two-way partitioning algorithm to take i n to account clock cycle period and latency with retiming.W e model the problem with a Quadratic Programming formulation to minimize the crossing edge coun t with nonlinear timing constraints.By using Lagrangian Approach on Modular Partitioning (LAMP), w e merge nonlinear constraints to the objective function.The problem is then decomposed into primal and dual two subprograms.The primal and dual problems are solv ed by a Quadratic Boolean Programming approac h and by a subgradient method using cycle mean method, respectively.Experimental results show our algorithm achieves an average of 23.25% clock cycle period and 19.54% latency reductions compared to the Fiduccia-Mattheyses algorithm.In terms of the a verage number of the crossing edges, our results are only 1.85% more.1 Problem F orm ulation A synchronous digital system can be represented by a directed graph, G(V = R [ C; E); where R is the set of register nodes and C is the set of combinational block nodes.Each n o d e i has an associated size s i and delay d i .E is the set of directed edges which correspond to signal ow in the system.Each edge (i; j) is associated with an attribute c i;j , which denotes the number of the interconnections from nodes i to j.A t w o-way partition P. The capacity limits of these modules are denoted by S 1 and S 2 , respectively.An edge (i; j) i s a crossing edge of P if node i and node j are in dierent subsets V 1 and V 2 .W e assume register nodes and non-crossing edges are of zero delay.The crossing edges have a n i n termodule delay determined by technologies. Assum ptionsW e make the following assumptions in this paper: 1.The intermodule delay is less than the desired clock period, T. 2. Data ow are ne-grained in nature.Although we assume the combinational blocks are negrained, some structures, e.g. the delays on crossing edges, are inherently coarse-grained and cannot be split.

Multi-chip module (MCM) technology has become an important means to package high performance systems. An important task during the packaging process is to check for possible open, short, and high resistance faults in the wiring networks of the bare MCM substrates, which is called substrate testing. After examining several substrate testing methodologies, we find that multi-probe or k-probe testers are cost-effective for substrate testing. However, the testing speed of this method is not high; hence, we focus on improving the throughput by reducing the number of tests and by deriving good probe routes. For test size reduction, we propose a routing tree model to capture the wiring structure of a given net; then by taking advantage of the routing tree, we generate a minimum number of tests while ensuring complete open fault coverage. Our algorithm reduces the number of tests by up to 50% compared to that of previous approaches. Given a routing tree with its node degree bounded by a constant, our test generation algorithm runs in linear time with respect to the number of leaves of the tree. For probe route scheduling, we observe that in order to obtain a balanced and efficient scheduling, the routes of different probes must be considered simultaneously, which motivates our Multi-Dimensional Traveling Salesman Problem (MDTSP) formulation. Our package has been installed on existing substrate testers and has achieved encouraging results.>

Multiple-way partitioning is an important extension of two-way partitioning as it provides a more natural and direct model for many partitioning applications. In this paper, we discuss several objective functions derived from such an extension and propose an iterative improvement algorithm to solve the multiple-way partitioning problem. The algorithm proceeds in three phases. The first phase employs a recursive ratio-cut scheme to group highly connected subcircuits into clusters. The second phase performs iterative improvement on the clustered circuit using a Dew net-based move model and a Primal-Dual refinement procedure. The third phase is the same as the second phase except that the iterative improvement is done on the original circuit. Experiments show good results in all tested cases.>

A block-oriented programmable design with switching network interconnect is proposed for fast turn-around, low manufacturing cost, and layout-independent high-speed systems. We introduce the architecture and investigate the constraints and properties originated from the architecture. We show that routability is the most crucial concern for a successful design, and propose objective functions as well as algorithms for switching network optimization. The mapping for the circuits is performed by partitioning, placement, and routing using a maximum matching method. The integration of the whole system demonstrates excellent results in terms of circuit usage.>

An approach toward ath-oriented tirnii -driven place-{ t ment is proposed.We rst transform the p acement with timing constraints to a Lagrange problem, A primal-dual a.ppro~IS USed to find the optimrd relative module locatlons.In each primal dual iteration, the primal problem is solved by a piecewise linear resistive network method, whale the dual process is used to update the Lagrange multiplier.The sparsity of the piecewiee liiear resistive network is exploited to obt airt dramatic improvement on the efficiency of the calculation.Up to 22.o% of clock cycle reduction was observed for Primary2 test case.1

This paper presents two performance-driven Steiner tree algorithms or global routing which consider the

In this paper, we propose an eflicient timing-driven global routing algorithm.Unlike other conventional global routing techniques, interconnection delays

We describe a new linear programming (LP)-based hierarchical pitchmatching method.Whh a simplified treatment of the intercell constraints, the size of the LP problems is significantly smaller than the best known methods.In particular, the pitchmatching problem is decomposed into independent subproblems by the natural slicing structure in layout.Each subproblem is folded further to reduce the LP problem size.Experiments show that the LP problem size can be 10 times smaller than the best known result.

Net matching is often critical for the correct performance of a circuit. We adopt a conservative design to route all matched nets with identical topology and equal wire lengths in order to achieve zero skew. We formulate the problem as one special D-dimensional Steiner tree problem. An iterative improvement strategy is used to generate the Steiner tree topology. We provide a more efficient method of computing the optimal Steiner point positions over the linear programming method involving a 45-degree rotation of the domain, and approximation matrices.

We propose a novel paradigm for two-way circuit partitioning which minimizes the clock cycle. The replication technique is suggested for feedback loops to minimize the impacts of intermodule delays and the crossing edges when necessary. A flow timing cut is devised to produce partitions which can be guaranteed to achieve clock cycles equal to their lower bound with respect to the partitions using retiming. When the clock cycle optimization is the major objective and feedback loop sizes are not large, we propose an efficient, easy to implement algorithm which still guarantees achieving the lower bound clock cycle with respect to its partition. Experimental results have shown that our algorithms can achieve an average of 15% clock cycle time reduction compared to the best retimed results produced by 20 runs on each test case using a Fiduccia-Mattheyses algorithm.

The k-probe testing methodology is an effective approach to detect open and short faults in MCM substrates. An algorithm which generates the minimum number of tests for complete open fault coverage is proposed. For k equals two, the algorithm is able to reduce the test size by up to 50% compared with that generated by an ordinary approach. A multidimensional traveling salesman problem formulation is developed to optimize probe routes. The approach has been tested on substrate testers and has achieved excellent results.>

Circuit clustering, which plays a fundamental role in hierarchical designs, is discussed. Identifying strongly connected components in the circuits can significantly reduce the complexity of the design and improve the performance of the design process. However, there has not been a clear objective function for circuit clustering. A clustering metric based on the random graph model and the ratio cust concept is presented. A probabilistic, multicommodity flow based algorithm is proposed and tested under the clustering metric. Experimental results show that this algorithm generates promising results with respect to the proposed metric. Extensions and directions for future work are also proposed.>

Abstract The work proposes several partitioning criteria, i.e, the flux cutA, the flux cutB, the cost ratio cut, and one generalized minimum cut. The flux cutBis an extension of the flux cutA. The cost ratio cut generates an optimal partitioning for a linear placement problem. The generalized minimum cut uses a cost function related to a polynomial function of the sizes of two partitioned subsets. A high‐order polynomial function tends to generate partitions such that the partitioned subsets equal specified sizes. A simplified case is the ratio cut that is shown to derive the clustering structure of the network. The physical meaning of the cuts is described. The partitioning problems are shown to be strongly related to the communication problems. Several network flow models are constructed. We illustrate relations between the maximum flow solutions and the minimum partitionings. We use linear programming to formulate the proposed maximum flow problems. The duality techniques of linear programming are utilized to derive a relation to the optimal partition solution. Thus, we have identified the cases when the optimal partition solutions can be determined in polynomial time.

The compaction of IC layouts subjected to conditional spacing rules in multiple-level metal technology is addressed. The constraints imposed by conditional rules make the automatic compaction of layout much more difficult than when the usual minimum separation rules are applied. To solve the problem, each conditional spacing rule is formulated with a set of arcs in the constraint graph representation. It is proven that finding the optimal solution under one bridge rule is NP-complete. A graph-theory method of compaction which, by reducing the problem size, can efficiently obtain an optimal solution is proposed.>

A channel compaction algorithm incorporating via minimization and lateral via shifting is discussed. Bump propagation from the center of vias is the crucial phenomenon preventing compaction results from attaining the lower bound. Via minimization reduces the sources of the bumps, and lateral via shifting splits the critical paths which dominate the height of the channel. The authors adopt a contour-following approach as the basic operation to compact and straighten each wire. The sequence of the wires is determined by a topological sorting algorithm which also resolves any ordering conflicts by splitting the wires. The authors show the effectiveness of via minimization and shifting in reducing channel routing area. An improvement of up to 22.9% over one-dimensional compaction has been observed. Experiments on various solutions of Deutsch's difficult example indicate no significant relationship between the compacted channel height and the number of tracks in the routing solution.>

The global routing problem is formulated as a multiterminal, multicommodity flow problem with integer flows.An epsilon bound 2-terminal multicommodity flow algorithm with fractional flows is adapted to handle multitermirtal commodities.We show that under certain conditions, our approach derives an approximate optimal solution.The experimental results with benchmark data are quite promising.

This paper presents a discussion of methods to solve multiple way partitioning problems under three different objective functions.A multicommodity flow fzeatmertt is proposed for partitioning without a size wmstrain~and an iterative improvement algorithm is proposed for partitioning with a size comt.rstint.This algoriti incorporates a top-down clustering technique to deal with the local minima problems in common heuristics, a novel multi-pin net model to capture the contributory moves, and a Primal-Dual iteration to enhance the iterative improvement.Experiments show good results in all tested cases over the algorithm proposal in [12].Also, the effect of different objective functions is manifested through numerical tabulation.

In the layout stage of VLSI and printed circuit board (PCB) design, after all circuit modules (rectangular) are placed, it is possible to flip the modules so as to reduce the total net length. The authors formulate the orientation of modules as a graph problem and prove it to be NP-complete. The orientation problem is shown to be equivalent to finding a minimum cut of a graph with some arcs of negative capacities. In many cases, the graph can be decomposed into subgraphs to reduce the search space for optimum orientation. Experiments with real cases show that module orientation reduces the total net length and improves the routability.>

A two-way partitioning algorithm is presented that significantly improves on the highly unstable results typically obtained from the traditional Kernighan-Lin-based algorithms. The algorithm groups highly connected components into clusters and rearranges the clusters into two final subsets with specified sizes. It is known that the grouping operations reduce the complexity, and thus improve the results, of partitioning very large circuits. However, if the grouping is inappropriate, the partitioning results may degenerate. To prevent degeneration, a ratio cut approach is used to do the grouping. By a series of experiments based on the tradeoff between cut weight and CPU time, the value which controls the resultant number of groups is determined. Good experimental results have been observed for cut weight and CPU time.>

Circuit partitioning for hierarchical VLSI design is addressed. A partitioning approach called ratio cut is proposed. It is demonstrated that the ratio cut algorithm can locate the clustering structures in the circuit. Finding the optimal ratio cut is NP-complete. However, in certain cases the ratio cut can be solved by linear programming techniques via the multicommodity flow formulation. Also proposed is a fast heuristic algorithm running in linear time with respect to the number of pins in the circuit. Experiments show good results in all tested cases.>

A two-way partitioning algorithm is presented which significantly improves on the highly unstable results from the traditional Kernighan-Lin based algorithms. The algorithm groups strongly connected components into clusters, and rearranges the clusters into two final subsets with specified sizes. It is known that the grouping operations reduce the complexity and thus improve the results of partitioning very large circuits. However, if the grouping is inappropriate, the partitioning results may degenerate. To prevent degeneration, the authors use a ratio cut approach to do the grouping. By a series of experiments based on the tradeoff between cut capacity and CPU time, the authors determine an optimal value to control the resultant number of groups. Good experimental results have been observed in terms of cut capacity and CPU time.>

A partitioning approach called ratio cut is proposed. The authors demonstrate that the ratio cut algorithm can locate the clustering structures in the circuit. Finding the optimal ratio cut is NP-complete. However, in certain cases the ratio cut can be solved by linear programming techniques via the multicommodity flow problem. They also propose a fast heuristic algorithm running in linear time with respect to the number of pins in the circuit. Experiments show good results in all tested cases, and as much as 70% improvement over the Kernighan-Lin algorithm in terms of the proposed ratio metric.>

Abstract A linear placement technique that uses an objective function of the sum of wiring lengths is proposed. The method evolves from well‐known concepts in job sequencing and network flow. The relation between a job sequencing problem and this linear placement problem was demonstrated by Lawler. Also, Sidney proposed decomposition algorithms for job sequencing problems. Building on Lawler's and Sidney's work, we first develop a polynomial‐time algorithm to obtain optimal solutions for the special case of parallel graphs. Adolphson and Hu applied the max‐flow min‐cut method of the network flow problem to the partitioning of general placement problems. However, when the cut operation creates the cut of the same configuration as the previous cut operations, no additional partitioning information is obtained. We devise an optimal graph modification that tries to change the configuration of the cut for further partitioning of the problem, and achieve the maximum partitioning of the problem. Finally, a heuristic algorithm is derived to solve some Very Large Scale Integrated Circuits (VLSI) design linear placement problems. A comparison with published papers shows that our VLSI placement method produces better results.

A new constructive placement and partitioning method based on resistive network optimization is proposed. The objective function used is the sum of the squared wire length. The method has the feature which includes fixed modules in the formulation. The overall algorithm comprises the following subprograms: optimization, scaling, relaxation, partitioning and assignment. The method is efficient because it takes advantage of net-list sparsity and has a complexity of O[n1.4 log n]. Another added special feature is that irregular-size modules within cell rows are allowed. Thus the method is particularly useful in standard-cell and gate-array designs. Experimental results on four 4K gate-array placements are illustrated, and they are far superior than manual placements.