Transactions on Machine Intelligence

Transactions on Machine Intelligence

On-Line Reusing-Based Scheduling Algorithm for 2-Dimensional Tasks in Reconfigurable Hardware

Document Type : Original Article

Authors
Department of Electrical Engineering, University of Science and Technology (IUST), Tehran, Iran
Abstract
Reducing reconfiguration overhead is critical to improving the runtime performance of dynamically reconfigurable Field-Programmable Gate Arrays (FPGAs). In this paper, we introduce a novel task-reuse strategy tailored for two-dimensional FPGA hardware layouts. The key idea is to identify and exploit repetitive computations by reusing already‐configured hardware modules rather than incurring costly bitstream reloads. First, incoming tasks are classified into two categories significant (high‐impact or frequently appearing) and non-significant based on metrics such as execution frequency, resource intensity, and temporal locality. Each category is assigned to its own hardware partition. Within the significant partition, when a new significant task arrives, the system either replaces an existing module whose future utility is low or, if sufficient empty regions exist in the non-significant partition, temporarily maps the task there. If neither option is feasible, the partition boundary is extended to accommodate the new module, up to predefined physical limits. We evaluated our approach on a suite of benchmark applications exhibiting high task repetition. Compared to leading dynamic‐reconfiguration algorithms, our method reduced overall makespan by 20.3% on average. Moreover, the task-placement decision algorithm operates in polynomial time, achieving placement decisions over three times faster than competing strategies. These results demonstrate that intelligent partitioning combined with selective reuse and partition‐border extension can substantially lower reconfiguration overhead and accelerate FPGA‐based computation pipelines.
Keywords

Pöppelmann, T., Naehrig, M., Putnam, A., & Macias, A. (2015). Accelerating Homomorphic Evaluation on Reconfigurable Hardware. Στο Lecture notes in computer science. Lecture Notes in Computer Science (pp. 143–163). doi:10.1007/978-3-662-48324-4_8
Liu, L., Wang, D., Chen, Y., Zhu, M., Yin, S., & Wei, S. (2016). An implementation of multiple-standard video decoder on a mixed-grained reconfigurable computing platform. IEICE Transactions on Information and Systems, E99. D(5), 1285–1295. doi:10.1587/transinf.2015edp7369
Fons, M., Fons, F., & Canto, E. (2010). Fingerprint image processing acceleration through run-time reconfigurable hardware. IEEE transactions on circuits and systems. II, Express briefs: a publication of the IEEE Circuits and Systems Society, 57(12), 991–995. doi:10.1109/tcsii.2010.2087970
Kao, C.-C. (2015). Performance-oriented partitioning for task scheduling of parallel reconfigurable architectures. IEEE transactions on parallel and distributed systems: a publication of the IEEE Computer Society, 26(3), 858–867. doi:10.1109/tpds.2014.2312924
Saha, P., & El-Ghazawi, T. (2007). A methodology for automating co-scheduling for reconfigurable computing systems. 2007 5th IEEE/ACM International Conference on Formal Methods and Models for Codesign (MEMOCODE 2007). Nice. doi:10.1109/memcod.2007.371229
Banerjee, S., Bozorgzadeh, E., Dutt, N., & Noguera, J. (2007). Selective bandwidth and resource management in scheduling for dynamically reconfigurable architectures. Proceedings of the 44th annual conference on Design automation - DAC ’07, San Diego, California. doi:10.1145/1278480.1278673
Liang, H., Sinha, S., Warrier, R., & Zhang, W. (2015, Σεπτέμβριος). Static hardware task placement on multi-context FPGA using hybrid genetic algorithm. 2015 25th International Conference on Field Programmable Logic and Applications (FPL). London, United Kingdom. doi:10.1109/fpl.2015.7293954
Marconi, T. (2014). Online scheduling and placement of hardware tasks with multiple variants on dynamically reconfigurable field-programmable gate arrays. Computers & Electrical Engineering: An International Journal, 40(4), 1215–1237. doi:10.1016/j.compeleceng.2013.07.004
Steiger, C., Walder, H., & Platzner, M. (2004). Operating systems for reconfigurable embedded platforms: online scheduling of real-time tasks. IEEE Transactions on Computers. Institute of Electrical and Electronics Engineers, 53(11), 1393–1407. doi:10.1109/tc.2004.99
Li, Z., Compton, K., & Hauck, S. (2002). Configuration caching management techniques for reconfigurable computing. Proceedings 2000 IEEE Symposium on Field-Programmable Custom Computing Machines (Cat. No.PR00871). Napa Valley, CA, USA. doi:10.1109/fpga.2000.903390
Li, Zhiyuan, & Hauck, S. (2002). Configuration prefetching techniques for partial reconfigurable coprocessor with relocation and defragmentation. Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays - FPGA ’02., Monterey, California, USA. doi:10.1145/503048.503076
Khuat, Q.-H., Chillet, D., & Hubner, M. (2014). Considering reconfiguration overhead in scheduling of dependent tasks on 2D reconfigurable FPGA. 2014 NASA/ESA Conference on Adaptive Hardware and Systems (AHS). United Kingdom. doi:10.1109/ahs.2014.6880151
Clemente, J. A., Ramo, E. P., Resano, J., Mozos, D., & Catthoor, F. (2014). Configuration mapping algorithms to reduce energy and time reconfiguration overheads in reconfigurable systems. IEEE transactions on very large scale integration (VLSI) systems, 22(6), 1248–1261. doi:10.1109/tvlsi.2013.2271917
Shahryar, S. H., Mansoub, B. M., & Mohtavi, P. S. M. (2013). Performance Evaluation of Reusing Based Scheduling In On-Line Reconfigurable Computing Systems.
Volume 1, Issue 1
Winter 2018
Pages 39-48

  • Receive Date 19 January 2018
  • Revise Date 22 February 2018
  • Accept Date 11 March 2018