Researchers from the Catalan Telecommunications Technology Centre in Spain credit ArrayFire in a paper published in the Applied Soft Computing Journal. The paper is titled “A GPU fully vectorized approach to accelerate performance of NSGA-2 based on stochastic non-domination sorting and grid-crowding” and showcases ArrayFire accelerating decision space exploration for multi-objective optimization problems.
Summary
This work introduces an accelerated implementation of NSGA-2 on a graphics processing unit (GPU) to reduce execution time. Parallelism is achieved at the population level using vectorization. All the algorithm components are run on the device, minimizing communication overhead. New stochastic versions of both non-domination sorting and crowding are introduced in the article. They are designed to be efficiently vectorized on GPU; therefore, the proposed approach is finally limited by the sorting procedure O(nlog(n)), while the original algorithm was of order O(n2).
This improvement is reflected in the speedups attained in the experiments. The results include solution quality metrics to show no significant trade-off between acceleration and performance. The possibilities to apply multi-objective evolutionary algorithms to real-time applications are discussed in the conclusions.
The Results
The proposed implementation was a full GPU version of NSGA-2 to minimize communication overhead. This required the implementation of genetic operators as well. It took advantage of the ArrayFire library wrapper for Julia and its particular properties to device a vectorized, high-performance code. The proposed approach was compared against a CPU version and the classic NSGA-2. The experiments showed both CPU and GPU versions of the proposed approach attained an execution time speed-up compared to the original NSGA-2 for the studied problems.
The following figures from the paper show speedups in the y-axis of the CPU (“NSGA2mod”) and GPU (“GNSGA2” using ArrayFire) version of the paper’s algorithmic acceleration over baseline implementations of the NSGA-2 algorithm.
From the paper: “The difference in speedup between the CPU version and the GPU version of the proposed approach could be attributed to the acceleration accomplished by the ArrayFire library. This means time is saved when performing basic operations of the algorithm. Although, the shape of the figures mentioned above seems to indicate the complexity of both versions is dominated by the sorting procedure, as expected.”
Thanks to these researchers for sharing their great work with us!