TY - GEN
T1 - Accelerated path-based timing analysis with MapReduce
AU - Huang, Tsung Wei
AU - Wong, Martin D.F.
N1 - Funding Information:
This work was partially supported by the National Science Foundation under Grant CCF-1320585.
Publisher Copyright:
© Copyright 2015 ACM.
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
T2 - 18th ACM International Symposium on Physical Design, ISPD 2015
Y2 - 29 March 2015 through 1 April 2015
ER -