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 one of the main topics in increasing speed and performance of dynamically reconfigurable Field-Programmable Gate Arrays (FPGA). In this paper, an approach for reusing a repetitive hardware task in 2-dimensional hardware is proposed. At first, incoming tasks are divided into significant and non-significant tasks based on their features. Each group is placed in a specific partition of hardware and several methods such as replacement of significant tasks, using empty spaces in other partition or extending the partition border are applied to better use the resources. Conducted experiments show that in repetitive programs, the proposed method has %20.3 less makespan and decides more than 3 times faster than state-of-the-art algorithms in this field.

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.