基于时空情境的可重构高性能任务调度体系

涂春萍， 柴亚辉， 黄卫春， 熊李艳

(华东交通大学 信息工程学院,江西 南昌 330013)



基于时空情境的可重构高性能任务调度体系

涂春萍， 柴亚辉， 黄卫春， 熊李艳

(华东交通大学 信息工程学院,江西 南昌 330013)

针对基于FPGA计算加速的异构高性能计算平台上的硬件任务调度需求，根据硬件任务的空间属性与时间属性，提出了一个基于时空情境CBTA的任务调度体系与相关算法。高性能计算平台的分级调度将CBTA的调度分为平台任务调度与节点任务调度。通过将任务与资源划分为不同的时空情境，提出了一个基于情境转化的自适应任务调度策略，并给出了CBTA调度算法的并行优化策略。最后通过实验来说明了算法在对用户响应时间、负载均衡以及任务拒绝率上的优势。

FPGA计算加速； 硬件任务调度； 时空情境； 自适应调度

0 引 言

基于异构架构[1]的高性能计算，是当今高性能计算的发展方向与热点之一，而随着FPGA的规模和性能的不断提高，将FPGA计算器件作为高性能计算机上的运算加速部件已经成为当前高性能计算研究方向的一个热点。任务调度系统的目标是要充分利用可重构硬件资源，任务调度是可重构操作系统[1]任务管理以及高性能计算平台任务管理的核心功能。对FPGA上的硬件任务的调度除了要考虑其运行时间外，更重要的是要在可重构器件中找到合适的放置位置，使得多个硬件任务在可重构器件上并行地执行[2]。本文主要研究在基于FPGA计算加速的可重构高性能计算平台系统中硬件任务的在线调度与放置算法与体系结构。

在FPGA上的基于二维的任务放置的研究已经取得了不少的研究成果，一般的放置算法均可以直接作为调度算法使用，放置算法中早期的以BL[3]、QA[4]、RBL[5]等为代表, 该类算法具有完全识别能力, 但早期的算法复杂度较高, 与可重构计算单元(Reconfigurable Computing Unit，RCU)数量成正比。

在硬件任务的调度上，除了空间因素之外，还需考虑时间属性，因此基于预约的任务调度被提了出来。文献[6]提出一种紧凑预约(Compact Reservation，CR)调度算法, 考虑所有的运行任务和预约任务，计算到达任务的接受区域各RCU最早可用时间，选择一个满足到达任务截止期要求的放置点, 该算法能够在一定程度上提高任务截止期保证率。文献[7]提出的Stuffing调度算法通过模拟未来时刻任务的终止和启动来为到达任务预约放置区域, 它是一种比较通用的算法，能够和现有的基于空闲空间的放置算法融合。而在文献[8]中作者提出一种基于时间窗口的Stuffing调度算法，从可以将Stuffing算法与扫描类放置算法进行融合。在进行任务调度时，通过在放置过程中，需要考虑FPGA的碎片化[9]程度来作为硬件任务放置到FPGA上的具体位置的一个决策依据，同时也会产生相应的碎片化评估算法与策略。而有的算法则是将时间与空间上的平衡[10]作为硬件任务调度的算法制定基础，而文献[11]中则提出一种R-T坐标体系，来构建FPGA上的任务调度算法。

纵观以上的从不同的视角出发所构建的关于FPGA上的硬件任务调度与管理算法，并没有从在基于多个FPGA上的资源对任务的竞争上来考虑任务调度算法的制定与构建。而异构高性能计算平台上的FPGA硬件任务调度除了要考虑在节点上的任务调度之外，还要考虑任务如何在计算节点之间进行抉择，因此在本文中我们将研究如何通过基于时间与空间情境下的任务调度体系与算法。

1 任务调度模型

从调度系统的功能结构上，基于FPGA的异构高性能计算平台上的硬件任务调度为一个多级任务调度系统，一般包括全局任务调度与节点任务调度两级系统。根据本文的研究方向,对高性能计算平台，其每个计算节点都是由通用处理器CPU和FPGA加速部件组成。CPU处理系统中的软件任务，而FPGA加速部件则处理系统中的硬件任务。本文仅研究如何调度和处理系统中的硬件任务。该系统调度模型分为平台任务调度与节点内任务调度两部分，调度系统软件运行在主处理器CPU上，而硬件任务则是运行在可重构器件FPGA上。

(1) 定义1：最大空闲矩形MFR。不能被其他任何一个空闲矩形所完全覆盖的空闲矩形为最大空闲矩形(Maximal Free Rectangle,MFR)[12-15]。对MFR的表示有多种方式，如：矩形的4个顶点坐标、矩形放置的左下角基点与矩形的长宽等。本文使用(xF,yF,w,h)来表示一个MFR，(xF,yF)是MFR左下角RCU的坐标，w与h是其宽与高。

(2) 定义2:硬件任务，包括待调度任务与正在运行任务。一个待调度任务定义为5元组：T(w,h,a,e,d)。其中w与h代表任务运行时占用的RCU的宽与高，则该任务面积AT=w*h，a为任务的到达时间，e为任务在FPGA上的预期运行时间，d为任务的截止时间，实时硬件任务必须满足时间约束关系a+e≤d。一个正在运行任务定义为7元组：TR(xR,yR,w,h,tS,e,tR)。xR与yR为该任务左下角在FPGA上的坐标点，tS为该任务在FPGA上的开始运行时间，tR为该任务在时刻t0时的剩余运行时间。

(3) 定义3：任务情境。将硬件任务根据其相关的属性，如：面积、运行时间、发生概率等，而将任务分为不同的情境。比如：根据任务的面积来划分任务情境时，可以设定一个面积阈值VA，当任务面积AT≥VA时，将该任务划分入大面积任务情境，否则划分入小面积任务情境。

(4) 定义4资源情境。将FPGA上的空闲资源根据其相关的属性，如面积、所在位置、边线组成情况等，将FPGA划分为不同的情境。比如：根据MFR的边线是否包含FPGA边界来划分MFR资源情境时，可以将MFR划分为非临边情境(Inner MFR,IM)、临边情境(Border MFR,BM)与顶角情境(Corner MFR,CM)，如图1所示。非临边情境IM指的是MFR的4条边线中不包含FPGA的边界线的子线段，如图1中的R3所示。临边情境BM指的是MFR的4条边中只有1条边线为FPGA边界线的子线段，如图1中的R5所示。顶角情境CM所指的是MFR的4个顶角中至少有1个顶角是FPGA的顶角，如图1中的R1、R2与R4所示。

图1 MFR资源位置情境实例

2 CBTA算法

对于任务集ST，FPGA上的任务调度系统关心的是如何将该ST内的所有的任务都尽量放置在本FPGA中，而尽量减少等待时间或减少任务拒绝率，而在高性能平台中，对每个FPGA而言，其关心的是如何能够让该ST内更多的任务来在“我”的FPGA上完成运行，而如何完成ST内所有任务的调度是平台调度所关心的，如何让多个节点共同来分担一部份任务子集。对于计算节点间的负载是否均衡，对于FPGA上任务调度而言，无须关心，其只需关心在该FPGA上的碎片化、负载率等问题。而平台任务调度，需要考虑不同计算节点间的负载均衡以及任务的吞吐量，而对于每个节点上的FPGA上的每个具体任务而言，则需要在任务平台上如何分配或者说是拿到对自己而言是“利益最大”的那个任务。

2.1 任务情境与资源情境

在基于以上关于任务情况与FPGA二维空间与时间维上的综合分析，我们提出了一个关于硬件任务放置与调度的基于时空情景(Context Based on Time and Area,CBTA)算法。

2.1.1 任务情境划分

对于任务情境我们从时间与空间的角度来对任务情境进行划分。根据任务的面积w*h，来将任务划分为N个不同的任务情境，N的取值取决于FPGA空间的大小与该平台上的任务大小的分布及其发生的概率。在本文中我们的实例是将任务划分为大面积任务(Large Square Rectangle Task,LSRT)、中面积任务(Middle Square Rectangle Task,MSRT)、小面积任务(Small Square Rectangle Task,SSRT)与极端矩形任务(Extreme Rectangle Task,ERT)。根据运行时间来对任务划分情境，根据某个时间阈值，将任务划分为长运行时间任务(Long Run Time Task,LRTT)与短运行时间任务(Short Run Time Task,SRTT)。

2.1.2 资源情境划分

对于资源情境我们从空间与位置的角度来对MFR资源情境进行划分。对MFR资源的面积划分与任务的面积w*h的划分保持对应，也对应划分为N个不同的MFR资源情境。同样在本文中我们将MFR划分为大面积MFR、中面积MFR、小面积MFR与极端矩形MFR。MFR没有直接的与时间情境有关的属性，但可以从其它的属性中来获取MFR上与时间相关的属性，比如：对于一个运行时间很长的任务，如果将其放置在FPGA的中央区域时，会造成长时间上的占据FPGA中间位置，而造成FPGA上的碎片化。而如果将其放置到FPGA上的边线或顶角上，则对FPGA造成的碎片化影响是较小甚至是最小的，如图2所示。

图2中，FPGA上正在运行多个任务，其中每个任务的小括号中为该任务的剩余运行时间。而T13是即将放置到FPGA上的新任务，可以看出其运行时间为120，有2个可以放置T13的MFR，分为R2与R3。R2的空间位置情境为IM，虽然其面积与T13的面积正好相等，但R3为CM情境，所以我们将T13放置到R3中。因为当20时间单位过去以后，如果T13在R2的位置上，则整个FPGA空间上所产生的新MFR的面积不会有很大的，而在R3的位置上，则MFR可以产生很大面积的新MFR。

图2 长运行任务时间放置情境

对于资源情境，我们分为节点资源情境与节点上MFR资源情境。节点资源情境为最大的MFR资源情境，MFR资源情境按面积从大到小进行排序，排序顺序为大面积MFR、极端矩形MFR、中面积MFR与小面积MFR。若当前MFR的最大资源情境为大面积MFR资源情境，则节点资源情境为大面积MFR资源情境。

2.2 CBTA调度体系

在基于FPGA计算加速的异构高性能计算平台中，对任务的放置与调度策略，是在传统的嵌入式系统上的进一步扩展，因此任务调度与放置将分为以下4个过程：

(1) 如何选择满足条件的候选计算节点；

(2) 如何从多个计算节点选中一个合适的FPGA；

(3) 如何从选中FPGA中选择一个合适的MFR；

(4) 如何将任务放置到MFR资源的合适位置上。

由于一个硬件任务最终运行在FPGA上要经过上面的4个过程，那么在基于任务情境与资源情境下，我们对应4个过程提出了一个CBTA调度体系。根据高性能计算平台的体系结构与本文模型的约定，我们设定如下调度模型。对于计算平台上的每个计算节点而言，设定其FPGA上的所有RCU资源为一个租用对像，而在FPGA上运行的任务，其占用的RCU资源作为一次租用，当任务运行结束时，租用结束，并按其租用的RCU数与时间进行租金支付。因此，每个FPGA都希望自己能够将自己的RCU资源全部出租出去或者尽可能多接收任务。

从平台的角度，希望用户提交到平台的任务尽可能全部被提交到FPGA上完成任务运行，而同时也要保证每个FPGA之间的负载量维持在一个均衡的角度。从用户的角度，则是希望所提交的任务能够尽快地完成提交并看到任务开始运行，至于是在哪个FPGA上，在FPGA的什么位置上用户不需关心。

CBTA任务调度的基本策略为：对用户提交的任务首先进行任务情境检测，根据其情境，放入到对应的情境任务队列；在资源端，每个计算节点在计算好自己的MFR资源全集后，对MFR进行资源情境分类，并确定节点资源情境；在全局资源管理器端，根据每个节点资源情境，确定好节点资源队列，然后在对应的任务情境与资源情境间进行资源匹配。以大面积任务队列匹配大面积MFR节点资源队列为例来说明任务调度策略，任务的调度不是由调度器任务去分配资源，而是由资源节点在任务队列上来取任务。取节点资源队列的当前头节点，然后依次在任务队列上从头节点开始匹配，如果当前队列节点上的任务能放置到该资源节点的MFR上，则取走该节点任务。继续下一个资源头节点，继续在剩余的任务队列上来取任务。而完成放置任务的资源节点，如果其资源情境没有发生变化，则将其节点排在节点资源队列的末尾。

在节点任务调度系统上，被节点资源选中的任务将根据一定的算法，在进行MFR选定时，我们基于以下原则来进行算法与策略的制定：①任务与资源对位匹配优先原则；②长运行时间任务优先放置到顶角MFR、临边MFR的原则；③大面积MFR入侵避免的原则；④如果资源节点上有满足当前任务TH的资源空间，则一定将调度该任务。在选定MFR之后，再根据任务所属的任务情境与MFR的资源情境的具体对应，而选择不同的任务放置策略。

2.3 计算节点竞争策略

当任务少，而资源空间多或者当节点资源队列在确定每个资源节点的位置时，必然要发生资源竞争问题，需要制定合理的任务与资源间的竞争策略，为了更好地提高每个资源节点上的资源利用率与负载均衡，我们采用资源负载率低优先的策略。

我们将时间维引入进负载率，将资源负载率LX重新定义：

令tRi为当前任务i的剩余运行时间，tRi=tE-tC+tS。当所有进行比较的资源节点的LX，其值最小的将排在第一位，如果最小值相等，则随机从其中选取一个节点。

2.4 资源情境与任务情境匹配算法

不同的任务情境在对应不同的资源情境时，由于没有一种算法能够对各种任务情境都产生好的效果，因此在不同的任务情境与资源情境的对应中，应采取适合于本情境下的任务资源分配算法。

在大面积MFR资源情境(Large Square MFR Resource,LSMR)下，可以放置的任务有：大面积任务LSRT、极端矩形任务ERT、中面积任务MSRT、小面积任务SSRT。对于每一种任务的面积情境，还对应着两种附加时间情境：长运行时间情境LRTT与短运行时间情境SRTT。

对于大面积任务情境LSRT，则采用大面积MFR入侵避免(Large MFR Invasion Avoiding First,LMIAF)与基于阈值碎片化(Defragmentation Threshold Based Best-Fit First,DTBBF)算法。

大面积MFR入侵避免算法LMIAF:设大面积MFR，其表示为ML(XL1,YL1,WL,HL)，而硬件任务TH放置在另外一个MFR(设为MA)之后，其左下角坐标为(XH1,YH1)，硬件任务的宽与高为(WH,HH)。判断该硬件任务TH是否入侵该MFR的计算如下：

ML的右上角坐标为(XL3,YL3)=(XL1+WL-1,YL1+HL-1)，放置后的TH的右上角坐标为(XH3,YH3) =(XH1+WH-1,YH1+HH-1)。IF (XH3>XL1&&XH1YL1&&YH1XL1&&XH1YL1&&YH1

阈值碎片化优先算法DTBBF，即：MFR的宽与高，要么与所选中任务TH的宽与高相同，要么其宽与高和TH的宽与高的之差大于等于一个阈值VW与VH。

对于极端矩形任务情境ERT，则采用大面积MFR入侵避免算法LMIAF。

对于中面积任务情境MSRT，则采用大面积MFR入侵避免LMIAF与最长相连实边(Maximal Connected Real Edge First，MCREF)算法。

最长相连实边优先算法MCREF，所谓相连实边，指的是构成MFR的实边EM1(n1,m1)与EM2(n2,m2)，n到m的方向为从左向右或从上向下。如果两条实边相连，则一定有：n1==m2||m1==n2||n1==n2||m1==m2，且EM1与EM2的交点一定为MFR的顶点。

MFS= max(LM1,LM2, …LMQ)，Q表示共有Q个候选MFR。

对于小面积任务情境SSRT，则采用大面积MFR入侵避免算法LMIAF与最长相连实边算法MCREF。

在极端矩形MFR资源情境(Extreme MFR Resource,EMR)下，可能可以放置的任务有：极端矩形任务ERT、中面积任务MSRT、小面积任务SSRT。

对于极端矩形任务情境ERT，则采用基于Best-Fit的算法。

对于中面积任务情境MSRT，则采用基于同高或同宽优先SWSHF(Same Width or Same Height First)算法。

同高或同宽优先算法SWSHF，即任务的高与宽至少要有一个与MFR的高与宽要相等，如果没有条件满足其要求，则选队列中的第一个能放置的下的MFR。

IF (TH.W==ML.W||TH.H==ML.H)，则选择该ML放置该硬件任务TH。

对于小面积任务情境SSRT，则采用最长相连实边算法MCREF。

在中面积MFR资源情境(Middle Square MFR Resource,MSMR)下，可以放置的任务有：中面积任务MSRT、小面积任务SSRT。

对于中面积任务情境MSRT，则采用最长相连实边MCREF与基于阈值碎片化算法DTBBF。

对于小面积任务情境SSRT，则采用最长相连实边算法MCREF。

在小面积MFR资源情境(Small Square MFR Resource,SSMR)下，可以放置的任务有：小面积任务SSRT。

对于小面积任务情境SSRT，则采用最长相连实边算法MCREF。

因此，我们需要有一个动态的情境任务调度算法库(Dynamic Context Task Schedule Library,DCTSAL)，来保存各种不同任务与资源情境匹配下的任务调度与任务放置算法，以供任务在线调度时及时调用。

3 实验模拟

本文实验用抽象模型的模拟调度来评估算法的调度性能。仿真环境是在Windows下用VC++开发的实验模拟程序。每个实验是在多次运行以后得到的平均值，因为在实验环境的参数中，多次使用随机函数产生的相关数据，因此采用多次运算的平均值。

在任务调度中，设定FPGA为20*20，每个计算节点1个FPGA计算加速部件，大矩形任务LSRT的面积AL≥8*8=64,且WL≥8 andHL≥8；中矩形任务MSRT的面积AM≥4*4，且4≤WM<8 and 4≤HM<8；小矩形任务SSRT的面积AM<4*4，且1≤WM<4 and 1≤HM<4；其它情况为极端矩形任务ERT；而长时间任务LRTT与短运行时间任务SRTT不设立单独的队列，根据其矩形的形状分散于不同的矩形队列处理的并行分支中。

试平台环境为4核，采用OpenMPI的基于ShareMemory的编程模式，考虑到在任务的不同情境中所出现的概率与在等待任务队列中大任务与极端任务出现等待的情况要远远高于中矩形与小矩形任务，因此，在对并行队列的并行处理上将到达与等待队列结合起来，分配策略如下：

到达大面积任务队列ALRTQ + 等待大面积任务队列WLRTQ；

到达极端矩形任务队列AERTQ + 等待极端矩形任务队列WERTQ；

到达中面积任务队列AMRTQ + 等待中面积任务队列WMRTQ；

到达小面积任务队列ASRTQ + 等待小面积任务队列WSRTQ。

测试条件如下：

C1：计算节点4个，任务集200；

C2：计算节点8个，任务集800；

C3：计算节点16个，任务集3 200；

C4：计算节点32个，任务集6 400。

在图3中，X方向上测试条件C1～C4，在Y方向上则是算法在平台级的运行时间(μs)，该时间不包含任务在节点上的调度与放置时间，也不包含等待任务运行完成的时间。可以看出，在只有4个节点时，任务调度的串行与并行计算效果并没有太大差别，但随着计算资源的增大以及对应的任务到达并发数目的增加，并行计算的优势逐渐显现。

图3 串行与并行运行效果比较

我们另一个测试比较是在基于非情境算法的调度性能参数比较。在一般的基于高性能计算平台上的任务调度算法并不适用于基于FPGA加速的高性能计算平台上的硬件任务调度，在基于FPGA上的任务放置中，我们常用的算法有Best-Fit，First-Fit等。我们选基于Best-Fit的调度算法作为调度测试性能的依据。

基于Best-Fit调度算法调度过程如下，采用一个统一的全局资源队列，来保存所有的计算节点上的MFR，对每个MFR除了标记其大小空间属性，还标记其属于哪个计算节点。当有任务到达时，从资源队列RQ中选择一个面积、宽与高都相差最小的一个MFR作为要放置任务的MFR，之后更新MFR情况，并重新更新资源队列，并继续接收新任务。CBTA调度算法的参数与上面的参数相同，测试情况为相同的负载概率，测试条件也为设计算节点为16节点，任务集为1 000，2 000，3 000，4 000。

图4为在不同的高负荷下的RCU数平均拒绝效果图，X方向为运行的任务集，Y方向上平均RCU数。由图中可以看出，因为Best-Fit为非情境模式，不能用并行程序实现，而CBTA则是用并行程序实现。而在基于自适应的节点任务调度策略中，通过根据不同的情境，对应不同的任务调度与放置算法，因此，在任务的吞吐率与响应时间上，体现了较高的优势。当任务集增加以后，非情境的Best-Fit算法的计算时间与响应时间明显增加，因为没有分情境，所以以串行的方式进行计算，而CBTA则是以4核并行计算，同时，大面积矩形任务的拒绝率的下降最为显著。

图4 任务拒绝RCU数效果图

图5为负载均衡效果图。X方向上为任务集，Y方向上为平均负载率差，即最高负载节点的负载率-最低负载节点的负载率，比如：某时刻t0时，最高负载节点为节点5，其负载率为82%，而最低负载节点为节点13，其负载率为40%，则负载率差为82%-40%=42%。在负载率差上，我们取不同的10个时刻时的负载率差之后的平均值。可以看出，在CBTA算法下，节点之间的平均负载率差相对比较稳定，且负载均衡远远好于Best-Fit算法。

图5 负载均衡效果图

4 结 语

本文中，针对基于FPGA计算加速的异构高性能计算平台上的硬件任务调度需求，根据硬件任务的空间属性与时间属性，提出了一个基于时空情境CBTA的任务调度算法。高性能计算平台的分级调度将CBTA的调度分为平台任务调度与节点任务调度，我们将任务与资源划分为不同的时空情境，提出了一个基于情境转化的自适应任务调度算法，并根据不同的任务与资源情境分别提出了适合对应情境的任务调度与放置算法，并给出了CBTA调度算法的并行优化策略，通过实验来说明了算法在对用户响应时间、负载均衡以及任务拒绝率上的优势。

在下一步的研究中，我们将更好地对分级调度中的任务与资源情境进行进一步研究，以更好地适应基于任务上的空间与时间上的调度算法。同时我们将对高性能计算架构进一步的进行扩展，包括的架构如每个计算节点上有多个FPGA加速部件时，当FPGA之间的性能具有差异时，如何能实现更高效的任务调度与放置等。

[1] 周 博,王石记,邱卫东,等. SHUM-UCOS:基于统一多任务模型可重构系统的实时操作系统[J].计算机学报, 2006, 29(2): 208-218.

[2] 周学功, 梁 樑, 黄勋章, 等. 可重构系统中的实时任务在线调度与放置算法[J].计算机学报, 2007, 30(11):1901-1908.

[3] 莎尔玛 D D, 普拉丹 D K. 一个快速有效子网格在网状连接并行计算机内的分配方法[C]: // 第五届IEEE并行分布式处理会议论文集, 华盛顿DC, IEEE计算机学会, 1993: 682-689.

[4] YOO S M, YOUNG H Y, SHIRAZIB. 2D网眼架构上的高效任务分配框架[J]. IEEE并行与分布式系统汇刊, 1997, 8(9): 934-942.

[5] CHIU G M, CHEN S K. 一个高效的极少开销代价的二维网眼上的子网格分配框架[J]. IEEE并行与分布式系统汇刊, 1999, 10(3): 471-486.

[6] 周学刚, 王 英, 黄新章. 可重构设备上快速任务放置与调度[C] //2007年国际可编程阵列逻辑与应用国际会议论文集, 华盛顿DC, IEEE, 2007:132-138.

[7] 施泰格 C, 瓦尔德 H, 普拉则内 M. 部分可重构设备上实时任务在线调度与放置[C] // 第24届国际实时系统会议论文集, 华盛顿DC, IEEE计算机学会, 2003:224-235.

[8] 周学刚, 王 英, 黄新章. 可重构计算机系统实时任务在线调度[C] // 2006年国际可编程阵列逻辑与应用国际会议论文集, IEEE, 2006: 57-64.

[9] 艾哈迈德 A E, 埃尔伯达 M, 沙辛 S I. 碎片化敏感的可重构设备任务放置[C] // 第六届片上系统实时应用国际会议, 华盛顿DC, IEEE, 2006: 37-44.

[10] 伊图尔贝 X, 贝壳里德 K, 阿斯兰 T, 等. 基于区间-时间反应平衡的实时硬件任务调度算法[C] // 2010年IEEE现场可编程技术国际会议, 北京, 2010: 224-232.

[11] 余国良,伍卫国,杨志华, 等.一种采用边界表进行可重构资源管理及硬件任务调度的算法[J]. 计算机研究与发展, 2011,48(4):699-708.

[12] 柴亚辉, 沈文枫, 徐炜民, 等. 基于CPTR的FPGA空闲矩形资源全集查找研究[J]. 上海大学学报(英文版), 2011, 15(5): 391-394.

[13] 柴亚辉, 张胜辉, 黄卫春, 等. 动态部分可重构系统空闲资源全集管理研究[J]. 计算机科学, 2013, (2): 20-23.

[14] 李 涛, 杨愚鲁. 基于最大空闲矩形的可重构资源管理方法[J]. 计算机工程, 2008, 34(3): 46-48.

[15] 李 涛, 刘培峰, 杨愚鲁. 动态部分重配置及其FPGA实现[J]. 计算机工程, 2006, 32(14):224-226.

Research on Task Schedule Architecture of Reconfigurable High Performance Computing Based on Time and Area Context

TUChun-ping,CHAIYa-hui,HUANGWei-chun,XIONGLi-yan

(College of Information Engineering, East China Jiao Tong University, Nanchang 330013, China)

According to the requirement of hardware task scheduling of heterogeneous high performance computing platform, based on FPGA computing accelerate, a task scheduling system is developed based on CBTA of time and area context. The development contains system architecture and related algorithms. The multi-level of task schedule on high performance platform divides the CBTA into platform task schedule and node task schedule. Classifying the task and resource into different time and area contexts, a self-adaptive task schedule strategy based on the resource context transform is proposed. Then a parallel optimization strategy is put forward. Finally through the experiment, the advantages of CBTA on response time, load balance and task reject ratio are shown.

FPGA computing accelerate; hardware task schedule; time and area contexts; self-adaptive schedule

2014-03-27

江西省自然科学基金项目(2014BAB201028)；华东交通大学校立基金(11XX04)

涂春萍(1970-)，女，江西南昌人，硕士，高级实验师，研究方向为嵌入式系统。

Tel.：13970948355；E-mail：tcp@ecjtu.jx.cn，915412273@qq.com

TP 316

A

1006-7167(2015)03-0116-06