НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o287.pdf (1002.56Кб)

УДК 004.051+519.171

1 МГТУ им. Н.Э. Баумана, Москва, Россия

Многие алгоритмы решения задач анализа и синтеза структур сложных систем имеют большой запас внутреннего параллелизма. Однако при их реализации на конкретной параллельной вычислительной системе коэффициент ускорения может оказаться крайне мал. Прежде всего такое поведение связано с программно-аппаратными особенностями используемой вычислительной системы. Данная статья посвящена выявлению факторов, не позволяющих достигнуть расчетных коэффициентов ускорения параллельных алгоритмов операций над графовыми моделями при использовании графических процессоров CUDA, и разработке рекомендаций, следование которым приведет к снижению непроизводительных временных затрат.
В статье была рассмотрена модель выполнения программ в CUDA, определен характер выполнения потоков, предложены 2 метода планирования потоков: итеративное выполнение параллельной функции и итеративное выполнения кода внутри параллельной функции. Для разработки эффективных структур данных был выполнен анализ особенностей работы с памятью в CUDA, проведены исследования различных алгоритмов выделения памяти, разработана реализация критической секции в CUDA, не приводящая к взаимной блокировке потоков. На основе полученных результатов были сформулированы рекомендации, позволяющие эффективно использовать возможности параллелизации в CUDA.
В рамках практической проверки предложенных методов и правил была разработана структура данных для представления графов, основанная на принципах CUDA, а также предложены несколько вариантов реализации параллельного алгоритма операции декомпозиции вершины графа: без использования критической секции в потоках с итеративным выполнением параллельной функции; без использования критической секции в потоках с итеративным выполнением кода внутри параллельной функции; с использованием критической секции в потоках с итеративным выполнением кода внутри параллельной функции. На основе анализа экспериментальных результатов был сделан вывод о применимости выработанных рекомендаций и высокой эффективности использования CUDA при реализации операций над графами в задачах больших размерностей.

1. Овчинников В.А. Графы в задачах анализа и синтеза структур сложных систем. М.: МГТУ им. Н.Э. Баумана, 2014. 423 с.
2. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. М.: МГТУ им. Н.Э. Баумана, 2001. 288 с.
3. Иванова Г.С. Методология и средства разработки алгоритмов решения задач анализа и синтеза структур программного обеспечения и устройств вычислительной техники: дис. … докт. техн. наук. М., 2007. 416 с.
4. Овчинников В.А., Иванова Г.С., Ничушкина Т.Н. Выбор структур данных для представления графов при решении комбинаторно-оптимизационных задач // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2001. № 2 (43). C. 39-51.
5. Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 10. Режим доступа: http://technomag.bmstu.ru/doc/132769.html (дата обращения 07.10.2015).
6. Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем (часть 2) // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 11. Режим доступа: http://technomag.bmstu.ru/doc/133223.html (дата обращения 07.10.2015).
7. Овчинников В.А. Операции над ультра и гиперграфами для реализации процедур анализа и синтеза структур сложных систем (часть 3) // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 12. Режим доступа: http://technomag.bmstu.ru/doc/134335.html (дата обращения 07.10.2015).
8. Иванова Г.С., Головков А.А. Оценка эффективности параллельных алгоритмов операций преобразования графовой модели // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 11. С. 535-554. DOI:10.7463/1114.0741563
9. Головков А.А., Иванова Г.С. Структура данных для представления графов на параллельных вычислительных системах и параллельные алгоритмы операций над графами // Инженерный вестник. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 11. С. 625-632. Режим доступа: http://engbul.bmstu.ru/doc/751611.html (дата обращения 07.10.2015).
10. Головков А.А. Представление графовых моделей в системах параллельной обработки // Молодежный научно-технический вестник. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 7. Режим доступа: http://sntbul.bmstu.ru/doc/727773.html (дата обращения 07.10.2015).
11. Гергель В.П. Теория и практика параллельных вычислений: учеб. пособие. М.: Интернет-университет Информационных технологий; БИНОМ. Лаборатория знаний, 2013. 423 с.
12. Wilt N. The CUDA Handbook: A Comprehensive Guide to GPU Programming. Addison - Wesley , 2013. 512 p .
13. Farber R. CUDA Application Design and Development. Waltham, MA, USA: Morgan Kaufmann, 2011. 336 p.
14. Merrill D., Garland M., Grimshaw A. Scalable GPU Graph Traversal // Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming (PPoPP '12). ACM New York, NY, USA, 2012. P. 117-128. DOI: 10.1145/2145816.2145832
15. Hussein M., Varshney A., Davis L. On Implementing Graph Cuts on CUDA // First Workshop on General Purpose Processing on Graphics Processing Units, 2007. Available at: http://www-lb.cs.umd.edu/gvil/papers/hussein_GPGPU07.pdf, accessed 07.10.2015.
16. Dechev D., Pirkelbauer P., Stroustrup B. Lock-Free Dynamically Resizable Arrays // Principles of Distributed Systems. Springer-Verlag Berlin Heidelberg, 2006. P. 142-156. (Ser. Lecture Notes in Computer Science; vol. 4305). DOI: 10.1007/11945529_11
17. Luo L., Wong M., Wen-mei Hwu. An Effective GPU Implementation of Breadth-First Search // Proceedings of the 47th Design Automation Conference (DAC '10). ACM New York, NY, USA, 2010. P. 52-55. DOI: 10.1145/1837274.1837289
18. Misra P., Chaudhuri M. Performance Evaluation of Concurrent Lock-free Data Structures on GPUs // Proceedings of the 18th IEEE International Conference on Parallel and Distributed Systems. IEEE Publ., 2012. P. 53-60. DOI: 10.1109/ICPADS.2012.18
19. Cederman D., Gidenstam A., Ha P., Sundell H., Papatriantafilou M., Tsigas P. Lock-free Concurrent Data Structures // Programming Multi-Core and Many-Core Computing Systems / ed. by S. Pllana, F. Xhafa. Wiley-Blackwell, 2013. (Wiley Series on Parallel and Distributed). Available at: http://arxiv.org/pdf/1302.2757.pdf, accessed 07.10.2015.
20. Schaeffer S.E. Graph clustering // Computer Science Review. 2007. Vol. 1, iss. 1. P. 27-64. DOI: 10.1016/j.cosrev.2007.05.001
21. Shucai Xiao, Wu-chun Feng. Inter-block GPU communication via fast barrier synchronization // 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS). IEEE Publ., 2010. P. 1-12. DOI: 10.1109/IPDPS.2010.5470477
22. Якобовский М.В. Введение в параллельные методы решения задач: учеб. пособие. М.: Изд-во Московского ун-та, 2013. 328 с.
23. Линев А.В., Богопелов Д.К., Бастраков С.И. Технологии параллельного программирования для процессоров новых архитектур: учебник. М.: Изд-во Московского ун-та, 2010. 160 с.
24. Pawan Harish, Vibhav Vineet and P. J. Narayanan. Large Graph Algorithms for Massively Multithreaded Architectures. Technical Report no. IIIT/TR/2009/74. Centre for Visual Information Technology, International Institute of Information Technology, Hyderabad - 500 032, INDIA, February 2009. Available at: http://cvit.iiit.ac.in/papers/pawan09GraphAlgorithms.pdf, accessed 07.10.2015.