一种基于多约束的多级聚类方法与流程

本发明涉及集成电路，具体涉及一种基于多约束的多级聚类方法。

背景技术：

1、随着集成电路制造工艺向先进节点演进，片上系统（soc）设计规模与复杂度呈指数级增长，现代高性能芯片通常集成数百个存储器、模拟ip、处理器核等宏模块。宏模块布局作为物理设计的核心初始环节，直接定义芯片物理框架，决定后续标准单元布局区域、电源网格分布及布线资源分配，深刻影响芯片性能、功耗与面积（ppa）指标。当前主流宏模块布局技术主要分为两类：一类是传统扁平化布局技术，将所有宏模块与标准单元视为同等粒度单元，以最小化半周长线长为核心目标，通过模拟退火、划分法、解析法等求解全局位置，代表性成果包括timber wolf、capo及ntuplace系列布局方案。另一类是层次化布局技术，基于分而治之策略通过聚类将宏模块分组，先完成簇级布局再细化簇内排布，典型方案如hier-rtlmp算法、remap布局方法等，目前已成为超大规模芯片宏模块布局的核心技术方向。

2、现有技术中，传统扁平化布局技术规模适配性差，面对千万门级以上大规模设计，计算复杂度随设计规模非线性上升，布局运行时间过长甚至内存溢出；且仅以几何线长为优化目标，缺乏设计意图感知，易切断关键数据通路引发时序违例与布线拥塞，同时多约束兼容能力弱，难以同时处理多维度约束，后期人工调整成本高。现有层次化布局技术则聚类约束来源单一，多仅基于网表连通性或单一层级信息构建聚类规则，无法兼容多维度设计约束；且异质约束缺乏统一度量体系，难以实现协同加权与优先级裁决；同时多级聚类未将约束层级属性与聚类深度对应，高优先级约束无法在聚类顶层得到保障，易出现约束违例，难以满足先进工艺的复杂设计需求。

3、基于此，需要一种新技术方案。

技术实现思路

1、有鉴于此，本发明实施例提供一种基于多约束的多级聚类方法，以至少解决建议的聚类方法难以处理多维度约束的问题。

2、本发明实施例提供以下技术方案：

3、本发明实施例提供一种基于多约束的多级聚类方法，包括：

4、获取输入数据，所述输入数据包括若干宏模块；

5、基于所述输入数据提取所述宏模块之间的多维度邻近约束，得到多源邻近约束集合；

6、按照预设的优先级从高到低的顺序，将所述多源邻近约束集合中的各所述邻近约束依次与已有的硬约束结构进行冲突校验，以剔除与所述硬约束结构存在重叠冲突或完全冗余的所述邻近约束；

7、将校验通过的所述邻近约束合并至所述硬约束结构中，生成与所述硬约束结构无冲突的合并约束集合；

8、根据所述合并约束集合中各所述邻近约束之间的包含关系或等价关系构建有向无环图，并对所述有向无环图进行拓扑排序；

9、为每条所述邻近约束分配对应的层级编号，得到层次化约束结构；

10、将带有所述层级编号的所述层次化约束结构应用于所述宏模块的多级聚类布局流程，使所述层次化约束结构的优先级层级与多级聚类深度相匹配。

11、进一步地，所述输入数据还包括线网集合以及设计层次结构树；

12、所述多维度邻近约束包括：

13、用户约束，所述用户约束为由设计人员显式指定的宏模块邻近约束；

14、阵列约束，所述阵列约束为基于所述宏模块的类型、几何尺寸、对称属性和端口定义进行特征匹配后，由属性完全一致的所述宏模块构成的邻近约束；

15、层级约束，所述层级约束为从所述设计层次结构树中提取的、同一父模块下的子模块之间的邻近约束；

16、位置约束，所述位置约束为基于所述宏模块在前期布局中的物理坐标进行二维空间聚类得到的邻近约束；

17、数据流约束，所述数据流约束为基于所述线网集合中模块间的数据交互强度提取的邻近约束。

18、进一步地，所述预设优先级从高到低的顺序依次为：所述用户约束优先级最高，其次为所述阵列约束，再次为所述层级约束，再次为所述位置约束，所述数据流约束优先级最低。

19、进一步地，优先级最低的所述数据流约束采用增量式方式合并至所述硬约束结构中：将所有所述数据流约束按数据流强度从高到低排序，逐条融入已有的所述层次化约束结构，插入过程中不调整已有的约束层级关系。

20、进一步地，所述阵列约束的提取步骤包括：

21、将所有所述宏模块按预设的最高层级进行分组；

22、对每一分组内的所述宏模块，提取每一所述宏模块的特征向量，所述特征向量包括宏模块类型、宽度、高度、对称属性和端口定义；

23、将每一所述分组内所述特征向量完全一致且所述宏模块数目不小于2的宏模块子集作为一条所述阵列约束输出。

24、进一步地，所述层级约束的提取步骤包括：

25、自底向上遍历所述设计层次结构树，过滤已被所述用户约束和所述阵列约束包含的宏模块；

26、对于每一层次节点下的宏模块集合，添加一条层级约束；

27、若某一所述层级约束中包含的宏模块总数n超过预设上限值n_max，则将所述层级约束拆分为k组，其中k=n/n_max，每组包含的宏模块数量不超过s=n/k，确保拆分后每一分组的宏模块数量不超过n_max。

28、进一步地，所述位置约束的提取步骤包括：

29、过滤已被所述用户约束、所述阵列约束和所述层级约束包含的所述宏模块；

30、对剩余的所述宏模块执行二维空间聚类，所述二维空间聚类包括水平方向聚类和垂直方向聚类，所述水平方向聚类按所述宏模块的水平中心点坐标升序排序，以排序后首个宏模块的水平中心点坐标为起点，将水平中心点坐标与自身起点之差不超过水平间距阈值dis_thx的连续宏模块划分至同一水平分组；所述垂直方向聚类为对每一所述水平分组内的所述宏模块，按垂直中心点坐标升序排序，以所述水平分组内首个宏模块的垂直中心点坐标为起点，将垂直中心点坐标与自身起点之差不超过垂直间距阈值dis_thy的连续宏模块划分至同一空间聚类簇；

31、将每一所述空间聚类簇作为一条所述位置约束输出。

32、进一步地，所述数据流约束的提取步骤如下：

33、对于所述线网集合中的单条线网netk，设所述线网netk权重为wk，所连接的引脚数为p_num(netk)，则所述线网上任意两个引脚之间的数据流强度为：

34、dfk=wk/(p_num(netk)-1)；

35、对于任意两个宏模块，记为宏模块a和宏模块b，所述宏模块a和所述宏模块b之间的数据流强度df(a，b)为连接所述宏模块a和所述宏模块b的所有线网的数据流强度之和；

36、df(a，b)=σ{netk∈net，ma，mb∈netk}dfk

37、其中，求和条件表示对所有同时连接所述宏模块a和所述宏模块b的线网求和；

38、将所述数据流强度df(a，b)超过预设数据流强度阈值th_df的所述宏模块作为一条所述数据流约束输出。

39、进一步地，所述按照预设的优先级从高到低的顺序，将所述多源邻近约束集合中的各所述邻近约束依次合并至已有的硬约束结构中包括：

40、将已有的所述硬约束结构作为高优先级硬约束集合，将当前轮次待合并的所述邻近约束作为低优先级软约束集合；

41、针对所述低优先级软约束集合中的每条所述邻近约束，校验所述邻近约束与所述高优先级硬约束集合中各所述硬约束的集合关系；

42、若所述低优先级的当前所述邻近约束与所述高优先级硬约束集合中的任意一条硬约束存在重叠关系或等价关系，则剔除当前所述邻近约束；其中，所述重叠关系为两条约束所涵盖的宏模块集合存在交集但互不包含，所述等价关系为两条约束所涵盖的宏模块集合完全相同；

43、将校验通过的所述邻近约束与所述高优先级硬约束集合进行并集运算，得到当前轮次的所述合并约束集合；

44、将每一轮合并得到的所述合并约束集合作为下一轮合并的高优先级硬约束集合，直至所有优先级的所述邻近约束全部完成合并。

45、进一步地，所述根据所述合并约束集合中各所述邻近约束之间的包含关系构建有向无环图，并对所述有向无环图进行拓扑排序包括：

46、遍历所述合并约束集合中的每一对所述邻近约束，判断两条所述邻近约束各自涵盖的宏模块集合之间的集合关系；

47、若两条所述邻近约束之间为包含关系或等价关系，则在两条所述邻近约束对应的节点之间添加由上层约束指向下层约束的有向边，构建得到所述有向无环图；其中，所述包含关系为一条约束所涵盖的宏模块集合完全包含另一条约束所涵盖的宏模块集合，所述等价关系为两条约束所涵盖的宏模块集合完全相同。

48、进一步地，所述为每条所述邻近约束分配对应的层级编号，得到层次化约束结构包括：

49、采用逐层递进的方式对所述有向无环图进行拓扑排序，并为每条所述邻近约束分配所述层级编号；

50、初始化所述层级编号为0，每一轮将所述有向无环图中当前所有入度为0的节点分配当前的所述层级编号，移除所述入度为0的节点以及与所述节点相连的有向边，并将所述层级编号递增，重复执行上述步骤直至所述有向无环图中的所有节点均分配有所述层级编号；

51、其中，在所述包含关系中，作为包含方的上层约束所对应的所述层级编号小于作为被包含方的下层约束所对应的所述层级编号。

52、与现有技术相比，本发明实施例采用的上述至少一个技术方案能够达到的技术效果至少包括：

53、本发明的一种基于多约束的多级聚类方法，通过多维度邻近约束的自动提取与优先级驱动的冲突校验机制，能够有效融合用户定制、层级架构、数据流强度等异质约束并自动裁决冲突，剔除冗余与重叠约束，保障高优先级设计意图在合并约束集合中不被破坏；同时，基于集合间的包含与等价关系构建有向无环图并进行拓扑排序，为每条约束分配与包含层级相匹配的层级编号，使层次化约束结构的优先级层级与多级聚类深度精准对应，从而在大规模宏模块布局中实现分而治之的高效求解，从源头避免约束违例和后期迭代返工，显著提升芯片时序、拥塞、功耗与面积（ppa）指标，加速物理设计收敛。