Abstract:
Dynamic reconfiguration feature in recent embedded systems provides flexibility in the execution of applications. Using this feature, several tasks of an application can be mapped simultaneously into a limited area of resources in several Execution Cycles (ECs). The complexity of resource management and efficient scheduling of tasks in such systems require more consideration of the task’s attributes. In this paper, we proposed a new model for execution configuration which satisfies task constraints such as routing and resource wasting to derive multiple configurations for each task. In order to reduce the surface fragmentation and efficient resource utilization, one partition-based scheduling algorithm with a scheduled time metric has been proposed to properly select among possible configurations and partitions. Several experiments with different scenarios such as heavy and light workloads have been conducted and the results show that rejection ratio is reduced 42.10% and 24.14% in compared with two First and Best Fit algorithms, respectively. Some improvements in other evaluation metrics have been obtained, as well.
Keywords: Reconfigurable Systems, Resource Allocation; Resource Management; Partitioning Algorithms
References:
[1] M. Awad, "FPGA supercomputing platforms: a survey," IEEE International Conference on Field Programmable Logic and Applications, 2009, pp. 564-568. Google Scholar
[2] J.M. Emmert, C.E. Stroud, and M. Abramovici, "Online fault tolerance for FPGA logic blocks," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 15, 2007 pp.216-226. Google Scholar
[3] H.S. Shahhoseini, M. Naderi, and R. Buyya, "Shared memory multistage clustering structure, an efficient structure for massively parallel processing systems," Proceedings of Fourth International Conference/Exhibition on High Performance Computing in the AsiaPacific Region, Vol. 1, 2000, pp. 22-27. Google Scholar
[4] A. Tabatabaei, M.R. Mosavi, A. Khavari, and H.S. Shahhoseini, "Reliable urban canyon navigation solution in GPS and GLONASS integrated receiver using improved fuzzy weighted least-square method," Wireless Personal Communications, Vol. 94, 2017, pp.3181-3196. Google Scholar
[5] H.J. Rad, M. Azarafrooz, H.S. Shahhoseini, and B. Abolhassani, "A new adaptive power optimization scheme for target tracking wireless
sensor networks," IEEE Symposium on Industrial Electronics & Applications, 2009, pp. 307-312. Google Scholar
[6] W. Liu, W. Li, P.S. Un, and Y.B. Cho, "High-throughput HW-SW implementation for MV-HEVC decoder," International SoC Design Conference (ISOCC), 2018, pp. 226-228. Google Scholar
[7] L. Pezzarossa, A.T. Kristensen, M. Schoeberl, and J. Sparsø, "Using dynamic partial reconfiguration of FPGAs in real-Time systems," Microprocessors and Microsystems, Vol. 61, 2018 pp.198-206. Google Scholar
[8] S.M. Mohtavipour, and H.S. Shahhoseini, "A Link-Elimination Partitioning Approach for Application Graph Mapping in Reconfigurable Computing Systems," The Journal of Supercomputing, 2019, pp. 1-29. Google Scholar
[9] H. Liang, S. Sinha, R. Warrier, and W. Zhang, "Static hardware task placement on multi-context FPGA using hybrid genetic algorithm," IEEE 25th International Conference on Field Programmable Logic and Applications (FPL),2015, pp. 1-8. Google Scholar
[10] S. Banerjee, E. Bozorgzadeh, and N.D. Dutt, "Integrating physical constraints in HW-SW partitioning for architectures with partial dynamic reconfiguration,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 14, 2006, pp.1189-1202. Google Scholar
[11] M.M. Bassiri, and H.S. Shahhoseini, "On-line HW/SW partitioning and co-scheduling in reconfigurable computing systems," 2nd IEEE International Conference on Computer Science and Information Technology, 2009, pp. 557-562. Google Scholar
[12] M.M. Bassiri, and H.S. Shahhoseini, "A new approach in on-line task scheduling for reconfigurable computing systems," IEEE International Conference on Application-specific Systems, Architectures and Processors, 2010, pp. 321-324. Google Scholar
[13] M.M. Bassiri, and H.S. Shahhoseini, "Mitigating reconfiguration overhead in on-line task scheduling for reconfigurable computing systems," 2nd International Conference on Computer Engineering and Technology, Vol. 4, 2010, pp. 391-397. Google Scholar
[14] G. Wassi, M.E.A. Benkhelifa, G. Lawday, F. Verdier, and S. Garcia, "Multi-shape tasks scheduling for online multitasking on FPGAs," IEEE 9th International Symposium on Reconfigurable and CommunicationCentric Systems-on-Chip (ReCoSoC), 2014, pp. 1-7. Google Scholar
[15] M. Huang, V.K. Narayana, H. Simmler, O. Serres, and T. El-Ghazawi, "Reconfiguration and communication-aware task scheduling for highperformance reconfigurable computing," ACM Transactions on Reconfigurable Technology and Systems (TRETS), Vol. 3, 2010, p.20-34. Google Scholar
[16] T. Marconi, "Online scheduling and placement of hardware tasks with multiple variants on dynamically reconfigurable field-programmable gate arrays," Computers & Electrical Engineering, Vol. 40, 2014, pp.1215-1237. Google Scholar
[17] 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, 2011, pp.463-474. Google Scholar