Top

Cluster Computing

Published in:

01-03-2016

Dynamic load balancing on heterogeneous clusters for parallel ant colony optimization

Authors: Antonio Llanes, José M. Cecilia, Antonia Sánchez, José M. García, Martyn Amos, Manuel Ujaldón

Published in: Cluster Computing | Issue 1/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Ant colony optimisation (ACO) is a nature-inspired, population-based metaheuristic that has been used to solve a wide variety of computationally hard problems. In order to take full advantage of the inherently stochastic and distributed nature of the method, we describe a parallelization strategy that leverages these features on heterogeneous and large-scale, massively-parallel hardware systems. Our approach balances workload effectively, by dynamically assigning jobs to heterogeneous resources which then run ACO implementations using different search strategies. Our experimental results confirm that we can obtain significant improvements in terms of both solution quality and energy expenditure, thus opening up new possibilities for the development of metaheuristic-based solutions to “real world” problems on high-performance, energy-efficient contemporary heterogeneous computing platforms.

next article A decentralized fault tolerance model based on level of performance for grid environment

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Alba, E., Luque, G., Nesmachnow, S.: Parallel metaheuristics: recent advances and new trends. Int. Trans. Oper. Res. 20(1), 1–48 (2013). doi:10.1111/j.1475-3995.2012.00862.x CrossRefMATH

Carretero, J., Garcia-Blas, J., Singh, D.E., Isaila, F., Fahringer, T., Prodan, R., Bosilca, G., Lastovetsky, A., Symeonidou, C., Perez-Sanchez, H., et al.: Optimizations to enhance sustainability of mpi applications. In: Proceedings of the 21st European MPI Users’ Group Meeting, p. 145. ACM (2014)

Cecilia, J.M., Garcia, J.M., Ujaldon, M., Nisbet, A., Amos, M.: Parallelization strategies for ant colony optimisation on GPUs. In: Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing, pp. 339–346. IEEE (2011)

Cecilia, J.M., Garcia, J.M., Nisbet, A., Amos, M., Ujaldón, M.: Enhancing data parallelism for ant colony optimization on GPUs. J. Parallel Distrib. Comput. 73(1), 42–51 (2013)CrossRef

Cecilia, J.M., Nisbet, A., Amos, M., Garcia, J.M., Ujaldón, M.: Enhancing GPU parallelism in nature-inspired algorithms. J. Supercomput. 63(3), 773–789 (2013)CrossRef

Chang, R.S.S., Chang, J.S.S., Lin, P.S.S.: An ant algorithm for balanced job scheduling in grids. Future Gener. Comput. Syst. 25(1), 20–27 (2009). doi:10.1016/j.future.2008.06.004 CrossRef

Chen, Y., Miao, D., Wang, R.: A rough set approach to feature selection based on ant colony optimization. Pattern Recognit. Lett. 31(3), 226–233 (2010). doi:10.1016/j.patrec.2009.10.013 CrossRef

De Michell, G., Gupta, R.K.: Hardware/software co-design. Proc. IEEE 85(3), 349–365 (1997)CrossRef

Delévacq, A., Delisle, P., Gravel, M., Krajecki, M.: Parallel ant colony optimization on graphics processing units. J. Parallel Distrib. Comput. 73, 52–61 (2013). doi:10.1016/j.jpdc.2012.01.003 CrossRef

10.

Dorigo, M., Di Caro, G.: Ant colony optimization: a new meta-heuristic. In: Proceedings of the 1999 Congress on Evolutionary Computation (CEC’99), pp. 1470–1477. IEEE Press (1999)

11.

Dorigo, M.: Optimization, learning and natural algorithms. Ph.D. thesis, Politecnico di Milano, Italy (1992)

12.

Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybernet. B 26(1), 29–41 (1996)CrossRef

13.

Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybernet. B 26, 29–41 (1996)CrossRef

14.

Dorigo, M., Birattari, M., Stutzle, T.: Ant colony optimization. IEEE Comput. Intell. Mag. 1(4), 28–39 (2006)CrossRef

15.

Dorigo, M., Stutzle, T.: Ant Colony Optimization. Bradford Company, Scituate (2004)CrossRefMATH

16.

Dorigo, M., Stützle, T.: Ant colony optimization: overview and recent advances. Handbook of Metaheuristics, pp. 227–263. Springer, Berlin (2010)CrossRef

17.

Garcia, M.P., Montiel, O., Castillo, O., Sepúlveda, R., Melin, P.: Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation. Appl. Soft Comput. 9(3), 1102–1110 (2009). doi:10.1016/j.asoc.2009.02.014 CrossRef

18.

Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional, New York (1989)MATH

19.

Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning, 1st edn. Addison-Wesley Longman Publishing Co. Inc, Boston (1989)MATH

20.

González, R., Horowitz, M.: Energy dissipation in general purpose microprocessors. IEEE J. Solid-State Circuits 31(9), 1277–1284 (1996)CrossRef

21.

Johnson, D.S., Mcgeoch, L.A.: The Traveling Salesman Problem: A Case Study in Local Optimization. Wiley, New York (1997)MATH

22.

Ke, B.R., Chen, M.C., Lin, C.L.: Block-layout design using max-min ant system for saving energy on mass rapid transit systems. IEEE Trans. Intell. Transp. Syst. 10(2), 226–235 (2009). doi:10.1109/TITS.2009.2018324 CrossRef

23.

Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948. IEEE (1995)

24.

Komarudin, Wong, K.Y.: Applying ant system for solving unequal area facility layout problems. Eur. J. Oper. Res. 202(3), 730–746 (2010). doi:10.1016/j.ejor.2009.06.016 CrossRefMATH

25.

Krueger, J., Donofrio, D., Shalf, J., Mohiyuddin, M., Williams, S., Oliker, L., Pfreund, F.J.: Hardware/software co-design for energy-efficient seismic modeling. In: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, p. 73. ACM (2011)

26.

Lawler, E., Lenstra, J., Kan, A., Shmoys, D.: The Traveling Salesman Problem. Wiley, New York (1987)MATH

27.

Manfrin, M., Manfrin, M., Stützle, T., Dorigo, M.: Parallel ant colony optimization for the traveling salesman problem. Ant Colony Optimization and Swarm Intelligence, pp. 224–234. Springer, Berlin (2006)CrossRef

28.

Martin, A.: Towards an energy complexity of computations. Inf. Process. Lett. 77, 181–187 (2001)CrossRefMATH

29.

Nickolls, J., Buck, I., Garland, M., Skadron, K.: Scalable parallel programming with cuda. Queue 6(2), 40–53 (2008)CrossRef

30.

Nvidia Corporation. NVML API Reference ([last accesed 15 November 2014]). http://developer.download.Nvidia.com/assets/cuda/files/CUDADownloads/NVML/nvml.pdf

31.

NVIDIA: NVIDIA CUDA C Programming Guide 6.5 (2014)

32.

Parallel forall blog. Nvidia CUDA Zone. http://devblogs.nvidia.com/parallelforall/increase-performance-gpu-boost-k80-autoboost/ [11 March 2015]

33.

Pedemonte, M., Nesmachnow, S., Cancela, H.: A survey on parallel ant colony optimization. Appl. Soft Comput. 11(8), 5181–5197 (2011). doi:10.1016/j.asoc.2011.05.042 CrossRef

34.

Pénzes, P., Martin, A.: Energy-delay efficiency of vlsi computations. In: Proceedings of the ACM Great Lakes Symposium on VLSI (GLSVLSI). IEEE (2002)

35.

Rahman, R.: Xeon phi system software. Intel \({\textregistered }\) Xeon Phi Coprocessor Architecture and Tools, pp. 97–112. Springer, Berlin (2013)CrossRef

36.

Reinelt, G.: TSPLIB—a traveling salesman problem library. ORSA J. Comput. 3(4), 376–384 (1991)MathSciNetCrossRefMATH

37.

Rozenberg, G., Bäck, T., Kok, J.N.: Handbook of Natural Computing. Springer, Berlin (2011)MATH

38.

Shalf, J., Quinlan, D., Janssen, C.: Rethinking hardware-software codesign for exascale systems. Computer 44(11), 22–30 (2011)CrossRef

39.

Stützle, T.: Parallelization strategies for ant colony optimization. In: PPSN V: Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, pp. 722–731. Springer, London (1998)

40.

Stützle, T.: Parallelization strategies for ant colony optimization. Parallel Problem Solving from Nature (PPSN V), pp. 722–731. Springer, Berlin (1998)CrossRef

41.

Stutzle, T., Hoos, H.H.: MAX-MIN ant system. Future Gener. Comput. Syst. 16(8), 889–914 (2000)CrossRefMATH

42.

Top 500 supercomputer site ([last accesed 15 November 2014]). http://www.top500.org/

43.

TSPLIB Webpage (2011). http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

44.

Wolf, W.: A decade of hardware/software codesign. Computer 36(4), 38–43 (2003)CrossRef

45.

Yu, B., Yang, Z.Z., Yao, B.: An improved ant colony optimization for vehicle routing problem. Eur. J. Oper. Res. 196(1), 171–176 (2009). doi:10.1016/j.ejor.2008.02.028 CrossRefMATH

46.

Zhu, W., Curry, J.: Parallel ant colony for nonlinear function optimization with graphics hardware acceleration. In: IEEE International Conference on Systems, Man and Cybernetics, SMC, pp. 1803–1808. IEEE (2009)

Title: Dynamic load balancing on heterogeneous clusters for parallel ant colony optimization
Authors: Antonio Llanes
José M. Cecilia
Antonia Sánchez
José M. García
Martyn Amos
Manuel Ujaldón
Publication date: 01-03-2016
Publisher: Springer US
Published in: Cluster Computing / Issue 1/2016
Print ISSN: 1386-7857
Electronic ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-016-0534-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2016

Consistency maintenance of Do and Undo/Redo operations in real-time collaborative bitmap editing systems

Effects of patent indicators on national technological level: concentrated on mobile communication, network, and convergence technologies

A knee-based multi-objective evolutionary algorithm: an extension to network system optimization design problem

Continuous and transparent multimodal authentication: reviewing the state of the art

An energy-efficient load balancing scheme to extend lifetime in wireless sensor networks

Frequent pagesets from web log by enhanced weighted association rule mining

Premium Partner