A Simulation Based Analysis of an Multi Objective Diffusive Load Balancing Algorithm
Keywords:
Petri Net simulation, High Performance Computing, load balancing, diffusive algorithm, multi-objective optimisationAbstract
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
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
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
