# A Method for Synthesizing Ultra-Large-Scale Clock Trees
## 2 IB-KSR Algorithm
### Balanced Split
```
**Algorithm 2** Parent Node Update
```
Input: A tree represented by an edge set \(E=\{e(u,v)|u,v\in V\}\) and the \(Parent[]\) array obtained from the Parent Node Update algorithm. Output: A balanced edge \(e_{b}=(u,Parent[u])\), which minimizes the size difference between the two subtrees when the edge is cut. 1: Let \(n=|V|\) be the number of nodes in the tree. 2: For each node \(u\in V\), Initialize \(SubtreeSize[u]=1\). End For
3: Let \(Leaves=\{u\in V|\text{degree}(\text{u})=1\cap u\
eq r\}\), which is the set of leaf nodes. 4: While\(Leaves\
eq 0\):
5:  Dedqueue node \(u\) from Leaves. 6:  Let \(p=Parent[u]\), the parent of \(u\). 7:  Update \(SubtreeSize[p]+=SubtreeSize[u]\). 8:  Remove edge \(e(u,p)\). 9:  If \(p\) becomes a leaf, add \(p\) to Leaves. 10: End While
11: Initialize \(diff_{\text{min}}=\infty,e_{b}=\) NULL. 12: For each node \(u\in V\):
13:  Compute \(diff(u)\) with Equation(2). 14:  If \(diff(u)<diff_{\text{min}}\), update \(diff_{\text{min}}\) and \(e_{b}=(u,Parent[u])\). 15: End For
16: Return the balanced edge \(e_{b}\). ```
**Algorithm 3** Balanced Edge identification

### Detail of IB-KSR

The IB-KSR algorithm is an improved version based on the KSR algorithm. The algorithm first generates an IMST based on the input set of registers. Then, it calculates the threshold EL using Equation (1) and prunes the edges in the IMST with weights greater than EL, resulting in an initial tree structure. Next, for trees with degrees exceeding the maximum fan-out of the buffers, a balanced cut operation is performed to generate initial clusters. For each cluster, the IB-KSR algorithm employs a heuristic Depth-First Search (DFS) algorithm to search for the optimal buffer insertion locations in order to balance the skew and total wire length of the clock tree. The inserted buffers will serve as the starting points for the next layer of clustering. This process continues until all clustering is completed, ultimately forming a complete clock tree. The complete IB-KSR algorithm, designated as Algorithm 4, is outlined as follows. ```
0: A set of registers \(S_{register}=\{r_{1},r_{2},\ldots,r_{n}\}\) with the location \((x_{r_{i}},y_{r_{i}})\) for register \(r_{i}\) and maxfound. 0: A complete clock tree. 1: Convert the register information \(S_{register}=\{r_{1},r_{2},\ldots r_{n}\}\) with locations \((x_{r_{i}},y_{r_{i}})\) into a set of points \(P=\{(x_{r_{1}},y_{r_{1}}),(x_{r_{2}},y_{r_{2}}),\ldots,(x_{r_{n}},y_{r_{n}})\}\). 1: While\(P.\text{size}()>0\)
2: Generate IMST \(E_{IMST}=\text{IMST}(P)\). (Algorithm 1)
3: Calculate \(WL\) with Equation (1). 4: Cut edges with weight \(w(e)>EL\), \(E_{IMST}=\text{CutEdges}(E_{IMST},EL)\). 5: Initialize Max-Heap \(H=\text{Heap}_{\text{max}}(E_{IMST})\)
6: While\(H.\text{top.size}>\text{maxfound}\):
7: Extract max tree \(E_{\text{max}}=H.\text{pop}()\)
8: Perform Parent Node Update on \(E_{\text{max}}\), ParentNodeUpdate\((E_{\text{max}})\). (Algorithm 2)
9: Perform Balanced Edge identification, \(e_{balance}=\text{BalancedEdgelIdentification}(E_{\text{max}})\). (Algorithm 3)
10: Split \(E_{\text{max}}\) at \(e_{balance}\), create new two trees \(E_{1},E_{2}\). 11: \(H.\text{push}(E_{1},E_{2})\). 12: End While
13: Initialize \(Points_{next}=\text{NULL}\). 14: For each cluster \(C\in H\)
15: Perform DFS on \(C\) to find the optimal buffer insertion node \(r_{b}\). 16: \(r_{b}.children.\text{push}(C)\)
17: \(Points_{next}\text{push}(r_{b})\). 18: End For
19: Update \(Points=Points_{next}\). 20: End While
21: Return clock tree \(Tree_{clock}=\text{Extract}ClockTree(Points)\). ```

**Algorithm 4** IB-KSR

The core idea of the heuristic DFS search algorithm is to prune in unnecessary directions. Specifically, we assume that moving the insertion point in a single direction will monotonically affect the skew of the clock tree. Therefore, during each recursive process, the algorithm will prune those directions that would lead to an increase in skew. The time complexity of the algorithm is \(O(\log(n))\), where n is the number of candidate insertion points.