1.基于同步并发和分级聚类的时钟树综合方法,其特征在于,包括如下步骤:
步骤S1,根据布局文件读取所有寄存器以及时钟源的物理信息,按照寄存器数量、可用线程数量得到粗聚类目标分组数量和单组寄存器数量阈值;
步骤S2,根据单组寄存器数量阈值,利用KmeansPlus算法对读入寄存器进行粗聚类分组,判断每组寄存器数量是否小于单组寄存器数量阈值,小于阈值则返回结果用于细聚类,否则重新进行粗聚类直到分组结果小于单组寄存器数量阈值;
步骤S3,提取步骤S2中的分组结果,结合该组寄存器数量和实例化汇聚点所使用的缓冲器Buffer的最大扇出max_fanout得到细聚类分组数量divide_number,对所有寄存器组群应用同步并发的KmeansPlus算法进行细聚类;
步骤S4,提取步骤S3中的细聚类汇聚点坐标,结合实例化该汇聚点所使用缓冲器的尺寸,判断是否和所连接的子寄存器发生重叠Overlap,并且计算汇聚点坐标与所连接寄存器之间的线长,判断每条路径是否超过最大线长约束,满足要求则为每个细聚类后的组群汇聚点使用缓冲器Buffer将其实例化,本级所有缓冲器Buffer作为下一级聚类的输入;
步骤S5,提取步骤S4实例化之后的缓冲器作为第一级综合结果,该级所有实例化后的缓冲器作为第二级的叶子节点输入KmeansPlus算法进行第二级粗聚类,迭代进行步骤S1至步骤S5,进行从寄存器到时钟源自下而上的层次聚类,逐级连接叶子节点与实例化后的汇聚节点,直至最后一级节点汇聚到时钟源。
2.根据权利要求1所述的基于同步并发和分级聚类的时钟树综合方法,其特征在于,所述步骤S1按照寄存器数量、可用线程数量得到目标分组数量和单组寄存器数量阈值的具体方法为:根据可用线程数和每条线程处理的组数计算出目标分组数量,再根据总的寄存器数量和目标分组数量计算出单组寄存器数量阈值。
3.根据权利要求1所述的基于同步并发和分级聚类的时钟树综合方法,其特征在于,所述步骤S2将寄存器insts、单组寄存器数量阈值n、迭代次数T、随机种子值seed输入KmeansPlus方法进行粗聚类。
4.根据权利要求3所述的基于同步并发和分级聚类的时钟树综合方法,其特征在于,所述步骤S2进行粗聚类使用的KmeansPlus算法具体如下:建立随机生成器gen;从众多insts中随机选择一个inst作为中心点;计算其余insts距离该中心点的曼哈顿距离,找到与该中心点曼哈顿距离最远的inst作为新的中心点,直到找到n个中心点;遍历剩余insts,将其归纳入最近的中心点作为一组;返回构建好的组群。
5.根据权利要求1所述的基于同步并发和分级聚类的时钟树综合方法,其特征在于,所述步骤S3利用步骤S2的粗聚类分组结果,根据每组寄存器数量、所使用缓冲器Buffer的最大扇出max_fanout、缩放比例ratio确定细聚类组群数divide_number,将单组寄存器insts、组群数divide_number、迭代次数T、随机种子值seed输入同步并发KmeansPlus方法进行细聚类,寄存器通过细聚类任务加入线程池进行多线程处理,设定聚类返回值为共享数据,对共享数据进行加锁以保护数据。
6.根据权利要求1所述基于同步并发和分级聚类的时钟树综合方法,其特征在于,所述步骤S4提取步骤S3每组KmeansPlus方法细聚类得到的汇聚点,将汇聚点实例化为缓冲器Buffer作为本级时钟树聚类结果,本级所有细聚类结果得到的缓冲器Buffer作为时钟树下一级的叶子节点。
7.根据权利要求1所述基于同步并发和分级聚类的时钟树综合方法,其特征在于,所述步骤S5提取步骤S4的实例化缓冲器作为分级时钟树综合的第一级结果,该级所有实例化后的缓冲器作为第二级时钟树的叶子节点输入,从第二级叶子节点开始直到时钟源的前一级,所有的汇聚点都是缓冲器Buffer,说明从第二级开始粗聚类、细聚类的输入为缓冲器Buffer,此时每一级信息相应的替换为缓冲器信息即可。
8.根据权利要求1所述基于同步并发和分级聚类的时钟树综合方法,其特征在于,所述步骤S5通过分级时钟树综合,对每一级叶子节点进行粗聚类、细聚类得到汇聚节点,直到汇聚节点数量为1,说明该汇聚节点实例化后的缓冲器为时钟源的子单元,连接时钟源则完成时钟树综合。
9.一种计算机可读存储介质,其上存储有计算机程序,其特征在于,所述计算机程序运行时执行权利要求1至8任意一项所述的时钟树综合方法的步骤。