可重构系统功耗相关的硬件任务调度算法
引言
可重构系统是指以软件改变硬件结构以实现具体应用的计算平台，一般由非柔性但可编程的处理器和柔性的以程序控制重构的数字逻辑器件构成。目前国内外的可重构系统研究中，采用的可重构硬件主要是现场可编程门阵列(Field Programming Gate Array，FPGA)。可重构系统非常适合于那些对功耗有严格要求或者计算密集的应用，因为此类应用在FPGA上实现的功耗要大大低于在处理器上实现的功耗。将在FPGA上运行的任务视为“硬件任务”纳入实时操作系统(Real-time Operating Sys-tem，RTOS)的统一管理范围，可简化系统的设计与管理。因此，需要在传统的RTOS中引入硬件任务管理器，实现硬件任务的管理和调度。
目前，该研究已经取得了一定进展。如在参考文献[1]中提出的商用可重构系统OS4RS，包含的主要功能有任务的创建／销毁、异构任务的动态迁移、任务之间的相互通信等。支持软／硬件任务调试以及允许对操作系统模块和用户任务的跟踪监控，是可重构硬件操作系统的重要特征。在参考文献[2]中设计了一种基于软／硬件统一多任务模型的实时操作系统SHUM-μCOS，实现了统一任务的管理、基于静态优先级的软／硬件任务独立调度、硬件资源的管理以及软／硬件任务基于软件层的通信等机制。
但是大多数研究者考虑的软／硬件调度算法一般难以在现有的FPGA硬件平台上实现，如参考文献[2]中FORS算法采用的2D FPGA资源模型。这是因为当前的FPGA技术只允许所有的任务占用同样的“高度”，并且上述工作中几乎没有将功耗纳入考虑范畴。因此，类似在嵌入式微处理器中广泛采用动态电压调整(DynamicVoltage Scaling，DVS)技术以降低系统功耗，本文提出了一种动态调整FPGA工作频率的算法，在可重构系统的性能需求和功耗需求之间达到平衡，并且可以在当前的FPGA技术条件下实现。
1 调度模型
1．1 可重构系统体系结构
本文只考虑在当前FPGA技术条件下的可重构系统结构，如图1所示。FPGA分为动态和静态两部分。动态部分包括很多可重构模块(Reconfigurable Modules，RM)，每个硬件任务运行在1个RM上，各个RM占用的FPGA宽度可以不相等，一般由若干同列的CLB(Config-urabIe Logic Block，可重构单元)组成。静态部分则负责与CPU和RM之间的数据交互。
假设FPGA是由很多CLB成阵列排列而成，每1个CLB可以看成1个1×1的单位正方形，1个FPGA则是1个面积为ω×h的长方形。其中ω为长方形的宽度，h为长方形的高度，ω×h为该FPGA包含CLB的总数(即面积)。图2所示为1块5×4的FPGA。在实现中，因为每个RM都使用相同的FPGA高度，即h，所以最小的RM的面积是ωmm×h，其中，ωmin的大小依赖于硬件任务需要使用的CLB的个数。所以，1块FPGA上RM最多可以有：
当对1块FPGA进行配置时，其动态部分可以划分成具有不同宽度的RM，从而具有不同CLB需求的多个硬件任务可以同时运行在FPGA上。另外，对其中1个RM进行配置时，对于其他正在运行的部分没有影响，从而可重配置硬件使得硬件任务以一种真正的动态多任务方式运行。
1．2 任务定义
①硬件任务：硬件任务是指可重构系统中基于FPGA实现的功能模块。一个硬件任务配置完成后即可开始执行，在完成之前一般不会释放其占用的可重配置资源，即不能被其他硬件任务抢占。
②一个硬件任务可表示为Ti(fi，max，ai,ci,ti,ei，fworking)。其中，fi,max是硬件任务可以运行在RM上的最大时钟频率，这个频率是由每个具体硬件任务设计的时序状况决定的，所以每个任务的fi,max可能不同。ωi是任务占用的可重构硬件的宽度资源，ai表示硬件任务的到达时间,ci表示硬件任务的最后完成时限，ti是硬件任务工作在fi,max时的运行时间。本文中不单独考虑硬件任务在FPGA上的配置时间，而是把它并入运行时间中一起考虑。e是硬件任务工作在fi,max时的功耗，可由参考文献[4]建立的功耗模型进行估算。fworking是该任务在运行时FPGA的实际频率。
在参考文献[4]中，硬件任务的功耗和硬件的运行频率直接相关，因此，可以使用以下2个公式对硬件任务实际的运行时间和功耗进行估算：
其中，f是硬件任务实际的运行频率。
2 功耗相关硬件任务调度算法EEHTS
2．1 硬件任务调度器设计
目标系统如图3所示。用户程序分为2部分，其中软件任务运行在CPU上，硬件任务运行在FPGA上。本文中只考虑功耗相关的硬件任务的调度，目标是将软／硬件任务统一起来进行考虑，在满足任务截止时限要求的情况下降低系统的整体功耗，即：
2．2 调度原则和放置原则
在嵌入式系统中，任务的正确性不但依赖于其功能正确性，而且依赖于其执行的及时性，所以确保任务不错过截止期是最重要的调度依据。在满足任务截止时间的前提下，1个新到达的硬件任务Ti的最迟开始执行时间(Last：Starting time，LST)为LST(Ti)=ci-ti，如果Ti在放置时没有找到合适的位置，调度器并不立刻拒绝Ti，因为只要在LST(Ti)之前有满足Ti需求的资源被释放，那么Ti仍然可以满足其截止期要求。在EEHTS算法中，需要维护到达任务列表Alist，Alist中保存所有已经到达且未能成功分配的任务。已到达列表的任务按照任务的LST增序排列，即按照最早最迟开始时问优先(EarliestLast Starting time First，ELST)的原则进行调度。硬件任务调度器的核心是进行定位分配，即根据硬件任务占用FPGA资源大小在FPGA上寻找合适的位置对FPGA进行配置，如参考文献[5]中提出的MER算法。但是此类算法采用的FPGA面积模型都是2D资源模型，并不能在当前的FPGA技术条件下实现，所以本文采用类似传统操作系统管理存储器资源的方法，即首次适配(FirstFit)算法。在EEHTS算法中，需要维护空白资源列表B，B中保存了所有当前未被使用的FPGA上的空白区域。放置成功的硬件任务即可开始配置运行，因此在EEHTS算法中需要维护正在运行的任务列表Elist。执行列表Elist中包含所有正在运行的硬件任务Ti，任务按照执行完毕时间的增序排列。
在硬件任务完成之前，不能被其他任务抢占；当硬件任务完成之后，即可释放其占用的FPGA资源，并将执行完毕的任务插入到执行完毕任务列表Flist中。这个特点是硬件任务和软件任务的显著区别。
2．3 功耗相关硬件任务调度算法EEHTS
(1)算法1：EEHTS算法
在任何时刻t，EEHTS算法首先检查Alist队列中的第1个任务Ti，函数有3种可能的返回结果：ACCEPT、REJECT和NULL。第2行中如果FPGA空白区域列表B中有合适的位置放置任务Ti，那么将Ti加入到Elist中，然后第6行重新计算1个更加优化的FPGA频率fe，如果fe小于当前FPGA运行的频率fworking，并且在fe下所有Elist中任务均能在其截止期内完成，那么说明可以在保证任务截止期的条件下通过降低频率而降低硬件任务的整体功耗，所以此时算法返回ACCEPT；第13行如果任务即将或者已经错过最迟开始时间，那么此时函数返回REJECT，表示此任务被拒绝；第15行如果当前时刻没有合适的位置，但是任务仍没有到其最迟开始时间，表示在将来的时刻仍然可能获得任务所需资源，所以函数返回结果NULL。
算法1中第6行重新计算FPGA工作频率的算法如算法2所示，其中F是所有硬件任务工作频率值的集合。需要说明的是，同一时刻在FPGA运行的硬件任务的工作频率值必须相同，并且选择5作为FPGA频率的增量也是符合实际FPGA技术情况的。
(2)算法2：选择最优的频率值作为FPGA的运行频率
步骤1：fscheduled,max=min(fi,min|Ti∈Elist)
步骤2：对于F集合中的满足fmin≤f≤fscheduled，max的每个f值，计算：
选取使得计算步骤2中结果最小的，值作为FPGA的运行频率值，从而使得FPGA的总体功耗最低。
3 模拟实验及分析
由于当前并没有一个统一的基准用于评价可重构系统功耗相关的调度算法，因此采取了类似参考文献[2]中的模拟实验模型设计了离散时钟的模拟器，模仿实时系统中的时钟滴答以进行任务截止期的检查。然后设计随机任务生成器，生成分别含有1 000、2 000、3 009、4 000、5 000、6 000个Ti(fi,max,ωi,ai,ci,ti,ei,fworking)的任务集，硬件任务的宽度和执行时间也是随机生成的。
假定目标器件为Xilinx Virtex XCV1000，共96列×64行，其中可用于配置硬件任务的动态部分是80列，其他用于操作系统进行通信和I／O。模拟实验中采用的参数如下：任务的最小宽度ωmin=1，Nmax=80，任务的宽度范围ωi为1～80；fmin=20 MHz，fmax=100MHz，所以各个任务的可运行的最大频率fi,max∈[20，25，…，1 000]；任务在fi,max频率时的运行时间ti范围为100～1 000 ms。ei范围为20～200 mJ，ei的大小和任务宽度相关。到达时间范围01．5～500 ms，模拟器的时钟滴答设置为500 μs。分别模拟了采用ELST算法和EEHTS算法的任务集的总体运行时间和整体功耗，如图4和图5所示。从图4中可以看到，采用ELST算法的任务运行时间曲线要比采用EEHTS算法的低，这是因为只采用ELST算法时并不改变FPGA的运行频率，FPGA始终使用最高频率运行，显然这种方法的功耗会大于EEHTS算法，实验结果也证明了这点。如图5所示，EEHTs算法虽然牺牲了一些时间性能，但是硬件任务仍然可以在其截止期内完成，并且相对于ELST算法，硬件任务功耗大约降低了32％。
结语
在嵌入式系统中，低功耗是非常重要的目标。本文通过对可重构系统中硬件任务调度算法的研究，在对硬件任务调度时加入了对功耗的考虑，动态改变硬件任务运行的频率，从而降低系统整体功耗。
可重构系统是指以软件改变硬件结构以实现具体应用的计算平台，一般由非柔性但可编程的处理器和柔性的以程序控制重构的数字逻辑器件构成。目前国内外的可重构系统研究中，采用的可重构硬件主要是现场可编程门阵列(Field Programming Gate Array，FPGA)。可重构系统非常适合于那些对功耗有严格要求或者计算密集的应用，因为此类应用在FPGA上实现的功耗要大大低于在处理器上实现的功耗。将在FPGA上运行的任务视为“硬件任务”纳入实时操作系统(Real-time Operating Sys-tem，RTOS)的统一管理范围，可简化系统的设计与管理。因此，需要在传统的RTOS中引入硬件任务管理器，实现硬件任务的管理和调度。
目前，该研究已经取得了一定进展。如在参考文献[1]中提出的商用可重构系统OS4RS，包含的主要功能有任务的创建／销毁、异构任务的动态迁移、任务之间的相互通信等。支持软／硬件任务调试以及允许对操作系统模块和用户任务的跟踪监控，是可重构硬件操作系统的重要特征。在参考文献[2]中设计了一种基于软／硬件统一多任务模型的实时操作系统SHUM-μCOS，实现了统一任务的管理、基于静态优先级的软／硬件任务独立调度、硬件资源的管理以及软／硬件任务基于软件层的通信等机制。
但是大多数研究者考虑的软／硬件调度算法一般难以在现有的FPGA硬件平台上实现，如参考文献[2]中FORS算法采用的2D FPGA资源模型。这是因为当前的FPGA技术只允许所有的任务占用同样的“高度”，并且上述工作中几乎没有将功耗纳入考虑范畴。因此，类似在嵌入式微处理器中广泛采用动态电压调整(DynamicVoltage Scaling，DVS)技术以降低系统功耗，本文提出了一种动态调整FPGA工作频率的算法，在可重构系统的性能需求和功耗需求之间达到平衡，并且可以在当前的FPGA技术条件下实现。
1 调度模型
1．1 可重构系统体系结构
本文只考虑在当前FPGA技术条件下的可重构系统结构，如图1所示。FPGA分为动态和静态两部分。动态部分包括很多可重构模块(Reconfigurable Modules，RM)，每个硬件任务运行在1个RM上，各个RM占用的FPGA宽度可以不相等，一般由若干同列的CLB(Config-urabIe Logic Block，可重构单元)组成。静态部分则负责与CPU和RM之间的数据交互。
假设FPGA是由很多CLB成阵列排列而成，每1个CLB可以看成1个1×1的单位正方形，1个FPGA则是1个面积为ω×h的长方形。其中ω为长方形的宽度，h为长方形的高度，ω×h为该FPGA包含CLB的总数(即面积)。图2所示为1块5×4的FPGA。在实现中，因为每个RM都使用相同的FPGA高度，即h，所以最小的RM的面积是ωmm×h，其中，ωmin的大小依赖于硬件任务需要使用的CLB的个数。所以，1块FPGA上RM最多可以有：
当对1块FPGA进行配置时，其动态部分可以划分成具有不同宽度的RM，从而具有不同CLB需求的多个硬件任务可以同时运行在FPGA上。另外，对其中1个RM进行配置时，对于其他正在运行的部分没有影响，从而可重配置硬件使得硬件任务以一种真正的动态多任务方式运行。
1．2 任务定义
①硬件任务：硬件任务是指可重构系统中基于FPGA实现的功能模块。一个硬件任务配置完成后即可开始执行，在完成之前一般不会释放其占用的可重配置资源，即不能被其他硬件任务抢占。
②一个硬件任务可表示为Ti(fi，max，ai,ci,ti,ei，fworking)。其中，fi,max是硬件任务可以运行在RM上的最大时钟频率，这个频率是由每个具体硬件任务设计的时序状况决定的，所以每个任务的fi,max可能不同。ωi是任务占用的可重构硬件的宽度资源，ai表示硬件任务的到达时间,ci表示硬件任务的最后完成时限，ti是硬件任务工作在fi,max时的运行时间。本文中不单独考虑硬件任务在FPGA上的配置时间，而是把它并入运行时间中一起考虑。e是硬件任务工作在fi,max时的功耗，可由参考文献[4]建立的功耗模型进行估算。fworking是该任务在运行时FPGA的实际频率。
在参考文献[4]中，硬件任务的功耗和硬件的运行频率直接相关，因此，可以使用以下2个公式对硬件任务实际的运行时间和功耗进行估算：
其中，f是硬件任务实际的运行频率。
2 功耗相关硬件任务调度算法EEHTS
2．1 硬件任务调度器设计
目标系统如图3所示。用户程序分为2部分，其中软件任务运行在CPU上，硬件任务运行在FPGA上。本文中只考虑功耗相关的硬件任务的调度，目标是将软／硬件任务统一起来进行考虑，在满足任务截止时限要求的情况下降低系统的整体功耗，即：
2．2 调度原则和放置原则
在嵌入式系统中，任务的正确性不但依赖于其功能正确性，而且依赖于其执行的及时性，所以确保任务不错过截止期是最重要的调度依据。在满足任务截止时间的前提下，1个新到达的硬件任务Ti的最迟开始执行时间(Last：Starting time，LST)为LST(Ti)=ci-ti，如果Ti在放置时没有找到合适的位置，调度器并不立刻拒绝Ti，因为只要在LST(Ti)之前有满足Ti需求的资源被释放，那么Ti仍然可以满足其截止期要求。在EEHTS算法中，需要维护到达任务列表Alist，Alist中保存所有已经到达且未能成功分配的任务。已到达列表的任务按照任务的LST增序排列，即按照最早最迟开始时问优先(EarliestLast Starting time First，ELST)的原则进行调度。硬件任务调度器的核心是进行定位分配，即根据硬件任务占用FPGA资源大小在FPGA上寻找合适的位置对FPGA进行配置，如参考文献[5]中提出的MER算法。但是此类算法采用的FPGA面积模型都是2D资源模型，并不能在当前的FPGA技术条件下实现，所以本文采用类似传统操作系统管理存储器资源的方法，即首次适配(FirstFit)算法。在EEHTS算法中，需要维护空白资源列表B，B中保存了所有当前未被使用的FPGA上的空白区域。放置成功的硬件任务即可开始配置运行，因此在EEHTS算法中需要维护正在运行的任务列表Elist。执行列表Elist中包含所有正在运行的硬件任务Ti，任务按照执行完毕时间的增序排列。
在硬件任务完成之前，不能被其他任务抢占；当硬件任务完成之后，即可释放其占用的FPGA资源，并将执行完毕的任务插入到执行完毕任务列表Flist中。这个特点是硬件任务和软件任务的显著区别。
2．3 功耗相关硬件任务调度算法EEHTS
(1)算法1：EEHTS算法
在任何时刻t，EEHTS算法首先检查Alist队列中的第1个任务Ti，函数有3种可能的返回结果：ACCEPT、REJECT和NULL。第2行中如果FPGA空白区域列表B中有合适的位置放置任务Ti，那么将Ti加入到Elist中，然后第6行重新计算1个更加优化的FPGA频率fe，如果fe小于当前FPGA运行的频率fworking，并且在fe下所有Elist中任务均能在其截止期内完成，那么说明可以在保证任务截止期的条件下通过降低频率而降低硬件任务的整体功耗，所以此时算法返回ACCEPT；第13行如果任务即将或者已经错过最迟开始时间，那么此时函数返回REJECT，表示此任务被拒绝；第15行如果当前时刻没有合适的位置，但是任务仍没有到其最迟开始时间，表示在将来的时刻仍然可能获得任务所需资源，所以函数返回结果NULL。
算法1中第6行重新计算FPGA工作频率的算法如算法2所示，其中F是所有硬件任务工作频率值的集合。需要说明的是，同一时刻在FPGA运行的硬件任务的工作频率值必须相同，并且选择5作为FPGA频率的增量也是符合实际FPGA技术情况的。
(2)算法2：选择最优的频率值作为FPGA的运行频率
步骤1：fscheduled,max=min(fi,min|Ti∈Elist)
步骤2：对于F集合中的满足fmin≤f≤fscheduled，max的每个f值，计算：
选取使得计算步骤2中结果最小的，值作为FPGA的运行频率值，从而使得FPGA的总体功耗最低。
3 模拟实验及分析
由于当前并没有一个统一的基准用于评价可重构系统功耗相关的调度算法，因此采取了类似参考文献[2]中的模拟实验模型设计了离散时钟的模拟器，模仿实时系统中的时钟滴答以进行任务截止期的检查。然后设计随机任务生成器，生成分别含有1 000、2 000、3 009、4 000、5 000、6 000个Ti(fi,max,ωi,ai,ci,ti,ei,fworking)的任务集，硬件任务的宽度和执行时间也是随机生成的。
假定目标器件为Xilinx Virtex XCV1000，共96列×64行，其中可用于配置硬件任务的动态部分是80列，其他用于操作系统进行通信和I／O。模拟实验中采用的参数如下：任务的最小宽度ωmin=1，Nmax=80，任务的宽度范围ωi为1～80；fmin=20 MHz，fmax=100MHz，所以各个任务的可运行的最大频率fi,max∈[20，25，…，1 000]；任务在fi,max频率时的运行时间ti范围为100～1 000 ms。ei范围为20～200 mJ，ei的大小和任务宽度相关。到达时间范围01．5～500 ms，模拟器的时钟滴答设置为500 μs。分别模拟了采用ELST算法和EEHTS算法的任务集的总体运行时间和整体功耗，如图4和图5所示。从图4中可以看到，采用ELST算法的任务运行时间曲线要比采用EEHTS算法的低，这是因为只采用ELST算法时并不改变FPGA的运行频率，FPGA始终使用最高频率运行，显然这种方法的功耗会大于EEHTS算法，实验结果也证明了这点。如图5所示，EEHTs算法虽然牺牲了一些时间性能，但是硬件任务仍然可以在其截止期内完成，并且相对于ELST算法，硬件任务功耗大约降低了32％。
结语
在嵌入式系统中，低功耗是非常重要的目标。本文通过对可重构系统中硬件任务调度算法的研究，在对硬件任务调度时加入了对功耗的考虑，动态改变硬件任务运行的频率，从而降低系统整体功耗。