-
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]

      Geng ZHAOHong LIYingjie MAXiaohong QIN . Discrete Dynamic System without Degradation -configure N Positive Lyapunov Exponents. Journal of Electronics and Information Technology, 2019, 41(9): 2280-2286. doi: 10.11999/JEIT180925

    3. [3]

      Yingjian YANMin LIUZhaoyang QIU . Design and Implementation of Hardware Trojan Detection Algorithm for Coarse-grained Reconfigurable Arrays. Journal of Electronics and Information Technology, 2019, 41(5): 1257-1264. doi: 10.11999/JEIT180484

    4. [4]

      Jun LUOZewei LIUPing ZHAGNXueming LIUZheng LIU . Application of Improved Bird Swarm Algorithm Based on Nonlinear Factor in Dynamic Energy Management. Journal of Electronics and Information Technology, 2019, 41(0): 1-8. doi: 10.11999/JEIT190264

    5. [5]

      Liang JINAolin CAIKaizhi HUANGZhou ZHONGYangming LOU . Secret Key Generation Method Based on Multi-stream Random Signal. Journal of Electronics and Information Technology, 2019, 41(6): 1405-1412. doi: 10.11999/JEIT181040

    6. [6]

      Ying CHENDandan HE . Spatial-temporal Stream Anomaly Detection Based on Bayesian Fusion. Journal of Electronics and Information Technology, 2019, 41(5): 1137-1144. doi: 10.11999/JEIT180429

    7. [7]

      Shuqin DONGBin ZHANG . A Probabilistic Flow Sampling Method for Traffic Anomaly Detection. Journal of Electronics and Information Technology, 2019, 41(6): 1450-1457. doi: 10.11999/JEIT180631

    8. [8]

      Songtao HANMing CHENCuilan LIWeitao LU . Research on Application of Same-beam Interferometry in China Lunar Exploration. Journal of Electronics and Information Technology, 2019, 41(8): 1960-1965. doi: 10.11999/JEIT180914

    9. [9]

      Xiang XIELiqiang ZHANGJing WANG . Application of Residual Network to Infant Crying Recognition. Journal of Electronics and Information Technology, 2019, 41(1): 233-239. doi: 10.11999/JEIT180276

    10. [10]

      Weiqing YAOBenshun YI . A Novel Encoding and Decoding Method of LT Codes and Application to Cognitive Radio. Journal of Electronics and Information Technology, 2019, 41(3): 571-579. doi: 10.11999/JEIT180427

    11. [11]

      Xiaodong QUYang SUNChong CHENJunlong SHIXin XUJutao LIWanhua ZHUGuangyou FANG . Direction Finding for Electromagnetic Radiation Source Using Ultra-short Baseline Array. Journal of Electronics and Information Technology, 2019, 41(4): 830-836. doi: 10.11999/JEIT180516

    12. [12]

      Ping TANLimei LIUFan GUOKaijun ZHOU . Applying Chernoff Weighted Classification Frame Method to MotorImagery Brain Computer Interface. Journal of Electronics and Information Technology, 2019, 41(0): 1-7. doi: 10.11999/JEIT181132

    13. [13]

      Huanlin LIUFei FANGYong CHENMin XIANGYue MA . Energy-efficient Scheduling Algorithm for All Optical IP Multicast Based on Colorless, Directionless and Contentionless-Flexible Reconfigurable Optical Add/Drop Multiplexer Node. Journal of Electronics and Information Technology, 2019, 41(0): 1-7. doi: 10.11999/JEIT180937

    14. [14]

      Aili ZHANGHao LIULin WULijie NIUCheng ZHANGXue CHENJi WU . The Application of the G-matrix Modification Methods in the Imaging of the 1-D Synthetic Aperture Microwave Radiometer. Journal of Electronics and Information Technology, 2019, 41(0): 1-7. doi: 10.11999/JEIT181067

    15. [15]

      Xinyu WANGZhiying LIShuai SHAOZhigang YU . Robust Application Mapping for Networks-on-chip Considering Uncertainty of Tasks. Journal of Electronics and Information Technology, 2019, 41(5): 1152-1159. doi: 10.11999/JEIT180600

    16. [16]

      Jing LIUHan LIUKaiyu HUANGLiyu SU . Automatic Rank Estimation Based Riemannian Optimization Matrix Completion Algorithm and Application to Image Completion. Journal of Electronics and Information Technology, 2019, 41(0): 1-8. doi: 10.11999/JEIT181076

    17. [17]

      Pengfei ZHANGShu WANGPan LI . Analysis of Some Mathematical Questions of Transformation Optics and Its Application to Stealth Carpet Design. Journal of Electronics and Information Technology, 2019, 41(6): 1336-1343. doi: 10.11999/JEIT180247

    18. [18]

      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

    19. [19]

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

    20. [20]

      Derong CHENHaibo LÜQiufu LIJiulu GONGZhiqiang LIXiaojun HAN . Total Variation Regularized Reconstruction Algorithms for Block Compressive Sensing. Journal of Electronics and Information Technology, 2019, 41(9): 2217-2223. doi: 10.11999/JEIT180931

Metrics
  • PDF Downloads(20)
  • Abstract views(329)
  • HTML views(149)
  • Cited By(0)

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

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

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

/

DownLoad:  Full-Size Img  PowerPoint
Return