A Parallel Strategy for a Genetic Algorithm in Routing Wavelength Assignment Problem Using GPU with CUDA

• Esdras La-Roque Universidade Federal do Pará
• Cassio Batista Universidade Federal do Pará
• Josivaldo Araújo Universidade Federal do Para

DOI: https://doi.org/10.5753/eniac.2020.12175

Resumo

This paper presents a parallel strategy with a heuristic approach to reduce the execution time bottleneck of a routing and wavelength assignment problem in wavelength-division multiplexing networks of a previous work that uses a sequential genetic algorithm. As the parallelization solution, the GPU hardware processing on CUDA architecture and CUDA C programming language were adopted. The results achieved were between 35 and 40 times faster than the sequential version of the genetic algorithm.

Palavras-chave: genetic algorithm, rwa problem, cuda, parallelization, wdm networks

Referências

Cantú-Paz, E. (1998). A survey of parallel genetic algorithms. CALCULATEURS PAALLELES, 10.

Cardoso, A. J. F., Costa, J. C. W. A., and Francês, C. R. L. (2010). A new proposal of an efficient algorithm for routing and wavelength assignment in optical networks. Journal of Communication and Information Systems, 25(1):11–18.

Chatterjee, B. C., Sarma, N., and Oki, E. (2015). Routing and spectrum allocation in elastic optical networks: A tutorial. IEEE Communications Surveys Tutorials, 17(3):1776– 1800.

Cheng, J., Grossman, M., and McKercher, T. (2014). Professional CUDA C Programming. John Wiley & Sons, Inc.

Corporation, N. (2019). Cuda c programming guide.

Ellinas, G., Labourdette, J. F., Walker, J. A., Chaudhuri, S., Lin, L., Goldstein, E., and Bala, K. (2004). Network control and management challenges in opaque networks utilizing transparent optical switches. IEEE Communications Magazine, 42(2):S16– S24.

Frazer, K., Inc., M. N., and (U.S.), N. S. F. (1996). NSFNET: A Partnership for Highspeed Networking : Final Report, 1987-1995. Merit Network.

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

Kirk, D. B. and mei W. Hwu, W. (2010). Progamming Massively Parallel Processors. Elsevier.

Lim, S. M., Sultan, A. B. M., Sulaiman, M. N., Mustapha, A., and Leong, K. (2017). Crossover and mutation operators of genetic algorithms. International Journal of Machine Learning and Computing, 7(1):9–12.

Randhawa, R. and Sohal, J. S. (2010). Static and dynamic routing and wavelength assignment algorithms for future transport networks. Optik - International Journal for Light and Electron Optics, 121(8):702 – 710.

Sanders, J. and Kandrot, E. (2011). CUDA by Example: An Introduction to GeneralPurpose GPU Programming. Addison-Wesley.

Silva, E. and Gabriel, P. (2019). Genetic algorithms and multiprocessor task scheduling: A systematic literature review. In Anais do XVI Encontro Nacional de Inteligência Artificial e Computacional, pages 250–261, Porto Alegre, RS, Brasil. SBC.

Teixeira, D. B. A., Batista, C. T., Cardoso, A. J. F., and Araújo, J. d. S. (2017). A genetic algorithm approach for static routing and wavelength assignment in all-optical wdm networks. In Oliveira, E., Gama, J., Vale, Z., and Lopes Cardoso, H., editors, Progress in Artificial Intelligence, pages 421–432, Cham. Springer International Publishing.

Varela, G. N. and Sinclair, M. C. (1999). Ant colony optimisation for virtual-wavelengthpath routing and wavelength allocation. In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), volume 3, pages 1809–1816.

Wason, A. and Kaler, R. S. (2007). Wavelength assignment problem in optical wdm networks. In IJCSNS International Journal of Computer Science and Network Security.

Zang, H. and Jue, J. P. (2000). A review of routing and wavelength assignment approaches for wavelength-routed optical wdm networks. Optical Networks Magazine, 1:47–60.