Parallelization of corner sort with CUDA for many-objective optimization

Abstract

Due to advancements in hardware capabilities and computation power, multi-objective optimization has recently been used in many industrial problems. These problems usually have multiple objectives of conflicting nature. To solve such problems, Multi-objective Evolutionary Algorithms (MOEAs) utilize Non-dominated Sorting (NDS) algorithms to rank the viability of the solutions efficiently. Researchers have focused on improving the time complexity of NDS algorithms for a long time due to their wide range of applications. With the increase in the use of GPUs for general-purpose scientific computing, it is now becoming possible to reduce the computation cost of such algorithms. In this paper, we have analyzed one such NDS algorithm, Corner Sort, and highlighted two areas within it with a high scope of parallelism. We propose a highly efficient, parallelized version of Corner Sort, implemented using CUDA framework. Utilizing the thousands of cores in a GPU, our algorithm is able to break the solution set into smaller chunks and simultaneously process them. Furthermore, the comparison between two solutions across all the objectives is done parallelly as well. On benchmark datasets, our algorithm performs up to 10x faster than the serial algorithm, and its performance improves for larger datasets, irrespective of the number of objectives. © 2022 ACM.