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


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


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.


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.

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.

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.

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

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

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

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

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

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

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.

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

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

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

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

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

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.

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

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

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

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.

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

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.

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.

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.

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

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

[Online]. Available: https://pop-coe.eu/node/69, Accesed on 26 february 2018



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.