An Efficient Clock Tree Synthesis Method Based on Bi-Partition Four-Branch Tree

GUO Jing-jing; LIU Run-kan; YANG Jun-wei; WANG Jia-wei; WANG Chong; CAI Zhi-kuang

doi:10.12263/DZXB.20250076

您当前的位置：

首页 >

文章列表页 >

An Efficient Clock Tree Synthesis Method Based on Bi-Partition Four-Branch Tree

PAPERS | 更新时间：2025-12-27

- An Efficient Clock Tree Synthesis Method Based on Bi-Partition Four-Branch Tree
- ACTA ELECTRONICA SINICA Vol. 53, Issue 8, Pages: 2719-2728(2025)
- 作者机构：
  
  1.南京邮电大学集成电路科学与工程学院（产教融合学院），江苏南京 210023
  2.南京理工大学微电子学院（集成电路学院），江苏南京 210094
- 作者简介：
- 基金信息：
  
  Natural Science Foundation of Jiangsu Province(BK20240637)
- DOI：10.12263/DZXB.20250076
  CLC： TN47;TN401
- Received：22 January 2025，
  
  Accepted：20 August 2025，
  
  Published：25 August 2025
- 稿件说明：
移动端阅览
郭静静, 刘润衎, 杨君威, 等. 一种基于二分区四分支树的高效时钟树综合方法[J]. 电子学报, 2025, 53(08): 2719-2728.

GUO Jing-jing, LIU Run-kan, YANG Jun-wei, et al. An Efficient Clock Tree Synthesis Method Based on Bi-Partition Four-Branch Tree[J]. Acta Electronica Sinica, 2025, 53(08): 2719-2728.
郭静静, 刘润衎, 杨君威, 等. 一种基于二分区四分支树的高效时钟树综合方法[J]. 电子学报, 2025, 53(08): 2719-2728. DOI：10.12263/DZXB.20250076

GUO Jing-jing, LIU Run-kan, YANG Jun-wei, et al. An Efficient Clock Tree Synthesis Method Based on Bi-Partition Four-Branch Tree[J]. Acta Electronica Sinica, 2025, 53(08): 2719-2728. DOI：10.12263/DZXB.20250076

摘要

在超大规模集成电路设计中，高效的时钟树综合对保障电路性能与可靠性至关重要.为应对大规模电路中时钟偏差、延迟和功耗的协同优化挑战，本文提出一种基于二分区四分支类H树的高效时钟树综合方法.该方法在自底向上阶段，首先采用贪婪聚类算法（Greedy-Based Clustering，GBC）提升底层缓冲器扇出利用率，显著减少了底层插入的缓冲器数量；随后，结合缓冲器重选位算法对局部时钟偏差进行精细控制.在自顶向下阶段，首先通过理论推导证明沿路径均匀插入特定数量缓冲器可使时钟延迟最小化，并基于此构建了查找表以指导缓冲器的最优插入.随后，本文将版图沿时钟源垂直划分为两个对称的半区，在每个半区内构建四分支的类H树结构.该结构不仅应用长路径缓冲器插入算法来最小化全局时钟延迟，还利用其对称性对对称路径上的缓冲器进行合并，在保证低时钟偏差和低延迟的同时，进一步优化了缓冲器数量.最后，针对综合过程中可能出现违反约束的情况，本文先基于布尔运算提取了缓冲器的可插入点，再根据曼哈顿矩形的性质确定了缓冲器的最优放置点.本文算法在1×10

-2×10

数量触发器规模的电路进行实例验证，结果表明本算法优势显著.相较于OpenROAD，时钟偏差与功耗分别降低32.3%和29.9%；相较于GH-Tree，时钟偏差与功耗分别降低59.9%和28.9%，同时全局时钟延迟均保持在同一水平．

Abstract

In very large scale integration (VLSI) design

efficient clock tree synthesis (CTS) is crucial for ensuring circuit performance and reliability. To address the co-optimization challenge of clock skew

latency

and power consumption in large-scale circuits

this paper proposes an efficient CTS method based on a bi-partition

four-branch H-like tree. In the bottom-up phase

the method first employs a greedy-based clustering (GBC) algorithm to enhance the fanout utilization of low-level buffers

significantly reducing the number of

inserted buffers. Subsequently

it incorporates a buffer re-placement algorithm for the fine-grained control of local clock skew. During the top-down phase

it is first theoretically proven that uniformly inserting a specific number of buffers along a path minimizes clock latency

and a look-up table is constructed based on this principle to guide optimal buffer insertion. Next

the layout is vertically divided into two symmetrical half-regions from the clock source

and a four-branch H-like tree structure is constructed within each half-region. This structure not only applies the long-path buffer insertion algorithm to minimize global clock latency but also leverages its symmetry to merge buffers on symmetrical paths

further optimizing the buffer count while ensuring low clock skew and latency. Finally

to handle potential constraint violations during synthesis

the method first extracts insertable locations for buffers based on Boolean operations and then determines their optimal placement according to the properties of Manhattan rectangles. The proposed algorithm is validated on circuit instances with 1×10

to 2×10

flip-flops

and the results demonstrate its significant advantages. Compared to OpenROAD

our method reduces clock skew and power consumption by 32.3% and 29.9%

respectively. In comparison with GH-Tree

it achieves reductions of 59.9% in clock skew and 28.9% in power consumption

while maintaining a comparable global clock latency.

关键词

Keywords

references

TENG S K , SOIN N . Low power clock gates optimization for clock tree distribution [C ] // 2010 11th International Symposium on Quality Electronic Design . Piscataway : IEEE , 2010 : 488 - 492 .

千路 , 林平分 . ASIC后端设计中的时钟偏移以及时钟树综合 [J ] . 半导体技术 , 2008 , 33 ( 6 ): 527 - 529 .

QIAN L , LIN P F . Clock skew and clock tree synthesis in ASIC backend design [J ] . Semiconductor Technology , 2008 , 33 ( 6 ): 527 - 529 . (in Chinese)

张祥 , 赵启林 . 基于缓冲器的ASIC芯片时序优化设计 [J ] . 集成电路与嵌入式系统 , 2024 , 24 ( 12 ): 33 - 37 .

ZHANG X , ZHAO Q L . Timing optimization design of ASIC chip based on buffer [J ] . Integrated Circuits and Embedded Systems , 2024 , 24 ( 12 ): 33 - 37 . (in Chinese)

TSAI J L , ZHANG L Z , CHEN C C . Statistical timing analysis driven post-silicon-tunable clock-tree synthesis [C ] // IEEE/ACM International Conference on Computer-Aided Design . Piscataway : IEEE , 2005 : 575 - 581 .

PULLELA S , MENEZES N , OMAR J , et al . Skew and delay optimization for reliable buffered clock trees [C ] // Proceedings of International Conference on Computer Aided Design . Piscataway : IEEE , 2002 : 556 - 562 .

KUZMIN P A . Comparative analysis of the characteristics of clock network structures buffer tree, H-tree, clock mesh for technological nodes 28nm and 90nm [C ] // 2024 IEEE 25th International Conference of Young Professionals in Electron Devices and Materials . Piscataway : IEEE , 2024 : 270 - 279 .

ABDELHADI A , GINOSAR R , KOLODNY A , et al . Timing-driven variation-aware synthesis of hybrid mesh/tree clock distribution networks [J ] . Integration , 2013 , 46 ( 4 ): 382 - 391 .

CONG J , KAHNG A B , KOH C K , et al . Bounded-skew clock and steiner routing [J ] . ACM Transactions on Design Automation of Electronic Systems , 1998 , 3 ( 3 ): 341 - 388 .

PAPA D , ALPERT C , SZE C , et al . Physical synthesis with clock-network optimization for large systems on chi-ps [J ] . IEEE Micro , 2011 , 31 ( 4 ): 51 - 62 .

CHAO T H , HSU Y C , HO J M , et al . Zero skew clock routing with minimum wirelength [J ] . IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing , 1992 , 39 ( 11 ): 799 - 814 .

SHIH X W , CHANG Y W . Fast timing-model independent buffered clock-tree synthesis [C ] // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . Piscataway : IEEE , 2012 : 1393 - 1404 .

曾璇 , 周丽丽 , 黄晟 , 等 . 时钟延时及偏差最小化的缓冲器插入新算法 [J ] . 电子学报 , 2001 , 29 ( 11 ): 1458 - 1462 .

ZENG X , ZHOU L L , HUANG S , et al . A novel buffer insertion algorithm for clock delay and skew minimization [J ] . Acta Electronica Sinica , 2001 , 29 ( 11 ): 1458 - 1462 . (in Chinese)

WANG H H , LEI Q Q , YANG Y F , et al . A clock tree synthesis scheme based on flexible H-tree [C ] // 2022 2nd International Conference on Electrical Engineering and Mechatronics Technology . Piscataway : IEEE , 2022 : 249 - 252 .

HAN K , KAHNG A B , LI J J . Optimal generalized H-tree topology and buffering for high-performance and low-power clock distribution [J ] . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2020 , 39 ( 2 ): 478 - 491 .

LI W G , HUANG Z P , YU B , et al . iCTS: Iterative and hierarchical clock tree synthesis with skew-latency-load tree [J ] . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2024 , 44 ( 10 ): 3948 - 3961 .

DING J H , WEN J Z , TANG H , et al . An effective and efficient cross-link insertion for non-tree clock network synthesis [C ] // 2025 Design , Automation & Test in Europe Conference . Piscataway : IEEE , 2025 : 1 - 7 .

ISMAIL Y I , FRIEDMAN E G , NEVES J L . Equivalent elmore delay for RLC trees [C ] // Proceedings of the 36th annual ACM/IEEE Design Automation Conference . New York : ACM , 1999 : 715 - 720 .

EDAHIRO M . A clustering-based optimization algorithm in zero-skew routings [C ] // Proceedings of the 30th international Design Automation Conference . New York : ACM , 1993 : 612 - 616 .

NIU F F , ZHOU Q , YAO H L , et al . Obstacle-avoiding and slew-constrained buffered clock tree synthesis for skew optimization [C ] // Proceedings of the 21st Edition of the Great Lakes Symposium on Great Lakes Symposium on VLSI . New York : ACM , 2011 : 199 - 204 .

DENG C , CAI Y C , ZHOU Q . Register clustering methodology for low power clock tree synthesis [J ] . Journal of Computer Science and Technology , 2015 , 30 ( 2 ): 391 - 403 .

AJAYI T , BLAAUW D . OPENROAD: Toward a self-driving, open-source digital layout implementation tool chain [C ] // Proceedings of Government Microcircuit Applications and critical Technology Conference . Virginia : Defense Technical Information Center , 2019 : 1105 - 1110 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Novel Buffer Insertion Algorithm for Clock Delay and Skew Minimization

Design of n-bit Full Adder Based on Quantum-Dot Cellular Automata

Simultaneous Routing and Buffer Insertion Under Fixed Buffer Locations Based on Accurate Delay Models

Related Author

ZENG Xuan

ZHOU Li-li

HUANG Sheng

ZHOU Dian

LI Wei

ZHANG Yong-qiang

XIE Guang-jun

ZHANG Hui

Related Institution

Department of Electronic Engineering,Fudan University

Department of Electronic Engineering,The University of Texas at Dallas,Richardson,TX 75083,U.S.

Department of Electronic EngineeringFudan UniversityShanghai 200433China

Department of Electronic EngineeringThe University of Texas at DallasRichardsonTX 75083U.S.

School of Microelectronics，Hefei University of Technology

⁰