A general cache framework for efficient generation of timing critical paths

Kuan Ming Lai, Tsung-Wei Huang, Tsung Yi Ho

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

Abstract

The recent TAU 2018 contest was seeking novel idea for efficient generation of timing reports. When the timing graph is updated, users query different forms of timing reports that happen subsequently and sequentially. This process is computationally expensive and inherently complex. Therefore, we introduce in this paper a general cache framework for efficient generation of timing critical paths. Our framework efficiently supports (1) a cache scheme to minimize duplicate calculation, (2) graph contraction to reduce the search space, and (3) multi-threading. We evaluated our framework on the TAU 2018 contest benchmarks and demonstrated promising performance over the top performer.

Original languageEnglish (US)
Title of host publicationProceedings of the 56th Annual Design Automation Conference 2019, DAC 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781450367257
DOIs
StatePublished - Jun 2 2019
Event56th Annual Design Automation Conference, DAC 2019 - Las Vegas, United States
Duration: Jun 2 2019Jun 6 2019

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Conference

Conference56th Annual Design Automation Conference, DAC 2019
CountryUnited States
CityLas Vegas
Period6/2/196/6/19

Fingerprint

Critical Path
Cache
Timing
Multithreading
Graph in graph theory
Search Space
Contraction
Query
Benchmark
Minimise
Framework

Keywords

  • Cache
  • Path-based Timing Analysis
  • Static Timing Analysis

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modeling and Simulation

Cite this

Lai, K. M., Huang, T-W., & Ho, T. Y. (2019). A general cache framework for efficient generation of timing critical paths. In Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019 [a108] (Proceedings - Design Automation Conference). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1145/3316781.3317744

A general cache framework for efficient generation of timing critical paths. / Lai, Kuan Ming; Huang, Tsung-Wei; Ho, Tsung Yi.

Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. a108 (Proceedings - Design Automation Conference).

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

Lai, KM, Huang, T-W & Ho, TY 2019, A general cache framework for efficient generation of timing critical paths. in Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019., a108, Proceedings - Design Automation Conference, Institute of Electrical and Electronics Engineers Inc., 56th Annual Design Automation Conference, DAC 2019, Las Vegas, United States, 6/2/19. https://doi.org/10.1145/3316781.3317744
Lai KM, Huang T-W, Ho TY. A general cache framework for efficient generation of timing critical paths. In Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019. Institute of Electrical and Electronics Engineers Inc. 2019. a108. (Proceedings - Design Automation Conference). https://doi.org/10.1145/3316781.3317744
Lai, Kuan Ming ; Huang, Tsung-Wei ; Ho, Tsung Yi. / A general cache framework for efficient generation of timing critical paths. Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. (Proceedings - Design Automation Conference).
@inproceedings{24f83b9b248e41af998d99c811332582,
title = "A general cache framework for efficient generation of timing critical paths",
abstract = "The recent TAU 2018 contest was seeking novel idea for efficient generation of timing reports. When the timing graph is updated, users query different forms of timing reports that happen subsequently and sequentially. This process is computationally expensive and inherently complex. Therefore, we introduce in this paper a general cache framework for efficient generation of timing critical paths. Our framework efficiently supports (1) a cache scheme to minimize duplicate calculation, (2) graph contraction to reduce the search space, and (3) multi-threading. We evaluated our framework on the TAU 2018 contest benchmarks and demonstrated promising performance over the top performer.",
keywords = "Cache, Path-based Timing Analysis, Static Timing Analysis",
author = "Lai, {Kuan Ming} and Tsung-Wei Huang and Ho, {Tsung Yi}",
year = "2019",
month = "6",
day = "2",
doi = "10.1145/3316781.3317744",
language = "English (US)",
series = "Proceedings - Design Automation Conference",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019",
address = "United States",

}

TY - GEN

T1 - A general cache framework for efficient generation of timing critical paths

AU - Lai, Kuan Ming

AU - Huang, Tsung-Wei

AU - Ho, Tsung Yi

PY - 2019/6/2

Y1 - 2019/6/2

N2 - The recent TAU 2018 contest was seeking novel idea for efficient generation of timing reports. When the timing graph is updated, users query different forms of timing reports that happen subsequently and sequentially. This process is computationally expensive and inherently complex. Therefore, we introduce in this paper a general cache framework for efficient generation of timing critical paths. Our framework efficiently supports (1) a cache scheme to minimize duplicate calculation, (2) graph contraction to reduce the search space, and (3) multi-threading. We evaluated our framework on the TAU 2018 contest benchmarks and demonstrated promising performance over the top performer.

AB - The recent TAU 2018 contest was seeking novel idea for efficient generation of timing reports. When the timing graph is updated, users query different forms of timing reports that happen subsequently and sequentially. This process is computationally expensive and inherently complex. Therefore, we introduce in this paper a general cache framework for efficient generation of timing critical paths. Our framework efficiently supports (1) a cache scheme to minimize duplicate calculation, (2) graph contraction to reduce the search space, and (3) multi-threading. We evaluated our framework on the TAU 2018 contest benchmarks and demonstrated promising performance over the top performer.

KW - Cache

KW - Path-based Timing Analysis

KW - Static Timing Analysis

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

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

U2 - 10.1145/3316781.3317744

DO - 10.1145/3316781.3317744

M3 - Conference contribution

T3 - Proceedings - Design Automation Conference

BT - Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019

PB - Institute of Electrical and Electronics Engineers Inc.

ER -