ЭФФЕКТИВНАЯ РЕАЛИЗАЦИЯ ТОЧНЫХ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ НА ГРАФИЧЕСКИХ УСКОРИТЕЛЯХ
Аннотация
Большинство задач дискретной оптимизации относятся к классу NP-полных задач. Это означает, что алгоритмы, позволяющие найти их точное решение, вообще говоря могут работать с экспоненциальной сложностью относительно длины входных данных. Благодаря прогрессу, сегодня появились технологии, которые пока еще не достаточно широко использовались для реализации методов прикладной оптимизации. К числу таких технологий можно отнести GP GPU (General Purposed Graphical Processing Unit) . Применение данной технологии к хорошо известным алгоритмам может помочь добиться большей эффективности работы. Цель данной работы – исследование возможностей применения параллельных вычислений на видеокартах для решения задач дискретной оптимизации. В качестве целевой задачи выбрана задача об одномерном булевом ранце. Для решения задачи рассмотрены методы получения точного решения – алгоритм полного перебора, являющийся начальной точкой в исследовании, и метод «ветвей и границ», позволяющему сократить перебор благодаря отсеву заведомо неподходящих решений. Рассмотренные алгоритмы оценены с точки зрения количества операций и времени выполнения, реализованы в однопоточной конфигурации центрального процессора, после чего распараллелены на видеокарте. По результатам реализации данных методов, был создан комбинированный алгоритм, объединяющий в себе оба алгоритма для достижения большей эффективности. Для распараллеливания вычислений на графической карте, выбрана технология CUDA. Алгоритмы реализованы на языке С. После реализации алгоритмов, проведено тестирование на различных наборах данных и разных конфигурациях целевой платформы. Представлены результаты экспериментальных исследований, исследовано ускорение работы при использовании параллельных вычислений и проведён сравнительный анализ эффективности работы алгоритмов.
Литература
[2] Kolesar P.J. A Branch and Bound Algorithm for the Knapsack Problem. Management science. 1967; 13(9): 609-772. DOI: 10.1287/mnsc.13.9.723
[3] Martello S., Pisinger D., Toth P. Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science. 1999; 45(3):297-454. DOI: 10.1287/mnsc.45.3.414
[4] Chu P.C., Beasley J.E. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics. 1998; 4(1):63-86. DOI: 10.1023/A:100964240
[5] Posypkin M.A., Sigal I.K. A combined parallel algorithm for solving the knapsack problem. Journal of Computer and Systems Sciences International. 2008; 47(4):543-551. DOI: 10.1134/S1064230708040072
[6] Harris M. Mapping computational concepts to GPUs. ACM SIGGRAPH 2005 Courses (SIGGRAPH '05), John Fujii (Ed.). ACM, New York, NY, USA, 2005. Article 50. DOI: 10.1145/1198555.1198768
[7] Official programming guide for CUDA, ver. 1.1. CUDA Programming Guide. Chapter 1. Introduction to CUDA → 1.2 CUDA: A New Architecture for Computing on the GPU. Available at: http://developer.download.nvidia.com/compute/cuda/1_1/NVIDIA_CUDA_Programming_Guide_1.1.pdf (accessed 26.04.2018).
[8] Boreskov A.V., Kharlamov A.A., Markovsky N.D. Foreword: Sadovnichiy V.A. Parallel'nye vychisleniya na GPU. Arhitektura i programmnaya model' CUDA [Parallel computing on the GPU. Architecture and software model CUDA]. Moscow: MSU. 2015. 336 p. (In Russian)
[9] Boyer V., El Baz D., Elkihel M. Solving knapsack problems on GPU. Computers & Operations Research. 2012; 39(1):42-47. DOI: 10.1016/j.cor.2011.03.014
[10] Lalami M.E., El-Baz D. GPU Implementation of the branch and bound method for knapsack problems. Proceedings of 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), Shanghai, China, 2012. pp. 1769-1777. DOI: 10.1109/IPDPSW.2012.219
[11] Kolpakov R.M., Posypkin M.A. On the best choice of a branching variable in the subset sum problem. Discrete Mathematics and Applications. 2018; 28(1):29-34. DOI: 10.1515/dma-2018-0004
[12] Finkelstein Yu.Yu. Priblizhennye metody i prikladnye zadachi diskretnogo programmirovaniya [Approximate methods and applied problems of discrete programming]. Moscow: Nauka, 1976. 265 p. (In Russian)
[13] Sigal I.K., Ivanova A.P. Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitel'nye algoritmy [Introduction to Applied Discrete Programming: Models and Computational Algorithms]. Moscow: Fizmatlit, 2007. 304 p. (In Russian)
[14] Keller H., Pfershy U., Pisinger D. Knapsack Problems. Springer, Berlin, Heidelberg, 2004. 548 p. DOI: 10.1007/978-3-540-24777-7
[15] Levitin A.V. Algoritmy: vvedenie v razrabotku i anali [Algorithms: Introduction to Development and Analysis]. M.: Williams Publishing House, 2006. 576 p. (In Russian)
[16] Sedgwick R. Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching, Third Edition. Addison-Wesley Professional, 1998. 752 p.
[17] Suri B. Accelerating the knapsack problem on GPUs. Linköping, Sweden, 2011. 87 p.
[18] Ristovski Z. et al. Parallel implementation of the modified subset sum problem in CUDA. Proceedings of 2014 22nd Telecommunications Forum Telfor (TELFOR), Belgrade, 2014. pp. 923-926. DOI: 10.1109/TELFOR.2014.7034556
[19] Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. Springer-Verlag Berlin Heidelberg, 2004. 548 p. DOI: 10.1007/978-3-540-24777-7
[20] Jaros J., Pospichal P. A Fair Comparison of Modern CPUs and GPUs Running the Genetic Algorithm under the Knapsack Benchmark. In: Di Chio C. et al. (eds) Applications of Evolutionary Computation. EvoApplications 2012. Lecture Notes in Computer Science, vol. 7248. Springer, Berlin, Heidelberg, 2012. pp. 426-435. DOI: 10.1007/978-3-642-29178-4_43
[21] Li K. et al. A cost-optimal parallel algorithm for the 0-1 knapsack and its performance on multicore CPU and GPU implementations. Parallel Computing. 2015; 43:27-42. DOI: 10.1016/j.parco.2015.01.004
[22] Boukedjar A., Lalami M.E., El-Baz D. Parallel branch and bound on a CPU-GPU system. Proceedings of 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing. Garching, 2012. pp. 392-398. DOI: 10.1109/PDP.2012.23
[23] Crawford M., Toth D. Parallelization of the Knapsack Problem as an Introductory Experience in Parallel Computing. Journal of Computational Science Education. 2013; 4(1):35-39. DOI: 10.22369/issn.2153-4136/4/1/6
[24] Kolpakov R.M., Posypkin M.A. Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem. Discrete Mathematics and Applications. 2010; 20(1):95-112. DOI: 10.1515/dma.2010.006
[25] Posypkin M.A., Slgal I.Kh. Investigation of algorithms for parallel computations in knapsack-type discrete optimization problems. Computational Mathematics and Mathematical Physics. 2005; 45(10):1735-1742.
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
