Accelerated Path-Based Timing Analysis with MapReduce

Tsung-Wei Huang, Martin D. F. Wong

Research output: Chapter in book/report/conference proceedingChapterpeer-review

14 Citations (Scopus)


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
Title of host publicationISPD'15: International Symposium on Physical Design
PublisherAssociation for Computing Machinery (ACM)
Number of pages8
ISBN (Electronic)9781450333993
Publication statusPublished - Mar 2015
Event24th International Symposium on Physical Design, ISPD 2015 - Monterey, United States
Duration: 29 Mar 20151 Apr 2015 (Link to conference proceedings)

Publication series

NameProceedings of the Symposium on International Symposium on Physical Design


Symposium24th International Symposium on Physical Design, ISPD 2015
Country/TerritoryUnited States
Internet address

User-Defined Keywords

  • Path-based static timing analysis
  • MapReduce


Dive into the research topics of 'Accelerated Path-Based Timing Analysis with MapReduce'. Together they form a unique fingerprint.

Cite this