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

龙图腾网获悉上海科技大学申请的专利高能效FPGA实现的乱序并行最大流\最小割方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN116302495B 。

龙图腾网通过国家知识产权局官网在2025-08-22发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202310121083.9，技术领域涉及：G06F9/50；该发明授权高能效FPGA实现的乱序并行最大流\最小割方法是由闫光耀;刘心哲;哈亚军;汪辉设计研发完成，并于2023-02-15向国家知识产权局提交的专利申请。

本高能效FPGA实现的乱序并行最大流\最小割方法在说明书摘要公布了：本发明公开了一种高能效FPGA实现的乱序并行最大流\最小割方法。本发明将一个单层大型二维格状图折叠成一个多层小型格状图。此方法有两重好处：折叠网格架构可以储存并处理一个尺寸远大于处理器阵列尺寸的格状图；此架构还赋予二维处理器阵列垂直方向的自由度，使其可以利用垂直方向的自由度提高架构的并行潜力。通过本发明提出的折叠网格架构，使一个小尺寸的处理器阵列拥有处理一个尺寸远大于它的格状图的能力。同时此折叠网格架构可以利用折叠的轴对称性，大量减少数据在处理器阵列中的跨边界传输，从而减少数据移动带来的额外开销。本发明还提出了一种乱序并行执行技术，此技术可以充分挖掘折叠网格架构中的并行潜力。

本发明授权高能效FPGA实现的乱序并行最大流\最小割方法在权利要求书中公布了：1.一种高能效FPGA实现的乱序并行最大流\最小割方法，其特征在于，包括以下步骤： 步骤1、将格状图按照处理器阵列的大小预处理成为折叠网格数据结构，设H,W为格状图的尺寸，h,w为处理器阵列的尺寸，X,Y为格状图中节点的坐标，其中X∈[1,H]，Y∈[1,W]，则预处理过程包括以下步骤： 步骤101、将格状图中的节点坐标X,Y转换至处理器阵列坐标系，转换后的坐标为x,y，其中，x∈[1,h]，y∈[1,w]；经过坐标转换后，将一张大型格状图的所有节点折叠映射至一个多层小型格状图中，且小型格状图的尺寸为处理器阵列的尺寸； 步骤102、按照转换后的处于处理器阵列坐标系下的节点坐标，将步骤101获得的多层小型格状图的数据输入至加速器当中，对应相同坐标的格状图节点储存在相同处理器当中，同时输入h,w、与作为参数，ceila指返回大于或等于a的最小整数，其中，h,w用来初始化加速器中的输入输出过程中具体的时钟延迟，与用来判断当前处理的节点数据是否被镜像，且坐标用于表示多层小型格状图的具体某一层； 步骤2、多层小型格状图中每个节点包含自身最多能够容纳多少流量的ef数据、指向四周节点的边的容量edge数据、节点高度h数据以及还指向虚拟的汇的边的容量sink，这些数据在输入阶段按照处理器阵列坐标的顺序储存在对应处理器当中，当加速器载入全部数据之后进行一次全局重标签操作，其中，处理器单元采用基于FIFO的乱序执行技术处理每一层小型格状图： 在基于FIFO的乱序执行技术中，执行全局重标操作时：遍历小型格状图中所有节点，若小型格状图中节点的容量sink数据不为0，则将这些节点初始化为种子点，并将它们全部放入FIFO队列当中，每次从FIFO队列中取出一个节点进行计算，将当前节点的节点高度h数据更新为从FIFO队列中读取到的高度加1； 若当前节点指向FIFO队列中缓存节点的边的容量edge数据大于0，则增长此节点；当所有处理器节点中的FIFO队列都为空时，全局重标签操作完成，同时，在执行过程中，若节点中ef数据大于0时，则被储存进下一步骤Push操作的待处理FIFO当中； 步骤3、若Push操作的待处理FIFO不为空的，则执行Push操作来完成推流操作。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人上海科技大学，其通讯地址为：201210 上海市浦东新区华夏中路393号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。