Register Clustering Methodology for Low Power Clock Tree Synthesis

1.概要

背景

​ 一个时钟网络通常消耗整个芯片功率的40%。因此，许多研究者关注根据(1)中提出的参数对时钟网络进行功率优化。

KMR：基于k均值的寄存器聚类算法

KSR：基于k-分裂的寄存器聚类算法

GSR：基于贪婪搜索的寄存器聚类算法

2.算法描述

2.1KMR

2.2.1.伪中心（“Pseudo Center” ）

​ “伪中心”技术不仅避免了寄存器聚类算法的失败，而且还破坏了可能违反约束条件的大型聚类（包括旋转、最大扇出、最大负载电容等）。

2.2.2.Algorithm1 : Get center

​ 如果一个集合 \(C\) 是空集，那么他的中心点为最大集合的一半的点的几何中心；否则，则为该集合所有点的集合中心。

2.2.3 簇的个数

​ 相比K-Means算法，KMR算法根据以下公式确定簇的个数。

​ $ K = Total_r / Max_f $

​ \(Total_r\) 表示寄存器总数，\(Max_f\)表示缓冲器最大扇出，\(\alpha\) 为用户自定义参数，通常大于1。

2.2.4 算法流程

​ 首先计算出簇的个数\(K\)，初始化\(K\)个簇的中心点，开始迭代。每次迭代先将所有簇清空，然后计算出每个点到每个簇的距离，将其分配到离他最近的簇中；全部分配完之后，重新计算簇的中心点，开始下一轮迭代，直到总线长不再减少为止。

2.2.5 小结

​ 白看半天，其实跟K-Means算法一样，只是多了一个计算K的方法。

2.2 KSR

​ KMR没有考虑寄存器的分布，选择一个不合适的\(K\)，结果会很糟。

​ 首先选取最小生成树方法生成一个初始聚类，然后再使用MSR方法迭代优化。

2.3 GSR

​ 从1~n遍历所有寄存器，如果可以找到满足条件的中心，则将该寄存器插入到这个簇中，否则，将该寄存器设置为一个新的簇中心。

2.4 buffer allocation

​ buffer放置于每个簇的中心，但需要考虑中心点放buffer是否会与寄存器重叠问题，需要将buffer向上下左右移动微调。