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

Ion Dan Mironescu, Lucian Vinţan

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.

Keywords


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

Full Text:

PDF

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




DOI: https://doi.org/10.15837/ijccc.2018.4.3308



Copyright (c) 2018 Ion Dan Mironescu, Lucian Vinţan

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]


INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2016: IF=1.374. .

IJCCC is indexed in Scopus from 2008 (CiteScore 2017 = 1.04; SNIP2017 = 0.616, SJR2017 =0.326):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.

 

 Impact Factor in JCR2017 (Clarivate Analytics/SCI Expanded/ISI Web of Science): IF=1.29 (Q3). Scopus: CiteScore2017=1.04 (Q2); Editors-in-Chief: Ioan DZITAC & Florin Gheorghe FILIP.