Abstract:
Reconfiguration overhead is an important obstacle that limits the performance of on-line scheduling algorithms in reconfigurable computing systems and increases the overall execution time. Configuration reusing (task reusing) can decrease reconfiguration overhead considerably, particularly in periodic applications or the applications in which the probability of tasks recurrence is high. in this paper, we improve reusing technique in order to reduce reconfiguration overhead and decrease total execution time of the tasks. in reusing method, input tasks are divided into significant and non-significant tasks. significant tasks are preserved on the RPU in order to be reused in near future. the main contribution in this paper include new task significance calculation and performance evaluation of resizing the RPU partitions. A large variety of experiments has been conducted on the proposed algorithm. Obtained results show when the recurrence of tasks is 40%, we have up to 14% improvement in overall execution time of resizable reusing based scheduling comparing reusing without resizing, and up to 25% improvement comparing scheduling without reusing.
Keywords: RECONFIGURABLE COMPUTING, ON-LINE SCHEDULING, CONFIGURATION REUSING, RPU PARTITIONING, REPLACEMENT MANAGEMENT, MANAGEMENTT PROBABIKITY

 
References:
[1]  C. Kao, "Performance-Oriented Partitioning for Task Scheduling of Parallel Reconfigurable Architectures," in IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 3, pp. 858-867, March 2015, doi: 10.1109/TPDS.2014.2312924.   Google Scholar
[2]  P. Saha, and T. El-Ghazawi, "A Methodology for Automating Co-Scheduling for Reconfigurable Computing Systems," Proc. IEEE/ACM Intl Conf. Formal Methods and Models for Codesign, pp. 159-168, 2007, doi: 10.1109/MEMCOD.2007.371229.   Google Scholar
[3]  A. Agne, M. Happe, A. Keller, E. Lubbers, B. Plattner, M. Platzner, and C. Plessl, "Recon OS-An Operating System Approach for Reconfigurable Computing," IEEE Micro, vol. 34, no. 3, pp. 60-71, 2014, doi: 10.1109/MM.2013.110.   Google Scholar
[4]  Q. Deng, S. Wei, H. Xu, Y. Han, and G. Yu, "A Reconfigurable RTOS with HW/SW Co-scheduling for SOPC," Proc. Second Intl Conf. Embedded Software and
Systems, pp. 60-66, 2005, doi: 10.1109/ICESS.2005.9.   Google Scholar
[5]  M. M. Bassiri, and H. S. Shahhoseini, "Configuration Reusing in On-Line Task Scheduling for Reconfigurable Computing Systems," Journal of Computer Science and Technology, vol. 26, no. 3, pp 463-473, 2011, doi: https://doi.org/10.1007/s11390-011-1147-2.  Google Scholar
[6]  K. Bazargan, R. Kastner, and M. Sarrafzadeh, "Fast Template Placement for Reconfigurable Computing Systems," IEEE Design and Test of Computer Journal, vol. 17, no. 1, pp. 68-83, 2000, doi: 10.1109/54.825678.   Google Scholar
[7]  Q. H. Khuat, D. Chillet, and M. Hubner, "Considering Reconfiguration Overhead in Scheduling of Dependent Tasks on 2D Reconfigurable FPGA," Proc. IEEE Intl Conf. Adaptive Hardware and Systems, pp.1-8, 2014, doi: 10.1109/AHS.2014.6880151.   Google Scholar
[8]  T. Marescaux, A. Bartic, V. Dideriek, S. Vernalde, and R. Lauwereins, "Interconnection Networks Enable Fine-Grain Dynamic Multi-tasking on FPGAs," Proc. IEEE Intl Conf. Field-Programmable Logic and Applications, pp. 795-805, 2002, doi: https://doi.org/10.1007/3-540-46117-5_82.   Google Scholar
[9]  Xilinx, "Field Programmable Gate Arrays," December 2002. 
[10]  S. Banerjee, E. Bozorgzadeh and N. D. Dutt, "Integrating Physical Constraints in HW-SW Partitioning for Architectures With Partial Dynamic Reconfiguration," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 14, no. 11, pp. 1189-1202, Nov. 2006, doi: 10.1109/TVLSI.2006.886411.  Google Scholar
[11]  I. Belaid, F. Muller, and M. Benjemaa, "Optimal Static Scheduling of Real-time Dependent Tasks on Reconfigurable Hardware Devices," Proc. IEEE/ACM Intl Conf. Formal Methods and Models for Codesign, pp. 1-6, 2011, doi: 10.1109/CCCA.2011.6031425.   Google Scholar
[12]  M. Huang, H. Simmler, and P. Saha and T. El-Ghazawi, "Hardware Task Scheduling Optimizations for Reconfigurable Computing," Proc. IEEE Intl workshop on High-Performance Reconfigurable Computing Technology and Applications, pp. 1-10, 2008, doi: 10.1109/HPRCTA.2008.4745681.  Google Scholar
[13]  W. Hu, and C. Wang, "A Novel Approach for Finding Candidate Locations for On-line FPGA Placement," Proc. IEEE Intl Conf. Field-Programmable Logic and
Applications, pp. 2509-2515, 2010, doi: 10.1109/CIT.2010.428.   Google Scholar
[14]  X. G. Zhou, Y. Wang, X. Z. Huang, and C. L. Peng, "On-line Scheduling of Real-time Tasks for Reconfigurable Computing System," Proc. IEEE Intl Conf. FieldProgrammable Logic and Applications, pp. 25-31, 2006, doi: 10.1109/FPT.2006.270295.  Google Scholar
[15]  K. Danne, and M. Platzner, "A Heuristic Approach to Schedule Periodic Real-Time Tasks on Reconfigurable Hardware," Proc. IEEE Intl Conf. Field Programmable Logic and Applications, pp. 568-573, 2005, doi: 10.1109/FPL.2005.1515787.  Google Scholar
[16]  A. Ahmadinia, C. Bobda, and J. Teich, "A Dynamic Scheduling and Placement Algorithm for Reconfigurable Hardware," Proc. IEEE Intl Conf. Field-Programmable Logic and Applications, pp. 125-139, 2004, doi: https://doi.org/10.1007/978-3-540-24714-2_11.   Google Scholar
[17]  T.Y. Lee, N. Y. Lin, W. C. Chen, and H. Wu, "An Efficient Task Placement Method for Reconfigurable FPGA Systems," Proc. IEEE Intl Conf. Complex, Intelligent, and Software Intensive Systems, pp. 451-455, 2013, doi: 10.1109/CISIS.2013.82.   Google Scholar
[18]  A. Al-Wattar, S. Areibi, and F. Saffih, "Efficient Online Hardware/Software Task Scheduling for Dynamic RunTime Reconfigurable Systems," Proc. IEEE Intl Symp. Parallel and Distributed Processing, pp. 401-406, 2012, doi: 10.1109/IPDPSW.2012.50.   Google Scholar
[19]  T. Marconi, Y. Lu, K. Bertels, and G. Gaydadjiev, "Online Hardware Task Scheduling and Placement Algorithm on Partially Reconfigurable Devices," Proc. IEEE Intl Conf. Adaptive Hardware and Systems, pp. 306-311, 2008, doi: https://doi.org/10.1007/978-3-540-78610-8_33.   Google Scholar
[20]  Y. Sheng, Y. Liu, R. Li, and X. Xiao, "A Communication-aware Scheduling Algorithm for Hardware Task Scheduling Model on FPGA-based Reconfigurable
Systems," Journal of Computers, vol. 9, no. 2, pp. 2552-2558, 2014, doi: 10.1109/FCCM.2010.18.   Google Scholar
[21]  T. Marconi, "Online Scheduling and Placement of Hardware Tasks with Multiple Variants on Dynamically Reconfigurable Field-programmable Gate Arrays,"
Computers and Electrical Engineering Journal, vol. 40, no. 4, pp. 1215-1237, 2014, doi: https://doi.org/10.1016/j.compeleceng.2013.07.004.   Google Scholar
[22] S. Roman, H. Mecha, D. Mozos and J. Septien, "Constant complexity scheduling for hardware multitasking in two dimensional reconfigurable field-programmable gate arrays," in IET Computers & Digital Techniques, vol. 2, no. 6, pp. 401-412, November 2008, doi: 10.1049/iet-cdt:20070060.   Google Scholar
[23]  K. Hassanli, A. K. Mahani, H. Shahhoseini and E. Teimoury, "Queuing Analysis for Reconfigurable Computing," 2008 Workshop on Power Electronics and Intelligent Transportation System, Guangzhou, 2008, pp. 284-288, doi: 10.1109/PEITS.2008.125.   Google Scholar
[24]  J. Cui, Z. Gu, W. Liu and Q. Deng, "An Efficient Algorithm for Online Soft Real-Time Task Placement on Reconfigurable Hardware Devices," 10th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC'07), Santorini Island, 2007, pp. 321-328, doi: 10.1109/ISORC.2007.18.   Google Scholar
[25]  F. Dittmann and S. Frank, "Caching in Real-Time Reconfiguration Port Scheduling," 2007 International Conference on Field Programmable Logic and Applications, Amsterdam, 2007, pp. 740-744, doi: 10.1109/FPL.2007.4380758.  Google Scholar
[26]  L. Liang, X. Zhou, Y. Wang and C. Peng, "Online Hybrid Task Scheduling in Reconfigurable Systems," 2007 11th International Conference on Computer Supported Cooperative Work in Design, Melbourne, Vic., 2007, pp. 1072-1077, doi: 10.1109/CSCWD.2007.4281589.   Google Scholar
[27]  J. Cui, Q. Deng, X. He and Z. Gu, "An Efficient Algorithm for Online Management of 2D Area of Partially Reconfigurable FPGAs," 2007 Design, Automation & Test in Europe Conference & Exhibition, Nice, 2007, pp. 1-6, doi: 10.1109/DATE.2007.364579.    Google Scholar
[28]  Xilinx Inc., Virtex Core Generator, December 2002.
[29]  Amphion Semiconductor Group:, http://www.amphion.com, May 2003.