摘要
随着现代芯片设计逐步进入超深亚微米设计阶段,芯片的器件密度越来越大、工作频率越来越高,芯片电源网格的噪声越来越大。电源网格的过大噪声不但能引起功能逻辑上的问题,而且可能由于电流分配的不均匀而严重影响芯片的寿命。因此,在超深亚微米芯片的电源网格设计中,对芯片电源网格噪声的分析以及电源网格设计的优化越来越重要。本文研究主要集中于芯片电源完整性相关议题。
芯片电源网格由于规模及复杂度较大,其建模、分析及优化都具有挑战性。本文在分析已有相关算法的基础上,提出了一些新的建模、分析及优化算法,在内容上主要涉及以下几个方面：芯片电源网格互连线建模算法,芯片电源网格快速仿真算法,电源Pads及去耦电容的优化放置算法,芯片电源网格简化模型构建算法以及芯片电源完整性分析软件设计探索,主要贡献如下：
1)分析了电源网格寄生参数以及晶体管级模型对电源网格噪声的影响,提出了一种新的基于表查找和有限回流路径的芯片局部有效电感提取算法,并从效率和精度方面验证了该算法的优越性。
2)针对分析整个网络时随机行走算法效率不高,提出了一种改进的随机行走算法。改进后的算法在分析整个电源网格时能在保持一定精度的前提下,比原有算法效率提高10倍左右。以此方法为预优算法,提出了一种基于随机行走算法预优的高斯-赛德尔迭代算法,该算法比基于不完全平方分解的共轭梯度法具有将近5倍提速,且具有易于并行实现、并行效率高等优点。
3)提出了一种基于随机行走算法的电源pads分配算法。该算法能在给定pads数量或者最大允许压降时准确、有效地确定接近最优化的pads位置或者数量。
4)提出了一种基于诺顿等效电路的芯片电源网格模型简化算法。该算法首先用本文提出的快速Y参数提取方法求取芯片电源网格端口间Y参数,然后用矢量拟合算法求解电源网格无源模型的等效电路,最后用随机行走算法求解端口电流源模型,从而构建出精简的芯片电源网格简化模型。仿真实验验证了该算法的精度以及高效性。该模型能用于芯片-封装-PCB电源分配网络的协同设计与优化。
5)提出了一种考虑芯片-封装谐振效应的芯片去耦电容优化算法,该算法首先利用电源网格模型简化算法并结合封装模型,求得引起电源网格最大噪声的器件切换模式,然后结合随机行走算法对电源网格去耦电容进行分块优化,从而保证在精度与效率上都使得该算法能应用于全芯片优化。
6)探索基于图形界面的电源完整性分析工具设计,并基于本文相关算法设计了一款功能相对完整的芯片电源完整性分析软件—IC P/G Simulator。
As modern IC design gradually enters ultra-deep sub-micron (UDSM) regime, higher device densities and faster switching frequency cause on-die power distribution network to burden higher voltage droop. Excessively high power grid noise may not only lead to functional failures, but also greatly shorten the die's lifetime because of unevenly distributed currents. Therefore, it's of high importance to analyze on-die power grid noise and optimize power grid network. This thesis will focus on the issues related to on-die power integrity.
Modeling, analyzing and optimizing are very challenging for on-die power grid network due to its large scale and complexity. A serie of novel modeling, analyzing and optimizing algorithms have been proposed in this thesis based on studying of existing algorithms, which involves the modeling algorithm of on-die power grid interconnect, fast analysis algorithm for on-die power grid, power pads and on-die decap placing and optimizing algorithms, constructing method of simplified on-die power grid model and EDA software design for on-die power integrity analysis. The main contributions of this thesis can be summarized as the followings:
1) The effect of power grid network's parasitics and transistor-level model on power grid noise is analyzed. A novel chip partial effective inductance extracting method based on limited return path and table-loopup has been proposed, and the superior performace is verified from efficiency and accuracy views.
2) To overcome the inefficiency of random walk when solving for entire network, we propose an improved random walk method for power grid analysis. The improved algorithm is ten times speedup with negligible error for certain designs. Using the improved random walk method as preconditioning algorithm, a novel preconditioning Gause-Seidel method is proposed which shows 5 times speedup compared with ICCG method and also has the advantages of being easy to be parallized and high parallel efficiency.
3) We propose an algorithm for power supply pads assignment based on random walk algorithm. This algorithm can efficiently decide nearly optimal locations or the number of power supply pads given the number of power supply pads or voltage droop margin.
4) A simplyfing algorithm of on-die power grid model based on Norton's theorem is proposed. This algorithm firstly uses proposed fast Y parameter calculating algorithm to obtain Y parameter among targeted ports of power grid, and then uses vector fitting algorithm to synthesize the simplified circuit model accurately and efficiently, and lastly adopts random walk algorithm to efficiently extract current signature at target ports of power grid. Thus the whole simplified on-die power grid model is generated including passive part and active part. Experimetal result verifies the algorithm's precision and high efficiency. This model can be used for co-analysis and optimizing of chip-package-pcb power distribution network.
5) A novel on-die decap optimizing algorithm considering the chip-package resonance is proposed. In this algorithm the simplified-like algorithm for on-die power grid model is firstly used to calculate device's switching mode which generates worst power grid noise, and then random walk algorithm is adopted to optimize the decap placing part by part, thus the accuracy and efficiency is guaranteed to apply this algorithm to full-chip level optimizing.
6) How to design GUI based on-die power integrity analysis tools is studied and an on-die power integrity analysis tool named as "IC P/G Simulator" is designed, which is based on related algorithms proposed in this thesis and has most of the needed functions.
引文
[1]S. Bobba, T. Thorp, K. Aingaran, and D. Liu.IC power distribution challenges [C]// Proc.ICCAD. San Jose:IEEE,2001:643-650.
[2]Q. K. Zhu, Power Distribution Network Design for VLSI, John Wiley,2004.
[3]The International Technology Roadmap for Semiconductors, http://www.itrs.net. Semiconductor Industry Association,2009.
[4]A. Dharchoudhury, R. Panda, D. Blaauw, and R. Vaidyanathan. Design and analysis of power distribution networks in powerPCTM microprocessors[C]//Proc. DAC.San Francisco:IEEE,1998:738-743.
[5]Saint-Laurent. M., Swaminathan, M. Impact of power-supply noise on timing in high-frequency microprocessors [J]. IEEE Trans.On Advance Packaging,2004,27(1): 135-144.
[6]R. Panda, D. Blaauw, R. Chaudhry, V. Zolotov, B. Young, and R. Ramaraju. Model and analysis for combined package and on-chip power grid simulation[C]//Proc. ISQED. San Jose:IEEE,2000:179-184.
[7]Jaemin Kim, Woojin Lee, Yujeong Shim, et al. Chip-Package Hierarchical Power Distribution Network Modeling and Analysis Based on a Segmentation Method[J]. IEEE Trans, on Advance Packaging,2010,33(3):647-659.
[8]Uematsu, Y. Osaka, H. Yagyu, et al. Modeling of chip-package resonance in power distribution networks by an impulse response[C]//Proc. SPI. Hildsheim:IEEE,2010: 15-18.
[9]Gawon Kim, Dong Gun Kam, Daehyun Chung, et al. Chip-package co-design of power distribution network for system-in-package applications[C]//Proc. EPTC. Pan Pacific Singapore:IEEE,2004:499-501.
[10]Chiprout. E. On-die power grid:The missing link[C]//Proc. DAC. Anaheim:IEEE. 2010:940-945.
[11]Dipak Sitaram, Yu Zheng, Kenneth L.Shepard. Full-chip, three-dimensional, shapes-based RLC extraction [J]. IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systimes,2004,23(5):711-727.
[12]Sunil Yu, Dusan M. Petranovic, Shoba Krishnan, et al. Loop-based inductance extraction and modeling for multiconductor on-chip interconnects [J]. IEEE Trans. On Electron Devices,2006,53(1):135-145.
[13]Kalpesh Shah, "Power grid analysis in VLSI designs," master dissertation, Indian Institute of Science,2007.
[14]Dubey, A. P/G pad placement optimization:problem formulation for best IR drop[C]//Proc. ISQED. San Jose:IEEE,2005:340-345
[15]ZHAO M. FU Y H, VLADIMIR Z. et al. Optimal placement of power supply pads and pins [C]//IEEE Proceedings of the 38th DAC. Las Vegas:IEEE,2001:559-562.
[16]TAKASHI S, MASANORI H, HIDETOSHI O. Successive pad assignment algorithm to optimize number and location of power supply pad using incremental matrix inversion[C]//IEEE ASP-DAC. Yokohama:IEEE,2004:63-68.
[17]Zu-ying Luo. Efficient Optimization Methodology in Early-Stage Design of Mesh-structured On-Chip Power/Ground (P/G) Networks[C]//IEEE ICSICT. Shanghai: IEEE,2006:1911-1913.
[18]Haifeng Qian, Sani R. Nassif, SAPATNEKAR S S. Early-stage power grid analysis for uncertain working modes [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2005 24(5):676-682.
[19]Smith, L., Shishuang Sun, Boyle, P., et al. System power distribution network theory and performance with various noise current stimuli including impacts on chip level timing[C]//IEEE CICC. San Jose:IEEE,2009:621-628
[20]Sang-Pil Sim, Shoba Krishnan, Dusan M., et al. A unified RLC model for high-speed on-chip interconnects [J]. IEEE Transactions on Electron Devices,2003,50 (6): 1501-1510.
[21]Srivastava, N., Xiaoning Qi, Banerjee, K. Impact of on-chip inductance on power distribution network design for nanometer scale integrated circuits[C]//IEEE ISQED. San Jose:IEEE,2005:346-351.
[22]Woo Hyung Lee, Pant, S., Blaauw, D.. Analysis and reduction of on-chip inductance effects in power supply grids[C]//IEEE ISQED. San Jose:IEEE,2004:346-351.
[23]Srivastava, N., Xiaoning Qi, Banerjee, K. Effects of on-chip inductance on power distribution grid [C]//ACM ISPD. San Fransico:ACM,2005:63-69.
[24]Clement Luk. "Efficient Inductance Extraction for on-chip interconnect," master dissertation. University of Wisconsin-Madison. May.2003.
[25]ZHAO M, PANDA R V, SAPATNEKAR S S, et al. Hierarchical analysis of power distribution networks [J]. IEEE Transactions on Computer-Aided Design.2002, 21(2):159-168.
[26]C. K. S. Zhao, C.-K. Koh, and K. Roy. Decoupling capacitance allocation and its application to power-supply noise-aware floorplanning [J]. IEEE Trans. on Computer-Aided Design,2002,21(1):81-92.
[27]H. Su, S. S. Sapatnekar, and S. R. Nassif. Optimal decoupling capacitor sizing and placement for standard cell layout designs[J]. IEEE Trans. on Computer-Aided Design,2003,22(4):428-436.
[28]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[C]//Proc. ASP-DAC. YoKohama:IEEE,2004:505-510.
[29]Z. Qi, H. Li, S. X.-D. Tan, L. Wu, Y. Cai, and X. Hong. Fast decap allocation algorithm for robust on-chip power delivery[C]//Proc. ISQED. San Jose:IEEE,2005:542-547.
[30]H. Li, Jeffrey Fan, Zhenyu Qi, et al. Partition-based approach to fast on-chip decoupling capacitor budgeting and minimization [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2006,25(11):2402-2502.
[31]K. Wang and M. Marek-Sadowask. On-chip power supply network optimization using multigrid-based technique [J]. IEEE Trans, on Computer-Aided Design,2005,24(3): 407-417.
[32]C. Zhuo, J. Hu, M. Zhao, and K. Chen. Fast decap allocation based on algebraic multigrid [C]//Proc. ICCAD. San Jose:IEEE,2006:107-111.
[33]Mikhail Popovich, Andrey V. Mezhiba, Eby G. Friedman. Power distribution networks with on-chip decoupling capacitors, Springer,2007.
[34]Kao, W.H., Ch-Yuan Lo, Singh, R., et al. Parasitic extraction:current state of the art and future trends [C]//IEEE ISCAS. Sydney:IEEE,2001:487-490.
[35]Young, Brian. Digital signal integrity-modeling and simulation with interconnects and package, Prentice Hall PTR,2001.
[36]Gala, K., Zolotov, V., Panda, R., et al. On-chip inductance modeling and analysis [C]// IEEE DAC. LA:IEEE,2000:63-68.
[37]Ansys, Q3D Extractor, http://www.ansoft.com.cn/Productsintroduce/Q3DExtractor.htm.
[38]Keith Nabors, Jacob White. FastCap:A multipole accelerated 3-D capacitance extraction program [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1991,10(11):1447-1459.
[39]E1-Moselhy, T.A., Elfadel, I.M., et al. A hierachical floating random walk algorithm for fabric-aware 3D capacitance extraction [C]//IEEE ICCAD. San Jose:IEEE,2009: 752-758.
[40]赵鹏,张杰,陈抗生.一种用于提取超大规模集成电路电容的新型库查找法.半导体学报.2007(11)：1794-1802.
[41]Shen Lin, Makoto Nagata, Kenji Shimazaki, et al. Full-chip vectorless dynamic power integrity analysis and verification against 100uV/100ps-resolution measurement [C]// IEEE CICC. Orlado:IEEE,2004:509-512.
[42]Dipanjan Gope, Albert E. Ruehli, Vikram Jandhyala. Speeding up PEEC partial inductance computations using a QR-based algorithm[J]. IEEE Transactions on VLSI Systems,2007,15(1):60-68.
[43]M. Kamon, M. J. Tsuk, and J. K. White. Fasthenry:a multipole-accelerated 3-D inductance extraction program[J]. IEEE Trans. Microwave Theory Tech.,1994: 1750-1758.
[44]Rong Jiang, Wenyin Fu, Charlie Chung-Ping Chen. EPEEC:comprehensive SPICE-compatible reluctance extraction for high-speed interconnects above lossy multilayer substrates [J]. IEEE Transactions on VLSI Systems,2005,25(10): 1562-1571.
[45]Kenneth L. Shepard, Zhong Tian. Return-limited inductances:A practical approach to on-chip inductance extraction [J]. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems,2000,19(4):425-436.
[46]Sang-Pil Sim, Charlie Chao, Shoba Krishnan, et al. An effective loop inductance model for general non-orthogonal interconnect with random capacitive coupling [C]//IEEE IEDM. San Francisco:IEEE,2002:315-318.
[47]Atsushi MURAMATSU, Masanori HASHIMOTO, Hidetoshi ONODERA. Effects of on-chip inductance on power distribution grid [J]. IEICE Transactions on Fundamentals,2000, E88-A(12):3564-3572.
[48]Wheling Cheng, Aveek Sarkar, Shen lin, et al. Worst case switching pattern for core noise analysis[C]//Proc. DesignCon. Santa Clara:IEEE.2009:105-108.
[49]Lawrence T. Pillage. Ronald A. Rohrer, Chandramouli Visweswariah. Electronic Circuit and System Simulation Methods, McGraw-Hill,1994.
[50]T. H. Chen and C. C.-P. Chen. Efficient large-scale power grid analysis based on preconditioned krylov-subspace iterative methods[C]//Proc. DAC. Las Vegas:IEEE. 2001:559-562.
[51]竺红卫,马琪,李春强等.用于快速P/G网分析的Cholesky分解法图模型.计算机辅助设计与图形学学报.2004年8月,第16卷,第8期.1080-1084.
[52]武晓海,殷莉,洪先龙等.基于不完全分解预优共轭梯度法的电源和地线网络求解器.半导体学报.2003年3月,第21卷,第3期.298-302.
[53]Y. Zhong and M. D. F. Wong. Fast algorithms for. IR drop analysis in large power grid[C]//Proc. ICCAD. San Jose:IEEE,2005:351-357.
[54]Ramachandra Achar, Michel S. Nakhla, Harjot S. Dhindsa, et al. Parallel and scalable transient simulator for power grids via waveform relaxation(PTS-PWR)[J]. IEEE Transactions on VLSI Systems,2011,19(4):319-332.
[55]Y. Cai, Z. Pan, X. Hong, S. X.-D. Tan, W. Hou, L. Wu. Relaxed hierarchical power/ground grid analysis[C]//Proc. ASP-DAC. Shanghai:IEEE,2005:1090-1093.
[56]W. Guo, S. X.-D. Tan, Z. Luo, and X. Hong. Partial random walk for large linear network analysis[C]//Proc. ISCAS. Vancouver:IEEE,2004:173-176.
[57]Hao Yu, Yiyu Shi, Lei He. Fast analysis of structured power grid by triangularization based structure preserving model order reduction[C]//ACM/IEEE DAC. Yokohama: IEEE,2006:205-210.
[58]J. N. Kozhaya, "Analysis and design of power and ground networks for VLSI circuits," Ph.D.dissertation, University of Illinois at Urbana-Champaign,2001.
[59]J. N. Kozhaya, S. R. Nassif, and F. N. Najm. A multigrid-like technique for power grid Analysis[J]. IEEE Trans. on Computer-Aided Design,2002,21(10):1148-1160.
[60]H. Su, E. Acar, and S. R. Nassif. Power grid reduction based on algebraic multigrid Principles[C]//Proc. DAC:IEEE,2003:109-112.
[61]Z. Zhu, B. Yao, and C. K. Cheng. Power network analysis using an adaptive algebraic Multigrid[C]// Proc. DAC:IEEE,2003:105-108.
[62]C. Zhuo, J. Hu, and K. Chen. An improved AMG-based method for fast power grid Analysis[C]//Proc. ISQED. San Jose:IEEE,2006:290-295.
[63]H. Qian, S. R. Nassif, and S. S. Sapatnekar. Power grid analysis using random walks[J]. IEEE Trans. on Computer-Aided Design,2005,24(8):1204-1224.
[64]Boghrati, B., S. S. Sapatnekar. A scaled random walk solver for fast power grid analysis[C]//IEEE DATE. Dresden:IEEE,2011:1-6.
[65]Boghrati, B., S. S. Sapatnekar. Incremental solution of power grids using random walks[C]//IEEE ASP-DAC. Dresden:IEEE,2010:752-762.
[66]Yu-Min Lee, Chen, C.C.-P. The power grid transient simulation in linear time based on 3-D alternating-direction-implicit method [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2003,22(11): 1545-1550.
[67]Y. Lee and C. C.-P. Chen. Power grid transient simulation in linear time based on transmission-line-modeling alternating-direction-implicit method[C]//Proc. ICCAD. San Jose:IEEE,2001:75-80.
[68]Subramanian N. Lalgudi, Madhavan Swaminathan, Yaron Kretchmer. On-chip power-grid simulation using latency insertion method [J]. IEEE Transactions on Circuits and Systems, April,2008,55(3):914-931.
[69]Klokotov, D., Schutt-Aine, J. Extensions of the latency insertion method (LIM) to DC analysis of power supply networks and modeling of circuit interconnects with frequency dependent parameters[C]//Proc. ECTC:IEEE,2009:1624-1629.
[70]Bosun Hwang, Jongeun Koo, Chanseok Hwang, et al. Fast power delivery network analyzer[C]//IEEE ISQED. Santa Clara:IEEE,2011:1-4.
[71]Kose S., Friedman, E.G. Fast algorithms for power grid analysis based on effective resistance[C]//IEEE ISCAS. Paris:IEEE.2010:3661-3664.
[72]Yici Cai, Le Kang, Jin Shi, et al. Random walk guided decap embedding for power/ground network optimization [J]. IEEE Transactions on Circuits and Systems, Jan.,2008,55(1):36-40.
[73]Y. Cao, Y. Lee, T. Chen, and C.C. Chen. HiPRIME:Hierarchical and passivity reserved interconnect macromodeling engine for RLKC power delivery[C]//Proc. DAC:IEEE, 2002:379-384
[74]Cadence, EPS, http://www.cadence.com/products/di/eps/pages/default.aspx.
[75]Apache Design Solution, Redhawk, http://www.apache-da.com/products/redhawk.
[76]Synopsys, PrimeRail, http://www.synopsys.com
[77]Sigrity, XcitePI, http://www.sigrity.com/products/xcitepi/xcitepi.htm.
[78]Magma, FinSimpro, http://www.magma-da.com/products-solutions/analvsis/finesimpro.aspx.
[79]Synopsys, Hsim. http://www.synopsys.com.
[80]Magma. QuickCapNx, http://www.magma-da.com/products-solutions/librarvCharacterization/quickcapnx.aspx
[81]Synopsys. StarRC, http://www.svnopsys.com.
[82]徐树方,矩阵计算的理论与方法,北京大学出版社,1995。
[83]Zlydina, L., Yagil, Y..3D power grid modeling[C]//IEEE ICECS. Huntsville:IEEE, 2004:129-132.
[84]邓俊勇,钱江华,卓成等.基于随机行走的电源pads分配算法.浙江大学学报.2008年6月,第42卷,第6期.943-948.
[85]张杰.超大规模集成电路寄生参数提取.[硕士论文].杭州.浙江大学.2006年.
[86]David L., Cregut C., Huret F., et al. Return path assumption validation for inductance modeling in digital design[C]//IEEE SPI. Dorint Sporthotel:IEEE,2005:93-96.
[87]E W. Grover, "Inductance Calculations:working formulas and tables'", Dover Publications.
[88]Haifeng Qian, S. S. Sapatnekar. A hybrid linear equation solver and its application in quadratic placement[C]//IEEE ICCAD. Dresden:IEEE,2005:905-909.
[89]Taucs, http://www.tau.ac.il/-stoledo/taucs/.
[90]Odabasioglu, A., Celik M., Pileggi L.T.. PRIMA:Passive reduced-order interconnect macromodeling algorithm [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(8):645-654.
[91]Freund R.W. A hybrid linear equation solver and its application in quadratic placement[C]//IEEE ICCAD. San Jose:IEEE,2004:80-87.
[92]Sheehan B.N. TICER:Realizable reduction of extracted RC circuits[C]//IEEE ICCAD. San Jose:IEEE,1999:200-203.
[93]Gustavsen. B., Semlyen, A. Rational approximation of frequency domain responses by vector fitting [J]. IEEE Transactions on Power Delivery,1999,14(3):1052-1061.
[94]Gustavsen. B., Heitz, C. Fast realization of the modal vector fitting method for rational modeling with accurate representation of small eigenvalues [J]. IEEE Transactions on Power Delivery,2009,24(3):1396-1405.
[95]Adam Semlyen, Gustavsen. B. A half-size singularity test matrix for fast and reliable passivity assessment of rational models [J]. IEEE Transactions on Power Delivery, 2009,24(1):345-351.
[96]P-ICCG.http://www.vinas.com/jp/en/seihin/sms/SMS_P_ICCG_index.html
