# A Method for Synthesizing Ultra-Large-Scale Clock Trees
## 2 IB-KSR Algorithm
### Balanced Split  
During clock tree synthesis, buffers have certain fan-out limitations. This limitation, when reflected in the clustering algorithm, means that an upper limit needs to be set for the size (number of nodes) of a single cluster. Many additive clustering algorithms can effectively enforce this constraint. For example, the GSR algorithm starts with an initial cluster and gradually adds nodes to it. When the cluster size reaches the set limit, it is easy to terminate the expansion of the current cluster and create a new cluster to continue adding nodes. This method provides real-time control over the size in an incremental manner, making it very intuitive. Alternatively, for the KSR algorithm, the clusters are generated by cutting a tree. Specifically, KSR generates multiple clusters by cutting edges to divide a single tree into two subtrees. In KSR, the number of clusters is controlled by a parameter. A threshold edge length is calculated using Equation (1), and the algorithm cuts all edges with weights greater than this threshold to generate the target number \(k\) of clusters. In Equation (1), Width and Length are the width and the length of the layout, respectively, \(Size_{ob}\) is the total size of the obstacles on the layout, \(Num_{registers}\) is the total number of the registers on the layout, and \(\alpha\) is a user-defined parameter to control the amount of clusters to be generated [1]. However, this method only constrains the number of clusters rather than their size (number of nodes). Hence, the size of a single cluster is hardly controllable. Experiments have shown that in a clock tree containing 100,000 registers, the maximum cluster size in the initial clustering can reach several thousand nodes. Such excessively large clusters can cause significant pressure on subsequent clustering steps, making it difficult to meet the requirements of buffer fan-out limitations. \[EL=\alpha\times\sqrt{\frac{Width\times Length-Size_{ob}}{Num_{registers}}} \tag{1}\]  
In order to control cluster size, skew, and bus length simultaneously, the authors propose a balanced cutting technique. This technique is based on the principle that for any tree, there must exist an edge, cutting which divides the tree into two parts with the minimum size difference between them. We refer to this edge as the balancing edge. By cutting the balancing edge, the two resulting subtrees not only have the minimum size difference but also significantly reduce the overall size of the original tree. This method ensures size control while avoiding unnecessary skew and bus length increases due to excessive splitting. The implementation of this algorithm can be divided into two main steps. Firstly, a Breadth-First Search (BFS) is conducted starting from an arbitrary node to traverse the entire tree so as to update the parent node information for each node. This computational step is formalized as Algorithm 2, with its pseudocode structure detailed below. ```
1:\(\alpha\) = \(\alpha\



smallest discrepancy is selected as the balancing node. Eventually, the edge pointing from this node to its parent is identified as the balancing edge, thus achieving a balanced cut of the tree. This step is formalized as Algorithm 3 and described as follows. \[diff(u)=\Big{|}\frac{n}{2}-SubtreeSize[u]\Big{|} \tag{2}\]
```
Input: A tree represented by an edge set \(E=\{e(u,v)|u,v\in V\}\), where \(V\) is the set of nodes. Output: An array \(Parent[]\) for each node u, where \(Parent[u]\) represents the parent of node \(u\) in the tree. 1: Initialize \(Parent[]=\) NULL for all \(u\in V\). 2: Select an arbitrary node \(r\in V\) as the root of the tree. 3: Create an empty queue \(Q\). 4: Enqueue the root \(r\) into \(Q\). 5: While\(Q\) is not empty:
6:  Dedqueue a node \(u\) from \(Q\). 7:  For each adjacent node \(v\) of \(u\) such that \(Parent[v]=\) NULL
8:  Set \(Parent[v]=u\). 9:  Enqueue \(v\) into \(Q\). 10: End For
11: End While
12: Return the \(Parent[]\) array.