Научная электронная библиотека ULRICH'S Periodicals Directory

Сибирский государственный университет
науки и технологий имени академика М.Ф. Решетнева

Сибирский аэрокосмический журнал
ISSN 2712-8970 (Print) ISSN 2782-5760 (on-line)

Сведения об образовательной организации

UDK 004.42 Vestnik SibGAU 2014, No. 3(55), P. 157–161
AN IMPROVEMENT OF THE DIFFERENTIAL EVOLUTION METHOD IMPLEMENTATED ON GPU
M. A. Farkov [1], A. I. Legalov [1], [2]
[1] Siberian Federal University 69, Svobodnyi prosp., Krasnoyarsk, 660041, Russian Federation Е-mail: mihail.farkov@gmail.com [2] Siberian State Aerospace University named after academician M. F. Reshetnev 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660014, Russian Federation E-mail: legalov@mail.ru
Differential evolution is a very effective numerical optimization method which applied to diverse the set of computationally intensive tasks. Due to the features of the algorithm, it is very suitable for graphics processing unit (GPU). Most of the algorithm stages can be executed independently that corresponds to the basic programming paradigm of GPU (single instruction multiple data). Besides, an algorithm has a regular memory structure for internal data. The use of GPU allows to improve the speed of the algorithm significantly. The analysis of existing implementations of differential evolution method on GPU is performed. Moreover, existing implementations of the differential evolution algorithm on GPU use several unoptimized techniques which restrict effective application of the algorithm to tasks which use multiple optimization procedures. A new computational model that improves current implementations is described. A presented model reduces kernel calls latency due to combining logically-connected kernel into a single global kernel. The algorithm allows to use computational grid which contains single computational block. This approach satisfies requirements of the differential evolution approach to size of population (from five to ten times greater than number of optimized variables) and allows to use GPU internal barrier synchronization techniques. Besides a proposed implementation has regular data allocation in the global memory of GPU that provides coalescence of requests to the slowest global memory thus all threads in warp can read and write information from global memory per single request. Moreover it allows to use Compute Unified Device Architecture (CUDA) streams in very effective manner. In fact, a proposed model can simultaneously execute as much optimization procedure as multiprocessors available on GPU and belimited only by computer capabilities restrictions.
GPGPU, CUDA, differential evolution.
References

1. Storn R., Price K. Differential evolution – A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization. 1997, 11(4), p. 341–359.

2. Veronese L.P., Krohling R.A. Differential evolution algorithm on the GPU with C-CUDA. In Proceedings of Evolutionary Computation (CEC). 2010.

3. Gonzalez D., Barriga N. G. Fully parallel differential evolution. In Competition of GPUs for Genetic and Evolutionary Computation at the 2011 Genetic and Evolutionary Computation Conference. GECCO’2011.

4. Kromer P., Platos J., Snasel V., Abraham A.
A comparison of many-threaded differential evolution and genetic algorithms on CUDA. Nature and Biologically Inspired Computing, 2011, p. 509–514.

5. Ramirez-Chavez L. E., Coello Coello C. A., Rodriguez-Tello E. A GPU-Based Implementation of Differential Evolution for Solving the Gene Regulatory Network Model Inference Problem. In Proceedings of: Proceedings of the Fourth International Workshop on Parallel Architectures and Bioinspired Algorithms, WPABA, 2011.

6. Davendra D., Gaura J., Bialic-Davendra M., Senkerik R. GPU based enhanced differential evolution algorithm: a computational analysis. In Proceedings of 26th European Conference on Modelling and Simulation, 2012, ISBN: 978-0-9564944-4-3.

7. Kromer P., Platos J., Snasel V., Abraham A. Many-Threaded Differential Evolution on the GPU. Massively Parallel Evolutionary Computation on GPGPUs, Natural Computing Series, Springer, 2013, p. 121–147.

8. Qin A. K., Raimondo F., Forbes F., Ong Y. S. An improved CUDA-based implementation of differential evolution on GPU. In Proceedings of the 14th annual conference on Genetic and evolutionary computation. GECCO '12, p. 991–998.

9. Price K., Storn R., Lampinen J. Differential Evolution: A Practical Approach to Global Optimization. Springer, 2005, ISBN: 3540209506.

10. Storn R. On the usage of differential evolution for function optimization. NAFIPS, 1996, p. 519–523.

11. Sanders J., Kandrot E. CUDA by Example: An Introduction to General-Purpose GPU Programming. Addison-Wesley. 2010, ISBN 978-0-13-138768-3.

12. Kirk D. B., Hwu W. Programming Massively Parallel Processors. A Hands-on Approach. Elsevier, 2010, ISBN: 978-0-12-381472-2.

13. Hwu W. GPU Computing Gems Emerald Edition. Elsevier, 2011, ISBN: 978-0123849885.

14. Wilt N. CUDA Handbook: A Comprehensive Guide to GPU Programming. Addison-Wesley. 2013, ISBN: 978-0-321-80946-9.

15. Hwu W. GPU Computing Gems Jade Edition. Elsevier, 2011, ISBN: 978-0123859631.


Farkov Mikhail Aleksandrovich – postgraduate student, Siberian Federal University. E-mail: mihail.farkov@gmail.com

Legalov Alexander Ivanovich – Doctor of Engineering Science, Professor. E-mail: legalov@mail.ru