欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2025105873676
申请人: 南京邮电大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于聚类的时钟树综合方法,其特征在于,包括如下步骤:

(1)读取电路中寄存器的尺寸、数量和位置;

(2)将寄存器的坐标存入坐标集,对坐标集进行聚类生成若干个待处理簇,清空所述坐标集;在每个待处理簇中根据约束条件进行调整,直至满足约束条件,将每个待处理簇中的聚类中心的位置作为插入的第一级的缓冲器的位置;

所述约束条件包括最大扇出数限制约束和最大RC约束,对于不满足约束条件的待处理簇,将其中距离聚类中心最远的缓冲器剔除并重新分配待处理簇,若无法分配则将该缓冲器的坐标存入所述坐标集;所述最大RC约束为:计算,若其不大于最大RC限制,则满足最大RC约束,是缓冲器到聚类中心之间的曼哈顿距离,r和c分别为缓冲器到聚类中心之间连线的电阻值和电容值;

(3)将第一级的缓冲器的坐标存入所述坐标集,重复步骤(2)得到第二级的缓冲器的位置;

(4)通过DME算法对第二级的缓冲器进行时钟树的搭建,直至完成所述电路的时钟树综合,得到第三级至第N级的缓冲器的位置;

(5)输出时钟树综合方案,包括缓冲器的数量、位置及其连接关系;

步骤(2)中,还包括位置重叠约束,若缓冲器与寄存器位置重叠则移动所述缓冲器的位置,具体包括以下步骤:寄存器为尺寸的第一矩形,缓冲器为尺寸的第二矩形,以第一矩形的预设方向的顶点为基础向外拓展,形成尺寸为的第三矩形,第三矩形包含第一矩形且与第一矩形的第一顶角重合,第一顶角位于第一矩形的预设方向的对角位置;

判断第二矩形的预设方向的顶点是否在第三矩形内部,若在第三矩形内部则寄存器与缓冲器重叠,将所述第二矩形的预设方向的顶点移动至第三矩形上的安全线段上;

所述第三矩形上的安全线段的选择方法为:

判断该寄存器周围是否有其他寄存器,根据该寄存器形成的第三矩形称为目标第三矩形,根据该寄存器周围其他寄存器形成的第三矩形称为近邻第三矩形,若相交,则该寄存器周围有其他寄存器;在第三矩形的边界上剔除与近邻第三矩形相交的部分,并且剔除与第一矩形重合的部分后得到安全线段。

2.根据权利要求1所述的基于聚类的时钟树综合方法,其特征在于,步骤(2)中,若坐标集中的坐标数量大于最大扇出数,则采用Minibatch Kmeans聚类算法进行聚类,否则采用K-means聚类算法进行聚类。

3.根据权利要求2所述的基于聚类的时钟树综合方法,其特征在于,在MinibatchKmeans聚类算法中,聚类中的K值为:;

其中为坐标集中坐标的总数,为最大扇出数。

4.根据权利要求2所述的基于聚类的时钟树综合方法,其特征在于,在K-means聚类算法中采用肘部法确定K值。

5.根据权利要求1所述的基于聚类的时钟树综合方法,其特征在于,步骤(4)中,判断缓冲器的位置是否满足位置重叠约束,满足位置重叠约束后判断是否满足最大RC约束,若不满足则继续插入缓冲器,继续检测位置重叠约束和最大RC约束直至满足约束。

6.一种基于聚类的时钟树综合系统,其特征在于,包括:

数据读取单元,用于读取电路中寄存器的尺寸、数量和位置;

第一级缓冲器插入单元,用于将寄存器的坐标存入坐标集,对坐标集进行聚类生成若干个待处理簇,清空所述坐标集;在每个待处理簇中根据约束条件进行调整,直至满足约束条件,将每个待处理簇中的聚类中心的位置作为插入的第一级的缓冲器的位置;

所述约束条件包括最大扇出数限制约束和最大RC约束,对于不满足约束条件的待处理簇,将其中距离聚类中心最远的缓冲器剔除重新并分配待处理簇,若无法分配则将该缓冲器的坐标存入所述坐标集;所述最大RC约束为:计算,若其不大于最大RC限制,则满足最大RC约束,是缓冲器到聚类中心之间的曼哈顿距离,r和c分别为缓冲器到聚类中心之间连线的电阻值和电容值;

第二级缓冲器插入单元,用于将第一级的缓冲器的坐标存入所述坐标集,重复第一级缓冲器插入单元得到第二级的缓冲器的位置;

后续缓冲器插入单元,用于通过DME算法对第二级的缓冲器进行时钟树的搭建,直至完成所述电路的时钟树综合,得到第三级至第N级的缓冲器的位置;

时钟树综合方案输出单元,用于输出时钟树综合方案,包括缓冲器的数量、位置及其连接关系;

第一级缓冲器插入单元中,还包括位置重叠约束,若缓冲器与寄存器位置重叠则移动所述缓冲器的位置,具体包括以下步骤:寄存器为尺寸的第一矩形,缓冲器为尺寸的第二矩形,以第一矩形的预设方向的顶点为基础向外拓展,形成尺寸为的第三矩形,第三矩形包含第一矩形且与第一矩形的第一顶角重合,第一顶角位于第一矩形的预设方向的对角位置;

判断第二矩形的预设方向的顶点是否在第三矩形内部,若在第三矩形内部则寄存器与缓冲器重叠,将所述第二矩形的预设方向的顶点移动至第三矩形上的安全线段上;

所述第三矩形上的安全线段的选择方法为:

判断该寄存器周围是否有其他寄存器,根据该寄存器形成的第三矩形称为目标第三矩形,根据该寄存器周围其他寄存器形成的第三矩形称为近邻第三矩形,若相交,则该寄存器周围有其他寄存器;在第三矩形的边界上剔除与近邻第三矩形相交的部分,并且剔除与第一矩形重合的部分后得到安全线段。

7.根据权利要求6所述的基于聚类的时钟树综合系统,其特征在于,所述第一级缓冲器插入单元中,若坐标集中的坐标数量大于最大扇出数,则采用Minibatch Kmeans聚类算法进行聚类,否则采用K-means聚类算法进行聚类;

在Minibatch Kmeans聚类算法中,聚类中的K值为:

;

其中为坐标集中坐标的总数,为最大扇出数;

在K-means聚类算法中采用肘部法确定K值。

8.一种电子设备,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序,其特征在于,所述计算机程序被加载至处理器时实现根据权利要求1-5任一项所述的基于聚类的时钟树综合方法。

9.一种计算机可读存储介质,所述计算机可读存储介质存储有计算机程序,其特征在于,所述计算机程序被处理器执行时实现根据权利要求1-5任一项所述的基于聚类的时钟树综合方法。