Browsing by Subject "Integrated circuits--Very large scale integration--Design and construction"
Now showing 1 - 10 of 10
Results Per Page
Sort Options
Item Analysis techniques for nanometer digital integrated circuits(2007-12) Ramalingam, Anand, 1979-; Pan, David Z.As technology has scaled into nanometer regime, manufacturing variations have emerged as a major limiter of performance (timing) in VLSI circuits. Issues related to timing are addressed in the first part of the dissertation. Statistical Static Timing Analysis (SSTA) has been proposed to perform full-chip analysis of timing under uncertainty such as manufacturing variations. In this dissertation, we propose an efficient sparse-matrix framework for a path-based SSTA. In addition to an efficient framework for doing timing analysis, to improve the accuracy of the timing analysis one needs to address the accuracy of: waveform modeling, and gate delay modeling. We propose a technique based on Singular Value Decomposition (SVD) that accurately models the waveform in a timing analyzer. To improve the gate delay modeling, we propose a closed form expression based on the centroid of power dissipation. This new metric is inspired by our key observation that the Sakurai-Newton (SN) delay metric can be viewed as the centroid of current. In addition to accurately analyzing the timing of a chip, improving timing is another major concern. One way to improve timing is to scale down the threshold voltage (Vth). But scaling down increases the subthreshold leakage current exponentially. Sleep transistors have been proposed to reduce leakage current while maintaining performance. We propose a path-based algorithm to size the sleep transistor to reduce leakage while maintaining the required performance. In the second part of dissertation we address power grid and thermal issues that arise due to the scaling of integrated circuits. In the case of power grid simulation, we propose fast and efficient techniques to analyze the power grid with accurate modeling of the transistor network. The transistor is modeled as a switch in series with an RC and the switch itself is modeled behaviorally. This model allows more accurate prediction of voltage drop compared to the current source model. In the case of thermal simulation, we address the issue of ignoring the nonlinearity of thermal conductivity in silicon. We found that ignoring the nonlinearity of thermal conductivity may lead to a temperature profile that is off by 10° C.Item Cell and interconnect timing analysis using waveforms(2002-08) Croix, John Francis, 1963-; Wong, Martin D. F.Item Incremental placement for modern VLSI design closure(2006) Ren, Haoxing; Pan, David Z.The nature of multiple objectives and incremental design process for modern VLSI design closure demands advanced incremental placement techniques. In this dissertation, I proposed several novel incremental placement methods for design closure objectives such as timing, signal integrity, legalization, and total wirelength (TWL). These methods can be applied to any physical synthesis system. First technique is sensitivity based netweighting. The objective is to improve both worst negative slack (WNS) and figure of merit (FOM), defined as the total slack difference compared to a certain slack threshold for all timing end points. It performs incremental global placements with netweights based on comprehensive analysis of the wirelength, slack and FOM sensitivities to the netweight. The experiments show promising results for both stand-alone timing driven placement and physical synthesis afterwards. The second technique is noise map driven two-step incremental placement. The novel noise map is used to estimate the placement impact on coupling noise, which takes into account of coupling capacitance, driver resistance and wire resistance. Guided by this accurate noise map, it performs a two-step incremental placement, i.e. cell inflation and local refinement, to expand regions with high noise impact in order to reduce total noise. Experimental results show significant timing and noise improvement with no wirelength penalty or CPU overhead. The third, yet most promising, technique is diffusion based placement migration, which is the smooth movement of cells in an existing placement to address a variety of post placement design closure issues. This method simulates a diffusion process where cells move from high concentration area to low concentration area. The application on placement legalization shows signifi- cant improvements in wirelength and timing as compared to other commonly used legalization techniques. The fourth technique is the first-do-no-harm detailed placement. It uses a set of pin-based timing and electrical constraints to prevent detailed placement techniques from degrading timing or violating electrical constraints while reducing wirelength. The experimental results show that this detailed placement technique not only reduces TWL, but also significantly improves timing.Item Layout optimization algorithms vor VLSI design and manufacturing(2007) Xu, Gang, 1974-; Pan, David Z.; Wong, Martin D. F.As the feature size of the transistor shrinks into nanometer scale, it becomes a grand challenge for semiconductor manufacturers to achieve good manufacturability of integrated circuits cost-effectively. In this dissertation, we aim at layout optimization algorithms from both manufacturing and design perspectives to address problems in this grand challenge. Our work covers three topics in this research area: a redundant via enhanced maze routing algorithm for yield improvement, a shuttle mask floorplanner, and optimization of post-CMP topography variation. Existing methods for redundant via insertion are all post-layout optimizations that insert redundant vias after detailed routing. In the first part of this dissertation, we propose the first routing algorithm that conducts redundant via insertion during detailed routing. Our routing problem is formulated as a maze routing with redundant via constraints and transformed into a multiple constraint shortest path problem, and then solved by Lagrangian relaxation technique. Experimental results show that our algorithm can find routing solutions with remarkably higher rate of redundant via insertion than conventional maze routing. Shuttle mask is an economical method to share the soaring mask cost by placing different chips on the same mask. Shuttle mask floorplanning is a key step to pack these chips according to certain objectives and constraints related to mask manufacturing and cost. In the second part of this dissertation, we develop a simulated annealing based floorplanner that can optimize these objectives and meet the constraints simultaneously. Chemical-mechanical polishing (CMP) is a crucial manufacturing step to planarize wafer surface. Minimum post-CMP topography variation is preferred to control the defocus in lithography process. In the third of this dissertation, we present several studies on optimization of the variation. First, we enhance the shuttle mask floorplanner to minimize the post-CMP topography variation. Then we study the following singleblock positioning problem: given a shuttle mask floorplan, how to determine a movable block's optimal position with respect to post-CMP topography variation. We propose a fast incremental algorithm achieving 6x to 9x speedup. Finally, we formulate a novel CMP dummy fill problem that targets at minimizing the height variance, which is key to reduce the image distortion by defocus. Experimental results show that with the new formulation, we can significantly reduce the height variance without sacrificing the height spread much.Item Layout optimization with dummy features for chemical-mechanical polishing manufacturability(2002) Tian, Ruiqi; Wong, D. F.Chemical-mechanical polishing (CMP) is an enabling technique used in deep- submicron VLSI manufacturing to achieve long range planarization. Control of postCMP topography variation is crucial to meeting present and future manufacturing process challenges, like the ever decreasing depth-of-focus in photo-lithography because of aggressive scaling down of feature sizes and the ever increasing levels of interconnect due to routing complexity of more and more devices on a chip. PostCMP topography is highly dependent on design pattern in the layout. To change layout pattern to reduce within-die post-CMP topography variation, layouts need to be optimized with dummy features, which are electrically inactive. A computer-aided design (CAD) framework is first proposed to give an uni- fied view of the layout optimization process for different process models and manufacturing integration procedures. An example using the CAD framework to solve a real-world problem with hybrid tiling is given. Layout optimization with dummy features for specific areas of VLSI manufacturing using CMP is then discussed in detail. Based on recent semi-physical models of post-CMP topography and polish pad bending, the dummy feature placement problem for oxide CMP is solved with linear programming for both single-layer and multiple-layer considerations. Also, based on additional models of local pad compression and dual-material polish that are important to CMP in the shallow trench isolation (STI) process, the dummy feature placement problem is formulated as a nonlinear programming problem using a derived time-dependent relation between local pattern density and post-CMP topography. An iterative approach is then employed to solve the dummy features placement problem after simplifications of the nonlinear programming problem. Moreover, both simulated annealing and greedy approaches are used to solve the dummy feature placement problem for copper CMP in an inlaid copper interconnect process. Computational experiences with real layouts from industry for the proposed solutions to the dummy feature placement problem in oxide CMP, CMP in STI, and copper CMP all give excellent reduction in simulated post-CMP topography with reasonable run time. Experimental results on layout optimizations for oxide CMP and hybrid tiling for STI are also presented as verifications to those solutions.Item Nanometer VLSI placement and optimization for multi-objective design closure(2007-12) Luo, Tao, Ph. D.; Pan, David Z.In a VLSI physical synthesis flow, placement directly defines the interconnection, which affects many other design objectives, such as timing, power consumption, congestion, and thermal issues. With the scaling of technology, the relative interconnect delay increases dramatically. As a result, placement has become a bottleneck in deep sub-micron physical synthesis. In this dissertation, I propose several optimization algorithms from global placement, placement migration, timing driven placements, to incremental power optimizations for multi-objective VLSI design closure. The first work is DPlace, a new global placement algorithm that scales well to the modern large-scale circuit placement problems. DPlace simulates the natural diffusion process to spread cells smoothly over the placement region, and uses both analytical and discrete techniques to improve the wire length. However, global placement is never sufficient for multi-objective design closure, a variety of design objectives have to be improved incrementally, such as timing, routing congestion, signal integrity, and heat distribution. Placement migration is a critical step to address the cell overlaps appearing during incremental optimizations. To achieve high placement stability, I propose a computational geometry based placement migration flow to cope with placement changes, and a new stability metric to measure the “similarity” between two placements accurately. Our placement migration algorithm has clear advantage over conventional legalization algorithms such that the neighborhood characteristics of the original placement are preserved. For timing closure in high performance designs, I present a linear programming based incremental timing driven placement to improve the timing on critical paths directly. I further present an efficient timing driven placement algorithm (Pyramids). Two formulations of Pyramids are proposed, which are suitable for different optimization stages in a physical synthesis flow. Both approaches find the optimal location for timing of a cell in constant time, through computational geometry based approaches. For fast convergence of design closure, placement should be integrated with other optimization techniques. I propose to combine placement, gate sizing and Vt swapping techniques to reduce the total power consumption, especially the leakage power, which is becoming increasingly critical for nanometer VLSI design closure.Item New algorithms for physical design of VLSI circuits(2002-08) Lai, Minghorng; Wong, D.F.Item Parallel prefix adder design(2004) Choi, Youngmoon; Swartzlander, Earl E.Adders are one of the critical elements in VLSI chips because of their variety of usages such as ALUs, floating point arithmetic units, memory addressing and program counting. For this reason, they have been studied for about half a century and a variety of adders have been invented. Among them, prefix adders are based on parallel prefix circuit theory which provides a solid theoretical basis for wide range of design trade-offs between delay, area and wiring complexity. This dissertation first presents an algorithm for prefix computation under the condition of non-uniform input signal arrival. To obtain the algorithm, the structure of prefix circuits is analyzed and a generalized circuit structure that is composed of two parts, a full-product generation tree and sub-product generation trees, is proposed. For the full-product generation tree, a delay optimized design algorithm is proposed and its optimality is shown. The proposed algorithm is easy of implement and fast in run-time due to its greedy strategy and it ensures the minimum depth prefix circuit design with the Ladner-Fischer strategy. This dissertation also presents a one-shot batch process that generates a wide range of designs for a group of parallel prefix adders. The prefix adders are represented by two two-dimensional matrixes and two vectors. This matrix representation makes it possible to compose two functions for gate sizing which calculate the delay and the total transistor width of the carry propagation graph of adders. After gate sizing, the critical path net list of the carry propagation graph is generated from the matrix representation for spice delay calculation. The process is illustrated by generating sets of delay and total transistor width pairs for 32-bit and 64-bit cases.Item Physical synthesis for nanometer VLSI and emerging technologies(2008-08) Cho, Minsik, 1976-; Pan, David Z.The unabated silicon technology scaling makes design and manufacturing increasingly harder in nanometer VLSI. Emerging technologies on the horizon require strong design automation to handle the large complexity of future systems. This dissertation studies eight related research topics in design and manufacturing closure in nanometer VLSI as well as design optimization for emerging technologies from physical synthesis perspective. In physical synthesis for design closure, we study three research topics, which are key challenges in nanometer VLSI designs: (a) We propose a highly efficient floorplanning algorithm to minimize substrate noise for mixed-signal system-on-a-chip designs. (b) We propose a clock tree synthesis algorithm to reduce clock skew under thermal variation. (c) We develop a global router, BoxRouter to enhance routability which is one of the classic but still critical challenges in modern VLSI. In physical synthesis for manufacturing closure, we propose the first systematic manufacturability aware routing framework to address three key manufacturing challenges: (a) We develop a predictive chemical-mechanical polishing model to guide global routing in order to reduce surface topography variation. (b) We formulate a random defect minimize problem in track routing, and develop a highly efficient algorithm. (b) We propose a lithography enhancement technique during detailed routing based on statistical and macro-level Post-OPC printability prediction. Regarding design optimization of emerging technologies, we focus on two topics, one in double patterning technology for future VLSI fabrication and the other in microfluidics for biochips: (a) We claim double patterning should be considered during physical synthesis, and propose an effective double patterning technology aware detailed routing algorithm. (b) We propose a droplet routing algorithm to improve routability in digital microfluidic biochip design.Item Synthesis of variation tolerant clock distribution networks(2008-12) Rajaram, Anand Kumar; Pan, David Z.In the sub-65nm VLSI technology, the variation effects like manufacturing variation, power supply noise and temperature variation become very significant. As one of the most vital components in any synchronous VLSI chip, the Clock Distribution Network (CDN) is especially sensitive to these variations. The unwanted clock skews caused by the variation effects consume increasing proportion of the clock cycle, thereby limiting chip performance and yield. Thus, making the clock network variation-tolerant is a key objective in the chip designs of today. In this dissertation, we propose several techniques that can be used to synthesize variation-tolerant clock networks. Our contributions can be broadly classified into following four categories: (i) Efficient algorithms for synthesizing link based non-tree clock networks. (ii) A methodology for synthesizing a balanced, variation tolerant, buffered clock network with cross-links. (iii) A comprehensive framework for planning, synthesis and optimization of clock mesh networks. (iv) A chip-level clock tree synthesis technique to address issues unique to hierarchical System-On-a-Chip (SOC) designs that are becoming more and more frequent today. Depending on the performance requirements and resource constraints of a given chip, the above techniques can be used separately or in combination to synthesize a variation tolerant clock network.