基于3D碎裂度布局策略的可重构硬件任务调度算法

徐金甫; 刘露; 李伟; 南龙梅

doi:10.11999/JEIT171205

基于3D碎裂度布局策略的可重构硬件任务调度算法

doi: 10.11999/JEIT171205

解放军信息工程大学郑州 450001

基金项目: 国家自然科学基金(61404175)

详细信息

作者简介:
徐金甫：男，1965年生，教授，硕士生导师，研究方向为专用集成电路设计

刘露：男，1992年生，硕士，研究方向为专用集成电路设计

李伟：男，1983年生，副教授，硕士生导师，研究方向为安全专用芯片设计

南龙梅：女，1981年生，讲师，研究方向为安全专用芯片设计

通讯作者:
李伟　 liulu13213238773@163.com

中图分类号: TP316.4
计量
- 文章访问数: 1237
- HTML全文浏览量: 437
- PDF下载量: 29
- 被引次数: 0
出版历程
- 收稿日期: 2017-12-21
- 修回日期: 2018-05-18
- 网络出版日期: 2018-06-06
- 刊出日期: 2018-08-01

Reconfigurable Hardware Task Scheduling Algorithm Based on 3D Fragmentation Layout Strategy

The PLA Information Engineering University, Zhengzhou 450001, China

Funds: The National Natural Science Foundation of China (61404175)

摘要

摘要: 现有硬件任务调度算法任务描述不完善且忽视时间维上紧凑性。该文考虑任务下载时间、完善任务属性，以器件2维资源与时间建立3维资源模型，将任务布局问题抽象成特殊的3维空间放置问题，在此模型上分析出现有算法不能克服任务不可预知性和资源占用多变性，导致调度成功率和资源利用率低。针对此问题，该文提出了一种3维可重构任务调度算法3D_RTSA。设计并实现了基于任务紧迫度的调度策略和基于3D碎裂度的布局策略。与其他4种算法实验对比结果表明，在重负载、小任务C30情况下，3D_RTSA调度成功率比GC, Look-aheadest, SPSA, DTI算法分别高3%, 21%, 28%, 35%左右；在轻负载、大任务C50情况下，资源利用率比Look-aheadest, SPSA算法分别高5%, 18%左右，且该文算法时间复杂度并未增加。
- 3维资源模型 /
- 任务紧迫度 /
- 3D碎裂度 /
- 调度成功率 /
- 资源利用率
Abstract: The existing hardware task scheduling algorithms describe task imperfectly and ignore the compactness of time dimension. The task downloading time is considered for improving the task attribute, and the 3D-resource model with the two dimensional resource of device and time is established, in order to abstract the issue of task layout into a special three-dimensional space placement issue. With this model, it is concluded that the existing algorithms can not overcome the unpredictability of the task and the diversity of resource occupancy, leading low scheduling success rate and resource utilization rate. To solve the problem, a three dimensional reconfigurable task scheduling algorithm called 3D_RTSA is proposed. A scheduling strategy based on task urgency and a layout strategy based on 3D fragmentation are designed and implemented. Compared with the other 4 algorithms, the results show that the scheduling success rate of 3D_RTSA is 3%, 21%, 28%, 35% higher than that of GC, Look-aheadest, SPSA and DTI algorithms under the condition of heavy load and small task C30, and the utilization ratio of resources is 5% and 18% higher than that of Look-aheadest and SPSA algorithm under the condition of light load and large task C50. Besides, the time complexity of the algorithm is not increased.
- 3D-resource model /
- Task urgency /
- 3D fragmentation /
- Scheduling success rate /
- Resource utilization

HTML全文

图 1 硬件任务调度系统结构模型

下载: 全尺寸图片幻灯片

图 2 任务块在3维空间布局示意图

下载: 全尺寸图片幻灯片

图 3 3种情况调度结果对比图

下载: 全尺寸图片幻灯片

图 4 文献[14]的优先级调度策略实例

下载: 全尺寸图片幻灯片

图 5 3D_RTSA算法流程

下载: 全尺寸图片幻灯片

图 6 前后硬件任务相对放置位置情况

下载: 全尺寸图片幻灯片

图 7 双任务布局时3D碎裂度计算模型

下载: 全尺寸图片幻灯片

图 8 深度优化布局必要性分析

下载: 全尺寸图片幻灯片

图 9 5种调度算法调度成功率对比

下载: 全尺寸图片幻灯片

图 10 3种调度算法资源利用率对比

下载: 全尺寸图片幻灯片

表 1 5种算法时间复杂度对比

算法	调度算法复杂度	布局算法复杂度
Look-aheadest	O(E2R+G)	O(E2R)
DTI	O(N)	O(E+R)
GC	O(N(E+R))	O(E+R)
SPSA	O(R2)	O(GR)
本文	O(N)	O(E+R)

下载: 导出CSV

参考文献(19)

张晶, 孙少杰, 范洪博, 等. 高实时性异构多核处理器任务调度算法[J]. 计算机工程, 2017, 43(5): 55－59. DOI: 10.3969/j.issn.1000-3428.2017.05.009.

ZHANG Jing, SUN Shaojie, FAN Hongbo, et al. Task scheduling algorithm in heterogeneous multi-core processor with high real-time performance[J]. Computer Engineering, 2017, 43(5): 55－59. DOI: 10.3969/j.issn.1000-3428.2017.05.009.

AL-WATTAR A, AREIBI S, and GREWAL G. An efficient evolutionary task scheduling/binding framework for reconfigurable systems[J]. International Journal of Reconfigurable Computing, 2016, (2): 1－24. DOI: 10.1155/2016/9012909.

MOLLAJAFARI M and SHAHHOSEINI H S. An Efficient ACO-based Algorithm for Scheduling Tasks onto Dynamically Reconfigurable Hardware Using TSP-likened Construction Graph[M]. New York: Kluwer Academic Publishers, 2016: 695–712.

徐晓东. 动态可重构系统中任务调度与布局算法研究[D]. [硕士论文], 中国科学技术大学, 2017: 25–59.

XU Xiaodong. Task scheduling and floorplanning algorithm in dynamically reconfigurable systems[D]. [Master dissertation], University of Science and Technology of China, 2017: 25–59.

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

ZHOU Xuegong, LIANG Liang, HUANG Xunzhang, et al. On-line scheduling and placement of real-time tasks for reconfigurable computing system[J]. Chinese Journal of Computers, 2007, 30(11): 1901－1909. DOI: 10.3321/j.issn:0254-4164.2007.11.002.

STEIGER C, WALDER H, and PLATZNER M. Heuristics for Online Scheduling Real-time Tasks to Partially Reconfigurable Devices[M]. Springer Berlin Heidelberg, 2003: 575–584.

STEIGER C, WALDER H, and PLATZNER M. Operating systems for reconfigurable embedded platforms: Online scheduling of real-time tasks[J]. IEEE Transactions on Computers, 2004, 53(11): 1393－1407. DOI: 10.1109/TC.2004.99.

SEPTIEN J, MOZOS D, MECHA H, et al. Perimeter quadrature-based metric for estimating FPGA fragmentation in 2D HW multitasking[C]. IEEE International Symposium on Parallel and Distributed Processing, Miami, USA, 2008: 1–8.

齐骥, 李曦, 胡楠, 等. 基于硬件任务顶点的可重构系统资源管理算法[J]. 电子学报, 2006, 34(11): 2094－2098. DOI: 10.3321/j.issn:0372-2112.2006.11.034.

QI Ji, LI Xi, HU Nan, et al. Algorithms of resource management for reconfigurable systems based on hardware task vertexes[J]. Acta Electronica Sinica, 2006, 34(11): 2094－2098. DOI: 10.3321/j.issn:0372-2112.2006.11.034.

LEUNG Y T, TAM T W, WONG C S, et al. Packing squares into a square[J]. Journal of Parallel & Distributed Computing, 1990, 10(3): 271－275. DOI: 10.1016/0743-7315(90)90019-L.

HANDA M and VEMURI R. An efficient algorithm for finding empty space for online FPGA placement[C]. Design Automation Conference. San Diego, USA, 2004: 960–965.

许新达. 基于局部可重构计算的在线硬件任务调度算法研究[D]. [硕士论文], 湖南大学, 2010.

XU Xinda. The research on online hardware task schedule algorithm based-on partial reconfigurable computing[D]. [Master dissertation], Hunan University, 2010.

刘彦, 李仁发, 许新达, 等. 一种异构可重构片上系统的实时任务调度算法[J]. 计算机研究与发展, 2010, 47(6): 1116－1124.

LIU Yan, LI Renfa, XU Xinda, et al. Research on a real-time task scheduling algorithm for hybrid reconfigurable system-on-chip[J]. Journal of Computer Research and Development, 2010, 47(6): 1116－1124.

曹晓磊. 基于LRSS的可重构任务调度算法研究[D]. [硕士论文], 解放军信息工程大学, 2010: 27–37.

CAO Xiaolei. Research on reconfigurable task scheduling algorithms based on LRSS[D]. [Master dissertation], PLA Information Engineering University, 2010: 27–37.

SHENG Y, LIU Y, LI R, et al. A communication-aware scheduling algorithm for hardware task scheduling model on FPGA-based reconfigurable systems[J]. Journal of Computers, 2014, 9(11). DOI: 10.4304/jcp.9.11.2552-2558.

杨锦江, 曹鹏, 杨军. 面向分组密码算法的高面积效率可重构架构[J]. 东南大学学报(自然科学版), 2016, 46(5): 939－944. DOI: 10.3969/j.issn.1001-0505.2016.05.007.

YANG Jinjiang, CAO Peng, and YANG Jun. Reconfigurable architecture with high area efficiency for block cipher algorithms[J]. Journal of Southeast University (Natural Science Edition) , 2016, 46(5): 939－944. DOI: 10.3969/j.issn.1001-0505.2016.05.007.

彭日光. 动态可重构片上系统的任务在线放置和调度算法研究[D]. [硕士论文], 湖南大学, 2009: 15–23.

PENG Riguang. Research on algorithms of onling placement and scheduling of real-time tasks for reconfigurable system-on-chip[D]. [Master’s dissertation], Hunan University, 2009: 15–23.

BANERJEE S, BOZORGZADEH E, and DUTT N. Physically-aware HW-SW partitioning for reconfigurable architectures with partial dynamic reconfiguration[C]. Design Automation Conference. Anaheim, USA, 2005: 335–340.

王金敏. 三维矩形布局吸引子性质的研究[J]. 图学学报, 2016, 37(3): 355－358. DOI: 10.11996/JG.j.2095-302X.2016030355.

WANG Jinmin. Research on the property of attractive factor in three dimensional rectangular packing problems[J]. Journal of Graphics, 2016, 37(3): 355－358. DOI: 10.11996/JG.j.2095-302X.2016030355.

施引文献

资源附件(0)

访问统计