[Home ]   [ فارسی ]  
Main Menu
Mission ::
Research Groups::
Contact Us::
Published Papers::
:: BOTS: Balanced-Objective Task Selector for Application Graph Scheduling in Reconfigurable Computing Systems ::
BOTS: Balanced-Objective Task Selector for Application
Graph Scheduling in Reconfigurable Computing Systems
Milad Gholamrezanejad Ferdos
Iran University of Science and Technology
School of Electrical Engineering
Tehran, Iran
Hadi Shahriar Shahhoseini
Iran University of Science and Technology
School of Electrical Engineering
Tehran, Iran
PDF     │   Abstract   │  Keywords   │  References   │  Cite This 


Hardware-based execution capability with resource reusing flexibility is one of the new features of Reconfigurable Computing (RC) systems. However, due to the reconfiguration constraints, it is difficult to fully exploit their advantages. For a better design with higher performance, several pivotal objectives should be investigated simultaneously such as task execution time, communication data between tasks, and required resources for implementation. In this paper, a new algorithm for task selection in an application graph has been introduced to balance objectives in RC system. This algorithm decides based on a selection merit to reduce the number of execution clusters and to save communication cost as much as possible. To remove forbidden solution, a set of free tasks has been constructed to satisfy the precedence constraints. The evaluation has been performed with different topological features such as parallelism degree and critical path. Results showed that the proposed method provides acceptable improvement in comparison with previous method for application execution time metric.

Keywords: Reconfigurable Systems; Task Scheduling; Resource Allocation; Multi-objective Algorithm


[1] P.E. Gaillardon, "Reconfigurable Logic: Architecture, Tools, and Applications," CRC Press, 2018.  Google Scholar

[2] M. Saeed and H.S. Shahhoseini, "APPMA - an Anti-phishing protocol with mutual Authentication," The IEEE symposium on Computers and Communications, Riccione, 2010, pp. 308-313, doi: 10.1109/ISCC.2010.5546794.  Google Scholar

[3] P.S. Choudhary and M.S. Ali, "FPGA-Based Adaptive Task Scheduler for Real Time Embedded Systems," 2018 International Conference on Research in Intelligent and Computing in Engineering (RICE), San Salvador, 2018, pp. 1-4, doi: 10.1109/RICE.2018.8509088.   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," Journal of Wireless Personal Communications, Vol.94, No.4, pp.3181-3196, 2017. https://doi.org/10.1007/s11277-016-3771-1.  Google Scholar

[5] H. Jamali Rad, M. Azarafrooz, H.S. Shahhoseini and B. Abolhassani, "A new adaptive power optimization scheme for target tracking Wireless Sensor Networks," 2009 IEEE Symposium on Industrial Electronics & Applications, Kuala Lumpur, 2009, pp. 307-312, doi: 10.1109/ISIEA.2009.5356452.  Google Scholar

[6] M.M. Bassiri and H.S. Shahhoseini,  "Configuration reusing in on-line task scheduling for reconfigurable computing systems," Journal of Computer Science and Technology, 26(3), pp. 463-473, 2011.https://doi.org/10.1007/s11390-011-1147-2.  Google Scholar

[7] A. Ait El Cadi, O. Souissi, R. Ben Atitallah, N. Belanger, and A. Artiba, "Mathematical programming models for scheduling in a CPU/FPGA architecture with heterogeneous communication delays," Journal of Intelligent Manufacturing, Vol. 29, pp. 629–640, 2018.https://doi.org/10.1007/s10845-015-1075-z.  Google Scholar

[8] M.M. Bassiri and H.S. Shahhoseini, "On-line HW/SW partitioning and co-scheduling in reconfigurable computing systems," 2009 2nd IEEE International Conference on Computer Science and Information Technology, Beijing, 2009, pp. 557-562, doi: 10.1109/ICCSIT.2009.5234664.  Google Scholar

[9] M.M. Bassiri and H.S. Shahhoseini, "Mitigating reconfiguration overhead in on-line task scheduling for reconfigurable computing systems," 2010 2nd International Conference on Computer Engineering and Technology, Chengdu, 2010, pp. V4-397-V4-402, doi: 10.1109/ICCET.2010.5485509. Google Scholar

[10] 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, pp. 198-206, 2018. https://doi.org/10.1016/j.micpro.2018.05.017.   Google Scholar

[11] H.S. Shahhoseini, M. Naderi and R. Buyya, "Shared memory multistage clustering structure, an efficient structure for massively parallel processing systems," Proceedings Fourth International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, Beijing, China, 2000, pp. 22-27 vol.1, doi: 10.1109/HPC.2000.846510.   Google Scholar

[12] M. Alam, A. Khan, A.K. Varshney, "A Review of Dynamic Scheduling Algorithms for Homogeneous and Heterogeneous Systems," In: Muttoo S. (eds) System and Architecture. Advances in Intelligent Systems and Computing, vol 732. Springer, Singapore. 2018. https://doi.org/10.1007/978-981-10-8533-8_8  Google Scholar

[13] M. Huang, V.K. Narayana, H. Simmler, O. Serres, and T. El-Ghazawi, "Reconfiguration and Communication-Aware Task Scheduling for High-Performance Reconfigurable Computing," ACM Transactions on Reconfigurable Technology and Systems (TRETS), Vol. 3, pp. 1–25, 2010. https://doi.org/10.1145/1862648.1862650  Google Scholar

[14] S.M. Mohtavipour, and H.S. Shahhoseini, "A Link-Elimination Partitioning Approach for Application Graph Mapping in Reconfigurable Computing Systems," The Journal of Supercomputing, pp. 1-25, 2020. https://doi.org/10.1007/s11227-019-03056-5.  Google Scholar

[15] K. Vipin, and S.A. Fahmy, "FPGA dynamic and partial reconfiguration: A survey of architectures, methods, and applications," ACM Computing Surveys (CSUR), Vol. 51, pp. 72-111, 2018. https://doi.org/10.1145/3193827.  Google Scholar

[16] M.M. Bassiri and H.S. Shahhoseini, "A New approach in on-line task scheduling for reconfigurable computing systems," ASAP 2010 - 21st IEEE International Conference on Application-specific Systems, Architectures and Processors, Rennes, 2010, pp. 321-324, doi: 10.1109/ASAP.2010.5540975.  Google Scholar

[17] A. Surendar, "FPGA based parallel computation techniques for bioinformatics applications," International Journal of Research in Pharmaceutical Sciences, Vol. 8, pp.124-128, 2017. Google Scholar

[18] J.J. Rodríguez-Andina, M.D. Valdés-Peña and M.J. Moure, "Advanced Features and Industrial Applications of FPGAs—A Review," in IEEE Transactions on Industrial Informatics, vol. 11, no. 4, pp. 853-864, Aug. 2015, doi: 10.1109/TII.2015.2431223.  Google Scholar

[19] G. Juve, A. Chervenak, E. Deelman, S. Bharathi, G. Mehta, and K. Vahi, "Characterizing and profiling scientific workflows," Future Generation Computer Systems, Vol. 29, pp. 682-692, 2013. https://doi.org/10.1016/j.future.2012.08.015.  Google Scholar

[20] Z. Chen, M. Qiu, Z. Ming, L.T. Yang, and Y. Zhu, "Clustering scheduling for hardware tasks in reconfigurable computing systems," Journal of Systems Architecture, vol. 59, no. 10, pp. 1424–1432, 2013. https://doi.org/10.1016/j.sysarc.2013.05.015.  Google Scholar


Cite this paper as:
M.  Gholamrezanejad Ferdos and H.S. Shahhoseini, "BOTS: Balanced-Objective Task Selector for Application Graph Scheduling in Reconfigurable Computing Systems," 10th International Conference on Information and Knowledge Technology (IKT 2019), Tehran, Iran, 2019.
View: 825 Time(s)   |   Print: 298 Time(s)   |   Email: 0 Time(s)   |   0 Comment(s)
All Rights reserved
Persian site map - English site map - Created in 0.12 seconds with 45 queries by YEKTAWEB 4652