Depth-driven graph partitioning&nbsp;for critical path delay optimization

YU Xuewen, CHEN Haiyan, HUANG Pengcheng

doi:10.3969/j.issn.1007-130X.2026.04.003

Computer Engineering & Science >

2026 , Vol. 48 >Issue 4: 590 - 598

DOI: https://doi.org/10.3969/j.issn.1007-130X.2026.04.003

High Performance Computing

Depth-driven graph partitioning for critical path delay optimization

Expand

(1.Key Laboratory of Advanced Microprocessor Chips and Systems，Changsha 410073;
2.College of Computer Science and Technology,National University of Defense Technology,Changsha 410073,China)

Received date: 2024-09-09

Revised date: 2025-01-16

Online published: 2026-04-29

Fold

Abstract

In microprocessor design, critical path delay is a crucial factor that restricts the increase in the microprocessor's clock frequency and performance enhancement. The ever-increasing design complexity poses challenges to traditional optimization methods. To address this difficult issue, an automated critical path delay optimization strategy based on depth-driven graph partitioning is proposed, along with the implementation of the corresponding algorithm. The delay optimization problem is modeled as a directed acyclic graph (DAG) partitioning and selection problem. Leveraging the logic netlist designed in the semi-custom design flow, the strategy utilizes depth-driven graph partitioning to identify and select a set of sub-circuit structures with optimization potential. These sub-circuits then undergo logical reconstruction, and the corresponding logic cells in the logic netlist are replaced accordingly. Experimental results demonstrate that the proposed algorithm can optimize circuits designed by electronic design automation (EDA) tools, effectively reducing the logical depth along critical paths. Consequently, it provides an effective strategy for optimizing critical path delay within limited costs, thus aiming to achieve an improvement in microprocessor performance.

Key words： critical path; delay optimization; logic depth; graph partitioning; logic restructuring

Cite this article

YU Xuewen, CHEN Haiyan, HUANG Pengcheng . Depth-driven graph partitioning for critical path delay optimization[J]. Computer Engineering & Science, 2026 , 48(4) : 590 -598 . DOI: 10.3969/j.issn.1007-130X.2026.04.003

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article