(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211277770.1 (22)申请日 2022.10.19 (71)申请人 江西软件职业 技术大学 地址 330000 江西省南昌市湾里区罗亭 (72)发明人 柴亚辉　曹良　李俊　徐国庆　 (74)专利代理 机构 南昌合达信知识产权代理事 务所(普通 合伙) 36142 专利代理师 张静 (51)Int.Cl. G06F 9/50(2006.01) G06F 15/78(2006.01) (54)发明名称 一个服务于FPGA计算加速集群系统的硬件 资源管理器 (57)摘要 本发明公开了一个服务于FPGA计算加速集 群系统的硬件资源管理器。 采用资源状态矩阵模 型与FPGA二维空间资源与任务模型， 以基于部份 重叠的最大空闲矩形为来管理FPGA上的空闲资 源。 本发明中提出了一个双向倒形塔结构， 并给 出了双向倒形塔上的相关操作， 包括： 搭塔、 抽 塔、 塔顶内容更新、 更换Bottom与相邻Bottom。 在 双向倒形塔的基础上公开了一个最大空闲资源 矩形扫描查找 算法， 以能够高效与灵活地查找最 大空闲矩形资源。 该方法的优势是能够从任何一 个KVP点即可开始最大空闲矩形的扫描查找， 巧 妙地将最大空闲矩形的查找与塔的操作结合起 来， 且发明的实施方案中的各个功能模块易于用 各种编程语言实现。 权利要求书3页 说明书8页 附图5页 CN 115525433 A 2022.12.27 CN 115525433 A 1.一个服务于FPGA计算加速集群系统的硬件资源管理器， 其特征在于： 本发明公开了 一个双向倒形塔的结构， 并在双向倒形塔的基础上公开了一个最大空闲资源矩形扫描查找 算法。 2.根据权利要求1所述的一个服务于FPGA计算加速集群系统的硬件资源管理器， 其特 征在于： 一个双向倒形塔的结构。 倒形塔： 一个塔从塔底到顶端的方向上， 塔的每一层其面积都要变小， 则倒形塔则是正 好相反， 越向塔顶， 其值越大。 我们 根据这种情况， 构建一个数据结构， 设有塔底Bottom， 塔 顶Top， 在 初始时， 塔顶与塔底都指向同一 地址。 双向倒形塔： 对于双向倒形塔设有两个塔顶指针， 上塔顶top1与下塔顶Top2， 并设有2 个塔底Bottom1与Bottom2与塔顶对应， 且两个方向上塔的建塔规则相同。 在不同的情形下， Bottom1与Bottom2的位置主要包括两种： ①重叠， 如图4 ‑8所示；②相邻， 即Bottom1与 Bottom2为上下相连的邻居。 无论是情形 ①还是情形 ②， Bottom1中的M值一定等于Bottom2 中的M值， 且是M值最小的。 如图1所示为塔为初始时的情形， 此时， Top1、 Top2与Bottom1、 Bottom2都指向同一个地址位置。 图2为双向倒形塔在某一时刻t0时的情形， 此时， Top1与 Top2分别指向双向倒形塔的不同位置， 而Bottom1与Bottom2则指向于双向倒形塔的相同位 置。 图3为Bottom1与Bottom2相邻的情形。 Bottom1与Bottom2节点中的M值是塔中所有节点 的M值中最小的。 双向倒形塔的每一塔层节点中所包 含的信息数据包括： (1)M[i][k]。 RCU(i,k)的M值， 该值为塔层的关键值， 即上层的塔层节点 的M值>上层的 塔层节点的M值； (2)标识位flag： 0表示该RCU为KVP， 1表示为非KVP， 2表示为非KVP但在进行塔操作前当 前塔顶节点的fla g为0且M值与当前扫描到的RCU的M值相等； (3)K： RCU所在的行。 对双向倒形塔操作主 要包括： 搭塔、 抽塔、 塔顶内容更新、 更 换Bottom与相邻Bot tom。 ⑴搭塔操作 搭塔操作的条件： 当前RCU的M值大于塔顶 节点的M值。 如果当前RCU的M值大于塔顶节点的M值， 该RCU的相关信息入新的塔层节点， 如果该RCU 为KVP， 标识其fla g为0； 如果非KVP， 标识fla g为1。 ⑵塔顶内容更新 塔顶内容更新操作的条件： 当前RCU的M值等于塔顶节点的M值且塔顶结点不为重叠 Bottom节点。 如果当前RCU 的M值等于塔顶节点的M值， 将塔顶节点的内容进行更新， 更新过程如下： ①M值保持不变； ②K值为当前RCU所在的K； ③关于flag值， 如果塔顶节点的flag为0， 则a)如 果RCU为非KVP， 则flag为2； b)如果RCU为KVP， 则flag为0； 如果塔顶节点的flag为1， 则a)如 果RCU为非KVP， 则flag为1； b)如果RCU为KVP， 则flag为0； 如果塔顶节点的flag为2， 则a)如 果RCU为非KVP， 则fla g为2； b)如果RCU为KVP， 则fla g为0。 ⑶抽塔操作 抽塔操作的条件： 当RCU的M值小于塔顶节点的M值且当前塔顶节点不是重叠Bottom节 点。权　利　要　求　书 1/3 页 2 CN 115525433 A 2如果前RCU的M值小于塔顶 节点的M值， 则进行抽塔操作， 抽塔操作的过程如下： ①如果塔顶节点的flag为1且塔顶节点不是非重叠的Bottom节点， 则直接将该塔顶节 点去除， 将塔顶 节点指向下层的塔顶 节点。 ②如果塔顶 节点的fla g为0或2， 将产生 最大空闲矩形。 产生 最大空闲矩形的过程如下： a)确定最大空闲矩形的左下角坐标(x,y)： x的值为i ‑塔顶节点的M值+1， y的值为塔顶 节点的下层顶点的K值加1， 即： 对于Top1， 则为S [Top1‑1].K； 对于Top2， 则为S [Top2+1].K。 b)确定最大空闲矩形的宽w与 高h： w的值为塔顶节点的M值， 高h 的值为当前RCU的k ‑塔 顶节点的下层顶点的K值 ‑1， 即： 对于Top1， 则为S [Top1‑1].K； 对于Top2， 则为S [Top2+1].K。 ⑷相邻Bottom操作 相邻Bottom操作的条件： 当前RCU的M值等于塔顶节点的M值且当前塔顶节点为重叠 Bottom节点。 相邻Bottom操作过程 为： 将当前RCU的相关信息， 在塔顶方向(向上或向下)建立新的塔层节点， 并设为新的塔顶 节点， 节点内的相关值为： ①M值为当前RCU上的M值； ②K值为当前RCU上的K值； ③如果RCU为 KVP， 则flag为0； 如果RCU 为非KVP， 则flag为1， 并且将这个新的塔顶节点设为Bottom节点与 Top节点。 ⑸更换Bottom操作 更换Bottom操作的条件： 当前RCU的M值小于塔顶节点的M值且当前塔顶节点为Bottom 节点。 更换Bottom操作过程分为两种情况。 情况1： 当前的Bottom节点为重叠Bottom， 此时， 将RCU的相关信息搭塔， 并将重叠Bottom指向 该新建的塔顶 节点。 情况2： 当前的Bottom节点为相邻Bottom， 此时， 将RCU的相关信息更换到当前塔顶的那个 Bottom节点， 将相邻Bot tom变为重 叠Bottom， 并将塔顶的Top指向该重 叠Bottom。 3.根据权利要求1所述的一个服务于FPGA计算加速集群系统的硬件资源管理器， 其特 征在于： 一个 基于双向倒形塔的最大空 闲矩形全集扫描算法。 第1步： 按照一定的顺序， 选中一个正在FPGA上运行的任务的坐标空间， 从其左邻居从 下到上开始选一KVP点RCU(i,k)， 并将其搭塔， 将T op1、 Top2、 Bottom1与Bottom2指向该塔层 节点。 设一个扫描方 向标记Fdir， 当Fdir为0 时， 沿扫描列向上即Top 1方向扫描； 当Fdir为1 时， 沿扫描列向下即Top2方向扫描。 Fdir的初值设为0， 进入第2步。 第2步： 对Fdir进行判断， 如果Fdir为0， 则进行第3步， 否则进入第8步。 第3步： 在扫描列向上 方向上取新的RCU， 转第4 步。 第4步： 判断当前RCU的M值， 如果其M值大于Top1中的M值， 则 进行搭塔操作， 之后进入第 5步； 如果其M值等于Top1中的M值且Top1指向重叠Bottom， 则进行相邻Bottom操作， 之后进 入第5步； 如果其M值等于Top1中的M值且Top1指向相邻Bottom或不指向Bottom， 则进行塔顶 内容更新操作， 之后进入第5步； 如果其M值小于Top 1上的M值且Top1不指向Bottom， 则进行 抽塔操作， 之后进入第6步； 如果其M值小于Top1上的M值且Top1指向Bottom， 则进行更换权　利　要　求　书 2/3 页 3 CN 115525433 A 3