(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202211121484.6 (22)申请日 2022.09.15 (65)同一申请的已公布的文献号 申请公布号 CN 115202661 A (43)申请公布日 2022.10.18 (73)专利权人 深圳大学 地址 518060 广东省深圳市南 山区南海大 道3688号 (72)发明人 徐鹏飞　李一帆　杨之瑾　施蔚然　 黄惠　 (74)专利代理 机构 深圳市君胜知识产权代理事 务所(普通 合伙) 44268 专利代理师 陈专 (51)Int.Cl. G06F 8/38(2018.01) G06F 9/451(2018.01)G06F 17/12(2006.01) (56)对比文件 CN 113688593 A,2021.1 1.23 CN 111625235 A,2020.09.04 CN 101339571 A,20 09.01.07 CN 113420804 A,2021.09.21 CN 111354076 A,2020.0 6.30 US 2019378010 A1,2019.12.12 US 2013107698 A1,2013.0 5.02 李煜 等.基 于O-TREE树表示的总线约束在 VLSI/PCB布局中的应用. 《成 都信息工程学院学 报》 .2005,第20卷(第0 3期), Alstrup, S 等.Ef ficient tre e layout in a multi level memory hierar. 《arXiv preprint cs》 .20 02, 审查员 黄帷 (54)发明名称 一种具有层次结构布局的混合生成方法及 相关设备 (57)摘要 本发明公开了一种具有层次结构布局的混 合生成方法及相关设备， 所述方法包括： 接收用 户输入的多个布局模板， 所述布局模板使用多叉 树结构表 示， 多叉树结构中的叶子节 点代表所述 布局模板中的单个元素， 根据节 点对应规则计算 元素之间的对应关系， 得到对应信息； 根据对应 信息建立一棵组合树， 基于所述组合树根据节点 类型并结合用户交互时产生的参数动态确定中 间状态元素以及元素之间应满足的关系； 将节点 的位置和大小作为软约束， 节 点之间应满足的关 系作为硬约束， 优化目标函数， 优化求解完成后 生成新的多样性布局。 本发明只需要输入少量的 布局模板而不需要大的数据集用于训练， 节约了 计算资源， 使得用户通过简单的交互就能够生成 出全新的多样性布局。 权利要求书5页 说明书10页 附图5页 CN 115202661 B 2022.11.29 CN 115202661 B 1.一种具有层次结构布局的混合生成方法， 其特征在于， 所述具有层次结构布局的混 合生成方法包括： 接收用户输入的多个布局模板， 所述布局模板使用多叉树结构表示， 所述多叉树结构 中的叶子节点代表所述布局模板中的单个元素， 根据 节点对应规则计算元素之 间的对应关 系， 得到对应信息； 根据对应信 息建立一棵组合树， 基于所述组合树根据节点类型并结合用户交互时产生 的参数动态确定中间状态元 素以及元 素之间应满足的关系； 将节点的位置和大小作为软约束， 节点之间应满足的关系作为硬约束， 优化目标函数， 优化求解完成后生成新的多样性布局； 所述节点对应规则包括第一对应规则、 第二对应规则、 第三对应规则和第四对应规则； 所述第一对应规则包括： 两个具有相似几何信息的叶子节点趋向对应在一 起； 两个具有相似子结构的分支 节点趋向对应在一 起； 两个具有不同语义信息的叶子节点 不能对应在一 起； 所述第二对应规则包括： 叶子节点和分支 节点允许对应为空； 所述第三对应规则包括： 如果两个分支节点 和 对应在一起， 则子树 中的节点只能对应子树 中的节点或者对应空； 所述第四对应规则包括： 两个处在不同层级的节点允许对应在一 起； 其中， 叶子节点的父节点 为分支节点； 所述根据节点对应规则计算元 素之间的对应关系， 得到对应信息， 之前还 包括： 使用递归的方法定义两个节点之间以及节点与空之间计算对应损失的函数； 两个叶子节点对应代价定义两个节点位置差的二范式加上大小差的二范式再加上一 个与语义信息相关的第一惩罚项 ， 第一惩罚项的引入使得两个语义信息不同 的节点不能对应在一 起， 为以下 形式： ； ； 其中， 和 分别表示两个叶子节点； 是计算两个叶子节点对应代价的函 数； 和 分别表示两个叶子节点的位置； 和 分别表示两个叶子节点的大小； 和 分别表示两个叶子节点对应的语义信息； 叶子节点对应空的代价 为该叶子节点对应一个大小为0的节点的损失， 具体权　利　要　求　书 1/5 页 2 CN 115202661 B 2为该节点大小与0 差的二范式再加上一个第二 惩罚项 ， 为： ； 其中， 设定 ； 分支节点对应空的代价定义 为该分支内所有叶子节点对应空的代价的累积和， 为： ； 其中， 是计算分支节点与空对应代价的函数， 是该分支节点下的叶子节 点； 分支节点对应叶子节点的代价： 递归调用计算损失方法来计算该分支节点的孩子节点 与叶子节点的代价， 计算该分支节点的孩子节点对空的代价以及叶子节点对空的代价； 用 计算出的代价值构建一个二维矩阵并通过匈牙利算法求解得到一个最小的损失以及最优 的匹配结果； 所述将节点的位置和大小作为软约束， 节点之间应满足的关系作为硬约束， 优化目标 函数， 具体包括： 当输入的参数值 小于0.5时， 用第一棵树中的关系， 否则， 用第二 树中的关系； 求解时将位置和大小作为软约束， 节点之间应满足的关系作为硬约束， 要优化的目标 函数如下： ； 其中， 是度量位置差的能量方程， 是度量大小差的能量方程； ； ； 其中， 是中间状态树中的一个节点； 代表该节点要求解的位置量； 代表该节 点要求解的大小值； 如果 为空， 则指示函数 ， 否则 ； 表示节点 对 应在第一棵树中的节点 的位置； 表示节点 的大小； 表示节点 对应在第二棵树 中的节点 的位置； 表示节点 的大小； 在一系列硬约束下最小化目标函数。 2.根据权利要求1所述的具有层次结构布局的混合生成方法， 其特征在于， 所述分支节 点对应分支 节点的计算代价包括： 两个分支节点都不下沉； 递归调用计算损失方法来计算第 一个分支节点的孩子节点与 另一分支节点的孩子节点之 间的代价； 计算第一个分支节点的孩子节点对空的代价以及第 二个分支节点的孩子节点对空的代价； 用计算出的代价值构建一个二维矩阵并通过匈牙利 算法求解就得到一个损失值记为 ；权　利　要　求　书 2/5 页 3 CN 115202661 B 3