Abstract
Extremal Optimization is a nature-inspired optimization method which features small computational and memory complexity. Due to these features it can be efficiently used as an engine for processor load balancing. The paper presents how improved Extremal Optimization algorithms can be applied to processor load balancing. Extremal Optimization detects the best strategy of tasks migration leading to balanced application execution and reduction in execution time. The proposed algorithm improvements cover several aspects. One is algorithms parallelization in a multithreaded environment. The second one is adding some problem knowledge to improve the convergence of the algorithms. The third aspect is the enrichment of the parallel algorithms by inclusion of some elements of genetic algorithms – namely the crossover operation. The load balancing based on improved Extremal Optimization aim at better convergence of the algorithm, smaller number of task migrations to be done and reduced execution time of applications. The quality of the proposed algorithms is assessed by experiments with simulated parallelized load balancing of distributed program graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Barker, K., Chrisochoides, N.: An evaluation of a framework for the dynamic load balancing of highly adaptive and irregular parallel applications. In: Proceedings of the ACM/IEEE Conference on Supercomputing. ACM Press, Phoenix (2003)
Boettcher, S., Percus, A.G.: Extremal optimization: methods derived from coevolution. In: Proceedings of the Genetic and Evolutionary Computation Conference(GECCO 1999), pp. 825–832. Morgan Kaufmann, San Francisco (1999)
De Falco, I., Laskowski, E., Olejnik, R., Scafuri, U., Tarantino, E., Tudruj, M.: Load balancing in distributed applications based on extremal optimization. In: Esparcia-Alcázar, A.I. (ed.) EvoApplications 2013. LNCS, vol. 7835, pp. 52–61. Springer, Heidelberg (2013)
De Falco, I., Laskowski, E., Olejnik, R., Scafuri, U., Tarantino, E., Tudruj, M.: Improving extremal optimization in loadbalancing by local search. In: Esparcia-Alcázar, A.I., Mora, A.M. (eds.) EvoApplications 2014. LNCS, vol. 8602, pp. 51–62. Springer, Heidelberg (2014)
De Falco, I., Laskowski, E., Olejnik, R., Scafuri, U., Tarantino, E., Tudruj, M.: Extremal optimization applied to load balancing in execution of distributed programs. Appl. Soft Comput. 30(5), 501–513 (2015)
Khan, R.Z., Ali, J.: Classification of task partitioning and load balancing strategies in distributed parallel computing systems. Int. J. Comput. Appl. 60(17), 48–53 (2012)
Mishra, M., Agarwal, S., Mishra, P., Singh, S.: Comparative analysis of various evolutionary techniques of load balancing: a review. Int. J. Comput. Appl. 63(15), 8–13 (2013)
Randall, M., Lewis, A.: An extended extremal optimisation model for parallel architectures. In: 2nd IEEE International Conference on e-Science and Grid Computing, e-Science 2006, p. 114 (2006)
Sneppen, K., et al.: Evolution as a self-organized critical phenomenon. Proc. Natl. Acad. Sci. 92, 5209–5213 (1995)
Tamura, K., Kitakami, H., Nakada, A.: Reducing crossovers in reconciliation graphs with extremal optimization (in japanese). Trans. Inf. Process. Soc. Jpn. 49(4) (TOM 20), 105–116 (2008)
Tamura, K., Kitakami, H., Nakada, A.: Island-model-based distributed modified extremal optimization for reducing crossovers in reconciliation graph. Transactions on Engineering Technologies. LNCS, vol. 275. Springer, New York (2013)
Tamura, K., Kitakami, H., Nakada, A.: Distributed modified extremal optimization using island model for reducing crossovers in reconciliation graph. Eng. Lett. 21(2), EL\(\_\)21\(\_\)2\(\_\)05, 81–88 (2013)
Zeigler, B.: Hierarchical, modular discrete-event modelling in an object-oriented environment. Simulation 49(5), 219–230 (1987)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Laskowski, E., Tudruj, M., De Falco, I., Scafuri, U., Tarantino, E., Olejnik, R. (2016). Parallel Extremal Optimization with Guided Search and Crossover Applied to Load Balancing. In: Wyrzykowski, R., Deelman, E., Dongarra, J., Karczewski, K., Kitowski, J., Wiatr, K. (eds) Parallel Processing and Applied Mathematics. PPAM 2015. Lecture Notes in Computer Science(), vol 9573. Springer, Cham. https://doi.org/10.1007/978-3-319-32149-3_41
Download citation
DOI: https://doi.org/10.1007/978-3-319-32149-3_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-32148-6
Online ISBN: 978-3-319-32149-3
eBook Packages: Computer ScienceComputer Science (R0)