Effectively parallelizing electronic design automation algorithms using the operator formulation

Electronic 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.