A Simulation Based Analysis of an Multi Objective Diffusive Load Balancing Algorithm

  • Ion Dan Mironescu "Lucian Blaga" University of Sibiu
  • Lucian Vinţan "Lucian Blaga" University of Sibiu

Abstract

In this paper, we presented a further development of our research on developing an optimal software-hardware mapping framework. We used the Petri Net model of the complete hardware and software High Performance Computing (HPC) system running a Computational Fluid Dynamics (CFD) application, to simulate the behaviour of the proposed diffusive two level multi-objective load-balancing algorithm. We developed an meta-heuristic algorithm for generating an approximation of the Pareto-optimal set to be used as reference. The simulations showed the advantages of this algorithm over other diffusive algorithms: reduced computational and communication overhead and robustness due to low dependence on uncertain data. The algorithm also had the capacity to handle unpredictable events as a load increase due to domain refinement or loss of a computation resource due to malfunction.

References

[1] Augonnet, C.; Samuel, T.; Namyst, R.; Wacrenier, P.-A. (2011); StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures, Concurrency and Computation: Practice and Experience, Special Issue: Euro-Par 2009, 23, 187-198, 2011.

[2] Blätke, M.A.; Heiner, M.; Marwan, W. (2015); Engineering with Petri Nets, In R. Robeva (Ed.), Algebraic and Discrete Mathematical Methods for Modern Biology, Elsevier Inc., 141– 193, 2015.

[3] Brahambhatt, M.; Panchal, D. (2015); Comparative Analysis on Heuristic Based Load Balancing Algorithms in Grid Environment, International Journal of Engineering Research & Technology (IJERT), 4(4), 802–806, 2015.

[4] Calore, E.; Gabbana, A.; Schifano, F.S.; Tripiccione, R. (2017); Evaluation of DVFS techniques on modern HPC processors and accelerators for energy-aware applications, Concurrency and Computation: Practice and Experience, DOI:
https://doi.org/10.1002/cpe.4143, 29(12), 1–19, 2017.
https://doi.org/10.1002/cpe.4143

[5] Casanova, H.; Giersch, A.; Legrand, A.; Quinson, M.; Suter, F. (2014); Versatile, Scalable and Accurate Simulation of Distributed Applications and Platforms, Journal of Parallel and Distributed Computing, DOI:
https://doi.org/10.1016/j.jpdc.2014.06.008, 74(10), 2899– 2917, 2014.
https://doi.org/10.1016/j.jpdc.2014.06.008

[6] Chatterjee, N.; Paul, S.; Mukherjee, P.; Chattopadhyay, S.(2017); Deadline and energy aware dynamic task mapping and scheduling for Network-on-Chip based multi-core platform, Journal of Systems Architecture, DOI:
https://doi.org/10.1016/j.sysarc.2017.01.008, 74, 61– 77, 2017.
https://doi.org/10.1016/j.sysarc.2017.01.008

[7] Chen, B.; Potts, C.N.; Woeginger, G.J. (1998); A Review of Machine Scheduling: Complexity, Algorithms and Approximability, In D.Z. Du, P.M. Pardalos (Eds.), Handbook of Combinatorial Optimization, Springer, 21–129, 1998.
https://doi.org/10.1007/978-1-4613-0303-9_25

[8] Guo, Z.; Shu, C.(2013); Lattice Boltzmann Method and Its Applications in Engineering Advances in computational fluid dynamics Volume:3, World Scientific, 2013.

[9] Heiner, M.; Herajy, M.; Liu, F.; Rohr, C.; Schwarick, M.(2012); Snoopy - a unifying Petri net tool, In S. Haddad, L. Pomello, (Eds.) Application and Theory of Petri Nets, Springer, 7347, 398–407, 2012.
https://doi.org/10.1007/978-3-642-31131-4_22

[10] Hugo, A. E.; Guermouche, A.; Wacrenier, P.A.; Namyst, R. (2013); Composing Multiple StarPU Applications over Heterogeneous Machines: A Supervised Approach, In 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, 1050–1059, 2013.

[11] Jahr, R.; Calborean, H.; Vintan, L.; Ungerer, T. (2012); Finding Near-Perfect Parameters for Hardware and Code Optimizations with Automatic Multi-Objective Design Space Explorations, In Concurrency and Computation: Practice and Experience, DOI: 10.1002/cpe.2975, 27(9), 2196–2214, 2012.
https://doi.org/10.1002/cpe.2975

[12] Jeannot, E.; Vernier, F., (2006); A Practical Approach of Diffusion Load Balancing Algorithms, INRIA, RR5875, 2006.

[13] Juarez, F.; Ejarque, J.; Badia, R.M. (2018); Dynamic energy-aware scheduling for parallel task-based application in cloud computing, Future Generation Computer Systems, 78, 257– 271, 2018.
https://doi.org/10.1016/j.future.2016.06.029

[14] Kale, L.V.; Bhatele, A.; (2013); Parallel Science and Engineering Applications: The Charm++ Approach (1st ed.), CRC Press, 2013

[15] Kasmi, N.; Zbakh, M.; Samadi, Y.; Cherkaoui, R.; Haouari, A. (2017) Performance evaluation of StarPU schedulers with preconditioned conjugate gradient solver on heterogeneous (multi-CPUs/multi-GPUs) architecture, In 3rd International Conference of Cloud Computing Technologies and Applications (CloudTech), 1–6, 2017.
https://doi.org/10.1109/CloudTech.2017.8284742

[16] Kaur, N.; Chhabra, A. (2017); Comparative Analysis of Job Scheduling Algorithms in Parallel and Distributed Computing Environments, International Journal of Advanced Research in Computer Science, 8(3), 948–956, 2017.

[17] Khan, S.; Nazir, B.; Khan, I. A.; Shamshirband, S.; Chronopoulos, A. T. (2017); Load balancing in grid computing: Taxonomy, trends and opportunities, Journal of Network and Computer Applications, 88, 99–111, 2017.
https://doi.org/10.1016/j.jnca.2017.02.013

[18] Kjolstad, F.B.; Snir, M.(2010); Ghost Cell Pattern, In Proceedings of the 2010 Workshop on Parallel Programming Patterns (ParaPLoP'10), DOI=http://dx.doi.org/10.1145/1953611.1953615, 4, 2010.
https://doi.org/10.1145/1953611.1953615

[19] Martinez, D. R.; Cabaleiro, J.C.;Pena, T.F.; Rivera, F.F.; Blanco,V. (2009); Accurate analytical performance model of communications in MPI applications, In 2009 IEEE International Symposium on Parallel & Distributed Processing, DOI:
https://doi.org/10.1109/IPDPS.2009.5161175, 1–8. 2009.
https://doi.org/10.1109/IPDPS.2009.5161175

[20] Mironescu, I.D.; Vintan, L. (2017); A task scheduling algorithm for HPC applications using colored stochastic Petri Net models, In Proceedings of 13th International Conference on Intelligent Computer Communication and Processing, 479–486, 2017.

[21] Rauber, T.; Rünger, G.; Schwind, M.; Xu, H.; Melzner, S. (2014); Energy measurement, modeling, and prediction for processors with frequency scaling, The Journal of Supercomputing, 70, 1451–1476, 2014.
https://doi.org/10.1007/s11227-014-1236-4

[22] Ubal, R.; Byunghyun, J., Mistry, P.; Schaa, D.; Kaeli, D., (2012); Multi2Sim: a simulation framework for CPU-GPU computing, In Proceedings of the 21st international conference on Parallel architectures and compilation techniques (PACT '12), ACM, 335–344, 2012.

[23] van Werkhoven, B.V.; Maassen, J.; Seinstra, F.J.; Bal, H.E. (2014); Performance Models for CPU-GPU Data Transfers, In 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, 11–20, 2014.

[24] Wu,J.; Contract Net Protocol for Coordination in Multi-Agent System, In 2008 Second International Symposium on Intelligent Information Technology Application, doi: 10.1109/IITA. 2008.273, 1052-1058, 2008.

[25] [Online]. Available: http://www.fe.infn.it/coka/doku.php?id=start, Accesed on 26 february 2018

[26] [Online]. Available: https://pcisig.com/specifications/pciexpress/base2/, Accesed on 26 february 2018

[27] [Online]. Available: https://pop-coe.eu/node/69, Accesed on 26 february 2018
Published
2018-07-25
How to Cite
MIRONESCU, Ion Dan; VINŢAN, Lucian. A Simulation Based Analysis of an Multi Objective Diffusive Load Balancing Algorithm. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 13, n. 4, p. 503-520, july 2018. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/3308>. Date accessed: 27 sep. 2020. doi: https://doi.org/10.15837/ijccc.2018.4.3308.

Keywords

Petri Net simulation, High Performance Computing, load balancing, diffusive algorithm, multi-objective optimisation