# A Method for Synthesizing Ultra-Large-Scale Clock Trees
## 2 IB-KSR Algorithm
### Balanced Split
## 3 Applicability and Complexity of the IB-KSR Algorithm

### Applicability

The IB-KSR algorithm is suitable for very large-scale clock tree synthesis (with \(>\)100 \(k\) nodes). It leverages the initial construction of an IMST to effectively avoid excessive computational resource consumption. The IMST explores the neighborhood topology information in the graph and stores this information in independent tree structures. Using Equation (1) for initial cutting allows neighboring nodes to naturally form clusters. Moreover, Equation (2) is utilized to further control the size of the clusters, effectively alleviating the fan-out pressure on the buffers. The IB-KSR algorithm not only endows the original KSR with the capability to handle ultra-large-scale clock tree synthesis but also retains the performance of the original KSR in the synthesis of small- to medium-scale clock trees (\(<\)1 k nodes). When the number of registers is relatively small, the structures generated by the IMST technique tend to closely resemble complete minimum spanning trees, causing the algorithm's behavior to gradually converge to that of the original KSR algorithm. The subsequent evaluation and validation phases will also demonstrate that the IB-KSR algorithm will exhibit significant advantages in ultra-large-scale clock tree synthesis while maintaining high performance in small- to medium-scale scenarios. Moreover, for scenarios requiring overlap control, overlap constraints can be incorporated into the DFS process. This effectively manages the overlap between buffers and registers, thereby enhancing the overall design quality. The IB-KSR algorithm demonstrates strong versatility, adapting to clock tree synthesis tasks of varying scales while delivering optimized results. ### Complexity

The IB-KSR algorithm primarily consists of five steps. Assuming the dataset contains \(n\) registers, the following derivation will be presented according to these five steps. Step 1: Constructing the initial connected graph (IMST technique): The initial connected graph is constructed using the IMST technique, with a time complexity of \(O(k\cdot n\cdot log\ n)\), where \(k\) represents the predefined number of nearest neighbors. Step 2: Edge cutting: Edge cutting is performed according to Equation (2). This step utilizes a max heap to manage edges that exceed the threshold. Let \(m_{1}\) represent the number of edges exceeding the threshold (where \(m_{1}<<n\)). Since each heap operation on an edge requires \(O(log\ m_{1})\) time, the time complexity of this step can be estimated as \(O(m_{1}\cdot log\ m_{1})\). Step 3: Balanced cutting (for trees exceeding the maximum fan-out limit, assuming the total number of edges is \(m_{2}\), where \(m_{2}<n\)): First, the nodes of these trees need to be traversed twice, requiring O(\(2m_{2}\)). Then, balanced cutting is performed on each subtree that exceeds the limit (let the number of such subtrees be \(m_{3}\), where \(m_{3}<<n\)). Each cutting operation involves an insertion operation in the max heap, taking \(O(log\ m_{3})\) time. Assuming all relevant edges need to be processed, the time complexity of this part is approximately \(O(m_{2}\cdot log\ m_{3})\). Therefore, the overall time complexity of Step 3 is approximately \(O(m_{2}+m_{2}\cdot log\ m_{3})\), which can be simplified to \(O(m_{2}\cdot log\ m_{3})\) when constants are ignored. Step 4: Buffer insertion point search: Each tree generated after balanced cutting is treated as a cluster. The search for buffer insertion points within each cluster is conducted using unidirectional pruning and overlap pruning techniques. Let the number of feasible candidate points in each cluster be \(m_{4}\) (where \(m_{4}\approx n\)), and let the number of clusters be \(m_{5}\) (where \(m_{5}<<n\)). The time complexity of this step is \(O(m_{5}\cdot log\ m_{4})\).