Task Scheduling Technology for Coarse-grained Dynamic Reconfigurable System Based on Configuration Prefetching and Reuse
-
摘要: 配置时间过长是制约可重构系统整体性能提升的重要因素，而合理的任务调度技术可有效降低系统配置时间。该文针对粗粒度动态可重构系统(CGDRS)和具有数据依赖关系的流应用，提出了一种3维任务调度模型。首先基于该模型，设计了一种基于预配置策略的任务调度算法(CPSA)；然后根据任务间的配置重用性，提出了间隔配置重用与连续配置重用策略，并据此对CPSA算法进行改进。实验结果证明，CPSA算法能够有效解决调度死锁问题、降低流应用执行时间并提高调度成功率。与其它调度算法相比，对流应用执行时间的平均优化比例达到6.13%～19.53%。
-
关键词:
- 粗粒度动态可重构系统 /
- 流应用 /
- 预配置 /
- 配置重用
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. -
表 1 CPSA调度算法相较于其它调度算法对应用执行时间的优化比例(%)
应用 O(Pre) O(CCF) O(RCP) O(BULB) J20&L5 12.30 4.38 6.50 19.79 J20&L10 10.32 5.87 8.06 15.73 J20&L15 9.66 7.33 11.48 18.18 J30&L5 12.06 5.02 6.35 15.28 J40&L15 20.75 8.63 16.10 20.90 J30&L10 8.57 5.59 13.81 18.26 J30&L15 16.95 7.55 11.93 21.63 J40&L5 21.57 5.11 17.28 26.02 J40&L10 10.89 5.68 15.72 19.97 平均值 13.67 6.13 11.91 19.53 
下载: 导出CSV
-
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.016LIANG 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.027HAN 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.01646CHEN 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/JEIT170900XU 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 -
下载:
图(8) / 表(1)
计量
- 文章访问数: 1805
- HTML全文浏览量: 673
- PDF下载量: 56
- 被引次数: 0
