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.
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,dynTOperforms 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.
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