# A Method for Synthesizing Ultra-Large-Scale Clock Trees
## 2 IB-KSR Algorithm
### Balanced Split
Step 5: Iterative merging: All newly inserted buffers are treated as the starting points for the next iteration of Step 1, and the above process is repeated until only one point remains directly connected to the clock source. The entire process requires \(O(log\ n)\) iterations. In summary, the overall time complexity can be estimated as \(O(\log n\cdot\left[k\cdot n\cdot\log n+m_{1}\cdot\log m_{1}+m_{2}\cdot\log m_{3 }+m_{5}\cdot\log m_{4}\right])\). Given that \(m_{1}<<n\), \(m_{2}<n\), \(m_{3}<<n\), \(m_{4}\approx n\) and \(m_{5}<<n\), the primary time cost is concentrated in the \(O(k\cdot n\cdot\log\ n)\) term. After considering the iterations, the overall complexity is approximately \(O\left(k\cdot n\cdot\left(log\ n\right)^{2}\right)\). In comparison, the time complexity of KSR in the simplest case can be as high as \(O\left(n^{2}\log(n)^{2}\right)\). The space complexity calculation is relatively straightforward. It primarily consists of the space required to store the graph, while other data structures occupy minimal space due to the use of pointer operations. The space complexity of the IB-KSR algorithm is approximately \(O(k\cdot n)\), whereas the KSR algorithm requires up to \(O\left(n^{2}\right)\). ## 4 Experiment

### Comparison Between IB-KSR and GSR

The authors utilized 10 sets of register placement data provided by the 2024 EDA Elite Challenge and implemented [PERSON]'s GSR algorithm to conduct a comparison with the IB-KSR algorithm in addressing ultra-large-scale clock tree synthesis. The testing platform was equipped with an Intel Core i7-11800 processor and 40 GB of memory. For the ten sets of register placement data, the IB-KSR algorithm demonstrated exceptional performance, as shown in Table 1. Compared to the GSR algorithm, the IB-KSR algorithm achieved a 43.4% improvement in global skew and a 34.3% improvement in average clock latency. This significant improvement came at the cost of only a 21.4% increase in the number of buffers. Another critical challenge in large-scale clock tree synthesis is the overlap issue between buffers and registers as well as between buffers themselves. To address this problem, the authors introduced an overlap detection mechanism during buffer insertion. Although IB-KSR and GSR share the same overlap detection strategy, GSR's structural characteristics limit the available selection space for the next-level nodes within a single clustering cluster. This limitation may make it difficult to find positions within the entire cluster where no overlap occurs. In contrast, IB-KSR significantly reduces the overlap rate by its tree-like distributed clustering strategy, demonstrating a 95.6% advantage in this metric. It should be noted that the performance improvement of the IB-KSR algorithm comes at the cost of increased program runtime with its synthesis time being approximately 87 times that of GSR. However, since the optimized algorithm can complete the synthesis within five minutes, the time consumption is still within an acceptable range. The primary reason for selecting GSR as a comparison target is that GSR and KSR share a common origin and both belong to clustering-based clock tree synthesis algorithms, which allows for a better demonstration of the improvements and innovations of IB-KSR within the same category of algorithms. Additionally, although GSR has existed for many years, it is considered a classic benchmark algorithm, and no direct improvements based on GSR for clock tree synthesis have been proposed to date. Therefore, GSR remains a meaningful point of comparison. Consequently, conducting performance comparisons between GSR and IB-KSR implementations in clock tree synthesis constitutes a technically valid and operationally meaningful evaluation framework. ### Comparison Between IB-KSR and KSR

To validate the performance of the IB-KSR algorithm in small- to medium-scale scenarios, the authors conducted a comparison with the KSR algorithm using a portion of benchmark data from ISPD 2010.