Effectively parallelizing electronic design automation algorithms using the operator formulation

dc.contributor.advisorPingali, Keshav
dc.contributor.committeeMemberFussell, Donald
dc.contributor.committeeMemberRossbach, Christopher
dc.contributor.committeeMemberManohar, Rajit
dc.creatorLu, Yi-Shan
dc.date.accessioned2022-09-14T01:35:22Z
dc.date.available2022-09-14T01:35:22Z
dc.date.created2022-05
dc.date.issued2022-05-04
dc.date.submittedMay 2022
dc.date.updated2022-09-14T01:35:23Z
dc.description.abstractElectronic design automation (EDA) algorithms are essential for circuit designers to handle huge circuits, modeled as graphs or hypergraphs, while meeting tight design schedules. Shortening the turn-around time of EDA algorithms through parallelization is attractive due to multicore machines being ubiquitous and inexpensive for more than a decade. However, parallelizing EDA algorithms effectively is difficult due to the compute irregularity in graph algorithms. In this dissertation, we study the effective parallelization of static timing analysis (STA), the core module for timing-driven EDA algorithms. We first analyze the parallelism within graph-based STA algorithms for synchronous circuits using the operator formulation, and identify suitable schedules for both full and incremental timing update. We then apply the same methodology to path-based STA algorithms for synchronous circuits, and distill out subgraph tagging as a building block for accuracy enhancement in STA. We prototype Blitz, a parallel STA engine built with Galois 6.0, and compare Blitz against the state-of-the-art open source parallel timers to demonstrate our effective parallelization for STA without losing timing accuracy. Finally, we study the parallelization of STA for AND-causal asynchronous circuits. We extract the parallelism available in asynchronous timing algorithms, devise efficient schedules for fast convergence when cyclic dependencies exist, and deploy subgraph tagging in checking asynchronous timing violations. This results in Cyclone, the first parallel STA engine for large asynchronous circuits.
dc.description.departmentComputer Science
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/2152/115702
dc.identifier.urihttp://dx.doi.org/10.26153/tsw/42600
dc.language.isoen
dc.subjectParallel programming
dc.subjectParallelization
dc.subjectOperator formulation
dc.subjectGraph algorithm
dc.subjectStatic timing analysis
dc.subjectElectronic design automation
dc.titleEffectively parallelizing electronic design automation algorithms using the operator formulation
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentComputer Sciences
thesis.degree.disciplineComputer Science
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
LU-DISSERTATION-2022.pdf
Size:
1.28 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.45 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description: