-
Advanced Search

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

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

  • Corresponding author: Tongzhou QU, qutongzhou@outlook.com
  • Received Date: 2018-08-24
    Accepted Date: 2019-02-02
    Available Online: 2019-06-01

Figures(8) / Tables(1)

  • 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. [1]

      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

    2. [2]

      梁樑, 周学功, 王颖, 等. 采用预配置策略的可重构混合任务调度算法[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

    3. [3]

      王延升. 粗粒度动态可重构处理器中的高能效关键配置技术研究[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.

    4. [4]

      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.

    5. [5]

      韩晓亚, 汪斌强, 黄万伟, 等. 采用配置完成优先策略的可重构任务调度算法[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

    6. [6]

      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.

    7. [7]

      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

    8. [8]

      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.

    9. [9]

      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.

    10. [10]

      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.

    11. [11]

      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.

    12. [12]

      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

    13. [13]

      陈锐, 杨海钢, 王飞, 等. 基于自路由互连网络的粗粒度可重构阵列结构[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

    14. [14]

      徐金甫, 刘露, 李伟, 等. 一种基于阵列配置加速比模型的无损压缩算法[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

    15. [15]

      徐晓东. 动态可重构系统中任务调度与布局算法研究[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.

    16. [16]

      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

  • 加载中
    1. [1]

      Kaihui TUZhihong HUANGZhengrong HOUHaigang YANG . Research on Efficient FPGA Bitstream Generation System Based on Mode Matching and Hierarchical Mapping. Journal of Electronics and Information Technology, 2019, 41(0): 1-7. doi: 10.11999/JEIT190143

    2. [2]

      Yiwei PANHua PENGTianyun LIWenya WANG . A Novel Radiometric Signature of Time-Division Multiple Access Signals and Its Application to Specific Emitter Identification. Journal of Electronics and Information Technology, 2019, 41(0): 1-8. doi: 10.11999/JEIT190163

    3. [3]

      Yuze SUXiangru MENGQiaoyan KANGXiaoyang HAN . Core Link Aware Survivable Virtual Network Link Protection Method. Journal of Electronics and Information Technology, 2019, 41(7): 1587-1593. doi: 10.11999/JEIT180737

    4. [4]

      Hongchang CHENTuosiyu MINGShuxin LIUChao GAO . Semantic Summarization of Reconstructed Abstract Meaning Representation Graph Structure Based on Integer Linear Pragramming. Journal of Electronics and Information Technology, 2019, 41(7): 1674-1681. doi: 10.11999/JEIT180720

    5. [5]

      Jiangtao LUOChen HEJunxia WANG . Traceable Lightweight and Fine-grained Access Control in Named Data Networking. Journal of Electronics and Information Technology, 2019, 0(0): 1-7. doi: 10.11999/JEIT181160

    6. [6]

      Hongyan ZANGHuifang HUANGHongyu CHAI . Homogenization Method for the Quadratic Polynomial Chaotic System. Journal of Electronics and Information Technology, 2019, 41(7): 1618-1624. doi: 10.11999/JEIT180735

    7. [7]

      Guangwu CHENJianhao CHENGJuhua YANGHao LIULinjing ZHANG . Improved Neural Network Enhanced Navigation System of Adaptive Unsented Kalman Filter. Journal of Electronics and Information Technology, 2019, 41(7): 1766-1773. doi: 10.11999/JEIT181171

    8. [8]

      Xinhua LUCarles Navarro MANCHÓNZhongyong WANGChuanzong ZHANG . Channel Estimation Algorithm Using Temporal-Spatial Structure for Up-Link of Massive MIMO Systems. Journal of Electronics and Information Technology, 2019, 41(0): 1-7. doi: 10.11999/JEIT180676

    9. [9]

      Cheng TAOGuichao CHENKai LIUTao ZHOU . Performance Analysis of Massive MIMO-OFDM System with Hybrid-Precision Analog-to-Digital Converter. Journal of Electronics and Information Technology, 2019, 41(0): 1-8. doi: 10.11999/JEIT181136

    10. [10]

      Jiexin ZHANGJianmin PANGZheng ZHANGMing TAIHao LIU . Heterogeneity Quantization Method of Cyberspace Security System Based on Dissimilar Redundancy Structure. Journal of Electronics and Information Technology, 2019, 41(7): 1594-1600. doi: 10.11999/JEIT180764

    11. [11]

      Shunwai ZHANGQi WEI . Joint Design of Quasi-cyclic Low Density Parity Check Codes and Performance Analysis of Multi-source Multi-relay Coded Cooperative System. Journal of Electronics and Information Technology, 2019, 41(0): 1-9. doi: 10.11999/JEIT190069

Metrics
  • PDF Downloads(16)
  • Abstract views(258)
  • HTML views(115)
  • Cited By(0)

通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

DownLoad:  Full-Size Img  PowerPoint
Return