This thesis investigates whether the Marriage in Honey Bees Optimization (MBO) heuristic, applied to the graph coloring problem, can be sped up by leveraging GPU-acceleration. Three versions of MBO were implemented; one baseline sequential version, one simple parallelized version where the MBO egg-raising process was parallelized using CUDA, and one where the worker heuristics were further adapted to better utilize hardware resources. As workers, naive implementations of the tabu coloring and partial coloring heuristics were used. The simple parallelized version achieved speedups of 2.7-6.1 times over the sequential version, whereas the further adapted version reached speedups of 26.3-109.0 times. Although the naive worker implementations hampered the execution times in absolute terms, the relative speedup of the further adapted version showed that future work on CUDA-based MBO should consider choosing worker heuristics that are themselves parallelizable.

Denna uppsats undersöker huruvida Marriage in Honey Bees (MBO) heuristiken, applicerad på graffärgningsproblemet, kan snabbas upp genom användning av GPU-acceleration. Tre versioner av MBO implementerades; en sekventiell version som bas, en simpel parallelliserad version där MBO:s äggutvecklingsstadium parallelliserades med hjälp av CUDA, och en version där arbetarheuristikerna dessutom anpassades för att bättre utnyttja grafikkortets hårdvaruresurser. Som arbetare användes naiva implementationer av tabu coloring och partial coloring heuristikerna. Den simpla parallelliserade versionen uppmättes vara 2.7-6.1 gånger snabbare än den sekventiella versionen. Versionen med anpassade arbetare var 26.3-109.0 gånger snabbare. Fastän de naiva arbetarimplementationerna gjorde de absoluta exekveringstiderna långsamma, så visade den relativa förbättringen på att framtida arbete med CUDA-baserad MBO bör välja heuristiker som i sig har parallelliseringspotential.