论文研究-可重构系统中实时任务容错调度算法.pdf

所需积分/C币:9 2019-07-22 18:28:04 525KB .PDF
8
收藏 收藏
举报

现在FPGA已被广泛的应用,但三模冗余(TMR)结构不能充分利用FPGA资源,基于主/从版本技术,提出一种实时任务容错调度算法。算法通过后向调度从版本,使得从版本在其截止期限内尽可能地推迟执行,从而同一任务的主从版本在执行时间上没有重叠或较少重叠,当任务主版本成功执行时释放任务从版本所占用的资源。仿真实验表明,与TMR相比,此方法能更有效地利用FPGA资源,提高硬件任务的接受率。
第5期 殷进勇,等:可重构系统中实时任务容错调度算法 1731 t的最迟有效时间为LA,(u)=maxs任务t以单元u为基点,初始值de,这是每个可重构单元的最迟有效时间。采用后向 s为启动时间的调度满足有效调度的条件a)e)d)}。 调度技术使得任务从版本的释放时间达到最迟。算法依次处 2算法设计 理已调度任务队列、待加载任务队列和运行任务队列,如果任 调度算法维护着三个队列,即EL、ML和L,分别保存当前务t的调度与现有的任务相冲突,则任务t的最迟允许开始时 的运行任务、已调度任务和待加载任务。二维数组FA[W 间提前,从而在算法结束时,A数组中保存了每个可重构单 Hn1用来保存EA矩阵或MA矩阵,EA矩阵和LA矩阵分别表示兀的最迟有效时间。 调度算法分为 schedule算法和 FTSchedule算法两部分。 每个可重构单元的最早有效时间和最迟有效时间。本节设计 hedule算法是对任务的主版本或从版本的调度; SCHedule 了四个算法,分别用于确定任务的放置位置和启动时间 是对实时任务的容错调度。算法分别描述如下 ComputeR和 computeR算法计算可重构单元的最早有效时 schedule(T) 问和最迟有效时问,确定任务主版本和从版本的放置位置 Schedule和 FTSchedule算法完成任务的调度和容错调度。 BSL= SLU TH 文献[7中的RCL最早有效时间的算法没有考虑任务的 SL=o; sort( rSI) 调度策略,按照任务的先来先服务(HCHS)方式计算可重构单 t=BSL. gethead(i 元的最早有效时间。本文算法可以采用不同的任务调度簧略, while(t!=null 如最早截止期限优先(EDF)等。算法描述如下 f(t是任务主版本) cunputeEA(t(wh, a,e, D, d)) computeX(t) for all(x,y)∈A1do I s, CI)+-findCandidate(1) ELA[x,y←a if(s>d-e) for all E(x, x2, y1, 2.s, f)EEL do for all(x,y)∈Ca∩A1d return false if ELALx, y] <f then ELALx, y for all L(xI, x,, y1, y2, s, f)eLL do 〈x,y)← findBase(CL); for all(x,y)∈C∩A1do addslit x if ELALx, y] <f then ELALx, y]e-f f(t是任务从版本) for alEx,y>∈Cs∩A;do computeLA(U if ELALx, y<f and ELA[X, y] +e>s I s, CL! +find Candidate(U) then ela[x,y]←f if (s<a) 算法首先为数组赋予初始值a,这是每个可重构单元的最 return talse i 早有效时间;随后依次处理EL、LL和SL任务队列;算法结東 时,每个可重构单元的最早有效时间被记录到ELA中。 x,y)← -findBase(CL) adsL(t, x, v, s); 为了提高任务的接收率,应使任务从版本在其截止期内尽 可能地推迟执行,现给出RCU的最迟有效时间算法。其中EL t=BSL. get Next() 和L按照任务结束时问的降序排列,SL按照任务启动时间的 // end while 降序排列。算法描述如下 return irule computeLA(I(w, h, a, e, D, d)) Schedule算法中,r为任务的主版本或从版本,返回fake 表示任务不可调度,返回tue表示调度成功。BSL为一个临时 for all (x, y)ca, do 队列,用于保存SL和任务τ。Sort()按照某种调度策略(如 ELA[x,y]←d-e for all S(x1, x2, y1, y2, s, f)ESL do EDF等)对任务排序;如果t为主版本则 findcandidate(t)找出 for all(x,y)∈Cst∩A1do ELA矩阵的最小数值,否则 find candidate(t)找出ELA矩阵的 if ELA [x, y] <f and ELALx, y]>s-e 最大数值作为任务t的预启动时间s,ELA中所有数值等于s的 then ela[x,y]←s-e 单元作为候选单元放在列表CL中; firebase()按照一定的放 for all L(x, x,, yI. V2, s, fELL do 置策略确定放置任务的基点;adSL()将任务t加人到已调度 for all(x,y)∈Cu∩A1do 任务集合SL中 f ELA [x, y] <f then ELA[X,yt-1 F'ISchedule(T(Tp, Tb)) for all F(x, x,, y1, y2, s, f)EEL. do for all(x,y)eCg1∩Ado if( schedule (Tp)==false f ELA x, y <f then ELA x, y 4-1 return false 算法首先进行初始化操作,为EA数组的每个单元赋予 if schedule(Tb)==false 1732 计算机应用研究 的可重构器件面积为原来的三倍。采用FTS方式,任务的主 e tur 版本所需的可重构器件而积为原来的两倍;从版本没有变化 return true 并且任务主版本顺利执行时,从版本被释放。因此,节省了可 重构器件资源,提高了硬件任务的接受率。 SChedule为容错调度算法。算法首先调度任务的主版 本,冉调度任务的从版本。如果返回me表示调度成功;否则4结束语 调度失败。 目前采用调度技术对可重构器件进行容错的研究还较少 3算法仿真 本文研究∫可重构器件中的实时任务在线容错调度问题,提出 了实时任务容错调度算法。硬件实时任务包括主版本和从版 可重构器件按照 Xilinx Virtex5X330的规模定义,具有本两种。算法首先调度任务的主版本,如果主版木运行失败, 240×108个RCU。生成的模拟任务按面积分为三类,分别记则调度任务的从版本;否则释放从版本所占的可重构器件资 为Cm、Cmn和C0。其中C.的宽度和高度在区间5,n]内均匀源。在湖度仟务从版本时,采用后向请度技术,即从任务的绝 分布以Cm为例,80%以上的任务面积在50-1250,这与现有对截止期限向前调度,使得任务从版本的释放时间达到最迟, 的可重构P核的面积基本符合。任务的运行时间在[5,50个 以便接收更多的任务主版。实验结果表明,与TMR方法相 时间单元内均匀分布;任务的相对截止期限在2003001均比,此方法有效地利用可重构器件资源,提高了硬件任务的接 匀分布 受率。 器件负载率对丁调度成功率影响很大,本文通过控制任务 本文模型还比较简单,今后的研究将针对实际的FPGA器 到达系统的频率来控制器件的负载率,任务到达系统的时间为件和可重构应用系统改进问题模型如硬件任务与软件任务联 参数为A的泊松流。在生成任务时,首先生成一组任务的宽合调度、考虑任务配置时间以及考虑任务间的通信开销等。 度、高度、运行时间和松地时间,最后以参数为A确定任务到 参考文献 达系统的时间。 [1 CHAPMAN G H, DUFOET B. Using laser defect avoidance to build 任务的主版本采用双模冗余法进行故障检测,其结构如图 large-area FPGAs[ J]. IEEE Design Test of Computers, 1998 3所示,从版本没有冗余模块。假设可重构器件的故障到达间 15(4):75-81 隔有一个最小值,使得任务主版本因故障失效时,仟务从版本[2] DOUMAR A, KANEKO S,moH. Defect and fault tolerance fpca 能够顺利执行。 by shifting the configuration data[ C]//Proc of the 14 th International 入/契 Symposium on Defect and Fault-Tolerance in VLSI Systems. Washing- 器)辙出 ton DC: IEEE Computer Society, 1999: 377-38 模块 [3 HANCHEK F, DUTT S. Methodologies for tolerating cell and inter- 图3双模冗余结构图 connect faults in FPGAs[ J. IEEE Trans on Computers, 1998, 47 每个任务组包含1000个任务,对于每个不同的面积类和 不同的鱼载率生成100组任务,将各组任务模拟数据的平均值4| ABRAMOVICI M, STROUD C, WIJESURIYA S,eal. Using rovin 作为评估结果,并与三模冗余(TMR)进行比较,结果如图4所 STARs for on-line testing and diagnosis of FPGAs in fault-tolerant ap- 示。其屮FTS( fault tolerant schedule)为本文算法。 plications[C]//Proc of IEEE International Test Conference. 1999 100 973-982 做6 [5 EMMERT J, STROUND C, SKACCS B, et al. Dynamic fault toler ance in FPGAs via partial reconfiguration[ C]//Proc of IEEE Sympo- sium on Fielrl-Programmable Custom Complting Machines. Washing- 1.21.41.61.82 1.21.41.61.82 1.21.41.61.8 ton DC: IEEE Computer Society, 2000: 165-174 泊松流强度() 泊松流强度() 泊松流强度(廴) □FTS■TMR □FTS口TMR TS口TMR [6]周,王石记,邱卫东,等, SHUM2UCOS:基于统一多任务模型 ( bc (c) Cse 可重构系统的实时操作系统[J.计算机学报,2006,29(2) 图4任务接受率对比 208-218 从图4可以看出,与TMR相比,FIS明显地提高了任务的[7]周学功,梁,黄勋章,等,可重构系统中的实时任务在线调度与 接受率。主要因为,如果采用TMR方式,硬件头时任务它所需 放置算法冂].计算机学报,2007,30(11):1901-199 (上接第1728页)方法。通过实例进行了仿真,对不同的交又 工程,2005,23(2):22-24 算子效果进行了比较,结果证明本文方法适合于距离对称和非[4]唐立新。热轧调度并行处理筑略的多旅行商模型J东北大学 对称的多旅行商问题。 学报,1999,20(2):148-150. 参考文献 [5]黄可信,汪定伟,热轧计划中的多旅行商问趣及其讣算方法 I|李军民,林淑飞,高让礼.月混合遗传算法求解多日标TsP|J J|.计算机应用研冤,207,24(7):43-45 西安科技大学学报,2006,26(4):515-518 [6]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中 [2]陶然,吕红霞,陈广秀,基于MTP的机车周转图编制模壟与算 国物资出版社,2001:63-73 法[冂].西南交通大学学报,2016,41(5):653-657 [7]王小平,曹立明遗传算法——理谂、应用与软件实现M].西安 [3]卢厚清,王挥东,黄杰,等.任务均分的多旅行商问题[J.系统 西安交通大学出版社,2002:28-38

...展开详情
试读 4P 论文研究-可重构系统中实时任务容错调度算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-可重构系统中实时任务容错调度算法.pdf 9积分/C币 立即下载
1/4
论文研究-可重构系统中实时任务容错调度算法.pdf第1页

试读结束, 可继续读1页

9积分/C币 立即下载 >