Bounded Dynamic Level Maintenance for Efficient Logic Optimization

Junfeng Liu, Qinghua Zhao, Liwei Ni, Jingren Wang, Biwei Xie, Xingquan Li, Bei Yu, Shuai MaarXiv 2025 · DOI · arXiv

Abstract: Logic synthesis iteratively optimizes circuit graphs, necessitating constant updates to node depths (levels) to satisfy timing constraints. Conventional update methods are "unbounded," where minor local modifications can trigger extensive, computationally expensive global recalculations. This paper presents boundLM, the first bounded dynamic level maintenance algorithm. By leveraging partial topological ordering and selective updates, boundLM achieves over a 1000x speedup in level maintenance and a 6.4x improvement in overall synthesis runtime without compromising circuit quality.

Introduction

In Electronic Design Automation (EDA), logic circuits are typically modeled as Directed Acyclic Graphs (DAGs), such as AND-Inverter Graphs (AIGs). A critical metric in these graphs is the "level" or depth of a node, which directly corresponds to the circuit's timing delay. Logic synthesis tools optimize these circuits by iteratively applying local transformations—replacing small subgraphs with functionally equivalent, more efficient ones.

However, each transformation requires updating the levels of affected nodes to ensure timing constraints are maintained. Existing incremental algorithms, such as those in the industry-standard ABC tool, are unbounded. A change involving only a few nodes can force the traversal of millions of downstream nodes in large-scale designs. As modern chips scale to hundreds of millions of gates, this $O(|V|^2)$ worst-case complexity becomes a significant bottleneck, often consuming the majority of optimization runtime.

Figure 1: Runtime breakdown of logic optimization across different circuit sizes, showing that level maintenance becomes the dominant bottleneck as designs scale.

The boundLM Approach

To address this bottleneck, the authors propose boundLM, a novel framework that transitions from exhaustive global updates to localized, bounded updates. The core of the approach relies on two key techniques:

  • Dynamic Partial Topological Order (dynTO): Instead of maintaining a global level map, the algorithm maintains a partial topological order. When a local edit occurs, dynTO performs local patches to the order rather than a global re-sort.
  • Selective Level Computation: The algorithm recognizes that global accuracy is not required at every step. It only computes accurate levels for nodes involved in the immediate next transformation. By using the structural skeleton of dynTO, forward and reverse level updates are strictly confined to the modified nodes and their immediate neighborhood.

These techniques bound the update complexity to the size of the local change ($\Delta$), effectively reducing the total time complexity for a sequence of updates from $O(|V|^2)$ to $O(|V| \Delta \log \Delta)$.

Experimental Results

The boundLM algorithm was integrated into the ABC logic synthesis tool and evaluated against standard benchmarks, including the EPFL Combinational Benchmark Suite and IWLS 2005.

The results demonstrate a massive performance leap. boundLM accelerated the level maintenance phase by an average of 1074.8x. On a 33-million node circuit, maintenance time was reduced from over two hours to just 2.1 seconds. This efficiency translates to a 6.4x overall speedup for common optimization operators like rewrite and refactor.

Figure 5: Comparison of node traversals and execution time between standard incremental level maintenance (incLM) and the proposed lazy update approach across various circuits.

Crucially, this speedup does not come at the cost of circuit quality. The Quality of Results (QoR) remained consistent, with boundLM occasionally producing slightly better depth metrics due to its localized processing order.

Conclusion

boundLM represents a significant advancement in EDA tool efficiency. By decoupling update costs from total graph size and bounding them to the scale of local changes, it enables linear scaling for logic optimization. This methodology provides a scalable foundation for the design of next-generation VLSI systems, where handling extreme complexity is paramount.

Summary updated

BibTeX
@misc{liu2025bounded,
  author = {Junfeng Liu and Qinghua Zhao and Liwei Ni and Jingren Wang and Biwei Xie and Xingquan Li and Bei Yu and Shuai Ma},
  title = {{Bounded Dynamic Level Maintenance for Efficient Logic Optimization}},
  year = {2025},
  eprint = {2512.12554},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.12554},
}
Figure