Parallel Extremal Optimization with Guided State Changes Applied to Load Balancing

详细信息    查看全文

• 作者：Ivanoe De Falco (15)
  Eryk Laskowski (16)
  Richard Olejnik (17)
  Umberto Scafuri (15)
  Ernesto Tarantino (15)
  Marek Tudruj (16) (18)
  
  15. Institute of High Performance Computing and Networking ; CNR ; Naples ; Italy
  16. Institute of Computer Science ; Polish Academy of Sciences ; Warsaw ; Poland
  17. Computer Science Laboratory ; University of Science and Technology of Lille ; Villeneuve-d鈥橝scq ; France
  18. Polish-Japanese Institute of Information Technology ; Warsaw ; Poland
  
• 关键词：Distributed program design ; Extremal optimization ; Load balancing ; Parallel computing
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9028
• 期：1
• 页码：79-90
• 全文大小：588 KB
• 参考文献：1. Khan, RZ, Ali, J (2012) Classification of task partitioning and load balancing strategies in distributed parallel computing systems. Int. J. Comput. Appl. 60: pp. 48-53
  2. Mishra, M, Agarwal, S, Mishra, P, Singh, S (2013) Comparative analysis of various evolutionary techniques of load balancing: a review. Int. J. Comput. Appl. 63: pp. 8-13
  3. Boettcher, S., Percus, A.G.: Extremal optimization: methods derived from coevolution. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), pp. 825鈥?32. Morgan Kaufmann, San Francisco (1999)
  4. Sneppen, K (1995) Evolution as a self-organized critical phenomenon. Proc. Natl. Acad. Sci. 92: pp. 5209-5213 dx.doi.org/10.1073/pnas.92.11.5209" target="_blank" title="It opens in new window">CrossRef
  5. Falco, I, Laskowski, E, Olejnik, R, Scafuri, U, Tarantino, E, Tudruj, M Load balancing in distributed applications based on extremal optimization. In: ditors">Esparcia-Alc谩zar, AI eds. (2013) Applications of Evolutionary Computation. Springer, Heidelberg, pp. 52-61 dx.doi.org/10.1007/978-3-642-37192-9_6" target="_blank" title="It opens in new window">CrossRef
  6. Falco, I, Laskowski, E, Olejnik, R, Scafuri, U, Tarantino, E, Tudruj, M Improving extremal optimization in load聽balancing by local search. In: ditors">Esparcia-Alc谩zar, AI, Mora, AM eds. (2014) Applications of Evolutionary Computation. Springer, Heidelberg, pp. 51-62 dx.doi.org/10.1007/978-3-662-45523-4_5" target="_blank" title="It opens in new window">CrossRef
  7. Zeigler, B (1987) Hierarchical, modular discrete-event modelling in an object-oriented environment. Simulation 49: pp. 219-230 dx.doi.org/10.1177/003754978704900506" target="_blank" title="It opens in new window">CrossRef
  8. 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)
  9. Tamura, K, Kitakami, H, Nakada, A (2008) Reducing crossovers in reconciliation graphs with extremal optimization (in japanese). Trans. Inf. Process. Soc. Japan 49: pp. 105-116
  10. Tamura, K., Kitakami, H., Nakada, A.: Distributed extremal optimization using island model for reducing crossovers in reconciliation graph. In: Proceedings of the International MultiConference of Engineers and Computer Scientists 2013, Hong-Kong, March 2013, pp. 1鈥? (2013)
  11. 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 (2013)
  
• 作者单位：Applications of Evolutionary Computation
• 丛书名：978-3-319-16548-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

The paper concerns parallel methods for Extremal Optimization (EO) applied for processor load balancing for distributed programs. In these methods the EO approach is used which is parallelized and extended by a guided search of next solution state. EO detects the best strategy of tasks migration leading to a reduction in program execution time. We assume a parallel improvement of the EO algorithm with guided state changes which provides a parallel search for a solution based on two step stochastic selection during the solution improvement based on two fitness functions. The load balancing improvements based on EO aim at better convergence of the algorithm and better quality of program execution in terms of the execution time. The proposed load balancing algorithm is evaluated by experiments with simulated parallelized load balancing of distributed program graphs.