Accelerated path-based timing analysis with MapReduce

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Path-based timing analysis (PBA) is a pivotal step to achieve accurate timing signoff. A core primitive extracts a large set of paths subject to path-specific or less-pessimistic timing update. However, this process in nature demands a very high computational complexity and thus has been a major bottleneck in accelerating timing closure. Therefore, we introduce in this paper a fast and scalable PBA framework with MapReduce - a recent programming paradigm invented by Google for big-data processing. Inspired by the spirit of MapReduce, we formulate our problem into tasks that are associated with keys and values and perform massively-parallel map and reduce operations on a distributed system. Experimental results demonstrated that our approach can easily analyze million nodes in a single minute.

Original languageEnglish (US)
Title of host publicationISPD 2015 - Proceedings of the ACM International Symposium on Physical Design 2015
PublisherAssociation for Computing Machinery
Pages103-110
Number of pages8
ISBN (Electronic)9781450333993
DOIs
StatePublished - Mar 29 2015
Event18th ACM International Symposium on Physical Design, ISPD 2015 - Monterey, United States
Duration: Mar 29 2015Apr 1 2015

Publication series

NameProceedings of the International Symposium on Physical Design
Volume29-March-2015

Other

Other18th ACM International Symposium on Physical Design, ISPD 2015
CountryUnited States
CityMonterey
Period3/29/154/1/15

Fingerprint

Computational complexity
Big data

Keywords

  • MapReduce
  • Path-based static timing analysis

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Huang, T-W., & Wong, M. D. F. (2015). Accelerated path-based timing analysis with MapReduce. In ISPD 2015 - Proceedings of the ACM International Symposium on Physical Design 2015 (pp. 103-110). (Proceedings of the International Symposium on Physical Design; Vol. 29-March-2015). Association for Computing Machinery. https://doi.org/10.1145/2717764.2717771

Accelerated path-based timing analysis with MapReduce. / Huang, Tsung-Wei; Wong, Martin D F.

ISPD 2015 - Proceedings of the ACM International Symposium on Physical Design 2015. Association for Computing Machinery, 2015. p. 103-110 (Proceedings of the International Symposium on Physical Design; Vol. 29-March-2015).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Huang, T-W & Wong, MDF 2015, Accelerated path-based timing analysis with MapReduce. in ISPD 2015 - Proceedings of the ACM International Symposium on Physical Design 2015. Proceedings of the International Symposium on Physical Design, vol. 29-March-2015, Association for Computing Machinery, pp. 103-110, 18th ACM International Symposium on Physical Design, ISPD 2015, Monterey, United States, 3/29/15. https://doi.org/10.1145/2717764.2717771
Huang T-W, Wong MDF. Accelerated path-based timing analysis with MapReduce. In ISPD 2015 - Proceedings of the ACM International Symposium on Physical Design 2015. Association for Computing Machinery. 2015. p. 103-110. (Proceedings of the International Symposium on Physical Design). https://doi.org/10.1145/2717764.2717771
Huang, Tsung-Wei ; Wong, Martin D F. / Accelerated path-based timing analysis with MapReduce. ISPD 2015 - Proceedings of the ACM International Symposium on Physical Design 2015. Association for Computing Machinery, 2015. pp. 103-110 (Proceedings of the International Symposium on Physical Design).
@inproceedings{7d93850f124f46329ff59366876e84d5,
title = "Accelerated path-based timing analysis with MapReduce",
abstract = "Path-based timing analysis (PBA) is a pivotal step to achieve accurate timing signoff. A core primitive extracts a large set of paths subject to path-specific or less-pessimistic timing update. However, this process in nature demands a very high computational complexity and thus has been a major bottleneck in accelerating timing closure. Therefore, we introduce in this paper a fast and scalable PBA framework with MapReduce - a recent programming paradigm invented by Google for big-data processing. Inspired by the spirit of MapReduce, we formulate our problem into tasks that are associated with keys and values and perform massively-parallel map and reduce operations on a distributed system. Experimental results demonstrated that our approach can easily analyze million nodes in a single minute.",
keywords = "MapReduce, Path-based static timing analysis",
author = "Tsung-Wei Huang and Wong, {Martin D F}",
year = "2015",
month = "3",
day = "29",
doi = "10.1145/2717764.2717771",
language = "English (US)",
series = "Proceedings of the International Symposium on Physical Design",
publisher = "Association for Computing Machinery",
pages = "103--110",
booktitle = "ISPD 2015 - Proceedings of the ACM International Symposium on Physical Design 2015",

}

TY - GEN

T1 - Accelerated path-based timing analysis with MapReduce

AU - Huang, Tsung-Wei

AU - Wong, Martin D F

PY - 2015/3/29

Y1 - 2015/3/29

N2 - Path-based timing analysis (PBA) is a pivotal step to achieve accurate timing signoff. A core primitive extracts a large set of paths subject to path-specific or less-pessimistic timing update. However, this process in nature demands a very high computational complexity and thus has been a major bottleneck in accelerating timing closure. Therefore, we introduce in this paper a fast and scalable PBA framework with MapReduce - a recent programming paradigm invented by Google for big-data processing. Inspired by the spirit of MapReduce, we formulate our problem into tasks that are associated with keys and values and perform massively-parallel map and reduce operations on a distributed system. Experimental results demonstrated that our approach can easily analyze million nodes in a single minute.

AB - Path-based timing analysis (PBA) is a pivotal step to achieve accurate timing signoff. A core primitive extracts a large set of paths subject to path-specific or less-pessimistic timing update. However, this process in nature demands a very high computational complexity and thus has been a major bottleneck in accelerating timing closure. Therefore, we introduce in this paper a fast and scalable PBA framework with MapReduce - a recent programming paradigm invented by Google for big-data processing. Inspired by the spirit of MapReduce, we formulate our problem into tasks that are associated with keys and values and perform massively-parallel map and reduce operations on a distributed system. Experimental results demonstrated that our approach can easily analyze million nodes in a single minute.

KW - MapReduce

KW - Path-based static timing analysis

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

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

U2 - 10.1145/2717764.2717771

DO - 10.1145/2717764.2717771

M3 - Conference contribution

AN - SCOPUS:84979243304

T3 - Proceedings of the International Symposium on Physical Design

SP - 103

EP - 110

BT - ISPD 2015 - Proceedings of the ACM International Symposium on Physical Design 2015

PB - Association for Computing Machinery

ER -