# A Method for Synthesizing Ultra-Large-Scale Clock Trees
They proved the equivalence between the wirelength minimization of the ZST and the diameter sum minimization of hierarchical clustering, and they proposed better algorithms for both the ZST and BST [6; 7]. [PERSON] et al. [8] introduced the skew-latency-load tree, which combines the merits of the BST and Steiner shallow-light tree. In addition, they provided a hierarchical CTS framework, and it is constructed by integrating partition schemes and buffering optimization techniques [8]. [PERSON] et al. [9] present the definition of bounded slew merging regions that are a conceptual shift in satisfying slew constraints during CTS. This major conceptual shift extends the popular DME framework of the CTS literature for ease of adoption by proposing the novel SMRcts algorithm with slew merging regions [9]. In addition to DME-based algorithms, register-clustering-based algorithms represent another branch of thought in addressing the problem of clock tree synthesis. [PERSON] et al. [10] propose a modified K-means algorithm which effectively assigns flops into clusters at the clustering step. Then, at the relocation step, flops are actually relocated, and regularly structured clusters are formed. [PERSON] et al. [11] propose a dynamic programming-based method to determine optimal clock power, skew and latency in the space of generalized H-tree solutions. And they further propose a balanced K-means clustering and a linear programming-guided buffer placement approach to embed the generalized H-tree with respect to a given sink placement [11]. [PERSON] et al. [12] proposed a clock tree synthesis scheme based on flexible H-tree. To reduce the magnitude of the clock-induced on-chip variation, [PERSON] et al. [13] incrementally relocate the flip-flops and the clock gaters in a bottom-up manner to implicitly guide the clock tree synthesis engine to produce clock trees with increased common clock tree paths. [PERSON] et al. [14] have presented an unsupervised machine learning-based multi-bit flip-flop clustering and relocation frame work to address the clock network power reduction without impacting the performance of the design. [PERSON] et al. (2018) have improved the KMR algorithm and then proposed the K-splitting-based register clustering (KSR) algorithm. By introducing a register clustering strategy, KSR optimizes register distribution and reduces power consumption and latency in the clock tree network, achieving satisfactory results. By effectively clustering registers, KSR groups geographically close registers together, thereby reducing the total delay in clock distribution and lowering power consumption. Despite having excellent performance in power consumption optimization, KSR still faces numerous challenges when dealing with ultra-large-scale clock tree synthesis, particularly in designs with over 100,000 registers where it only stores the minimum spanning results. These challenges primarily stem from bottlenecks in computational resources and memory. Therefore, in response to the limitations of the KSR method in ultra-large-scale clock tree synthesis, this paper proposes an improved clock tree synthesis method, named IB-KSR. The IB-KSR method optimizes upon the traditional KSR method, aiming to effectively address the computational resource and memory constraints in ultra-large-scale clock tree synthesis while further enhancing the overall performance of the clock tree network. By improving the register clustering strategy and optimizing the clustering scale, IB-KSR is able to achieve efficient clock distribution in larger-scale designs while striking a better balance between timing and resource consumption. This approach brings fresh perspectives to tackle the challenges of ultra-large-scale clock tree synthesis and offers a more scalable and efficient solution for future clock network optimization. The authors mainly optimized the construction of the minimum spanning tree (MST) in the KSR algorithm by adopting the incomplete MST (IMST) technique, which significantly reduced the time complexity and space complexity.