Search

As the technology scales into 90 nm and below, process-induced variations become more pronounced. In this paper, we propose an efficient stochastic method for analyzing the voltage drop variations of on-chip power grid networks, considering 10g-normal leakage current variations with spatial correlation. The new analysis is based on the Hermite polynomial chaos (PC) representation of random processes. Different from the existing Hermite PC based method for power grid analysis (Ghanta et al., 2005), which models all the random variations as Gaussian processes without considering spatial correlation, the new method consider both wire variations and subthreshold leakage current variations, which are modeled as log-normal distribution random variables, on the power grid voltage variations. To consider the spatial correlation, we apply orthogonal decomposition to map the correlated random variables into independent variables. Our experiment results show that the new method is more accurate than the Gaussian-only Hermite PC method using the Taylor expansion method for analyzing leakage current variations. It is two orders of magnitude faster than the Monte Carlo method with small variance errors. We also show that the spatial correlation may lead to large errors if not being considered in the statistical analysis. Index Terms--Hermite polynomials, leakage current, power delivery network, spectral analysis.

The reliability of Power/Ground networks is becoming significantly important in modern integrated circuits, while decap insertion is a main approach to enhance the power grid safety. In this brief, we propose a fast and efficient decap allocation algorithm, and adequately consider the leakage effect of decap. This approach borrows the idea of random walks to perform circuit partitioning and does subsequent decap insertion based on locality property of partitioned area, which avoids solving a large nonlinear programming problem in traditional decap optimization process. The optimization flow also integrates a refined leakage current model for decaps which makes it more practical. Experimental results show that our proposed method can achieve approximate 15X speed up over the optimal budget method within the acceptable error tolerance. Also this algorithm only causes a few penalty area to compensate the leakage effect. Index Terms--Leakage, optimization, power/ground (P/G) network, random walks.

Three-dimensional (3-D) IC physical design problems are usually of higher complexity, with a greatly enlarged solution space due to multiple device structure. In this paper, a new 3-D floorplanning algorithm is proposed for wirelength optimization. Our main contributions and results can be summarized as follows. First, a new hierarchical flow of 3-D floorplanning with a new interlayer partitioning method. The blocks are partitioned into different layers before floorplanning. A simulated annealing (SA) engine is used to partition blocks with the objective of minimizing the statistical wirelength estimation results. The solution quality is not degraded by the hierarchical flow. Second, floorplans of all the layers are generated in a SA process. Original 3-D floorplanning problem is transformed into solving several 2-D floorplanning problems simultaneously. The solution space is scaled down to maintain a low design complexity. Finally, Experimental results show that our algorithm improves wirelength by 14%-51% compared with previous 3-D floorplanning algorithms. The hierarchical approach is proven to be very efficient and offers a potential way for high-performance 3-D design. Index Terms--Computer-aided design (CAD), integrated_circuit_layout, optimization, very large-scale integration (VLSI).

This brief presents an improved multilevel full-chip routing system which integrates the redundant via placement in the routing flow for yield and reliability enhancement. The system features a pre-coarsening stage which is equipped with fast congestion-driven L-pattern global router followed by detailed router. The L-pattern global routing benefits to the reduction of vias and thus relieves the burden of redundant via addition. In addition, a rvia-driven maze routing algorithm is also integrated in the system to improve the insertion of redundant vias. Finally a redundant via placement heuristic is adopted to enhance the completion rate. We have tested the system on a set of commonly used benchmark circuits and compared the results with a previous multilevel routing system. Besides much enhancement obtained in the aspect of redundant via placement, the system also obtains high routing completion rate, minimized total wire length and total number of vias in satisfactory runtime. Index Terms--DFM, routing, redundant via, yield enhancement.

In this brief, the authors take a first look at the leakage effects of decaps in power/ground (P/G) grid optimization. Through the use of an approximate leakage current model, it is revealed that simple usage of the leakage model in traditional optimization methods cannot help in reducing noises on P/G grids, and it even hurts power consumption due to overadded decaps. Therefore, it is necessary to develop an efficient method to budget decaps when leakage effect is considered. Here, a new two-stage approach to solve this problem is proposed. Experimental results demonstrate the effectiveness of our new method. Index Terms--Decap, leakage, optimization, power/ground (P/G) network.

This brief deals with the crosstalk minimization problem in an integrated routing resource assignment stage containing several operations between global routing and detailed routing. A two-step heuristic algorithm consisting of coarse assignment and detailed assignment is proposed. In coarse assignment, shield lines are planned based on the chromatic number of a light coarse coupling graph, and the assignment of segments that are longer than a predefined threshold is solved with semidefinite programming. In detailed assignment, a strategy based on a dynamic priority queue is introduced to mitigate common problems caused by sequential routing. Experimental results on a set of benchmarks show significant reduction in coupling length between sensitive segments compared to a prevalent bipartite-matching-based algorithm. Index Terms--Crosstalk, layout, routing, shield insertion, track assignment.

Corner block list (CBL) is a room-based floorplan representation. In this brief, we give a sufficient and necessary condition for the feasibility of a CBL, and we also deal with aligmnent constraints in CBL. A method is proposed to identify topological relation between two blocks in CBL. Based on the topological relations between blocks, it is also found that a sufficient and necessary condition to judge whether or not a CBL is feasible under alignment constraints. The experimental results showed the efficiency and effectiveness of the proposed method. Index Terms--Alignment, corner block list (CBL), floor-planning, placement.

We propose to use a corner block list (CBL) representation for mosaic floorplans. In a mosaic floorplan, each room has only one block assigned to it. Thus, there is a unique corner room on the top right corner of the chip. Corner block deletion and corner block insertion keep the floorplan mosaic. Through a recursive deletion process, a mosaic floorplan can be converted to a representation that is named as CBL. Given a CBL, it takes only linear time to construct the floorplan. The CBL is used for the application to very large-scale integration floorplan and building block placement. We adopt a simulated annealing process for the optimization. Soft blocks and the aspect ratio of time chip are taken into account in the optimization process. The experimental results demonstrate that the algorithm is quite promising. Index Terms--Building block layout, floorplanning representation, NP hard, placement algorithm, simulated annealing.