NDLI: Power grid analysis using random walks

Content Provider	IEEE Xplore Digital Library
Author	Haifeng Qian Nassif, S.R. Sapatnekar, S.S.
Copyright Year	1982
Abstract	This paper presents a class of power grid analyzers based on a random-walk technique. A generic algorithm is first demonstrated for dc analysis, with linear runtime and the desirable property of localizing computation. Next, by combining this generic analyzer with a divide-and-conquer strategy, a single-level hierarchical method is built and extended to multilevel and "virtual-layer" hierarchy. Experimental results show that these algorithms not only achieve speedups over the generic random-walk method, but also are more robust in solving various types of industrial circuits. Finally, capacitors and inductors are incorporated into the framework, and it is shown that transient analysis can be carried out efficiently. For example, dc analysis of a 71 K-node power grid with C4 pads takes 4.16 s; a 348 K-node wire-bond dc power grid is solved in 93.64 s; transient analysis of a 642 K-node power grid takes 2.1 s per timestep.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	1204
Ending Page	1224
Page Count	21
File Size	754025
File Format	PDF
ISSN	02780070
Volume Number	24
Issue Number	8
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-08-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Power grids Wire Capacitors Transient analysis Voltage Inductors Circuit simulation Very large scale integration Integrated circuit interconnections Capacitance supply network inductance physical design power grid random walk simulation
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Electrical and Electronic Engineering Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Wire-sizing optimization with inductance consideration using transmission-line model

Exterior templates for capacitance computations [interconnections]

Wire width planning for interconnect performance optimization

Process-Based Three-Dimensional Capacitance Simulation -- TRICEPS

Multiobjective optimization of VLSI interconnect parameters

A comparison of strong and weak distributed transverse coupling between VLSI interconnects

Equivalent Elmore delay for RLC trees

Asymptotic waveform evaluation for transient analysis of 3-D interconnect structures

Efficient Space Management Techniques for Large-Scale Interconnect Capacitance Extraction With Floating Random Walks

Power grid analysis using random walks

Similar Documents

Wire-sizing optimization with inductance consideration using transmission-line model

Exterior templates for capacitance computations [interconnections]

Wire width planning for interconnect performance optimization

Process-Based Three-Dimensional Capacitance Simulation -- TRICEPS

Multiobjective optimization of VLSI interconnect parameters

A comparison of strong and weak distributed transverse coupling between VLSI interconnects

Equivalent Elmore delay for RLC trees

Asymptotic waveform evaluation for transient analysis of 3-D interconnect structures

Efficient Space Management Techniques for Large-Scale Interconnect Capacitance Extraction With Floating Random Walks

Power grid analysis using random walks