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.

The authors address the problem of simultaneous routing and buffer insertion. Recently the authors considered simultaneous maze routing and buffer insertion under the Elmore delay model. Their algorithms can take into account both routing obstacles and restrictions on buffer locations. It is well known that the Elmore delay is only a first-order approximation of signal delay and hence could be very inaccurate. Moreover, constraints cannot be imposed on the transition times of the output signal waveform at the sink or at the buffers on the route. The authors extend the algorithm in so that accurate delay models (e.g., transmission line model, delay lookup table from SPICE, etc.) can be used. They show that the problem of finding a minimum-delay buffered routing path can be formulated as a shortest path problem in a specially constructed weighted graph. By including only the vertices with qualifying transition times in the graph, they guarantee that all transition time constraints are satisfied. Their algorithm can be easily extended to handle buffer sizing and wire sizing. It can be applied iteratively to improve any given routing tree solution. Experimental results show that their algorithm performs well.

In this paper we address the problem of simultaneous routing and buffer insertion. Simultaneous maze routing and buffer insertion under the Elmore delay model have been reported in the literature previously. Such algorithms can take into account both routing obstacles and restrictions on buffer locations. It is well known that Elmore delay is only a first-order approximation of signal delay and hence could be very inaccurate. Moreover, we cannot impose constraints on the transition times of the output signal waveform at the sink or at the buffers on the route. In this paper we extend previously reported algorithm so that accurate delay models (e.g., transmission line model, delay look-up table from SPICE, etc.) can be used We show that the problem of finding a minimum-delay buffered routing path can be formulated as a shortest path problem in a specially constructed weighted graph. By including only the vertices with qualifying transition times in the graph, we guarantee that all transition time constraints are satisfied. Our algorithm can be easily extended to handle buffer sizing and wire sizing. It can be applied iteratively to improve any given routing tree solution. Experimental results show that our algorithm performs well.

The authors propose an elegant formulation of the Maze Routing with Buffer Insertion and Wiresizing problem as a graph-theoretic shortest path problem. This formulation provides time and space performance improvements over previously proposed dynamic programming based techniques. Routing constraints such as wiring obstacles and restrictions on buffer locations and types are easily incorporated in the formulation. They construct a buffer planning (BP)-graph such that the length of every path in this graph is equal to the Elmore delay. Therefore, finding the minimum Elmore delay path becomes a finite shortest path problem. The buffer choices and insertion locations are represented as the vertices in the BP-graph. The interconnect wires are sized by constructing a look-up table for buffer-to-buffer wiresizing solutions. The authors also provide a technique that is able to tremendously improve the runtime. Experiments show improvements over previously proposed methods.

Interconnect design has emerged as one of the major challenges facing chip designers as VLSI manufacturing progresses and gate sizes scale down. Dynamic programming(DP) is an efficient and robust technique for finding optimal solutions to interconnect optimization problems in VLSI design. However, DP's huge memory requirement often limits its effectiveness and sometimes, due to limited storage resources, even makes it impossible to solve a problem of practical size. Since interconnect optimization is often a subprocess embedded in an upper level design procedure, a memory and time efficient implementation of DP can be very favorable to circuit designers. In this paper, we develop a new memory-efficient dynamic programming approach to interconnect optimization problems. Our method utilizes selective storage and recomputation technique. This memory and time efficient algorithm speeds up the dynamic programming method without compromising solution quality. Experiments show tremendous saving, both in storage and time, over traditional dynamic programming algorithms. Our novel approach can also be generalized for other VLSI applications using DP algorithms.

Slicing tree has been an effective tool for VLSI floorplan design. Floorplanners using slicing tree representation take full advantage of shape and orientation flexibility of circuit modules to find highly compact slicing floorplans. However, slicing floorplans are commonly believed to suffer from poor utilization of space when all modules are hard. For this reason, a large body of literature has recently been devoted to various new representations of non-slicing floorplans to improve space utilization. In this paper, we prove that by using slicing tree representation and compaction, all maximally compact placements of modules can be generated. In conclusion, slicing tree is a complete floorplan representation for all non-slicing floorplans as well.

We propose an elegant formulation of the Maze Routing with Buffer Insertion and Wiresizing pr oblem as a graph-the oretic shortest path problem. This formulation provides time and space performance improvements over previously proposed dynamic-programming based techniques. R outing c onstr aints such as wiring obstacles and restrictions on buffer locations and types are easily inc orporated in the formulation. Furthermore, efficient softwar e routines solving shortest path problems in existing graph applic ation libraries can be applied. We construct a BP-Graph such that the length of every path in this graph is e qual to the Elmore delay. Therefore, finding the minimum Elmore delay path becomes a finite shortest path problem. The buffer choices and insertion locations are repr esente d as the vertices in the BP-Graph. The inter connect wir es are sized by constructing a look-up table for buffer-to-buffer wir esizing solutions. We also provide a technique that is able to tremendously improve the runtime. Experiments show improvements over previously proposed methods.