Article

Article title DEVELOPMENT OF AUTOPARALLELIZATION METHODSFOR COMPUTATIONAL SYSTEMS WITH SHARED MEMORY ARCHITECTURE
Authors O.V. Shapovalov, A.E. Andreev, S.A. Fomenkov
Section SECTION I. ARCHITECTURE, MODELS AND TOOLS FOR INFORMATION SYSTEMS
Month, Year 03, 2015 @en
Index UDC 519.688
DOI
Abstract In this paper problem of automation of parallel software development for shared memory systems is considered. The goal of this work was to develop software that will enable the programmer to compare the performance and maximize the efficiency of using various parallel programming technologies for the specific problem. For decreasing time for development of parallel programs unified interface for parallel technologies OpenMP, Cilk Plus, Intel TBB, PPL, BoostThreads is suggested. For increasing efficiency of parallelization new method is proposed, it is used for parallel execution of some programming code with various parallel programming technologies, the choice between them is realized at runtime with developed classification algorithm. The developed algorithm of selection of the parallel technology is a multi-class classification algorithm; it is a modification of the method of nearest neighbors for a limited amount of information. The algorithm also takes as its basis some parts of the algorithm of multiple logit regression. The necessary statistics were produced for classification algorithm by a developed learning algorithm, which controls the selection of parallel programming technology for calculating the new statistical data and the results from the current classification are used in the following classification. The learning algorithm has a linear convergence, this is proved by theoretically and empirically grounded research findings. This interface is used for automatic parallelization of serial programming code with technologies which are enumerated above. Programming library, that helps to realize efficient parallel programs for shared memory systems with coprocessors and accelerators, is developed. In addition to OpenMP, Cilk Plus, Intel TBB, PPL, Boost Threads parallel technologies, for which parallelization is performed automatically, the programmer, who uses our library, can add his own implementations of parallelism. An efficiency of proposed methods is shown with example program, that calls matrix multiplication method, execution time was reduced by 43 % as compared to standard parallelization approach, that uses only one parallel programming technology.

Download PDF

Keywords Automatic parallelization; adaptive classifier; OpenMP; Cilk Plus; Intel TBB; PPL; BoostThreads.
References 1. Шаповалов О.В., Андреев А.Е., Фоменков С.А. Применение библиотеки параллельных шаблонов в разработке геометрического ядра // Вестник компьютерных и информационных технологий. – 2014. – № 11. – С. 8-12.
2. ParallelPatternsLibrary (PPL) [Электронный ресурс]. – Режим доступа: https://msdn. microsoft.com/en-us/library/dd492418.aspx (дата обращения: 03.05.2015).
3. Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: классификация и снижение размерности. – М.: Финансы и статистика, 1989.
4. Клевцов С.И. Прогнозирование изменений физической величины в реальном времени с использованием линейного адаптивного фильтра // Известия ЮФУ. Технические науки. – 2013. – № 5 (142). – С. 180-185.
5. Shakhnarovish G., Darrel T., Indyk P. Nearest-Neighbor Methods in Learning and Vision // Pattern Analysis and Applications. – 2008. – Vol. 11, Issue 2. – P. 221-222.
6. Freedman, D. Statistical Models: Theory and Practice // Cambridge University Press. – 2009. – p. 128.
7. Ромм Я.Е., Стаховская И.И. Временная сложность параллельного кусочно-интерполяционного вычисления функций // Известия ЮФУ. Технические науки. – 2013. – № 5 (142). – С. 160-165.
8. Центр разработки NVIDIA CUDA [Электронный ресурс]. – Режим доступа: https://developer.nvidia.com/cuda-zone (дата обращения: 03.05.2015).
9. Jackson Q., Landgrebe D.A. An adaptive classifier design forhigh-dimensional data analysis with a limited training data set // IEEETrans. Geosci. Remote Sens. – 2001. – Vol. 39. – P. 2664-2679.
10. Антонов А.С. Параллельное программирование с использованием технологии OpenMP: Учеб. пособие. – М.: Изд-во МГУ, 2009. – 77 с.
11. Бочаров Н.В. Технологии и техника параллельного программирования [Электронный ресурс]. – Режим доступа: http://dks.invitation.ru (дата обращения: 03.05.2015).
12. Карпов А.Н. Тестирование параллельных программ [Электронный ресурс]. – Режим доступа: http://www.viva64.com/ru/a/0031 (дата обращения: 03.05.2015).
13. Жариков Д.Н., Лукьянов В.С., Шамов Е.А., Шаповалов О.В., Попов Д.С. Моделирование динамики электронного потока в скрещенных полях на кластере из центральных и графических процессорных устройств / // Современные наукоёмкие технологии. – 2010. – № 4. – C. 58-60.
14. Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.: БХВ-Петербург, 2002. – 400 с.
15. Кузьмина К.С., Марчевский И.К. Об ускорении вычислений при решении двумерных сопряженных задач гидроупругости вихревыми методами // Вестник Пермского Национального исследовательского политехнического университета. Аэрокосмическая техника. – 2014. – № 39. – С. 145-163.
16. Yokota R., Barba L.A. Hierarchical N-body simulations with auto-tuning for heterogeneous systems // Computing in Science and Engineering. – 2012. – Vol. 14. – P. 30-39.
17. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем: Пер с англ. Дж. Ортега. – М.: Мир, 1991. – 367 с.
18. Сообщество разработчиков программного обеспечения [Электронный ресурс]. – Режим доступа: http://software.intel.com/ru-ru/?iid=gg_work-RU+home_software (дата обращения: 03.05.2015).
19. Шамов Е.А., Шаповалов О.В., Стуров Д.А., Горобцов А.С. Анализ эффективности применения технологии Nvidia CUDA для задач физической электроники // Известия Волгоградского государственного технического университета: Межвуз. сб. науч. ст. – Волгоград: ВолгГТУ, 2009. – № 12 (60). – 128 с. – (Сер. Актуальные проблемы управления,
вычислительной техники и информатики в технических системах. Вып. 7).
20. Шаповалов О.В. Параллельные методы численного решения жестких СОДУ // XV Региональная конференция молодых исследователей Волгоградской области. – Волгоград: ВолгГТУ, 2010.
21. Шаповалов О.В., Юдкин А.А., Андреев А.Е. Разработка параллельных решателей для систем многотельного моделирования // Информационные технологии в образовании, технике и медицине: Материалы Междунар. конф. – Волгоград: ВолгГТУ, 2009.
22. Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования: Пер. с англ. Г.Р. Эндрюс. – М.: Издательский дом «Вильямс», 2003. – 505 с.
23. Prasad S., Bruce L. M. A robust multi-classifier decision fusion framework for hyperspectral, multi-temporal classification // Proc. IEEE IGARSS. – 2008. – Vol. 2. – P. 273-276.
24. Ranawana R. Intelligent multi-classifier design methods for the classification of imbalanced data sets: Ph.D. dissertation. – Univ. of Oxford, Oxford, U.K., 2007. – P. 33-39.
25. Changhong F., Fernandez S., Antonio R., Miguel A., Pascual C. Real-Time Adaptive Multi-Classifier Multi-Resolution Visual Tracking Framework for Unmanned Aerial Vehicles // Research, Education and Development of Unmanned Aerial Systems. – 2010. – Vol. 2, Part 1. – P. 99-106.
26. The OpenMP® API specification for parallel programming [Электронный ресурс].–Режим доступа: https://openmp.org (дата обращения: 03.05.2015).
27. ThreadingBuildingBlocks [Электронный ресурс]. – Режим доступа: https://www.threadingbuildingblocks.org (дата обращения: 03.05.2015).

Comments are closed.