Incremental power network analysis using backward random walks

Baktash Boghrati; Sachin S Sapatnekar

doi:10.1109/ASPDAC.2012.6164983

Incremental power network analysis using backward random walks

Baktash Boghrati, Sachin S Sapatnekar

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

The process of power network analysis during VLSI chip design is inherently iterative. It is very common for the designer to make many small perturbations to an otherwise complete design, to enhance the design or fix design violations. Considering the size of the modern chips, updating the solution for the changed network can be a computationally intensive task. In this paper we propose an efficient and accurate incremental solver that utilizes the backward random walks to identify the region of influence of the perturbation. The solution of the network is updated for the significantly smaller region only. The proposed algorithm is capable of handling consecutive perturbations without any degradation. The experimental results show speedups of up to 13.7x as compared to a complete solution.

Original language	English (US)
Title of host publication	ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference
Pages	41-46
Number of pages	6
DOIs	https://doi.org/10.1109/ASPDAC.2012.6164983
State	Published - Apr 26 2012
Event	17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012 - Sydney, NSW, Australia Duration: Jan 30 2012 → Feb 2 2012

Publication series

Name	Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Other

Other	17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012
Country/Territory	Australia
City	Sydney, NSW
Period	1/30/12 → 2/2/12

Publisher link

10.1109/ASPDAC.2012.6164983

Find It

Find It at U of M Libraries

Cite this

Incremental power network analysis using backward random walks. / Boghrati, Baktash; Sapatnekar, Sachin S.
ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference. 2012. p. 41-46 6164983 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Boghrati, B & Sapatnekar, SS 2012, Incremental power network analysis using backward random walks. in ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference., 6164983, Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, pp. 41-46, 17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012, Sydney, NSW, Australia, 1/30/12. https://doi.org/10.1109/ASPDAC.2012.6164983

@inproceedings{067f5a73b2114c31ba943e141960a2c4,

title = "Incremental power network analysis using backward random walks",

abstract = "The process of power network analysis during VLSI chip design is inherently iterative. It is very common for the designer to make many small perturbations to an otherwise complete design, to enhance the design or fix design violations. Considering the size of the modern chips, updating the solution for the changed network can be a computationally intensive task. In this paper we propose an efficient and accurate incremental solver that utilizes the backward random walks to identify the region of influence of the perturbation. The solution of the network is updated for the significantly smaller region only. The proposed algorithm is capable of handling consecutive perturbations without any degradation. The experimental results show speedups of up to 13.7x as compared to a complete solution.",

author = "Baktash Boghrati and Sapatnekar, {Sachin S}",

year = "2012",

month = apr,

day = "26",

doi = "10.1109/ASPDAC.2012.6164983",

language = "English (US)",

isbn = "9781467307727",

series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",

pages = "41--46",

booktitle = "ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference",

note = "17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012 ; Conference date: 30-01-2012 Through 02-02-2012",

}

TY - GEN

T1 - Incremental power network analysis using backward random walks

AU - Boghrati, Baktash

AU - Sapatnekar, Sachin S

PY - 2012/4/26

Y1 - 2012/4/26

N2 - The process of power network analysis during VLSI chip design is inherently iterative. It is very common for the designer to make many small perturbations to an otherwise complete design, to enhance the design or fix design violations. Considering the size of the modern chips, updating the solution for the changed network can be a computationally intensive task. In this paper we propose an efficient and accurate incremental solver that utilizes the backward random walks to identify the region of influence of the perturbation. The solution of the network is updated for the significantly smaller region only. The proposed algorithm is capable of handling consecutive perturbations without any degradation. The experimental results show speedups of up to 13.7x as compared to a complete solution.

AB - The process of power network analysis during VLSI chip design is inherently iterative. It is very common for the designer to make many small perturbations to an otherwise complete design, to enhance the design or fix design violations. Considering the size of the modern chips, updating the solution for the changed network can be a computationally intensive task. In this paper we propose an efficient and accurate incremental solver that utilizes the backward random walks to identify the region of influence of the perturbation. The solution of the network is updated for the significantly smaller region only. The proposed algorithm is capable of handling consecutive perturbations without any degradation. The experimental results show speedups of up to 13.7x as compared to a complete solution.

UR - http://www.scopus.com/inward/record.url?scp=84859949212&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84859949212&partnerID=8YFLogxK

U2 - 10.1109/ASPDAC.2012.6164983

DO - 10.1109/ASPDAC.2012.6164983

M3 - Conference contribution

AN - SCOPUS:84859949212

SN - 9781467307727

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 41

EP - 46

BT - ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference

T2 - 17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012

Y2 - 30 January 2012 through 2 February 2012

ER -

Incremental power network analysis using backward random walks

Abstract

Publication series

Other

Publisher link

Find It

Other files and links

Fingerprint

Cite this