Task Scheduling Technology for Coarse-grained Dynamic Reconfigurable System Based on Configuration Prefetching and Reuse

Zibin DAI; Tongzhou QU

doi:10.11999/JEIT180831

Volume 41 Issue 6

Jun. 2019

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2019 > 41(6): 1458-1465

Zibin DAI, Tongzhou QU. Task Scheduling Technology for Coarse-grained Dynamic Reconfigurable System Based on Configuration Prefetching and Reuse[J]. Journal of Electronics & Information Technology, 2019, 41(6): 1458-1465. doi: 10.11999/JEIT180831

Citation:

Zibin DAI, Tongzhou QU. Task Scheduling Technology for Coarse-grained Dynamic Reconfigurable System Based on Configuration Prefetching and Reuse[J]. Journal of Electronics & Information Technology, 2019, 41(6): 1458-1465. doi: 10.11999/JEIT180831

Citation:

PDF( 2689 KB)

Task Scheduling Technology for Coarse-grained Dynamic Reconfigurable System Based on Configuration Prefetching and Reuse

doi: 10.11999/JEIT180831

Zibin DAI,
Tongzhou QU^,

The PLA Information Engineering University, Zhengzhou 450001, China

Received Date: 2018-08-24
Rev Recd Date: 2019-02-02

Available Online: 2019-02-26

Publish Date: 2019-06-01

Abstract

Abstract

Long configuration time is a significant factor which restricts the performance improvement of the reconfigurable system, and a reasonable task scheduling technology can effectively reduce the system configuration time. A three-dimensional task scheduling model for Coarse-Grain Dynamic Reconfigurable System (CGDRS) and flow applications with data dependencies is proposed. Firstly, based on this model, a Configuration Prefetching Schedule Algorithm (CPSA) applying pre-configured strategy is designed. Then, the interval and continuous configuration reuse strategy are proposed according to the configuration reusability between tasks, and the CPSA algorithm is improved accordingly. The experimental results show this algorithm can avoid scheduling deadlock, reduce the execution time of flow applications and improve scheduling success rate. The optimization ratio of total execution time of flow applications achieves 6.13%～19.53% averagely compared with other scheduling algorithms.
- Coarse-Grain Dynamic Reconfigurable System (CGDRS),
- Flow applications,
- Pre-configured,
- Configuration reuse

FullText(HTML)

References(16)

References

WANG Yansheng, LIU Leibo, YIN Shouyi, et al. On-chip memory hierarchy in one coarse-grained reconfigurable architecture to compress memory space and to reduce reconfiguration time and data-reference time[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2014, 22(5): 983–994. doi: 10.1109/TVLSI.2013.2263155

梁樑, 周学功, 王颖, 等. 采用预配置策略的可重构混合任务调度算法[J]. 计算机辅助设计与图形学学报, 2007, 19(5): 635–641. doi: 10.3321/j.issn:1003-9775.2007.05.016

LIANG Liang, ZHOU Xuegong, WANG Ying, et al. Pre-configuration based hybrid tasks scheduling in reconfigurable systems[J]. Journal of Computer-Aided Design & Computer Graphics, 2007, 19(5): 635–641. doi: 10.3321/j.issn:1003-9775.2007.05.016

王延升. 粗粒度动态可重构处理器中的高能效关键配置技术研究[D]. [博士论文], 清华大学, 2014: 1–13.

WANG Yansheng. High energy-efficient key techniques in configurations for coarse-grained dynamically reconfigurable processor[D]. [Ph.D. dissertation], Tsinghua University, 2014: 1–13.

LI Zhiyuan and HAUCK S. Configuration prefetching techniques for partial reconfigurable coprocessor with relocation and defragmentation[C]. Proceedings of 2002 ACM/SIGDA Tenth International Symposium on Field-Programmable Gate Arrays, Monterey, California, USA, 2002: 187–195.

韩晓亚, 汪斌强, 黄万伟, 等. 采用配置完成优先策略的可重构任务调度算法[J]. 小型微型计算机系统, 2012, 33(3): 587–593. doi: 10.3969/j.issn.1000-1220.2012.03.027

HAN Xiaoya, WANG Binqiang, HUANG Wanwei, et al. Scheduling algorithm for dependent reconfigurable tasks based on configuration completion first[J]. Journal of Chinese Computer Systems, 2012, 33(3): 587–593. doi: 10.3969/j.issn.1000-1220.2012.03.027

LIFA A, ELES P, and PENG Zebo. Minimization of average execution time based on speculative FPGA configuration prefetch[C]. Proceedings of 2012 International Conference on Reconfigurable Computing and FPGAs, Cancun, Mexico, 2012: 1–8.

LIFA A, ELES P, and PENG Zebo. A reconfigurable framework for performance enhancement with dynamic FPGA configuration prefetching[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016, 35(1): 100–113. doi: 10.1109/TCAD.2015.2448694

MORALES-VILLANUEVA A, KUMAR R, and GORDON-ROSS A. Configuration prefetching and reuse for preemptive hardware multitasking on partially reconfigurable FPGAs[C]. Proceedings of 2016 Conference on Design, Automation & Test in Europe, Dresden, Germany, 2016: 1505–1508.

WU Binbin, YAN Like, WEN Yuan, et al. Run-time configuration prefetching to reduce the overhead of dynamically reconfiguration[C]. Proceedings of the 23rd IEEE International SOC Conference, Las Vegas, USA, 2010: 305–308.

RUSCHKE T, JUNG L J, and HOCHBERGER C. A near optimal integrated solution for resource constrained scheduling, binding and routing on CGRAs[C]. Proceedings of 2017 IEEE International Parallel and Distributed Processing Symposium Workshops, Lake Buena Vista, USA, 2017: 213–218.

RUSCHKE T, JUNG L J, WOLF D, et al. Scheduler for inhomogeneous and irregular CGRAs with support for complex control flow[C]. Proceedings of 2016 IEEE International Parallel and Distributed Processing Symposium Workshops, Chicago, USA, 2016: 198–207.

BONDALAPATI K and PRASANNA V K. Reconfigurable computing systems[J]. Proceedings of the IEEE, 2002, 90(7): 1201–1217. doi: 10.1109/JPROC.2002.801446

陈锐, 杨海钢, 王飞, 等. 基于自路由互连网络的粗粒度可重构阵列结构[J]. 电子与信息学报, 2014, 36(9): 2251–2257. doi: 10.3724/SP.J.1146.2013.01646

CHEN Rui, YANG Haigang, WANG Fei, et al. Coarse-grained reconfigurable array based on self-routing interconnection network[J]. Journal of Electronics &Information Technology, 2014, 36(9): 2251–2257. doi: 10.3724/SP.J.1146.2013.01646

徐金甫, 刘露, 李伟, 等. 一种基于阵列配置加速比模型的无损压缩算法[J]. 电子与信息学报, 2018, 40(6): 1492–1498. doi: 10.11999/JEIT170900

XU Jinfu, LIU Lu, LI Wei, et al. A new lossless compression algorithm based on array configuration speedup model[J]. Journal of Electronics &Information Technology, 2018, 40(6): 1492–1498. doi: 10.11999/JEIT170900

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

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

KWOK Y K and AHMAD I. Static scheduling algorithms for allocating directed task graphs to multiprocessors[J]. ACM Computing Surveys, 1999, 31(4): 406–471. doi: 10.1145/344588.344618

Relative Articles

Supplements(0)

Cited By

Proportional views