基于3D碎裂度布局策略的可重構(gòu)硬件任務(wù)調(diào)度算法

徐金甫; 劉露; 李偉; 南龍梅

doi:10.11999/JEIT171205

基于3D碎裂度布局策略的可重構(gòu)硬件任務(wù)調(diào)度算法

doi: 10.11999/JEIT171205 cstr: 32379.14.JEIT171205

解放軍信息工程大學(xué) ??鄭州 ??450001

基金項目: 國家自然科學(xué)基金(61404175)

詳細信息

作者簡介:
徐金甫：男，1965年生，教授，碩士生導(dǎo)師，研究方向為專用集成電路設(shè)計

劉露：男，1992年生，碩士，研究方向為專用集成電路設(shè)計

李偉：男，1983年生，副教授，碩士生導(dǎo)師，研究方向為安全專用芯片設(shè)計

南龍梅：女，1981年生，講師，研究方向為安全專用芯片設(shè)計

通訊作者:
李偉　 liulu13213238773@163.com

中圖分類號: TP316.4
計量
- 文章訪問數(shù): 1341
- HTML全文瀏覽量: 489
- PDF下載量: 30
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2017-12-21
- 修回日期: 2018-05-18
- 網(wǎng)絡(luò)出版日期: 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)

摘要

摘要: 現(xiàn)有硬件任務(wù)調(diào)度算法任務(wù)描述不完善且忽視時間維上緊湊性。該文考慮任務(wù)下載時間、完善任務(wù)屬性，以器件2維資源與時間建立3維資源模型，將任務(wù)布局問題抽象成特殊的3維空間放置問題，在此模型上分析出現(xiàn)有算法不能克服任務(wù)不可預(yù)知性和資源占用多變性，導(dǎo)致調(diào)度成功率和資源利用率低。針對此問題，該文提出了一種3維可重構(gòu)任務(wù)調(diào)度算法3D_RTSA。設(shè)計并實現(xiàn)了基于任務(wù)緊迫度的調(diào)度策略和基于3D碎裂度的布局策略。與其他4種算法實驗對比結(jié)果表明，在重負載、小任務(wù)C30情況下，3D_RTSA調(diào)度成功率比GC, Look-aheadest, SPSA, DTI算法分別高3%, 21%, 28%, 35%左右；在輕負載、大任務(wù)C50情況下，資源利用率比Look-aheadest, SPSA算法分別高5%, 18%左右，且該文算法時間復(fù)雜度并未增加。
- 3維資源模型 /
- 任務(wù)緊迫度 /
- 3D碎裂度 /
- 調(diào)度成功率 /
- 資源利用率
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 硬件任務(wù)調(diào)度系統(tǒng)結(jié)構(gòu)模型

下載: 全尺寸圖片幻燈片

圖 2 任務(wù)塊在3維空間布局示意圖

下載: 全尺寸圖片幻燈片

圖 3 3種情況調(diào)度結(jié)果對比圖

下載: 全尺寸圖片幻燈片

圖 4 文獻[14]的優(yōu)先級調(diào)度策略實例

下載: 全尺寸圖片幻燈片

圖 5 3D_RTSA算法流程

下載: 全尺寸圖片幻燈片

圖 6 前后硬件任務(wù)相對放置位置情況

下載: 全尺寸圖片幻燈片

圖 7 雙任務(wù)布局時3D碎裂度計算模型

下載: 全尺寸圖片幻燈片

圖 8 深度優(yōu)化布局必要性分析

下載: 全尺寸圖片幻燈片

圖 9 5種調(diào)度算法調(diào)度成功率對比

下載: 全尺寸圖片幻燈片

圖 10 3種調(diào)度算法資源利用率對比

下載: 全尺寸圖片幻燈片

表 1 5種算法時間復(fù)雜度對比

算法	調(diào)度算法復(fù)雜度	布局算法復(fù)雜度
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)

下載: 導(dǎo)出CSV

參考文獻(19)

張晶, 孫少杰, 范洪博, 等. 高實時性異構(gòu)多核處理器任務(wù)調(diào)度算法[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.

徐曉東. 動態(tài)可重構(gòu)系統(tǒng)中任務(wù)調(diào)度與布局算法研究[D]. [碩士論文], 中國科學(xué)技術(shù)大學(xué), 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.

周學(xué)功, 梁樑, 黃勛章, 等. 可重構(gòu)系統(tǒng)中的實時任務(wù)在線調(diào)度與放置算法[J]. 計算機學(xué)報, 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.

齊驥, 李曦, 胡楠, 等. 基于硬件任務(wù)頂點的可重構(gòu)系統(tǒng)資源管理算法[J]. 電子學(xué)報, 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.

許新達. 基于局部可重構(gòu)計算的在線硬件任務(wù)調(diào)度算法研究[D]. [碩士論文], 湖南大學(xué), 2010.

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

劉彥, 李仁發(fā), 許新達, 等. 一種異構(gòu)可重構(gòu)片上系統(tǒng)的實時任務(wù)調(diào)度算法[J]. 計算機研究與發(fā)展, 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的可重構(gòu)任務(wù)調(diào)度算法研究[D]. [碩士論文], 解放軍信息工程大學(xué), 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.

楊錦江, 曹鵬, 楊軍. 面向分組密碼算法的高面積效率可重構(gòu)架構(gòu)[J]. 東南大學(xué)學(xué)報(自然科學(xué)版), 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.

彭日光. 動態(tài)可重構(gòu)片上系統(tǒng)的任務(wù)在線放置和調(diào)度算法研究[D]. [碩士論文], 湖南大學(xué), 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.

王金敏. 三維矩形布局吸引子性質(zhì)的研究[J]. 圖學(xué)學(xué)報, 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.

相關(guān)文章

施引文獻

資源附件(0)

訪問統(tǒng)計