A Review on Performance Evaluation of Multiprocessor based System using Scheduling Algorithms and Simulation Tools

M. Sreenath*, P. A. Vijaya**
*-** Department of Electronics and Communication Engineering, BNMIT, Bangalore, Karnataka, India.
Periodicity:January - June'2020
DOI : https://doi.org/10.26634/jes.8.2.17120

Abstract

The scheduling algorithm determines the process of execution by allocating the tasks to the available processors in a system. In an embedded system, real time control is essential for different applications like aircraft, manufacturing, information processing systems, etc. Multiprocessor based systems play a vital role to satisfy the real time performance constraints. In this aspect, different issues came to light when using scheduling algorithms for proper resource allocation and utilization. Many of the research scholars face difficulty in choosing the suitable platform for developing the new scheduling algorithms. For this concern, we acknowledge the performance parameters reviewed in the evaluation of multiprocessor based system using scheduling algorithms and simulation tools. Traditional real time scheduling algorithms are implemented using standard structure on suitable simulation tools for improved performance in terms of makespan, latency, flow time, utilization, success ratio, throughput and energy consumption. The main objective of this review is to find the optimum solution for multi-processor based system using scheduling algorithms in supported simulation tools.

Keywords

Algorithms, Process, Simulation, Multiprocessor, Optimization, Performance.

How to Cite this Article?

Sreenath, M., and Vijaya, P. A. (2020). A Review on Performance Evaluation of Multiprocessor based System using Scheduling Algorithms and Simulation Toolsi-manager's Journal on Embedded Systems, 8(2), 26-33. https://doi.org/10.26634/jes.8.2.17120

References

[1]. Abdelhafez, A., Alba, E., & Luque, G. (2019). Performance analysis of synchronous and asynchronous distributed genetic algorithms on multiprocessors. Swarm and Evolutionary Computation, 49, 147-157. https://doi. org/10.1016/j.swevo.2019.06.003
[2]. Albers, S., Bampis, E., Letsios, D., Lucarelli, G., & Stotz, R. (2017). Scheduling on power-heterogeneous processors. Information and Computation, 257, 22-33. https://doi.org/10.1016/j.ic.2017.09.013
[3]. Audsley, N. C., Burns, A., Richardson, M. F., & Wellings, A. J. (1994). STRESS: A simulator for hard real‐time systems. Software: Practice and Experience, 24(6), 543-564. https://doi.org/10.1002/spe.4380240603
[4]. Baek, H., Lee, J., & Shin, I. (2018). Multi-level contention-free policy for real-time multiprocessor scheduling. Journal of Systems and Software, 137, 36-49. https://doi.org/10.1016/j.jss.2017.11.027
[5]. Bhuiyan, A., Guo, Z., Saifullah, A., Guan, N., & Xiong, H. (2018). Energy-efficient real-time scheduling of DAG tasks. ACM Transactions on Embedded Computing Systems (TECS), 17(5), 1-25. https://doi.org/10.1145/3241049
[6]. Blumenthal, J., Hildebrandt, J., Golatowski, F., & Timmermann, D. (2003). YASA-A Framework for Validation, Test, and Analysis of Real-Time Scheduling Algorithms. In th Proceedings of 5 Real-Time Linux Workshop (pp. 197-204).
[7]. Bose, A., Biswas, T., & Kuila, P. (2019). A novel genetic algorithm based scheduling for multi-core systems. In Smart Innovations in Communication and Computational Sciences (pp. 45-54). Springer, Singapore. https://doi.org/ 10.1007/978-981-13-2414-7_5
[8]. Chandarli, Y., Fauberteau, F., Masson, D., Midonnet, S., & Qamhieh, M. (2012, July). Yartiss: A tool to visualize, test, compare and evaluate real-time scheduling rd algorithms. Proceedings of the 3 International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems, Pisa (Italy).
[9]. Chasapis, D., Moretó, M., Schulz, M., Rountree, B., Valero, M., & Casas, M. (2019, June). Power efficient job scheduling by predicting the impact of processor manufacturing variability. In Proceedings of the ACM International Conference on Supercomputing (pp. 296- 307). https://doi.org/10.1145/3330345.3330372
[10]. Chéramy, M., Hladik, P. E., & Déplanche, A. M. (2014, July). Simso: A simulation tool to evaluate real-time th multiprocessor scheduling algorithms. In 5 International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS) (pp. 1-6).
[11]. Courbin, P., & George, L. (2011). Fortas: Framework for real-time analysis and simulation. Proceedings of the nd 2 International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (pp. 21-26).
[12]. De Vroey, S., Goossens, J., & Hernalsteen, C. (1996, April). A generic simulator of real-time scheduling th algorithms. In Proceedings of the 29 Annual Simulation Symposium (pp. 242-249). IEEE. https://doi.org/10.1109/ SIMSYM.1996.492172
[13]. Diaz, A., Batista, R., & Castro, O. (2007, September). th Realtss: a real-time scheduling simulator. In 2007, 4 International Conference on Electrical and Electronics Engineering (pp. 165-168). IEEE. https://doi.org/10.11 09/ICEEE.2007.4344998
[14]. Díaz-Ramírez, A., Orduño, D. K., & Mejía-Alvarez, P. (2012, February). A multiprocessor real-time scheduling nd simulation tool. In CONIELECOMP 2012, 22 International Conference on Electrical Communications and Computers (pp. 157-161). IEEE. https://doi.org/10.1109/ CONIELECOMP.2012.6189901
[15]. Edun, A., Vazquez, R., Gordon-Ross, A., & Stitt, G. (2019, March). Dynamic scheduling on heterogeneous multicores. In 2019, Design, Automation & Test in Europe Conference & Exhibition (DATE) (pp. 1685-1690). IEEE. https://doi.org/10.23919/DATE.2019.8714804
[16]. Hangan, A., & Sebestyen, G. (2012, July). RTMultiSim: A versatile simulator for multiprocessor realrd time systems. In Proceedings of the 3 International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems, Pisa, Italy.
[17]. Harbour, M. G., García, J. G., Gutiérrez, J. P., & Moyano, J. D. (2001, June). Mast: Modeling and analysis th suite for real time applications. In Proceedings 13 Euromicro Conference on Real-Time Systems (pp. 125- 134). IEEE.
[18]. He, Q., Guan, N., & Guo, Z. (2019). Intra-task priority assignment in real-time scheduling of dag tasks on multicores. IEEE Transactions on Parallel and Distributed Systems, 30(10), 2283-2295. https://doi.org/10.1080/00 207543.2018.1497312
[19]. Jakovljevic, G., Rakamaric, Z., & Babic, D. (2002, June). Java simulator of real-time scheduling algorithms. th In ITI 2002 Proceedings of the 24 International Conference on Information Technology Interfaces (pp. 411-416). IEEE. https://doi.org/10.1109/ITI.2002.1024708
[20]. Ji, M., Zhang, W., Liao, L., Cheng, T. C. E., & Tan, Y. (2019). Multitasking parallel-machine scheduling with machine-dependent slack due-window assignment. International Journal of Production Research, 57(6), 1667-1684.
[21]. Jin, S., Schiavone, G., & Turgut, D. (2008). A performance study of multiprocessor task scheduling algorithms. The Journal of Supercomputing, 43(1), 77-97. https://doi.org/10.1007/s11227-007-0139-z
[22]. Juarez, F., Ejarque, J., & Badia, R. M. (2018). Dynamic energy-aware scheduling for parallel taskbased application in cloud computing. Future Generation Computer Systems, 78, 257-271. https://doi. org/10.1016/j.future.2016.06.029
[23]. Khalib, Z., Ahmad, B., & Bi, O. (2012, September). Performance analysis of a non-preemptive dynamic soft real time scheduler using discrete event simulator. In 2012 Fourth International Conference on Computational Intelligence, Modelling and Simulation (pp. 182-187). IEEE. https://doi.org/10.1109/CIMSim.2012.19
[24]. Leupers, R., Aguilar, M. A., Castrillon, J., & Sheng, W. (2019). Software compilation techniques for heterogeneous embedded multi-core systems. In Handbook of Signal Processing Systems (pp. 1021-1062). Springer, Cham. https://doi.org/10.1007/978-3-319-9173 4-4_28
[25]. Manacero, A., Miola, M. B., & Nabuco, V. A. (2001, October). Teaching real-time with a scheduler simulator. st In 31 Annual Frontiers in Education Conference (Vol. 2, pp. T4D15-T4D19. IEEE. https://doi.org/10.1109/FIE.2001.9 63651
[26]. Nikolic, B., Awan, M. A., & Petters, S. M. (2011, November). SPARTS: Simulator for power aware and realth time systems. In 2011, IEEE 10 International Conference on Trust, Security and Privacy in Computing and Communications (pp. 999-1004). IEEE. https://doi.org/ 10.1109/TrustCom.2011.137
[27]. Öztop, H., Tasgetiren, M. F., Eliiyi, D. T., & Pan, Q. K. (2018, August). Green permutation flowshop scheduling: A trade-off-between energy consumption and total flow time. In International Conference on Intelligent Computing (pp. 753-759). Springer, Cham. https://doi. org/10.1007/978-3-319-95957-3_79
[28]. Pillai, A. S., & Isha, T. B. (2013, December). ERTSim: An embedded real-time task simulator for scheduling. In 2013, IEEE International Conference on Computational Intelligence and Computing Research (pp. 1-4). IEEE. https://doi.org/10.1109/ICCIC.2013.6724195
[29]. Pillai, A. S., & Isha, T. B. (2014, March). Optimal task allocation and scheduling for power saving in multiprocessor systems. In 2014, Power and Energy Systems: Towards Sustainable Energy (pp. 1-5). IEEE. https://doi.org/10.1109/PESTSE.2014.6805324
[30]. Qin, Y., Zeng, G., Kurachi, R., Li, Y., Matsubara, Y., & Takada, H. (2019). Energy-efficient intra-task dvfs scheduling using linear programming formulation. IEEE Access, 7, 30536-30547. https://doi.org/10.1109/ACCESS .2019.2902353
[31]. Reddy, M. S., Ratnam, C., Rajyalakshmi, G., & Manupati, V. K. (2018). An effective hybrid multi objective evolutionary algorithm for solving real time event in flexible job shop scheduling problem. Measurement, 114, 78-90. https://doi.org/10.1016/j.measurement. 2017.09.022
[32]. Rivas Concepción, J. M., Gutiérrez García, J. J., & González Harbour, M. (2014). GEN4MAST: A tool for the evaluation of real-time techniques using a rd supercomputer. In Proceedings of 3 International Workshop on Real Time and Distributed Computing in Emerging Applications Co-located with 34th IEEE Real Time Systems Symposium (pp. 41-47).
[33]. Sahoo, R. M., & Padhy, S. K. (2019, August). Improved crow search optimization for multiprocessor task scheduling: A novel approach. In International Conference on Application of Robotics in Industry using Advanced Mechanisms (pp. 1-13). Springer, Cham. https://doi.org/10.1007/978-3-030-30271-9_1
[34]. Salimi, S., Mawlana, M., & Hammad, A. (2018). Performance analysis of simulation-based optimization of construction projects using high per formance computing. Automation in Construction, 87, 158-172. https://doi.org/10.1016/j.autcon.2017.12.003
[35]. Sensini, F., Buttazzo, G., & Ancilotti, P. (1997, June). Ghost: A tool for simulation and analysis of real-time scheduling algorithms. In Proceedings of the IEEE Real- Time Educational Workshop (pp. 42-49). https://doi.org/10. 1109/EMRTS.2001.934015
[36]. Shin, D., Kim, W., Jeon, J., Kim, J., & Min, S. L. (2002, February). SimDVS: An integrated simulation environment for performance evaluation of dynamic voltage scaling algorithms. In International Workshop on Power-Aware Computer Systems (pp. 141-156). Springer: Berlin, Heidelberg. https://doi.org/10.1007/3-540-36612-1_10
[37]. Short, M. (2017). Timing analysis for embedded systems using non-preemptive EDF scheduling under bounded error arrivals. Applied Computing and Informatics, 13(2), 130-139. https://doi.org/10.1016/j.acI. 2016.07.001
[38]. Singhoff, F., Legrand, J., Nana, L., & Marcé, L. (2004, November). Cheddar: A flexible real time scheduling framework. In Proceedings of the 2004 Annual ACM SIGAda International Conference on Ada: The engineering of correct and reliable software for real-time & distributed systems using Ada and related technologies (pp. 1-8). https://doi.org/10.1145/1032297.1032298
[39]. Sreenath, M., & Sukumar, P. (2013). Amalgamate scheduling of real-time tasks and effective utilization on multiprocessors with work-stealing. The International Journal of Engineering and Science (IJES), 2(1), 293-298.
[40]. Strohbach, M., Gellersen, H. W., Kortuem, G., & Kray, C. (2004, September). Cooperative artefacts: Assessing real world situations with embedded technology. In International Conference on Ubiquitous Computing (pp. 250-267). Springer: Berlin, Heidelberg. https://doi.org/10. 1007/978-3-540-30119-6_15
[41]. Sucha, P., Kutil, M., Sojka, M., & Hanzálek, Z. (2006, October). Torsche scheduling toolbox for matlab. In 2006, IEEE Conference on Computer Aided Control System Design, (pp. 1181-1186). IEEE. https://doi.org/101109/ CACSD-CCA-ISIC.2006.4776810
[42]. T'kindt, V., & Billaut, J. C. (2002). Introduction to scheduling. In Multicriteria Scheduling (pp. 5-27). Springer: Berlin, Heidelberg.
[43]. Rupanetti, D., & Salamy, H. (2019). Task allocation, migration and scheduling for energy-efficient real-time multiprocessor architectures. Journal of Systems Architecture, 98, 17-26. https://doi.org/10.1016/j.sysarc. 2019.06.003
[44]. Urunuela, R., Déplanche, A. M., & Trinquet, Y. (2010, September). Storm a simulation tool for real-time th multiprocessor scheduling evaluation. In 2010, IEEE 15 Conference on Emerging Technologies & Factory Automation (ETFA 2010) (pp. 1-8). IEEE. https://doi.org/10. 1109/ETFA.2010.5641179
[45]. Wang, Z., Ranka, S., & Mishra, P. (2012, January). Temperature-aware task partitioning for real-time th scheduling in embedded systems. In 2012, 25 International Conference on VLSI Design (pp. 161-166). IEEE. https://doi.org/10.1109/VLSID.2012.64
[46]. Xu, M., Phan, L. T. X., Choi, H. Y., & Lee, I. (2016, April). Analysis and implementation of global preemptive fixedpriority scheduling with dynamic cache allocation. In 2016, IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) (pp. 1-12). IEEE. https:// doi.org/10.1109/RTAS.2016.7461322
[47]. Yun, Y., Hwang, E. J., & Kim, Y. H. (2019). Adaptive genetic algorithm for energy-efficient task scheduling on asymmetric multiprocessor system-on-chip. Microprocessors and Microsystems, 66, 19-30. https:// doi.org/10.1016/j.micpro.2019.01.011
[48]. Zhang, Y. W. (2019). Energy-aware mixed partitioning scheduling in standby-sparing systems. Computer Standards & Interfaces, 61, 129-136. https://doi.org/10. 1016/j.csi.2018.06.004
[49]. Zhou, J., Yan, J., Cao, K., Tan, Y., Wei, T., Chen, M., Zhang., G., Chen, X., & Hu, S. (2018). Thermal-aware correlated two-level scheduling of real-time tasks with reduced processor energy on heterogeneous MPSoCs. Journal of Systems Architecture, 82, 1-11. https://doi.org/ 10.1016/j.sysarc.2017.09.007
If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Single Article

North Americas,UK,
Middle East,Europe
India Rest of world
USD EUR INR USD-ROW
Pdf 35 35 200 20
Online 35 35 200 15
Pdf & Online 35 35 400 25

Options for accessing this content:
  • If you would like institutional access to this content, please recommend the title to your librarian.
    Library Recommendation Form
  • If you already have i-manager's user account: Login above and proceed to purchase the article.
  • New Users: Please register, then proceed to purchase the article.