一种可重构资源管理模型及其调度技术

米　捷，王佳欣

MI Jie,WANG Jiaxin

河南工程学院 计算机学院，郑州 451191

College of Computers,Henan Institute of Engineering,Zhengzhou 451191,China

1　引言

可重构计算机把算法映射到一些专门的硬件电路，这些硬件电路的配置和执行一般基于静态随机存取存储器（Static Random Access Memory，SRAM）的现场可编程门阵列（Field-Programmable Gate Array，FPGA），使得这些计算机通过硬件重新配置就变得更加灵活。对于许多计算密集型的应用如数字信号处理领域，可重构系统相比于一般的处理器，可获得更高的性能和能量效率。

早期的FPGA在密度和重构能力方面有限，但随着微处理器的发展，如今的器件/设备可提供数百万门，且能实现部分重构和回读，允许在器件/设备上配置和执行电路，而不会影响其他正在运行的电路。为了表达这种电路的动态特性，通常把这种电路表示为硬件任务。在许多基于可重构嵌入式系统的应用领域，如网络化移动系统[1]和可穿戴计算系统[2]，不同任务的激活时间和频率仅在运行时才知道，任务执行是通过用户生成的事件和环境的变化来触发的。在这种高度动态情形下，需要定义一组好的系统服务来支持可靠的应用以及管理运行时的可重构资源，通常把这些系统服务称为可重构操作系统。

可重构操作系统中的一个核心问题，就是部分可重构资源的建模和运行在可重构资源上的任务的在线调度。一个多任务可重构器件可以被看作是一个受额外全局资源约束的多处理器。对可重构面的划分从某种程度上可减轻这种资源约束并简化任务的调度，所以可重构操作系统成为近些年来的研究热点。

硬件多任务描述首先由文献[3]提出，文献[4]对包括设备分区、分配、放置和寻由的操作系统服务进行了研究；文献[5]对硬件任务的优先权进行了研究；文献[6]提出了一种可重构操作系统，操作系统的主要部分是资源管理单元，并针对资源管理单元提出了对应的在线调度和放置算法，其特点是资源的再利用和再配置；文献[7]根据可重构平台的任务特征以及资源特征，将对硬件任务和可重构资源的管理纳入到操作系统的范畴，通过在系统中添加硬件函数库以及定制软件函数库辅助完成任务调度和资源管理，并实现了基于可变窗口的任务调度算法和资源管理算法；文献[8]采用预取（预重构）技术通过并行重构配置和其他任务执行来减少重构时延，在考虑任务之间的数据依赖关系的情况下优化重构调度，并用最短关键路径算法减小重构开销；文献[9]针对一维可重构器件中硬件任务的调度问题，提出了一种基于边界表的可重构资源管理方法，该方法用“边界表”数据结构记录R-T坐标系中的区域边界及其位置关系，实现对可重构资源的管理，并提出了R-T坐标系下的任务调度及布局算法；文献[10]提出了一种适用于二维可重构器件的双仲裁时间片可重构硬件任务调度算法DATS（Double Arbiters Time-Sliced），算法采用两个仲裁器对硬件资源进行管理，并根据空间和时间约束动态裁决任务布局位置，同时设计了双仲裁时间片任务调度模式图，对任务的调度和布局过程进行合理分离，使任务调度和布局过程相对独立并简化处理过程；文献[11]提出了支持功能演进的可重构数据平面结构以及用户功能定制的映射算法，通过插入用户配置单元的方式对数据包解析、匹配和处理过程进行编程，从而支持用户自定义的功能部署。

本文针对可重构器件的操作系统层面进行了研究，提出了一种有效的管理模型和在线调度算法。仿真结果表明，基于本文提出的资源管理模型和调度算法，不仅能优化平均响应时间和实现任务的有效调度，而且相比于其他调度算法，还能获得更高的资源利用率。

2　可重构资源管理模型

可重构资源的管理通常用可配置逻辑块的一个矩形阵列来建模，在其上执行的任务也是用这种更小的逻辑块矩形阵列来建模；可重构资源区域模型与重构面上的任务放置和调度问题的复杂性密切相关。因此本文先通过对两种典型的区域模型的优缺点进行分析，然后提出一种新的可重构资源管理模型。

2.1　二维区域模型

图1（a）所示为最灵活的区域模型，它允许把矩形任务放置在二维可重构面上的任何地方。这种模型得到了广泛采用，其优点是当多个任务可以打包处理时，有很高的资源利用率；但另一方面，该模型的高度灵活性，又使得任务放置和调度相当困难。在线放置算法的提出，找到一个很好的、甚至是可行的任务放置方法。文献[12]对此进行了研究，并提出了一种高效的数据结构和启发式算法。当任务被放置在任意位置时，其余的自由区域就是分散碎片化的。这种外部碎片可能会阻止一个新的任务的放置，尽管有足够的可用资源。为了防止或减少这种外部碎片化，文献[13]研究了去碎片整理技术，即局部重装和有序压缩；同时，图1（a）所示的区域模型很难采用目前流行的FPGA技术-赛灵思（Xilinx Virtex）来实现。首先，任务需要外部导线连接到其他任务和I/O焊盘，相关研究或认为这种通信是通过配置和回读（这是可行的但可能是低效的）建立在长方形任务区域内部，或提出在任务之间留出一些空间作为通信信道；其次，任务连接和I/O必须动态重新寻由，而且时间安排必须重新进行分析，这是目前的商业设计工具所不支持的。

图1　可重构资源模型

图1（b）所示为一个二维划分模型，在这个模型中，可重构面被划分成一个静态的、数量固定的配置位置，即所谓的块。每个块可以一次容纳一个任务。这种划分技术由文献[14-15]首次提出。这种区域划分简化了放置和调度，使得目前的技术实现更具现实性。由于块有固定的位置，其余的区域就可以作为操作系统的资源。通信信道和I/O由操作系统专门提供。对于在线寻由和时序分析来说，在任务和操作系统之间就不需要采用固定接口。其不足之处就是内部碎片化，也就是说，当一个任务小于一个块时，该区域就被浪费掉了。

2.2　一维区域模型

图1（c）所示为一个一维区域模型，在这个模型中，任务可以沿水平方向尺寸的任何位置放置，垂直尺寸是固定的。这种模型首先由文献[16]提出，可简化放置和调度，适合在Xilinx Virtex上实现。然而，这种模型会导致内部和外部碎片化，需要去碎片整理技术；图1（d）所示为一维块划分区域模型，这种模型将图1（b）模型中简化的调度和放置与图1（c）模型中的可实现优势结合了起来，其缺点在于内部的高度碎片化。

2.3　本文提出的可重构资源管理模型

本文提出的可重构资源管理模型如图2所示。可重构器件由一个主CPU控制，主CPU运行在线调度器和放置器（放置器可工作在约束模式和选择模式），并通过一个配置/回读端口实现配置和回读。配置和回读时间取决于任务的宽度。该模型的实现主要包括三方面：首先，主CPU可以从外部连接到可重构器件；其次，主CPU和可重构区域可以被集成在一个芯片上的可配置系统（Configurable system on Chip，CsoC）里；第三，主CPU可以在可重构器件的操作系统区域实现为一个合成的软芯。

图2　本文提出的可重构资源管理模型

可重构器件由有相同垂直尺寸的固定大小的块构成。考虑不同宽度的块，即有宽度为l的m个块，l≤m，不同宽度为w1,w1,…,wl，假设通信通过在操作系统区域预先分配的信道进行，调度和放置不受通信需求的限制。因此，不失一般性，可以这样来安排块：其宽度从左到右单调减小，即wj≥wi,j＞i。图1（d）的区域模型就是本文提出的资源模型的一个特例。

采用不同大小的块的目的是为了在资源和任务之间实现更好的匹配。让块宽度适应任务宽度可以减少内部的碎片化，并可得到更高的平均资源利用率。尽管在一个任务集的调度过程中块宽度是固定的，但仍然能够在一个较长的时间尺度上改变宽度。例如，如果一个即将到达的任务集的最大任务宽度已知，则可以对器件重新划分，把其最大块宽度限制为最大任务的宽度，从而增加可用块的数量。

可见，划分技术决定着块的数量和宽度，也起着至关重要的作用。一个合理的划分方法会得到好的调度结果，比如减少一个任务集的总执行时间。假设一组任务必须执行，调度目标是使总的执行时间最小化，全部任务在同一时间到达，其宽度在[wmin,wmax]上服从均匀分布，其执行时间也为均匀分布，放置器工作在约束模式，可重构器件被划分成宽度为w1,w2,…,wl的块，每一宽度的块数目分别为m1,m2,…,ml。约束模式将任务进行分类，一个类由一个宽度间隔如(wi-1,wi]来确定，进入这个宽度间隔的任务获得mi个块来执行。定义δi=wi-wi-1、Δ=wmax-wmin。被调度给(wi-1,wi]的任务的百分比为δi/Δ，这就是类(wi-1,wi]总的执行时间请求的度量。如果有mi个块被分配给类(wi-1,wi]，则可得到类(wi-1,wi]的总的执行时间的度量为δi/(Δ·mi)。任务集的总的执行时间是全部类的执行时间的最大值。因此，划分技术应选择参数wi和mi以满足：

例如，考虑一个可重构器件的Wˉ=80，wmin=4，wmax=20 ，则划分{3×20，2×10}得到的执行时间度量划分{2×20，2×15，1×10}得到的执行时间度量，可见，第一个划分对于所描述的情形来说有更好的性能。

3　在线调度算法

在线调度问题主要是把任务放置在可重构面上。鉴于任务在器件上的具体配置，不是每个就绪的任务都是可放置的，这样可能会严重影响调度，因此任务的在线调度也是一个很重要的问题，对此，本文提出如下的调度算法。

假设任务集由n个不相关的任务构成，每个任务tj由一个事先未知的到达时间aj来描述，其请求的区域用它的宽度wj、请求执行时间cj和截止时间dj（可选）来表示，配置和回读时间与任务宽度成正比。

调度器采用图3所示的结构，它由多个队列和两个函数fSPLIT和fSELECT构成。队列的数量和位置取决于器件的块划分。如果靠近右边的下一个块bi有更小的宽度，即wj＞wi，则生成队列qj并把它分配给块bj。最右边的块b1总是获取所分配的队列q1。

函数fSPLIT的工作分为两个步骤：首先，它将一个块宽度wx分配给最右边队列到达的任务tx（wx足以容纳tx）；其次，fSPLIT按照某个排序规则将任务插入到队列。

图3　在线调度算法的构成

函数fSELECT实际上是选择和放置下一个即将要执行的任务。当每次一个执行任务终结，一个配置或回读过程结束，或一个新的任务到达某个队列头部时fSELECT就被调用。在全部队列头部中，fSELECT选择可以被分配和配置到能够容纳其大小的最小空闲块的任务。

fSELECT中的放置器可以工作在两种模式：在约束模式下，队列qi中的任务只能被放置到对应于qi的块中；在选择模式下，放置器可以把一个任务分配给能容纳它的任何块。因此，队列qj中等待的任务可被分配给块bj,…,bm，而不是块b1,b2,…,bi。图3的示例就表示选择模式，来自q3的任务可以放置在b4和b3中，而q1中的任务可以放置在任何块中。

为了实现上述在线调度算法的思想，可采用非抢占式和抢占式调度方法。

3.1　非抢占式调度方法

非抢占式调度既不抢占在可重构器件上运行的任务，也不抢占配置过程本身。一旦fSELECT选择一个任务，任务就被加载并运行至终止。本文采用以下两种方案来实现非抢占式目标：

（1）先到先服务（First-Come First-Serve，FCFS）

对于FCFS来说，fSPLIT分配一个时间戳给每个到达的任务并将这个任务插入到合适的队列。排序规则是先进先出（First-In First-Out，FIFO）；fSELECT的选择规则是挑选具有最早到达时间戳的任务。

（2）最短作业优先（Shortest Job First，SJF）

对于SJF来说，fSPLIT根据任务的执行时间来对队列进行排序。在每个队列中，头部记录识别具有最小执行时间的任务；fSELECT的选择规则是挑选具有最小执行时间的任务。

3.2　抢占式调度方法

抢占式调度抢占在可重构器件上运行的任务来分配给具有更高优先级的任务，而且配置和回读过程也可以被抢占（负载中断和卸载中断），如图4所示为任务状态图。配置过程总是被更高优先级的任务所中断。只有当更高优先级的任务即将被加载到一个不同于bl的块时，卸载块bl的回读过程才被中断；否则，回读继续，bl必须卸载完。本文采用以下两种方案来实现抢占式目标：

图4　抢占式调度的任务状态

（1）最短剩余处理时间（Shortest Remaining Processing Time，SRPT）

对于SRPT来说，fSPLIT根据任务的剩余执行时间来对队列进行排序。fSELECT的选择规则是挑选具有最小剩余执行时间的任务。

（2）最早截止时间优先（Earliest Deadline First，EDF）

对于EDF来说，fSPLIT根据任务的截止时间来对队列进行排序。在每个队列中，头记录识别具有最早截止时间的任务。fSELECT的选择规则是挑选具有最早截止时间的任务。

当全部块都是等宽度时，只有一个队列被分配给最右边的块。在这种情况下，FCFS、SJF、SRPT和EDF完全表现出和单处理器一样的功能；因此，不同大小的块实际上构成了一个附加的资源约束，这个约束可能会削弱调度算法的性能。例如，FCFS可在一个更早到达的更大任务之前调度一个稍后到达的更小的任务，这就是对不同的任务要采用不同调度算法的原因。

4　仿真实验

通过仿真实验来评价本文提出的资源模型和在线调度算法的运行情况和性能。

仿真实验在一个基于PC的XESS XSV-800板上进行，板上安装有一个Virtex XCV-800 FPGA。任务采用VHDL来设计，用商业设计工具Xilinx Foundation来实现FPGA比特流，从这些完整的比特流中提取了部分比特流；然后在部分比特流内设置并存储状态位的位置；在FPGA上创建一个操作系统并把剩余区域划分成许多块，每个块有一个复位信号。主机PC可以执行下列操作系统功能。

（1）任务负荷：任务是通过修改部分比特流的帧地址重新放置的，然后把部分比特流写入到FPGA，当块复位信号被激活，就加载初始状态并开始任务执行。

（2）任务抢占：正在运行任务的状态被抢占是通过激活FPGA上的抢占信号来实现的，然后，具有该状态的任务被回读，最后，运行环境被提取并通过访问回读比特流中的状态位保存下来。

（3）任务恢复：这与任务加载基本相同，唯一的区别在于把先前提取的状态插入到加载前的部分比特流。

为了实现调试，让块访问连接到外部发光二极管的I/O引脚；仿真参数包括可重构器件的规模大小、一个器件列的配置和回读时间以及块划分，在仿真中忽略CPU所需的运行时间。仿真框架包括仿真器模块、一个任务发生器、一个数据采集和统计分析（含甘特图查看器）模块，以及配置情况和队列负荷的图形化显示。

4.1　划分和放置方法的评价

本节仿真用于分析划分和放置方法对非抢占式调度算法FCFS性能的影响进行评价。假设任务独立，因此调度算法的性能就可以通过一个任务集的平均响应时间来度量。任务ti的响应时间为：

式中，fi为任务的完成时间，ai为任务的到达时间。假设一个列的配置或回读需159 μs，可用列为96列，其中只有80列为块可用列，剩余的16列被操作系统占用。采取随机生成有100个任务的任务集，任务宽度均匀分布在[4，20]列之间，执行时间在[2，200]ms之间，到达时间在[0.5，500]ms之间，仿真器分辨率即一个时钟周期的时间设置为500 μs。

如图5所示为两种放置器模式（即约束模式和选择模式）和五种不同划分时得到的仿真结果。对于两种放置器模式来说，划分[1×20，2×15，3×10]表现出最好的性能。在约束模式，划分[2×20，2×15，1×10]对于较小的任务明显表现出瓶颈，而选择模式有更好的结果，因为较小的任务也能够被分配给较大的块。划分[1×20，10×6]是一种不正常的情形，因为宽度为6的10个块都是很低效的。在这种情况下，总负荷的88%将被调度到一个大的块，因此，平均响应时间急剧增加。

图5　FCFS的平均响应时间

4.2　抢占式调度EDF的仿真分析

如图6所示为调度器运行抢占式调度算法EDF、放置器工作在选择模式时的甘特图查看器截图。可重构面被划分成两个块b1和b2，其宽度分别为w1=5、w2=10，调度的任务集Tx(ax,wx,cx,dx)由四个任务构成：T1（1，5，8，26），T2（2，5，8，24），T3（8，5，4，23），T4（9，8，4，20）。

图6　抢占式EDF调度算法的甘特图

任务T1、T2和T3的配置和回读时间是两个时间单位，任务T4的配置和回读时间是三个时间单位。从图6可见，在时刻1，T1到达并开始配置到b1；在时刻2，T2到达，并获得一个比T1更高的优先级，放置器工作在选择模式把T2放置到b2，即T1的配置被抢占（配置中断），T2被配置到b2。

在时刻4，配置/回读端口被T2释放，T1开始重新配置到b1；在时刻8，比T1和T2有更高优先级的T3到达。由于两个块已经被使用，故调度器选择T1被抢占，因为T1的截止时间较长，b1上的T1的回读开始；在时刻9，全部任务中具有最高优先级的T4到达，T4只能被放置在b2上，因此T2必须被抢占。在当前处理过程中的T1的回读被停止（卸载中止），而由T2的回读开始取代，T1恢复在b1上的执行；在时刻11，T2的回读已经完成，T4被加载到b1。

可见，调度算法能很好地对到达任务实现有效的调度。

4.3　不同调度算法的资源利用率比较分析

本节对本文提出的非抢占式调度算法FCFS和抢占式调度算法EDF与文献[6]和[7]的调度算法在资源利用率方面进行比较，如图7所示为可重构资源利用率比较曲线。从图7可见，基于本文提出的可重构资源模型和划分技术，采用抢占式调度算法的资源利用率最高，可达90%以上，非抢占式调度算法次之，文献[6-7]的调度算法的资源利用率明显要低于本文的两种调度算法；而且随着任务负荷的增加，本文的两种算法表现出更好的性能，主要是本文提出的资源模型考虑了不同块的大小，让块的宽度自适应任务的宽度，从而可减少内部的碎片化，同时在已知到达任务集的最大任务宽度时，划分技术可以对器件重新划分，把其最大块宽度限制为最大任务的宽度，从而增加可用块的数量，减少总的任务执行时间。

图7　不同调度算法的资源利用率比较

5　结束语

本文研究了可重构器件的区域模型，提出了一种基于块划分的资源管理模型，并设计了一种在线调度算法，采用非抢占式和抢占式策略来调度任务；同时，给出了仿真实验来评价具体的划分、放置和调度算法的性能。

参考文献：

[1]Rudy L.Creating a world of smart re-configurable devices[C]//Proceedings of the 12th International Conference on Field-Programmable Logic and Applications：Reconfigurable Computing Is Going Mainstream，Montpellier，France，2002：790-794.

[2]Plessl C，Enzler R，Walder H，et al.Reconfigurable hardware in wearable computing nodes[C]//Proceedings of the 6th International Symposium on Wearable Computers，Seattle，USA，2002：215-222.

[3]Brebner G.A virtual hardware operating system for the Xilinx XC6200[C]//Proceedings of the 6th International Workshop on Field-Programmable Logic and Applications，New Paradigms and Compilers，Darmstadt，Germany，1996：327-336.

[4]Wigley G，Kearney D.The development of an operating system for reconfigurable computing[C]//Proceedings of the 9th IEEE Annual Symposium on FPGAs for Custom Computing Machines，California，USA，2001：249-250.

[5]Simmler H，Levinson L，Manner R.Multitasking on FPGA coprocessors[C]//Proceedings of the 10th International Workshop on Field-Programmable Logic and Applications：The Roadmap to Reconfigurable Computing，Villach，Austria，2000：121-130.

[6]Bassiri M M，Shahhoseini H S.Mitigating reconfiguration overhead in on-line task scheduling for reconfigurable computing systems[C]//Proceedings of the 2nd IEEE International Conference on Computer Engineering and Technology，2010：397-402.

[7]张军能.动态可重构平台操作系统中的资源管理问题研究[D].合肥：中国科学技术大学，2014.

[8]张吉昕.基于FPGA部分动态可重构技术的划分和调度算法研究[D].武汉：武汉理工大学，2014.

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

[10]杨志华，伍卫国，王涛，等.一种基于双仲裁时间片策略的可重构硬件任务调度算法[J].计算机学报，2013，36（9）：1850-1867.

[11]段通，兰巨龙，胡宇翔，等.一种支持网络功能演进的可重构数据平面[J].电子学报，2016，44（7）：1721-1727.

[12]Bazargan K，Kastner R，Sarrafzadeh.Fast template placement for reconfigurable computing systems[J].IEEE Design and Test of Computers，2000，17（1）：68-83.

[13]Diessel O，ElGindy H，Middendorf M，et al.Dynamic scheduling of tasks on partially reconfigurable FPGAs[J].IEEEProceedingsonComputersandDigitalTechniques，2000，147（3）：181-188.

[14]Merino P，Jacome M，Lopez J C.A methodology for task based partitioning and scheduling of dynamically reconfigurable systems[C]//Proceedings of the IEEE Symopsium on FPGAs for Custom Computing Machines，Tallinn，Estonia，1998：324-325.

[15]Marescaux T，Andrei B，Dideriek V，et al.Interconnection networks enable fine-grain dynamic multi-tasking on FPGAs[C]//Proceedings of the 12th International Conference on Field-Programmable Logic and Applications：Reconfigurable Computing is Going Mainstream，Montpellier，France，2002：795-805.

[16]Brebner G，Diessel O.Chip-based reconfigurable task management[C]//Proceedings of the 11th International Workshop on Field-Programmable Logic and Applications，Belfast，Northern Ireland，UK，2001：182-191.