Browsing by Subject "Integrated circuits--Very large scale integration--Design"

Now showing 1 - 3 of 3

Algorithms for VLSI design planning
(2003) Chen, Hung-ming; Mok, Aloysius Ka-Lau.; Wong, D. F.
With shrinking feature sizes, much more transistors can be integrated on a single chip. Moore’s Law has been followed closely in the past decades, resulting in larger and faster chips every year. In order to design larger and faster chips in deep submicron (DSM) technology, it is necessary to perform early design planning. In this dissertation, we present several algorithms for a number of VLSI design planning problems. First, we propose a method to integrate interconnect planning with floorplanning. Our approach is based on the Wong-Liu floorplanning algorithm. We perform pin assignment and fast global routing during every iteration of floorplanning. We use a multi-stage simulated annealing approach in which different interconnect planning methods are used in different ranges of temperatures to reduce running time. A temperature adjustment scheme is designed to give smooth transitions between different stages of simulated annealing. Second, floorplanning problems typically have relatively small number of blocks (e.g., 50-100) but have a large number of nets (e.g. 20K). Since existing floorplanning algorithms use simulated annealing which needs to examine a large number of floorplans, this has made interconnect-centric floorplanning computationally very expensive. We present approaches that can dramatically improve the run time of problems with large number of nets and at the same time improve solution quality. Third, we propose a method for simultaneous power supply planning and noise avoidance in floorplan design. Without careful power supply planning in layout design, the design of chips will suffer from mostly signal integrity problems including IR-drop, I noise, and IC reliability. Post-route methodologiesin solving signal integrity problem have been applied but they will cause a long turn-around time, which adds costly delays to time-to-market. We show that the noise avoidance in power supply planning problem can be formulated as a constrained maximum flow problem. Fourth, I/O placement has been a concern in modern IC design. Due to flipchip and multi-chip module technologies, 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 and I/O buffer site building cost, the decision of positions for placing I/O buffers has become critical. Our objective is to reduce the number of I/O buffer sites and to decide their positions in an existing standard cell placement. We formulate it as a minimum cost flow problem.
Fundamental algorithms for physical design planning of VLSI
(2002) Tang, Xiaoping; Wong, D. F.
Rapid advances in semiconductor technologies have led to a dramatic increase in the complexity of VLSI circuits. With fabrication technology entering deep submicron era, devices are scaled down, more functionalities are integrated into one chip, and chips run at higher clock frequencies. Handling the extremely large designs with ever-increasing clock rates, while reducing design turnaround time and ensuring timing convergence, is exhausting the capabilities of traditional design tools. Thus careful up-front design planning, analyzing physical implementation effects before the actual place-and-route, is essential in designing today’s multi-million and future’s billion gate ICs. We study several fundamental problems of VLSI physical design planning in this dissertation. In floorplanning, we develop a floorplanner FAST-SP based on sequence pair floorplan representation. A new approach is proposed to evaluate a sequence pair based on computing longest common subsequence in a pair of weighted sequences in time. Our evaluation algorithm is significantly faster than the previous graph-based algorithm. For all MCNC benchmark problems, we obtain the best results ever reported in the literature with significantly less runtime. Placement constraints are important in floorplanning. We consider fixedframe floorplanning and extend FAST-SP to handle placement constraints such as pre-placed constraint, range constraint, boundary constraint, abutment constraint, alignment constraint, rectilinear shape constraint, and performance constraint. We propose a uniform method to deal with all these constraints. Buffer planning is a key component in design planning. We present a new approach to buffer planning based on network flow computation. Our algorithm optimally solves the problem of inserting maximum number of buffers into the free space between the circuit blocks with minimum total cost in polynomial time. Buffered routing tree construction is essential in wire planning. We consider the problem of constructing routing trees with simultaneous buffer insertion and wire sizing in the presence of routing and buffer obstacles. A new graph-based approach is proposed to solve the problem. Both theoretical and experimental results show that the graph-based algorithm outperforms the previous DP-based algorithm by a large margin. Routing resource allocation or distribution is a key issue in wire planning. We need to minimize the use of routing resource while satisfying the delay constraints. Thus we study the problem and extend the graph-based algorithm to solve it. We also develop a hierarchical approach to buffered routing tree construction to tradeoff runtime and routing quality.
Physical design of VLSI with electrical and power consideration
(1995-08) Chao, Kai-yuan, 1964-; Not available