Bounded Dynamic Level Maintenance for Efficient Logic Optimization
IEEE Transactions on Computers · 2026-07 · 75 (7) · 2548-2562
DOI: 10.1109/tc.2026.3688680 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Computers, 2026-07. Verfasst von Junfeng Liu und 7 weiteren Autor:innen. Die Arbeit nennt 36 Literaturangaben. Gefördert von: China Postdoctoral Science Foundation, Major Key Project of PCL, NSF of China.
Abstract (Originalsprache)
Logic optimization is a critical phase in Electronic Design Automation (EDA) flow for meeting desired circuit power, performance, and area (PPA) targets. These logic circuits are typically represented as Directed Acyclic Graphs (DAGs), where the structural depth, quantified by node level, critically correlates with timing performance. Modern optimization strategies frequently employ iterative, local transformation heuristics ( e.g., rewrite , refactor ) directly on this DAG structure. As optimization locally modifies the graph, node levels require dynamic updates to guide subsequent decisions. However, a significant gap exists: existing algorithms for incrementally updating node levels are unbounded to small changes. This leads to a worst total complexity in $O(|V|^{2})$ O ( | V | 2 ) for given local subgraphs $\{\Delta G_{i}\}_{i = 1}^{|V|}$ { Δ G i } i = 1 | V | updates on DAG $G(V,E)$ G ( V , E ) . This unbounded nature poses a severe efficiency bottleneck, hindering the scalability of optimization flows, particularly when applied to large circuit designs prevalent today. In this paper, we analyze the dynamic level maintenance problem endemic to iterative logic optimization, framing it through the lens of partial topological order. Building upon the analysis, we present the first bounded algorithm for maintaining level constraints, with $O(|V|\Delta\log\Delta)$ O ( | V | Δ log Δ ) time for a sequence $|V|$ | V | of updates $\{\Delta G_{i}\}$ { Δ G i } , where $\Delta=\max_{i}\|\Delta G_{i}\|$ Δ = max i ∥ Δ G i ∥ denotes the maximum extended size of $\Delta G_{i}$ Δ G i . Experiments on comprehensive benchmarks show our algorithm enables an average 6.4 ${\boldsymbol{\times}}$ × overall speedup relative to rewrite and refactor , driven by the proposed bounded maintenance that achieves subquadratic time updates, all without any quality sacrifice.
Förderung
- China Postdoctoral Science Foundation
- Major Key Project of PCL
- NSF of China
- NSF of Fujian Province
Zitieren
APA
Liu, J., Zhao, Q., Ni, L., Wang, J., Xie, B., Li, X., Yu, B., & Ma, S. (2026). Bounded Dynamic Level Maintenance for Efficient Logic Optimization. IEEE Transactions on Computers, 75(7), 2548-2562. https://doi.org/10.1109/tc.2026.3688680
Vancouver
Liu J, Zhao Q, Ni L, Wang J, Xie B, Li X, et al. Bounded Dynamic Level Maintenance for Efficient Logic Optimization. IEEE Transactions on Computers. 2026;75(7):2548-2562. doi:10.1109/tc.2026.3688680
BibTeX
@article{Liu2026,
author = {Liu, Junfeng and Zhao, Qinghua and Ni, Liwei and Wang, Jingren and Xie, Biwei and Li, Xingquan and Yu, Bei and Ma, Shuai},
title = {Bounded Dynamic Level Maintenance for Efficient Logic Optimization},
journal = {IEEE Transactions on Computers},
year = {2026},
volume = {75},
number = {7},
pages = {2548--2562},
doi = {10.1109/tc.2026.3688680}
}
EUVIMED