Bounded Dynamic Level Maintenance for Efficient Logic Optimization

doi:10.1109/TC.2026.3688680

Bounded Dynamic Level Maintenance for Efficient Logic Optimization

2026-04-29

0

PRE

AI

DOI：10.1109/TC.2026.3688680

Original

Original request for help

Save

Abstract

En 中文

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 <inline-formula><tex-math notation="LaTeX">$O(|V|^{2})$</tex-math></inline-formula> for given local subgraphs <inline-formula><tex-math notation="LaTeX">$\{\Delta G_{i}\}_{i = 1}^{|V|}$</tex-math></inline-formula> updates on DAG <inline-formula><tex-math notation="LaTeX">$G(V,E)$</tex-math></inline-formula>. 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 <inline-formula><tex-math notation="LaTeX">$O(|V|\Delta\log\Delta)$</tex-math></inline-formula> time for a sequence <inline-formula><tex-math notation="LaTeX">$|V|$</tex-math></inline-formula> of updates <inline-formula><tex-math notation="LaTeX">$\{\Delta G_{i}\}$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$\Delta=\max_{i}\|\Delta G_{i}\|$</tex-math></inline-formula> denotes the maximum extended size of <inline-formula><tex-math notation="LaTeX">$\Delta G_{i}$</tex-math></inline-formula>. Experiments on comprehensive benchmarks show our algorithm enables an average 6.4<inline-formula><tex-math notation="LaTeX">${\boldsymbol{\times}}$</tex-math></inline-formula> overall speedup relative to rewrite and refactor, driven by the proposed bounded maintenance that achieves subquadratic time updates, all without any quality sacrifice.

Keywords:

Logic optimization

dynamic level maintenance

incremental graph computation

Bounded Dynamic Level Maintenance for Efficient Logic Optimization

Abstract

Journal

Organization