A Power Grid Optimization Algorithm by Direct Observation of Manufacturing Cost Reduction


With the recent advances of the VLSI technologies, stabilizing the physical behavior of VLSI chips is becoming a very complicated problem. Power grid optimization is required to minimize the risks of timing error by IR drop, defects by electro migration (EM), and manufacturing cost by the chip size. This problem includes complicated tradeoff relationships. We propose a new approach by observing the direct objectives of manufacturing cost, and timing error risk caused by IR drop and EM. The manufacturing cost is based on yield for LSI chip. The optimization is executed in early phase of the physical design, and the purpose is to find the rough budget of decoupling capacitors that may cause block size increase. Rough budgeting of the power wire width is also determined simultaneously. The experimental result shows that our approach enables selection of a cost sensitive result or a performance sensitive result in early physical design phase.

Share and Cite:

T. Hayashi, Y. Kawakami and M. Fukui, "A Power Grid Optimization Algorithm by Direct Observation of Manufacturing Cost Reduction," Circuits and Systems, Vol. 3 No. 4, 2012, pp. 325-333. doi: 10.4236/cs.2012.34046.

1. Introduction

With the advent of super deep submicron technologies, designing stable and dependable physical behavior of LSIs is becoming very difficult and serious problems, due to the IR-drop and the EM. Insertion of decupling capacitances and making wider the power grid wires are most effective for this purpose, but we must pay area penalty which causes cost increase. Conventional approaches [1,2] deal with the chip area or the IR drop as their design constraint or objective function. However, no designer can say adequate goal of the chip area without detailed statistical data about the relations between the chip area and the manufacturing cost. Similarly, no designer can say adequate value of the IR drop constraint without detailed statistical data about the relations between the IR drop and timing error risks. Only experienced manager can indicate those goals and suitable values. Without considering that the manufacturing cost increases exponentially as the chip area increase, it is difficult to develop effective optimization system. Furthermore, there is another aspect of the design optimization. Many conventional power grid optimization algorithms have been proposed [1-5]. But most of them select one metric from IR-drop, EM, wiring congestion, or area. Then it is used for their objective function of the optimization, and other metrics are selected as their constraint function. We introduced in [6] a new concept of a risk function to deal with those different characteristics of metrics at the natural process of the optimization schedule. Furthermore, we introduced a timing error risk as a direct metrics for optimization instead of IR drop in [7].

In this paper we propose a new efficient and effective power optimization algorithm, appropriate for current large scale chips. It deals directly with the manufacturing cost, which is calculated by the chip area increase caused by inserting the decoupling capacitors. The main design steps of VLSI are composed of system level design, function/logic design, and physical design. The area and timing can be dealt with the physical design phase. Especially, the manufacturing cost information is more effectively optimized in the early physical design phase called floor planning because there is more freedom of shape and size selection of the functional blocks. To reduce the design turnaround time, the power grid optimization is usually divided into two steps, high-level power grid optimization and detailed power grid optimization. The insertion of decoupling capacitors is executed in the high-level optimization to abstracted power grids. After the area of each block is fixed, the detailed power grid optimization makes detailed power grid physical patterns.

Our target is “power grid resource budgeting” in early physical design phase. The power grid resource includes both of power supply/ground lines and decoupling capacitors. The advantage of our approach is to optimize power/ground supply lines roughly and to insert decoupling capacitors analyzing trade-off between the yield for LSI chip and a manufacturing cost. Since the ground wiring can be treated as well as the power wiring, in the following description, we will explain using only the power supply wiring. As a result, the unnecessary costcan be eliminated from early design phase, and LSI’s design becomes more sophisticated. That is to say, not only the cost of a chip but also IR-drop, EM and wiring congestion are considered simultaneously in this optimization.

The rest of this paper is organized as follows. We discuss the layout model which enables the design exploration in high-level floor-plan in Section 2. In Section 3, we briefly summarize the optimization flow that enables simultaneous optimization of multi-objective optimization. In Section 4, we explain an important concept of risk function which is introduced in the optimization algorithm. The risk function is defined for each objective, the wiring congestion, the EM, the timing error due to IR drop, and the chip cost. Most of these are already proposed in other papers [6,7]. Thus, we spend more space to the chip cost risk. It represents the manufacturing cost characteristic which is associated with the chip area. In Section 5, experimental results are showed and the effectiveness of our proposed algorithm is discussed. The conclusion is stated in Section 6.

2. Layout Model

A power grid model and block layer model are shown in Figure 1. The power grid formed the mesh has two-layer structure, the horizontal and the vertical layer. These layers are connected with vias. The power grid optimization is performed by not only changing power wiring width [4] but also insertion of decoupling capacitors. Insertion of decoupling capacitors is effective for reducing IR-drop and inductor noise. Decoupling capacitors are placed in spare area in the block layer [3]. Block layer is mainly covered with standard cells. The ratio of the spare area is preset as the limitation which is able to place decoupling capacitors. The chip area is not increased by insertion of the capacitors if they were placed in the spare area. However the optimization algorithm may require additional decoupling capacitors by increasing the block size. It is necessary to consider resulting in manufacturing cost increase.

3. Multi-Objective Optimization Flow

Power grid optimization is a multi-objective optimization problem. We want to optimize many objectives, IR drop, EM, chip area, wiring congestion and so on simultaneously. It is, generally, a very difficult problem. One reason is that each objective has different dimension. Second reason is that each of them has a different characteristic curve. We have introduced a new concept of risk functions to deal with those different characteristics at the natural process of the optimization schedule [6,7]. The risk function represents dangerous condition of LSI implementation by using 0% to 100%. Each objective is converted into the same dimension of risk using the risk function. The shape of the risk function should be carefully defined. The combination of IR drop risk, EM, and wiring congestion risk is defined for each grid. Detail definition of the risk functions are stated in [7]. The risk value of the chip area is stated in this paper. The effectiveness is also shown in the section of experimental results.

Figure 2 shows a flow of the power grid optimization. The optimization is scheduled with the gradient method. First, the power grid circuit is constructed with an RC network and initial values of the circuit elements are given (STEP 1). The dynamic current consumption of each functional blockis pre-determined by an RTL power simulation. It is represented as current sources connecting the power grid nodes of the corresponding area. Then, voltage and current of each nodes and edges are calculated by dynamic circuit simulation (STEP 2). Next, a risk value of each grid is calculated (STEP 3). And the worst and four random grids are selected as the candidates of that they may be improved (STPE 4). Then for each candidate grid, the improvement operation i.e., change of power wiring width or insertion of decoupling capacitors, is examined (STEP 5). And a combination of selection of grids which has the highest value of the evaluation function is selected. If the value of the evaluation

Conflicts of Interest

The authors declare no conflicts of interest.


[1] H. Su, K. H. Gala and S. S. Sapatnekar, “Fast Analysis and Optimization of Power/Ground Networks,” International Conference on Computer Aided Design, San Jose, 5-9 November 2000, pp. 477-480. doi:10.1109/ICCAD.2000.896518
[2] K. Wang and M. M. Sadowska, “On-Chip Power Supply Network Optimization Using Multigrid-Based Technique,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24, No. 3, 2005, pp. 407-417. doi:10.1109/TCAD.2004.842802
[3] J. Fu, Z. Luo, X. Hong, Y. Cai, S. X.-D. Tan and Z. Pan, “A Fast Decoupling Capacitor Budgeting Algorithm for Robust On-Chip Power Delivery,” Proceedings of the Asia and South Pacific Design Automation Conference, Yokohama, 27-30 January 2004, pp. 505-510.
[4] T.-Y. Wang and C. C.-P. Chen, “Optimization of the Power/Ground Network Wire-Sizing and Spacing Based on Sequential Network Simplex Algorithm,” Proceedings of International Symposium on Quality Electronic Design, San Jose, 21 March 2002, pp. 157-162. doi:10.1109/ISQED.2002.996721
[5] X. Wu, X. Hon, Y. Ca, C. K. Cheng, J. Gu and W. Dai, “Area Minimization of Power Distribution Network Using Efficient Nonlinear Programming Techniques,” International Conference on Computer Aided Design, San Jose, 4-8 November 2001, pp. 153-157.
[6] H. Ishijima, K. Kusano, T. Harada, Y. Kawakami and M. Fukui, “An Algorithm for Power Grid Optimization Based on Dynamic Current Consumption,” International Association of Science and Technology for Development on Circuits, Signals and Systems, Vol. 531, 2006, pp. 114-119.
[7] Y. Kawakami, M. Terao, M. Fukui and S. Tsukiyama, “A Power Grid Optimization Algorithm by Observing Timing Error Risk by IR Drop,” The IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E91-A, No. 12, 2008, pp. 3423-3430.
[8] The Institute of Electronics and Communication Engineers, “LSI Handbook,” Ohmsha, 1984.
[9] C.-C. Chiang and J. Kawa, “Design for Manufacturability and Yield for Nano-Scale CMOS,” Springer, Berlin, 2007.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.