面向多任务调度的可重构算法设计*

黄庆华

（柳州职业技术学院电子信息工程系，广西　柳州　545006）

面向多任务调度的可重构算法设计*

黄庆华

（柳州职业技术学院电子信息工程系，广西柳州545006）

针对在单个逻辑芯片上实现多任务的应用场合，设计了面向多任务调度的可重构算法，以此提高逻辑芯片的资源利用率和任务的响应效率.详细描述了面向多任务调度的重构设计原理，并针对逻辑芯片中多任务的调度种类分别设计了逻辑芯片的重构调度算法，最后选取了多个典型的任务进行对比测试.测试结果表明，使用重构算法之后的逻辑芯片在资源占有率和任务响应延迟上均优于传统的逻辑芯片设计方法.

重构；任务调度；逻辑芯片；利用率；加载

0　引言

随着逻辑芯片的硬件设计技术和生产工艺的提高，在单个逻辑芯片上所能够提供的计算资源和存储资源越来越丰富，从而促使人们在单个逻辑芯片上开发和设计多任务的应用功能.而且在单个逻辑芯片上开发多任务的应用功能，也能够使得单个逻辑芯片满足多种不同应用需求的场合[1－3].然而在单个逻辑芯片上设计多任务的应用时，往往面临逻辑芯片资源利用率不高，任务响应延迟较长等问题.为此国内很多学者对这一问题纷纷开展了相关研究.比如：刘沙，周学功[4]等人对可重构系统在线任务预约重调度问题进行了研究，并提出了任务调度算法，提高了在线任务预约调度效率.周学功，梁樑[5]等人则研究了可重构系统中的实时任务在线调度问题，并设计相应的放置算法.李涛，杨愚鲁[6]等人针对可重构系统中的资源管理及硬件任务布局问题开展了研究，并提出实现算法.

为了更好地提高逻辑芯片在实现多任务应用时的综合效率，笔者设计了一种面向多任务调度的可重构算法，该算法通过对多任务的调度模式进行重新设计和优化，使得在逻辑芯片上能够同时实现多个应用功能，从而实现提高逻辑芯片综合利用效率的目的.

1　面向多任务调度的重构原理

面向多任务调度的逻辑芯片重构设计，目的是为了尽可能提高逻辑芯片的利用率.由于这类逻辑芯片在使用的时候，往往会将多个任务调度到该逻辑芯片上进行实现，而每个任务所占用的资源，以及持续的时间各不相同.传统的设计模式中往往是将逻辑芯片按照不同任务的调度顺序，依次将不同任务在逻辑芯片上进行实现[7－8]，实现过程的示意图如图1所示.图1给出了5个待执行的任务，这5个任务所占用的逻辑芯片资源，以及持续的时间都不相同，在传统的设计模式中这5个任务都将分别进行设计并加载至调度逻辑芯片中，最后完成特定的功能.

传统的这种任务调度模式不能很好地提高逻辑芯片的运行效率，尤其是对逻辑芯片在执行过程中，往往会留下较多的空闲资源区域，从而降低了逻辑芯片的使用效率[9－10].为了提高逻辑芯片的工作效率，笔者设计了一种面向多任务调度的逻辑芯片重构设计方案.其设计原理是将待调度执行的任务进行调整和优化次序，尽可能地使得逻辑芯片处于较高的运行负荷.在进行重构设计时，可以根据不同任务的执行时间和所需要占用的逻辑资源，动态的调整任务的次序和时间.通过重构设计之后，既能够提高逻辑芯片的资源利用率，同时由于有些任务的调度次序得到了优化，因此对于同样的任务其得到的执行的响应时间还会更短.调度模式如图2所示.

图1　传统的任务调度模式Fig.1　The traditional task adjusts one degree mode

图2　重构后的任务调度模式Fig.2　The heavy task after reaching adjusts one degree mode

2　重构算法设计

重构算法的设计目的是提高逻辑芯片上任务加载效率.由于任务加载的时刻是不确定的，有些任务要求在固定时刻必须加载，有些任务的加载时刻可以动态调整，因此，重构算法的设计分为固定时刻的任务调度模式和非固定时刻的任务调度模式[12－13].其中非固定时刻的任务调度模式又可分为非周期性的任务最优调度模式和周期性的任务最优调度模式.

1）固定任务调度模式.

假设有N个待计算的任务序列，首先计算任务序列的计算资源和存储资源的总占用量，算式如下：

将计算得到的任务序列占用计算资源和存储资源与逻辑芯片可提供的资源量对比，对比之后按如下算式进行任务调度调整.

若在给定的时间段[t1，t2]，Fc≤Mc（Mc为逻辑芯片的最大可提供计算资源），则在时间段[t1，t2]中，N个任务可同时加载至逻辑芯片中进行重构.

若在给定的时间段[t1，t2]，Fc＞Mc，则对N个任务中的计算资源占用量进行排序，得到序列ΓA，取序列中ΓA的一个子序列ΓB.

两个序列元素之差ΓA－ΓB为新一批待调度的任务，记该任务集以固定任务调度模式重新进行调度，过程如上，直至ΓA－ΓB中所有任务均调度完成.

2）非周期性的任务最优调度模式.

为了得到最优调度效果，其实现原理是通过调整各个任务调度时刻，让逻辑芯片的平均任务负荷处于最高的状态.

假设有N个待计算的任务序列，每个任务Wi的预定加载时刻为YTi.因此N个待计算的任务序列的预定加载时刻分别为YT1，…，YTi，…，YTN，所有任务中最长任务加载时间为Tmax.

若将每个任务的加载时刻进行调整，调整幅度为△ti.则N个待计算的任务序列的加载时刻分别为YT1＋△t1，…，YTi＋△ti，…，YTN＋△tN.

定义在给定的时间T内，任意时刻逻辑芯片上占用的计算资源为Hct.

在给定的时间T内，当前任务序列在逻辑芯片上的计算资源利用率为Gc.

若给定的T＞Tmax且（T－Tmax）＝ξ，ξ表示一个无穷小的数，寻找时间序列Γ＝｛△t1，…，△ti，…，△tN｝，使得下式成立

式中α为一个固定的系数，该系数的设定是确保逻辑芯片不影响其计算能力时的计算资源最大占用率，Gck表示任意一个时间序列Γk下计算得到的逻辑芯片计算资源利用率.

通过极大似然估计算法，能够计算得到近似解Γθ，该近似解中表示的时间序列Γθ＝｛△t1，…，△ti，…，△tN｝即为最优的任务调度序列.

3）周期性的任务最优调度模式.

对于N个待计算的任务序列，假设每个任务的运行周期分别为｛T1，…，Ti，…，TN｝.

定义函数E（A）如下：

E（A）＝LCM（T1，…，Ti，…，TN）

LCM（T）表示对集合T中的所有元素计算最小公倍数.

令T0＝E（A）作为当前逻辑芯片的资源统计周期，选择一个T＞T0且（T－T0）＝ξ，

由于每个任务为周期性任务，因此假设每个任务的初始加载时刻都为0.在统计的时间周期T0内，每个任务Wi的插入的时间片序列为｛△ti1，…，△tij，…，△timi｝，式中（1≤j≤mi），每个任务插入的时间片个数分别为｛m1，m2，…，mN｝.

将每个任务的加载时刻按中间插入的时间片进行调整，则每个待计算的任务序列的加载时刻分别为△ti1，…，i*Ti＋△ti1＋△ti2＋…＋△tij，…，mi*Ti＋△ti1＋△ti2＋…＋△timi.同样上文定义的Gc和Hct.

若给定的T＞T0且（T－T0）＝ξ，寻找时间序列Γ＝｛△ti1，…，△tij，…，△timi｝，使得下式成立

α和Gck的定义和上文一样，同理采用极大似然估计算法，能够计算得到近似解Γθ，该近似解中表示的时间序列Γθ＝｛△ti1，…，△tij，…，△timi｝即为最优的任务调度序列.

3　实验测试

针对笔者所设计的逻辑芯片重构算法，选取了10个典型的待调度执行任务，在逻辑芯片中进行实现，并分别采用传统的实现模式和重构优化之后的实现模式进行对比测试，测试结果如图3和图4所示.

图3给出的测试结果是针对逻辑芯片重构前后资源占用比率的对比测试结果.从测试结果可以看出在重构之前，逻辑芯片是按照需要执行的任务顺序，依次加载相应的任务，逻辑芯片的资源占用率忽高忽低，在整个逻辑芯片运行周期中，整体的逻辑芯片平均资源利用率并不高.而进行重构设计之后，能够将逻辑芯片上所需要运行的程序，调度次序进行优化，从而保证了逻辑芯片的平均资源占用率处于一个较高的水平.而且在整个运行过程中，逻辑芯片的资源占用率波动也很小，确保了逻辑芯片的工作效率一直处于较高的状态.

图4给出的是在逻辑芯片重构前后对7个典型的任务其响应时间的测试.从测试结果可以看出在重构之前，逻辑芯片由于都是单独的一次加载任务，因此在每个任务加载之前都会存在一个准备时间.而且由于任务的调度次序也没有优化，从而使得有些任务在执行的时候需要更多的等待时间.测试结果表明，在重构之前任务2的等待时间最长，达5.6s，而在重构之后，最长的等待仍然为任务2，其等待时间只有3.9s.在整个7个任务的测试过程中，通过重构之后所使用的逻辑芯片，其总体的任务响应等待时间也明显低于重构之前的任务响应时间.

图3　逻辑芯片重构前后资源占用率对比Fig.3　The logic chip is heavy to reach front and back resource occupation to lead contrast

图4　逻辑芯片重构前后任务的响应延时Fig.4　When logic chip was heavy to reach the response of front and back task to postpone

4　结语

随着逻辑芯片占的资源越来越丰富，在逻辑芯片上所实现的任务数量也变得越来越多，面向多任务的逻辑芯片可重构设计，能够在单个芯片上更好地提高芯片的利用效率.同时对多个任务的执行响应延迟也有明显地减少，因此设计面向多任务调度的可重构算法，能够提高逻辑芯片的综合应用效率.

[1]齐骥，李曦，于海晨，等.一种面向动态可重构计算的调度算法[J].计算机研究与发展，2007，44（8）：1439－1447.

[2]马宏星，周学海，高妍妍，等.一种集成可重构硬件的多核片上系统的软硬件任务划分与调度算法[J].中国科学院研究生院学报，2010，27（5）：664－669.

[3]焦铬，李仁发，彭日光，等.一种动态可重构系统的实时任务调度算法[J].计算机工程与科学，2010，32（12）：145－148.

[4]刘沙，周学功，王颖，等.可重构系统在线任务预约重调度算法[J].计算机工程，2011，37（8）：271－274.

[5]周学功，梁樑，黄勋章，等.可重构系统中的实时任务在线调度与放置算法[J].计算机学报，2007，30（11）：1901－1909.

[6]李涛，杨愚鲁.可重构资源管理及硬件任务布局的算法研究[J].计算机研究与发展，2008，45（2）：375－382.

[7]Nup Kumar Raghavan，Peter Sutton.JPG－A Partial Bitstream Generation Tool to Support Partial Reconfiguration in Virtex FPGAs[C].Proceedings of the 16th International Parallel and Distributed Processing Symposium，2002：155－160.

[8]Steffen Toscher，Thomas Reinemann，Roland Kasper.An Adaptive FPGA－Based Mechatronic Control System Supporting Partial Reconfiguration of Controller Functionalities[C].Adaptive Hardware and Systems，2006（AHS 2006），First NASA/ESA Conference on，2006：225－228.

[9]周盛雨.基于FPGA的动态部分重构系统实现[D].中国科学院研究生院（空间科学与应用研究中心），2007：1－127.

[10]谷銮，徐贵力，王友仁.FPGA动态可重构理论及其研究进展[J].计算机测量与控制，2007，15（11）：1415－1418.

[11]王颖，陈伟男，周学功，等.可重构计算中的负载可分应用性能分析与预测[J].小型微型计算机系统，2010，31（8）：1668－1674.

[12]Tanya Vladimirova，XiaoFeng Wu.On－board Partial Runtime Reconfiguration for Pico－Satellite Constellations[C].A-daptive Hardware and Systems，2006（AHS 2006），First NASA/ ESA Conference on，2006：262－269.

[13]许骏，晏渭川，彭澄廉.基于模块的动态可重构系统设计[J].计算机工程与设计，2008，29（6）：1367－1369.

[责任编辑 苏 琴]

[责任校对 黄招扬]

Design of Reconfigurable Algorithm for Multi Task Scheduling

HUANG Qing-hua
（Department of Electronic Information Engineering，Liuzhou Vocational ＆Technical College，Liuzhou 545006，China）

Aimed at the application of multi task on a single logic chips，reconfiguration algorithm for multi task scheduling is designed，in order to improve the response efficiency logic chip utilization ratio of resources and tasks.A detailed description of the design principle for the reconstruction of multi task scheduling，and according to the logic chip multi task scheduling are designed reconfigurable scheduling algorithm logic chip，finally selected a number of typical task compared to the test.The test results show that，the logic chip after using the reconstruction algorithm in share and tasks in resource response delay logic chip design method is superior to traditional.

Reconstruction；task scheduling；logic chip；utilization；loading

TP302

A

1673－8462（2015）01－0073－04

2014-09-10.

广西自然科学基金项目（2013GXNSFAA019006）.

黄庆华（1969-），男，广西桂平人，柳州职业技术学院电子信息工程系副教授，研究方向：电气自动化技术.