In today's VLSI designs, crosstalk effects causing chips to fail or suffer from low yields have become one of the very essential design issues. In this paper, we attempt to reduce crosstalk noise in logic and physical synthesis stage, which is usually done in post-layout stage. We propose a technology mapping method that can reduce the crosstalk noise while meeting delay constraints. The algorithm employing a dynamic programming framework in the matching phase determines the routing of fanin nets for all the matches to estimate the track utilization in probability. These routings are stored as virtual routing maps to compute the crosstalk noise during the covering phase, which will select the crosstalk-minimal solutions satisfying the delay constraints rather than the delay-minimal ones. This problem is different from wire congestion-driven technology mapping and our experimental results are encouraging. We experiment on the benchmark circuits in 90nm process, the results show that, with 7% of area increase, our proposed approach is effective to improve the crosstalk by 28% on average, as compared to the conventional delay- and/or congestion-driven technology mapping. The overall result is better than the efforts done in post-layout stage, and has been validated by modern commercial EDA tools. In addition, this proposed approach can be applied in local technology remapping at post-placement/post-routing and ECO stages as well.

High power consumption not only leads to short battery life for hand-held devices but also causes on-chip thermal and reliability problems in general. As power consumption is proportional to the square of supply voltage, reducing supply voltage can significantly reduce power consumption. Multi-supply voltage (MSV) has previously been introduced to provide finer grain power and performance tradeoff. In this paper, we propose a methodology on top of a set of algorithms to exploit nontrivial voltage island boundaries for optimal power versus design-cost tradeoff under performance requirement. Our algorithms are efficient, robust, and error-bounded and can be flexibly tuned to optimize for various design objectives (e.g., minimal power within a given number of voltage islands, or minimal fragmentation in voltage islands within a given power bound) depending on the design requirement. Our experiment on real industry designs shows a tenfold improvement of our method over current logical-boundary-based industry approach.

Multi-Vdd is an effective method to reduce both leakage and dynamic power. A key challenge in a multi-Vdd design is to limit the design cost and the demand for level shifters. This can be tackled by grouping cells of different supply voltages into a small number of voltage islands. Recently, an elegant algorithm [7] is proposed for generating voltage islands that balance the power versus design cost tradeoff under performance requirement, according to the placement proximity of the critical cells. One prerequisite of [7] is an initial voltage assignment at the standard cell level that meets timing. In this paper, we present a novel method to produce quality voltage assignment to [7], which not only meets timing but also forms good proximity of the critical cells to provide [7] with a smooth input. The algorithm is based on effective delay budgeting and efficient computation of physical proximity by Voronoi diagram. Our extensive experiments on real industrial designs show that our algorithm leads to 25% - 75% improvement in the voltage island generation, with the computation time only linear to the design size.

Input-output (I/O) placement has always been a concern in modern integrated circuit design. Due to flip-chip technology, I/O can be placed throughout the whole chip without long wires from the periphery of the chip. However, because of I/O placement constraints in design cost (DC) and performance, I/O buffer planning becomes a pressing problem. During the early stages of circuits and package co-design, I/O layout should be evaluated to optimize DC and to avoid product failures. The objective of this brief is to improve the existing/initial standard cell placement by I/O clustering, considering DC reduction and signal integrity preservation. The authors formulate it as a minimum cost flow problem that minimizes alphaW+betaD, where W is the I/O wirelength of the placement and D is the total voltage drop in the power network and, at the same time, reduces the number of I/O buffer blocks. The experimental results on some Microelectronics Center of North Carolina benchmarks show that the author's method averagely achieves better timing performance and over 32% DC reduction when compared with a conventional rule-of-thumb design that is popularly used by circuit designers

High power consumption not only leads to short battery life for handheld devices, but also causes on-chip thermal and reliability problems in general. As power consumption is proportional to the square of supply voltage, reducing supply voltage can significantly reduce power consumption. Multi-supply voltage (MSV) has previously been introduced to provide finer-grain power and performance trade-off. In this work we propose a methodology on top of a set of algorithms to exploit non-trivial voltage island boundaries for optimal power versus design cost trade-off under performance requirement. Our algorithms are efficient, robust and error-bounded, and can be flexibly tuned to optimize for various design objectives (e.g., minimal power within a given number of voltage islands, or minimal fragmentation in voltage islands within a given power bound) depending on the design requirement. Our experiment on real industry designs shows a ten-fold improvement of our method over current logical-boundary based industry approach.

With today's advanced integrated circuit manufacturing technology in deep submicron (DSM) environment, we can integrate entire electronic systems on a single system on a chip. However, without careful power supply planning in layout, the design of chips will suffer from local hot spots, insufficient power supply, and signal integrity problems. Postfloorplanning or postroute methodologies in solving power delivery and signal integrity problems have been applied but they will cause a long turnaround time, which adds costly delays to time-to-market. In this paper, we study the problem of simultaneous power supply planning and noise avoidance as early as in the floorplanning stage. We show that the problem of simultaneous power supply planning and noise avoidance can be formulated as a constrained maximum flow problem and present an efficient yet effective heuristic to handle the problem. Experimental results are encouraging. With a slight increase of total wirelength, we achieve almost no static IR (voltage)-drop requirement violation in meeting the current and power demand requirement imposed by the circuit blocks compared with a traditional floorplanner and 45.7% of improvement on a /spl Delta/I noise constraint violation compared with the approach that only considers power supply planning.

I/O placement has always been a concern in modern IC design. Due to flip-chip technology, I/O can be placed throughout the whole chip without long wires from the periphery of the chip. However, because of I/O placement constraints in design cost and performance, I/O buffer planning becomes a pressing problem. During the early stages of circuits and packaging co-design, I/O layout should be evaluated to optimize design cost and to avoid product failures. In this paper, our objective is to better an existing/initial standard cell placement by I/O clustering, considering design cost reduction and signal integrity preservation. We formulate it as a minimum cost flow problem minimizing /spl alpha/W+/spl beta/D, where W is the I/O wirelength of the placement and D is the total voltage drop in the power network. The experimental results on some MCNC benchmarks show that our method achieves better timing performance and averagely over 30% design cost reduction when compared with the conventional design rule of thumb popularly used by circuit designers.

The antenna problem is a phenomenon of plasma-induced gate-oxide degradation. It directly affects manufacturability of very large scale integration (VLSI) circuits, especially in deep submicron technology using high-density plasma. Diode insertion is a very effective way to solve this problem. Ideally, diodes are inserted directly under the wires that violate antenna rules. But in today's high-density VLSI layouts, there is simply not enough room for "under-the-wire" diode insertion for all wires. Thus, it is necessary to insert many diodes at legal "off-wire" locations and extend the antenna-rule violating wires to connect to their respective diodes. Previously, only simple heuristic algorithms were available for this diode insertion and routing problem. In this paper, we show that the diode insertion and routing problem for an arbitrary given number of routing layers can be optimally solved in polynomial time. Our algorithm guarantees finding a feasible diode insertion and routing solution whenever one exists. Moreover, we can guarantee to find a feasible solution to minimize a cost function of the form /spl alpha//spl times/L+/spl beta//spl times/N, where L is the total length of extension wires and N is the total number of vias on the extension wires. Experimental results show that our algorithm is very efficient.

Abstract — With today’s advanced integrated circuits (ICs) manufacturing technology in deep submicron (DSM) environ-ment, we can integrate entire electronic systems on a single chip (SoC). However, without careful power supply planning in lay-out, the design of chips will suffer from mostly signal integrity problems including IR-drop, I noise, and IC reliability. Post-route methodologies in solving signal integrity problem have been applied but they will cause a long turn-around time, which adds costly delays to time-to-market. In this paper, we study the prob-lem of power supply noise avoidance as early as in floorplanning stage. We show that the noise avoidance in power supply planning problem can be formulated as a constrained maximum flow prob-lem and present an efficient yet effective heuristic to handle the problem. Experimental results are encouraging. With slight in-crease of total wirelength, we achieve almost no IR-drop require-ment violation and 46.6 % of improvement on I noise constraint violation compared with a previous approach. I.

Antenna problem is a phenomenon of plasma induced gate oxide degradation. It directly affects manufacturability of VLSI circuits, especially in deep-submicron technology using high density plasma. Diode insertion is a very effective way to solve this problem Ideally diodes are inserted directly under the wires that violate antenna rules. But in today's high-density VLSI layouts, there is simply not enough room for "under-the-wire" diode insertion for all wires. Thus it is necessary to insert many diodes at legal "off-wire" locations and extend the antenna-rule violating wires to connect to their respective diodes. Previously only simple heuristic algorithms were available for this diode insertion and routing problem. In this paper we show that the diode insertion and routing problem for an arbitrary given number of routing layers can be optimally solved in polynomial time. Our algorithm guarantees to find a feasible diode insertion and routing solution whenever one exists. Moreover we can guarantee to find a feasible solution to minimize a cost function of the form /spl alpha/ /spl middot/ L + /spl beta/ /spl middot/ N where L is the total length of extension wires and N is the total number of Was on the extension wires. Experimental results show that our algorithm is very efficient.

One of the most challenging issues in today's high-performance VLSI design is to ensure high-quality power supply to each individual circuit blocks. Reduced power supply voltage can result in slower cell switching, or even circuit failure. Nevertheless, most floorplanning methodologies have ignored power supply considerations. Thus, the resulting floorplan may suffer from local hot spots and insufficient power supply for certain circuit blocks. In this paper, we present an optimal power supply planning algorithm based on network flow to shorten the current paths from power bumps to local power supply wirings. We have incorporated our algorithm into a floorplanning algorithm for integrated floorplanning and power supply planning. Experimental results are encouraging.

We address the problem of inserting repeaters, selected from a library, at feasible locations in a placed and routed network to meet user-specified delay constraints for deep submicron (DSM) technology. We use minimal repeater area by taking advantage of slacks available in the network. Specifically, we transform the problem into an unconstrained optimization problem and solve it by iterative local refinement. We show that the optimal repeater locations and sizes that locally minimize the objective function in the unconstrained problem can be efficiently computed. We have implemented our algorithm and tested it on a set of benchmarks; experimental results are promising.

We present a novel algorithm for delay constrained optimization of combinational logic, extending the state-of-the-art sizing algorithm based on Lagrangian relaxation. We tightly integrate fanout tree construction, buffer insertion/sizing and gate sizing, thereby achieving more optimization than if they were performed independently. We consider the network in its entirety, thereby taking full advantage of the slacks available on the noncritical paths. We have implemented our algorithm and experimented with it on ISCAS-89 benchmark circuits; the results demonstrate that it is effective as well as fast.

We propose an integrated clock tree construction algorithm which performs simultaneous routing, wire sizing and buffer insertion.In existing approaches, wire sizing and clock buffer insertion are typically applied sequentially after a clock tree is generated and routed, i.e., they are done as post-processing steps.None of the known methods can perform clock routing while simultaneously considering wire sizing and buffer insertion.We introduce wire widths and levels of buffers inserted as variables in forming merging segments in the proposed Integrated Deferred-Merge Embedding (IDME) algorithm.As a result, more zero-skew merging locations are made possible and the clock trees generated are zero-skew by construction.Our experiments show that by taking the advantage offered by wire sizing, we are able to minimize phase delay as well as to reduce wire length and use less buffers.

During the routing of global interconnects, macro blocks form useful routing regions which allow wires to go through but forbid buffers to be inserted. They give restrictions on buffer locations. In this paper, we take these buffer location restrictions into consideration and solve the simultaneous maze routing and buffer insertion problem. Given a block placement defining buffer location restrictions and a pair of pins (a source and a sink), we give a polynomial time exact algorithm to find a buffered route from the source to the sink with minimum Elmore delay.

Article Free Access Share on Simultaneous routing and buffer insertion with restrictions on buffer locations Authors: Hai Zhou Department of Computer Sciences, University of Texas, Austin, TX Department of Computer Sciences, University of Texas, Austin, TXView Profile , D. F. Wong Department of Computer Sciences, University of Texas, Austin, TX Department of Computer Sciences, University of Texas, Austin, TXView Profile , I-Min Liu Department of Electrical and Computer Engineering, University of Texas, Austin, TX Department of Electrical and Computer Engineering, University of Texas, Austin, TXView Profile , Adnan Aziz Department of Electrical and Computer Engineering, University of Texas, Austin, TX Department of Electrical and Computer Engineering, University of Texas, Austin, TXView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 96–99https://doi.org/10.1145/309847.309885Published:01 June 1999Publication History 44citation315DownloadsMetricsTotal Citations44Total Downloads315Last 12 Months43Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We propose a novel buffer insertion algorithm for handling more general networks, whose underlying topology is a directed acyclic graph rather than just a RC tree. The algorithm finds a global buffering which minimizes buffer area while meeting the timing constraints. We use Lagrangian relaxation to translate the timing constraints to a cost in the objective function, and simplify the resulting objective function using the special structure of the problem we are solving. The core of the algorithm is a local refinement procedure, which iteratively computes the optimal buffering for each edge so as to minimize a weighted area and delay objective. The resulting procedure is fast, and takes full advantage of the slack available on noncritical paths.