买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网获悉北京大学申请的专利一种GPU加速构建最小直角斯坦纳树的芯片布线方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN115563927B 。

龙图腾网通过国家知识产权局官网在2025-10-24发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202211285801.8，技术领域涉及：G06F30/394；该发明授权一种GPU加速构建最小直角斯坦纳树的芯片布线方法是由林亦波;郭资政;谷丰设计研发完成，并于2022-10-20向国家知识产权局提交的专利申请。

本一种GPU加速构建最小直角斯坦纳树的芯片布线方法在说明书摘要公布了：本发明公布了一种GPU加速构建最小直角斯坦纳树的芯片布线方法，属于集成电路设计自动化技术领域，涉及集成电路芯片布线技术，设计了一种应用于芯片布线的GPU加速计算的最小直角斯坦纳树构建方法，使用GPU大规模并行加速多个线网的斯坦纳树搜索过程，包括：查找表初始化，获得扁平化的斯坦纳树分支列表和分支查找表索引，并从CPU内存复制到GPU显存；线网数据初始化，获得线网的管脚列表和管脚起始位置索引，并从CPU内存复制到GPU显存；线网并行分割，建立分层的线网分割森林；线网并行求解合并；本发明提供的技术方案提升了集成电路芯片布线的计算效率。

本发明授权一种GPU加速构建最小直角斯坦纳树的芯片布线方法在权利要求书中公布了：1.一种GPU加速构建最小直角斯坦纳树的芯片布线方法，其特征是，包括步骤： A.查找表初始化，获得扁平化的斯坦纳树分支列表和分支查找表索引，并从CPU内存复制到GPU显存；包括： A1.对芯片中线网度数小于查找表阈值的所有线网，构建最小直角斯坦纳树查找表；最小直角斯坦纳树查找表包含从线网管脚相对位置编码到潜在最小直角斯坦纳树的映射；查找表阈值为常数； A2.将最小直角斯坦纳树查找表扁平化，获得扁平化的斯坦纳树分支列表和分支查找表索引；具体过程是将潜在最小直角斯坦纳树的所有分支按照管脚相对位置编码顺序存放在数组中，使得上一个斯坦纳树的最后一个分支与下一斯坦纳树的首个分支相邻，得到的分支数组即为扁平化的斯坦纳树分支列表；计算每个潜在最小直角斯坦纳树的首个分支在数组中的下标，得到分支查找表索引； A3.将扁平化的斯坦纳树分支列表和分支查找表索引从CPU内存复制到GPU显存； B.线网数据初始化，获得线网的管脚列表和管脚起始位置索引，并从CPU内存复制到GPU显存； B1.芯片中所有线网为输入的线网，将输入的线网扁平化，获得线网的管脚列表和管脚起始位置索引，其中线网的管脚列表包含横坐标列表和纵坐标列表； B2.将管脚列表和起始位置索引从CPU内存复制到GPU显存； C.线网并行分割，建立分层的线网分割森林； 在GPU上对线网的管脚列表和管脚起始位置索引进行迭代分割，建立分层的线网分割森林，线网分割森林由多个线网分割树组成，每个线网分割树的节点是线网，连接父节点和子节点的树边代表由父节点线网分割得到子节点线网，根节点为输入的线网，叶子结点为无需继续分割的线网，即管脚个数小于查找表阈值的线网； 迭代分割的具体过程包括： C1.从输入的线网开始进行分割操作，输入的线网构成第一层线网； C2.对本层内的每个线网，通过管脚起始位置索引获得线网管脚列表中这个线网的管脚所在的区间； C3.定义线网度数为线网中的管脚数量，对度数已经小于查找表阈值的线网，不做任何操作；对度数大于等于查找表阈值的线网，选择其中的一个管脚作为分割点，将线网分割成两个线网，即为当前线网在线网分割树上的子节点； D.线网并行求解合并：在GPU上对分割的线网进行求解，求解的具体方式是： D1.若线网度数小于查找表阈值，则通过扁平化的斯坦纳树分支列表和分支查找表索引获得线网的最小直角斯坦纳树，具体方法是计算管脚的相对位置编码，通过分支查找表索引获得最小直角斯坦纳树的所有分支在分支列表中的区间，这些分支即构成本线网的最小直角斯坦纳树； D2.若线网度数大于查找表阈值，则从下层线网的求解结果合并得到本线网的最小直角斯坦纳树，具体方法是将下层线网的最小直角斯坦纳树在分割点处连接起来；对多个分割方案，取直角斯坦纳树总线长最小的方案作为本线网的分割方案； D3.对线网求解的顺序是在分层的线网分割森林上从下层到上层，获得顶层线网的合并结果，即为输入线网的最小直角斯坦纳树求解结果； E.根据得到的输入线网的最小直角斯坦纳树求解结果，实现GPU加速构建最小直角斯坦纳树的芯片布线。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人北京大学，其通讯地址为：100871 北京市海淀区颐和园路5号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。

以上内容由龙图腾AI智能生成。