一种可重构器件片上面积管理优化方法

IPC分类号 : G06F9/50

申请号

CN201710111642.2

可选规格: 数量

库存1件

确认取消

￥30000; 库存1件

首页

立即咨询

看了又看

专利摘要

本发明公开了一种可重构器件片上面积管理优化方法。本发明采用了可重构器件的四类顶点作为候选位置，通过其中某一种顶点来找到合适的空闲区域作为面积分配的对象，并通过顶点来合并已经执行完的任务所使用的面积。本方法实现了快速高效的片上面积管理和候选位置的选择，能够更为有效的进行可重构器件片上面积的管理。

权利要求

1.一种可重构器件片上面积管理优化方法，其特征在于，包括如下步骤：

S1、模型化可重构器件；将可重构器件建模为一个二维数组C(X,Y)，该二维数组C(X,Y)称为可重构矩阵，其中X和Y分别是可配置逻辑块所构成的阵列的宽度和高度，可重构矩阵中的每一个可配置逻辑块与二维数组C(X,Y)中的一个数组成员对应；

S2、确定可用候选位置；使用可重构矩阵中位于矩阵中凹角处的顶点作为候选位置选择的基础，基于该顶点构建和维护可用候选位置列表；

S3、在新的可重构计算任务Tj到达时，检查所述可用候选位置列表，将可重构计算任务Tj分配到满足要求的区域，并更新所述可用候选位置列表，之后进行下一步；若无满足Tj分配要求的区域，则退出分配程序；若新的可重构计算任务Tj的宽度属性为w，高度属性为h，则该可重构计算任务Tj需要的可配置逻辑块的数量为w*h；

当可用候选位置列表选用左下顶点列表时，检查所述可用候选位置列表具体包括：

S31a、检查左下顶点列表，如果没有未检查过的左下顶点，到步骤S33a；

S32a、如果有未检查过的左下顶点，取未检查过的第一个左下顶点BLk，检查以下条件：

Ex2＝X2-w；

Ey2＝Y2-h；

如果Ex2和Ey2均大于或者等于0，该左下顶点BLk满足要求，将可重构计算任务Tj分配到与该左下顶点BLk邻接的右上方区域，大小为w*h，可重构计算任务Tj的分配完成；如果Ex2和Ey2中有一个小于0，则回到步骤S31a；

S33a、无法满足可重构计算任务Tj的分配任务，退出分配程序；

当可用候选位置列表选用右下顶点列表时，检查所述可用候选位置列表具体包括：

S31b、检查右下顶点列表，如果没有未检查过的右下顶点，到步骤S33b；

S32b、如果有未检查过的右下顶点，取未检查过的第一个右下顶点BRk，检查以下条件：

Ex1＝X1-w；

Ey1＝Y1-h；

如果Ex1和Ey1均大于或者等于0，该左下顶点BLk满足要求，将可重构计算任务Tj分配到与该右下顶点BLk邻接的左上方区域，大小为w*h，可重构计算任务Tj的分配完成；如果Ex1和Ey1中有一个小于0，则回到步骤S31b；

S33b、无法满足可重构计算任务Tj的分配任务，退出分配程序；

当可用候选位置列表选用左上顶点列表时，检查所述可用候选位置列表具体包括：

S31c、检查左上顶点列表，如果没有未检查过的左上顶点，到步骤S33c；

S32c、如果有未检查过的左上顶点，取未检查过的第一个左上顶点BRk，检查以下条件：

Ex4＝X4-w；

Ey4＝Y4-h；

如果Ex4和Ey4均大于或者等于0，该左下顶点BLk满足要求，将可重构计算任务Tj分配到与该左上顶点BLk邻接的右下方区域，大小为w*h，可重构计算任务Tj的分配完成；如果Ex4和Ey4中有一个小于0，则回到步骤S31c；

S33c、无法满足可重构计算任务Tj的分配任务，退出分配程序；

当可用候选位置列表选用右上顶点列表时，检查所述可用候选位置列表具体包括：

S31d、检查右上顶点列表，如果没有未检查过的右上顶点，到步骤S33d；

S32d、如果有未检查过的右上顶点，取未检查过的第一个右上顶点BRk，检查以下条件：

Ex3＝X3-w；

Ey3＝Y3-h；

如果Ex3和Ey3均大于或者等于0，该左下顶点BLk满足要求，将可重构计算任务Tj分配到与该右上顶点BLk邻接的左下方区域，大小为w*h，可重构计算任务Tj的分配完成；如果Ex3和Ey3中有一个小于0，则回到步骤S31d；

S33d、无法满足可重构计算任务Tj的分配任务，退出分配程序；

S4、在可重构计算任务Tj执行完成后，检查可重构计算任务Tj所占用的每个可配置逻辑块，并检查可重构矩阵中不再是可用候选位置和新产生的可用候选位置，更新所述可用候选位置列表，进行下一次分配；其中更新所述可用候选位置列表具体包括：

可重构计算任务Tj插入后，检查可重构计算任务Tj所占用的每个可配置逻辑块，将可重构计算任务Tj所占用的每个可配置逻辑块都标记为占用状态；可重构计算任务Tj执行完成后，将可重构计算任务Tj所占用的每个可配置逻辑块都标记为空闲状态；检查不再是可用候选位置，并将这些不再是可用候选位置对应的顶点从可用候选位置列表中删除；检查新产生的可用候选位置，并将新产生的可用候选位置所对应的顶点加入到可用候选位置列表中；更新每个可用候选位置所对应的顶点的属性；对可用候选位置列表中的顶点按照从上到下、从左到右的规则排序；

对于一个可用候选顶点Vi，有属性ViT(X1,Y1)，属性ViB(X2,Y2)，属性ViL(X3,Y3)和属性ViR(X4,Y4)，分别表示在顶点左上方、顶点右上方、顶点左下方和顶点右下方可用的可配置逻辑块所组成的矩形的宽度和高度；如果可用候选顶点某个方向上没有可用的可配置逻辑块，则对应的值为0；

对于右下顶点，只有顶点左上方可能存在可用的可配置逻辑块所组成的矩形，右下顶点列表只维护和更新每个右下顶点的属性VBRiT(X1,Y1)；对于左下顶点，只有顶点右上方可能存在可用的可配置逻辑块所组成的矩形，左下顶点列表只维护和更新每个左下顶点的属性VBLiB(X2,Y2)；对于右上顶点，只有顶点左下方可能存在可用的可配置逻辑块所组成的矩形，右上顶点列表只维护和更新每个右上顶点的属性VTRiL(X3,Y3)；对于左上顶点，只有顶点右下方可能存在可用的可配置逻辑块所组成的矩形，左上顶点列表只维护和更新每个左上顶点的属性VTLiR(X4,Y4)。

2.如权利要求1所述的可重构器件片上面积管理优化方法，其特征在于，步骤S1中，可重构矩阵左上角的第一个可配置逻辑块使用C(1,1)来进行标识，最右下角的可配置逻辑块使用C(X,Y)来进行标识；如果可重构矩阵中的一个可配置逻辑块被某个任务占用了，则对应的可配置逻辑块标记为占用状态，在二维数组C(X,Y)中对应的数组成员标记为1；如果某个可配置逻辑块未被使用，则这个可配置逻辑块就被标记为空闲状态，在二维数组C(X,Y)中的对应成员标记为0。

3.如权利要求2所述的可重构器件片上面积管理优化方法，其特征在于，步骤S2中，使用左下、右下、左上或右上顶点中的任意一种顶点作为候选位置选择的基础，根据从上到下、从左到右的规则，分别构建和维护可用候选位置列表；其中，左下顶点列表为VBL＝{BL1,BL2,BL3,…,BLm}；

右下顶点列表为VBR＝{BR1,BR2,BL3,…,BRl}；

左上顶点列表为VTL＝{TL1,TL2,TL3,…,TLp}；

右上顶点列表为VTR＝{TR1,TR2,TR3,…,TRq}。

说明书

技术领域

本发明涉及可重构技术领域，特别是涉及一种可重构器件片上面积管理优化方法。

背景技术

可重构计算被视为能够将传统处理器的高度灵活性与ASIC(ApplicationSpecific Integrated Circuit)所具有的高处理效率进行结合的有效解决方案。由于可重构体系结构具有较好的适应性，针对不同应用能够通过不同粒度的并行来加快处理速度。在可重构设备中，FPGA(Field－Programmable Gate Array)是最广泛使用的可重构器件。动态可充配置的FPGA是实现硬件级别多任务的重要基础。此类FPGA的处理区域通常划分成不同的子块，可配置逻辑块(Configurable Logic Block，CLB)。此外，还包括了输入输出块(I/O块)和可编程互连网络(又称连线，Routing)。CLB是实现用户功能的基本单元，通常排列成一个阵列，散布整个芯片；I/O块是片上逻辑与外部封装管脚的接口，通常围绕分布在CLB阵列四周；可编程互连网络包括各种长度的连线和一些可编程连接开关，它们将CLB或I/O块连接起来，实现特定功能的电路。

这些子块分属于不同的硬件任务。当新的硬件任务达到时，需要为该硬件任务分配一个空闲的子块，同时其他的既存硬件任务不能受到影响。如果一个硬件任务执行完成，那么该任务所占据的子块应当被释放，并作为候选子块以备其他硬件任务的使用。在重分配期间，没有任何的其他硬件任务会受到影响，多个硬件任务可以共享整个处理区域。可见，通过对子块的重新利用，动态重配置能够提高FPGA的利用率。并行任务的数据仅仅受到FPGA容量的限制。然而子块的动态分配和替换操作会带来额外时间损耗。硬件任务的复杂化和重定位的频繁发生，导致了重配置代价的增加。因此，通过对重配置的资源映射进行高效管理以改善重构的性能就变得非常重要。

在线的FPGA分配是减少重配置代价的重要方向。FPGA的高度碎片化会导致相当差的配置结果：在有足够空闲面积的情况下，却由于碎片化问题造成硬件任务不能在片上进行配置。在线的FPGA分配用于确定怎样将硬件任务分配到可重构平台的恰当区域，从而能够更好的利用可重构FPGA。Bazargan等人提出了针对2D PRTR FPGA的bin-packing在线分配方法。该方法以可重配置计算系统的模型建立为基础，通过对经典算法的扩展来进行在线的实际分配；其中最大空闲方块(Maximum Empty Rectangles,MER)的大小是Ω(n2)。Walder等人提出了使用哈希-矩阵数据结构来对空闲区域进行管理，并设计了在线分配算法。该方法是既有方法的一种改进，其改进之处在于可用处理区域的实际分裂时间被推迟，从而能够提高分配的质量。Ahmadinia等人所提出的方法与Bazargan等人提出的方法相似。这两种方法的主要差别在于所管理的处理区域(processing-area)：Ahmadinia方法用于管理已占用的区域，而Bazargan方法则用于管理空闲区域。这两种方法具有相同的复杂度，在进行数据结构管理时也非常耗时，所需要的时间复杂度函数是非线性的。

Cui等人提出了用来寻找和构建完成MER集合的算法，能够较为高效的进行处理区域的管理。Lu等人提出了运行时MER的管理算法。Lu等人的算法对MER完整集合的构建基于已配置任务边的动态信息。新的优化方法提出了三种用于改善在线分配算法的技术，分别是仅在合需要时合并(Merging Only if Needed,MON)，部分合并(Partial Merging,PM)和直接合并(Direct Combination,DC)。这三种技术分别应用于不同的具体操作环境当中。Handa等人提出了在PRTR FPGA上快速找到空闲空间的方法。该算法的基础是使用阶梯型数据结构以反映基于MER的空闲区域状态。Tabero等人提出了硬件多任务的新方法，使用基于顶点列表集合的空间管理器来实现处理区域管理。顶点列表用来描述PRTR(Partial Run-Time Reconfigurable)平台上未被占用区域的片段。当新任务到达的时候，区域管理器将会搜索顶点列表并使用不同的位置启发式算法来找到合适的位置。这种方法能够以更高的效率来管理处理区域，但是由于任务的插入和删除，导致对顶点列表的管理非常复杂。此外，不是所有顶点列表中的顶点都是可用的任务分配候选区域。事实上只有一部分顶点列表中的顶点能够作为任务分配的候选位置使用。该算法的复杂度是Ο(n2)，其中n是FPGA平台上运行时的任务数量。

发明内容

本方法提出了一种可重构器件片上面积管理优化方法，能够以定点为基础，更为有效的实现了可重构器件的片上面积管理。

本发明解决其技术问题采用的技术方案如下：

一种可重构器件片上面积管理优化方法，包括如下步骤：

S2、确定可用候选位置；使用可重构矩阵中位于矩阵中凹角处的顶点作为候选位置选择的基础，基于该顶点构建和维护可用候选位置列表；

S3、在新的可重构计算任务Tj到达时，检查所述可用候选位置列表，将可重构任务Tj分配到满足要求的区域，并更新所述可用候选位置列表，之后进行下一步；若无满足Tj分配要求的区域，则退出分配程序；

S4、在可重构计算任务Tj执行完成后，检查可重构计算任务Tj所占用的每个可配置逻辑块，并检查可重构矩阵中不再是可用候选位置和新产生的可用候选位置，更新所述可用候选位置列表，进行下一次分配。

进一步的，步骤S1中，可重构矩阵左上角的第一个可配置逻辑块使用C(1,1)来进行标识，最右下角的可配置逻辑块使用C(X,Y)来进行标识；如果可重构矩阵中的一个可配置逻辑块被某个任务占用了，则对应的可配置逻辑块标记为占用状态，在二维数组C(X,Y)中对应的数组成员标记为1；如果某个可配置逻辑块未被使用，则这个可配置逻辑块就被标记为空闲状态，在二维数组C(X,Y)中的对应成员标记为0。

进一步的，步骤S2中，使用左下、右下、左上或右上顶点中的任意一种顶点作为候选位置选择的基础，根据从上到下、从左到右的规则，分别构建和维护可用候选位置列表；其中，左下顶点列表为VBL＝{BL1,BL2,BL3,,BLm}；

右下顶点列表为VBR＝{BR1,BR2,BL3,,BRl}；

左上顶点列表为VTL＝{TL1,TL2,TL3,,TLp}；

右上顶点列表为VTR＝{TR1,TR2,TR3,,TRq}。

进一步的，步骤S3中，若新的可重构计算任务Tj的宽度属性为w，高度属性为h，则该可重构计算任务Tj需要的可配置逻辑块的数量为w*h；

当可用候选位置列表选用左下顶点列表时，检查所述可用候选位置列表具体包括：

S31、检查左下顶点列表，如果没有未检查过的左下顶点，到步骤S33；

S32、如果有未检查过的左下顶点，取未检查过的第一个左下顶点BLk，检查以下条件：

Ex2＝X2-w；(1)

Ey2＝Y2-h；(2)

如果Ex2和Ey2均大于或者等于0，该左下顶点BLk满足要求，将可重构计算任务Tj分配到与该左下顶点BLk邻接的右上方区域，大小为w*h，可重构计算任务Tj的分配完成；如果Ex2和Ey2中有一个小于0，则回到步骤S31；

S33、无法满足可重构计算任务Tj的分配任务，退出分配程序；

当可用候选位置列表选用右下、左上或右上顶点列表时，检查所述可用候选位置列表的步骤与左下顶点的步骤类似。

进一步的，步骤S3或S4中，更新所述可用候选位置列表具体包括：可重构任务Tj插入后，检查可重构计算任务Tj所占用的每个可配置逻辑块，将可重构计算任务Tj所占用的每个可配置逻辑块都标记为占用状态；可重构计算任务Tj执行完成后，将可重构计算任务Tj所占用的每个CLB都标记为空闲状态；检查不再是可用候选位置，并将这些不再是可用候选位置对应的顶点从可用候选位置列表中删除；检查新产生的可用候选位置，并将新产生的可用候选位置所对应的顶点加入到可用候选位置列表中；更新每个可用候选位置所对应的顶点的属性；对可用候选位置列表中的顶点按照从上到下、从左到右的规则排序。

进一步的，对于一个可用候选顶点Vi，有属性ViT(X1,Y1)，属性ViB(X2,Y2)，属性ViL(X3,Y3)和属性ViR(X4,Y4)，分别表示在顶点左上方、顶点右上方、顶点左下方和顶点右下方可用的可配置逻辑块所组成的矩形的宽度和高度；如果可用候选顶点某个方向上没有可用的可配置逻辑块，则对应的值为0；

对于右下顶点，只有顶点左上方可能存在可用的可配置逻辑块所组成的矩形，右下顶点列表可以只维护和更新每个右下顶点的属性VBRiT(X1,Y1)；对于左下顶点，只有顶点右上方可能存在可用的可配置逻辑块所组成的矩形，左下顶点列表可以只维护和更新每个左下顶点的属性VBLiB(X2,Y2)；对于右上顶点，只有顶点左下方可能存在可用的可配置逻辑块所组成的矩形，右上顶点列表可以只维护和更新每个右上顶点的属性VTRiL(X3,Y3)；对于左上顶点，只有顶点右下方可能存在可用的可配置逻辑块所组成的矩形，左上顶点列表可以只维护和更新每个左上顶点的属性VTLiR(X4,Y4)。

本发明与背景技术相比，具有的有益的效果是：本发明使用了四类顶点中的一类来作为候选位置管理的基础，通过对顶点的管理来实现快速高效的片上面积管理和候选位置的选择。本发明对可重构器件片上面积管理的效率更高。

(1)高效性。本发明通过四类顶点来进行可重构器件片上面积管理，每个顶点都有相应的属性，通过属性来直接进行条件测试并进行可重构计算任务的分配和删除，效率更高。

(2)易于实现。本发明将可重构器件进行模型化，通过模型化后的可重构矩阵来进行片上面积管理，更易于实现。

附图说明

图1是本发明的可重构器件片上面积管理优化方法的流程示意图。

图2是本发明的方法中可重构矩阵的示意图。

图3是可重构矩阵中的可用候选位置和四类顶点的示意图。

图4是任务插入后的可重构矩阵示意图。

图5是任务删除后的可重构矩阵示意图。

具体实施方式

下面结合附图和具体实施方式对本发明做进一步的描述，并非对其保护范围的限制。

一种可重构器件片上面积管理优化方法，其具体实现流程如下。

第一步、可重构器件的模型化

可重构器件由多个可配置逻辑块(Configurable Logic Block，CLB)构成，将可重构器件建模为一个二维数组C(X,Y)，其中X和Y分别是CLB所构成的阵列的宽度和高度。由可重构器件建模构成的二位数组C(X,Y)称为可重构矩阵，可重构矩阵中的每一个单元与二位数组C(X,Y)中的一个数组成员对应，即可重构矩阵中的每个单元是可重构器件上的一个CLB。可重构矩阵左上角的第一个单元使用C(1,1)来进行标识，最右下角的单元使用C(X,Y)来进行标识。如果可重构矩阵中的一个CLB被某个任务占用了，则对应的单元标记为占用状态，在二位数组C(X,Y)中对应的数组成员标记为1。如果某个CLB未被使用，则这个CLB就被标记为空闲状态，在二维数组C(X,Y)中的对应成员标记为1。图2是模型化后的可重构器件对应的二维数组C(X,Y)与二维数组C(X,Y)中各数组成员的单元标记状态。C(1,1)＝0在二维数组C(X,Y)中表示数组成员C(1,1)所对应的可重构矩阵中对应的CLB未被任何任务占用；C(2,1)＝1在二维数组C(X,Y)中表示数组成员C(2,1)所对应的可重构矩阵中的CLB被某个任务占用了。

第二步、可用候选位置的确定

在可重构器件上使用可重构矩阵中位于矩阵中凹角处的顶点作为候选位置选择的基础。要为某个任务选择一个可用的位置，可以用4种顶点中的一种来确定。这4种顶点分别是左下(Bottom-Left,BL)顶点，即BL顶点；右下(Bottom-Right,BR)顶点，即BR顶点；左上(Top-Left,TL)顶点，即TL顶点；右上(Top-Right,TR)顶点，即TR顶点。对于所有的可用候选位置，根据从上到下、从左到右的规则，分别构建出4个可用候选位置列表：

BL顶点列表为VBL＝{BL1,BL2,BL3,,BLm}；

BR顶点列表为VBR＝{BR1,BR2,BL3,,BRl}；

TL顶点列表为VTL＝{TL1,TL2,TL3,,TLp}；

TR顶点列表为VTR＝{TR1,TR2,TR3,,TRq}；

4个可用候选位置列表中的任何一个均可以完成任务插入的工作。在实际实现时，可以只创建并维护4个可用候选位置列表中的任何一个。

对于一个可用候选顶点Vi，有属性ViT(X1,Y1)，属性ViB(X2,Y2)，属性ViL(X3,Y3)和属性ViR(X4,Y4)，分别表示在顶点左上方、顶点右上方、顶点左下方和顶点右下方可用CLB所组成的矩形的宽度和高度。如果可用候选顶点某个方向上没有可用CLB，则对应的值为0。对于BR顶点，只有顶点左上方可能存在可用CLB所组成的矩形，BR顶点列表可以只维护和更新每个BR顶点的属性VBRiT(X1,Y1)；对于BL顶点，只有顶点右上方可能存在可用CLB所组成的矩形，BL顶点列表可以只维护和更新每个BL顶点的属性VBLiB(X2,Y2)；对于TR顶点，只有顶点左下方可能存在可用CLB所组成的矩形，TR顶点列表可以只维护和更新每个BL顶点的属性VBLiL(X3,Y3)；对于TL顶点，只有顶点右下方可能存在可用CLB所组成的矩形，TL顶点列表可以只维护和更新每个TL顶点的属性VTLiR(X4,Y4)。

在图3中，黑色箭头指向的顶点就是一个候选位置。这是任务T1所在面积的左上角与矩阵的左侧边构成了一个凹角，凹角处所在的顶角就是一个候选位置顶点。由于这个顶点位于任务T1上方的空闲面积的左下角，因此这是一个BL顶点。那么对应的可用候选位置可以使用这个BL顶点来表示为Vbl。所有的候选位置顶点都是具有同样属性的可重构矩阵中的CLB所形成顶点。

对于图3中的顶点Vbl，顶点左上方Vbl无可用的CLB组成的矩形，即VblT(X1,Y1)＝VblT(0,0)；顶点右上方Vbl可用的CLB组成的矩形的面积为斜线覆盖的面积，共有9个，宽度为3，高度为3，即VblB(X2,Y2)＝VblB(3,3)，顶点左上方Vbl无可用的CLB组成的矩形，即VblL(X3,Y3)＝VblL(0,0)；顶点左上方Vbl无可用的CLB组成的矩形，即VblR(X4,Y4)＝VblR(0,0)。由于即VblT(X1,Y1)，VblL(X3,Y3)，VblR(X4,Y4)均为0，对于顶点Vbl，只维护和更新VblB(X2,Y2)即可。

对于图3中的可重构矩阵，有BL顶点列表：

BL顶点列表为VBL＝{BL1,BL2,BL3,BL4}；

其中：

BL1B(X2,Y2)＝BL1T(2,2)

BL2B(X2,Y2)＝BL2T(3,3)

BL3B(X2,Y2)＝BL3T(5,4)

BL4B(X2,Y2)＝BL4T(2,5)

第三步、可重构计算任务的插入

可重构计算任务Tj有宽度属性w和高度属性h，w*h表示可重构计算任务Tj所需要的CLB的数量。在可重构计算任务Tj到达时，检查可用候选位置列表。以下均以BL顶点列表进行说明，其他三个顶点列表的处理方法相似。按照BL顶点列表中的顶点排列顺序：

1)检查BL顶点列表，如果没有未检查过的BL顶点，到步骤3)；如果有，取未检查过的第一个BL顶点BLk，检查以下条件：

Ex2＝X2-w；(1)

Ey2＝Y2-h；(2)

如果Ex2和Ey2均大于或者等于0，该BL顶点BLk满足要求，将可重构计算任务Tj分配到与该顶点BLk邻接的右上方区域，大小为w*h，可重构计算任务Tj的分配完成；如果Ex2和Ey2中有一个小于0，则到步骤1)

2)无法满足可重构计算任务Tj的分配任务，退出分配程序

可重构计算任务Tj插入后，检查可重构计算任务Tj所占用的每个CLB，将可重构计算任务Tj所占用的每个CLB都标记为占用状态；检查不再是可用候选位置，并将这些不再是可用候选位置对应的顶点从可用候选位置列表中删除；检查新产生的可用候选位置，并将新产生的可用候选位置所对应的顶点加入到可用候选位置列表中；更新每个可用候选位置所对应的顶点的属性；对可用候选位置列表中的顶点按照从上到下、从左到右的规则排序。

对于BR顶点列表，在可重构计算任务Tj插入后，检查可重构计算任务Tj所占用的每个CLB，将可重构计算任务Tj所占用的每个CLB都标记为占用状态；检查不再是BR顶点的可用候选位置，并将这些BR顶点从BR顶点列表中删除；检查新产生的BR顶点，并将新产生的BR顶点加入到BR顶点列表中；更新每个BR顶点的属性；对BR顶点列表中的顶点按照从上到下、从左到右的规则排序。

对于BL顶点列表，在可重构计算任务Tj插入后，检查可重构计算任务Tj所占用的每个CLB，将可重构计算任务Tj所占用的每个CLB都标记为占用状态；检查不再是BL顶点的可用候选位置，并将这些BL顶点从BL顶点列表中删除；检查新产生的BL顶点，并将新产生的BL顶点加入到BL顶点列表中；更新每个BL顶点的属性；对BL顶点列表中的顶点按照从上到下、从左到右的规则排序。

对于TR顶点列表,在可重构计算任务Tj插入后，检查可重构计算任务Tj所占用的每个CLB，将可重构计算任务Tj所占用的每个CLB都标记为占用状态；检查不再是TR顶点的可用候选位置，并将这些TR顶点从TR顶点列表中删除；检查新产生的TR顶点，并将新产生的TR顶点加入到TR顶点列表中；更新每个TR顶点的属性；对TR顶点列表中的顶点按照从上到下、从左到右的规则排序。

对于TL顶点列表,在可重构计算任务Tj插入后，检查可重构计算任务Tj所占用的每个CLB，将可重构计算任务Tj所占用的每个CLB都标记为占用状态；检查不再是TL顶点的可用候选位置，并将这些TL顶点从TL顶点列表中删除；检查新产生的TL顶点，并将新产生的TL顶点加入到TL顶点列表中；更新每个TL顶点的属性；对TL顶点列表中的顶点按照从上到下、从左到右的规则排序。

对于图3中的可重构矩阵，可重构计算任务T6的w＝2，h＝3，则：

1)检查BL顶点列表，取未检查过的第一个BL顶点BL1，检查以下条件：

Ex2＝X2-w＝2-2＝0；

Ey2＝Y2-h＝2-3＝-1；

Ey2小于0，则到下一个步骤

3)检查BL顶点列表，取未检查过的第一个BL顶点BL2，检查以下条件：

Ex2＝X2-w＝3-2＝1；(1)

Ey2＝Y2-h＝3-3＝0；(2)

Ex2和Ey2均大于或者等于0，该BL顶点BL2满足要求，将可重构计算任务T6分配到与该顶点BL2邻接的右上方区域，大小为w*h，可重构计算任务T6的分配完成，如图4所示。

其中原BL顶点BL2不再是BL顶点，新增一个BL顶点BL1，原BL顶点BL1变为BL顶点BL2。BL顶点BL3和BL顶点BL4没有改变。各个BL顶点的属性变化为：

BL1B(X2,Y2)＝BL1T(3,1)

BL2B(X2,Y2)＝BL2T(2,2)

BL3B(X2,Y2)＝BL3T(5,4)

BL4B(X2,Y2)＝BL4T(2,5)

第四步、可重构计算任务的删除

在可重构计算任务Tj执行完成后，检查可重构计算任务Tj所占用的每个CLB，将可重构计算任务Tj所占用的每个CLB都标记为空闲状态；检查不再是可用候选位置，并将这些不再是可用候选位置对应的顶点从可用候选位置列表中删除；检查新产生的可用候选位置，并将新产生的可用候选位置所对应的顶点加入到可用候选位置列表中；更新每个可用候选位置所对应的顶点的属性；对可用候选位置列表中的顶点按照从上到下、从左到右的规则排序。

对于BR顶点列表，在可重构计算任务Tj执行完成后，检查可重构计算任务Tj所占用的每个CLB，将可重构计算任务Tj所占用的每个CLB都标记为空闲状态；检查不再是BR顶点的可用候选位置，并将这些BR顶点从BR顶点列表中删除；检查新产生的BR顶点，并将新产生的BR顶点加入到BR顶点列表中；更新每个BR顶点的属性；对BR顶点列表中的顶点按照从上到下、从左到右的规则排序。

对于BL顶点列表，在可重构计算任务Tj执行完成后，检查可重构计算任务Tj所占用的每个CLB，将可重构计算任务Tj所占用的每个CLB都标记为空闲状态；检查不再是BL顶点的可用候选位置，并将这些BL顶点从BL顶点列表中删除；检查新产生的BL顶点，并将新产生的BL顶点加入到BL顶点列表中；更新每个BL顶点的属性；对BL顶点列表中的顶点按照从上到下、从左到右的规则排序。

对于TR顶点列表,在可重构计算任务Tj执行完成后，检查可重构计算任务Tj所占用的每个CLB，将可重构计算任务Tj所占用的每个CLB都标记为空闲状态；检查不再是TR顶点的可用候选位置，并将这些TR顶点从TR顶点列表中删除；检查新产生的TR顶点，并将新产生的TR顶点加入到TR顶点列表中；更新每个TR顶点的属性；对TR顶点列表中的顶点按照从上到下、从左到右的规则排序。

对于TL顶点列表,在可重构计算任务Tj执行完成后，检查可重构计算任务Tj所占用的每个CLB，将可重构计算任务Tj所占用的每个CLB都标记为空闲状态；检查不再是TL顶点的可用候选位置，并将这些TL顶点从TL顶点列表中删除；检查新产生的TL顶点，并将新产生的TL顶点加入到TL顶点列表中；更新每个TL顶点的属性；对TL顶点列表中的顶点按照从上到下、从左到右的规则排序。

对于图4所示的情况，可重构计算任务T1已经完成，则新增加了BL顶点BL3，原BL顶点BL3和BL顶点BL4变为BL顶点BL4和BL顶点BL5。各个BL顶点的属性变化为：

BL1B(X2,Y2)＝BL1T(3,1)

BL2B(X2,Y2)＝BL2T(2,2)

BL3B(X2,Y2)＝BL3T(7,3)

BL4B(X2,Y2)＝BL4T(5,4)

BL5B(X2,Y2)＝BL4T(2,5)

一种可重构器件片上面积管理优化方法专利购买费用说明