Successive pad assignment algorithm to optimize number and location of power supply pad using incremental matrix inversion

ABSTRACT

An efficient pad assignment algorithm to minimize voltage drop on a power distribution network is proposed. Combination of the successive pad assignment (SPA) and the incremental matrix inversion (IMI) provides an efficient assignment for both location and number of power supply pads. The SPA creates equivalent resistance matrix which preserves both pad candidates and power consumption points as external ports so that topological modification due to connection or disconnection between voltage sources and candidate pads are consistently represented. By reusing sub-matrix of equivalent matrix, the SPA greedily searches next pad location that minimizes the worst drop voltage. Each time the candidate pad is added, the IMI reduces computational complexity significantly. Experimental results show that the proposed procedures efficiently enumerate pad order in practical time.

REFERENCES

• 1: SIA, International Technology Roadmap for Semiconductors, 2003 Edition, Assembly and Packaging; Interconnect.
• 2: Alexander Dalal , Lavi Lev , Sundari Mitra, Design of an efficient power distribution network for the UltraSPARC-I microprocessor, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.118-123, October 02-04, 1995
• 3: Abhijit Dharchoudhury , Rajendran Panda , David Blaauw , Ravi Vaidyanathan , Bogdan Tutuianu , David Bearden, Design and analysis of power distribution networks in PowerPC microprocessors, Proceedings of the 35th annual conference on Design automation, p.738-743, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277229]
• 4: J. Kozhaya, S. Nassif, and F. N. Najm, "A multigrid-like technique for power grid analysis," IEEE Trans. on CAD, vol. 21, no. 10, pp. 1148--1160, October 1998.
• 5: Yu-Min Lee , Charlie Chung-Ping Chen, The Power Grid Transient Simulation in Linear Time Based on 3D Alternating-Direction-Implicit Method, Proceedings of the conference on Design, Automation and Test in Europe, p.11020, March 03-07, 2003
• 6: Haifeng Qian , Sani R. Nassif , Sachin S. Sapatnekar, Random walks in a supply network, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775860]
• 7: Massoud Pedram , Kamal Chaudhary , Ernest S. Kuh, I/O Pad Assignment Based on the Circuit Structure, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.314-318, October 14-16, 1991
• 8: Amir H. Ajami , Kaustav Banerjee , Amit Mehrotra , Massoud Pedram, Analysis of IR-Drop Scaling with Implications for Deep Submicron P/G Network Designs, Proceedings of the 4th International Symposium on Quality Electronic Design, p.35, March 24-26, 2003
• 9: M. Marek-Sadowska, "Pad assignment for power nets in VLSI circuits," IEEE Trans. on CAD, vol. 6, no. 4, pp. 550--560, July 1987.
• 10: Jaewon Oh , Massoud Pedram, Multi-pad power/ground network design for uniform distribution of ground bounce, Proceedings of the 35th annual conference on Design automation, p.287-290, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277128]
• 11: Min Zhao , Yuhong Fu , Vladimir Zolotov , Savithri Sundareswaran , Rajendran Panda, Optimal placement of power supply pads and pins, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996615]
• 12: "GNU octave," http://www.octave.org/.
• 13: O. Schenk, M. Hagemann, and S. Röllin, "Recent advances in sparse linear solver technology for semiconductor device simulation matrices," in Proc. SISPAD, September 2003, pp. 103--108.
• 14: Olaf Schenk , Klaus Gärtner, Solving unsymmetric sparse systems of linear equations with PARDISO, Future Generation Computer Systems, v.20 n.3, p.475-487, April 2004 [doi>10.1016/j.future.2003.07.011]