Условия приватизации элементов массива потоками вычислений

  • Николай Александрович Лиходед Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь
  • Максим Александрович Полещук Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

Аннотация

Множество операций параллельного алгоритма для реализации на графическом процессоре должно быть разбито на потоки (нити) вычислений. Потоки следует сгруппировать в блоки вычислений, выполняющиеся атомарно на потоковых процессорах, называемых также мультипроцессорами. Для хорошей производительности  графического процессора важно, чтобы как можно больше данных умещались в быстрых регистровой и разделяемой памяти, иначе используются медленные глобальная и локальная память. Степень использования памяти  с быстрым доступом отражает вычислительное свойство алгоритма, называемое локальностью. При реализации  алгоритмов на многопроцессорных вычислительных устройствах применение локальности играет важнейшую  роль для достижения высокой производительности. В данной работе сформулированы и доказаны необходимые  условия и достаточные условия, использование которых позволяет получать  потоки с приватизированными данными, т. е. такие потоки вычислений, что элемент массива используется только одним потоком, и поэтому его  целесообразно разместить в регистре.

Биографии авторов

Николай Александрович Лиходед, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

доктор физико-математических наук, профессор; профессор кафедры вычислительной математики факультета прикладной математики  и информатики

Максим Александрович Полещук, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

ассистент кафедры вычислительной математики факультета прикладной математики и информатики

Литература

1. Воеводин ВлВ, Воеводин ВадВ. Спасительная локальность суперкомпьютеров. Открытые системы. 2013;9:12–15.
2. Buluc A, Gilberta JR, Budak C. Solving path problems on the GPU. Parallel Computing. 2010;36(5– 6):241–253.
3. Лиходед НА, Полещук МА. Оценка локальности параллельных алгоритмов, реализуемых на графических процессорах. Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2016:5(3):96 –111. DOI: 10.14529/cmse160307.
4. Лиходед НА, Полещук МА. Метод ранжирования параметров размера блоков вычислений параллельного алгоритма. Доклады Национальной академии наук Беларуси. 2015;59(4):25–33.
5. Kandemir M, Ramanujam J, Irwin M, Narayanan V, Kadayif I, Parikh A. A compiler based approach for dynamically managing scratch-pad memories in embedded systems. IEEE Transactions on Computer-Aided Design. 2004;23(2):243–260.
6. Baskaran M, Bondhugula U, Krishnamoorthy S, Ramanujam J, Rountev A, Sadayappan P. Automatic data movement and computation mapping for multi-level parallel architectures with explicitly managed memories. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming; 2008 February 20 –23; Salt Lake City, USA. New York: ACM; 2008. p. 1–10. DOI: 10.1145/1345206.1345210.
7. Полещук МА, Лиходед НА. Приватизация элементов массивов потоками вычислений. В: CSIST’2016. Международный конгресс по информатике: информационные системы и технологии; 24 –27 октября 2016 г.; Минск, Беларусь. Минск: БГУ; 2016. с. 883–888.
8. Baskaran M, Ramanujam J, Sadayappan P. Automatic C-to-CUDA code generation for affine programs. In: Compiler Construction. 19th International Conference. Part of the Joint European Conferences on Theory and Practice of Software; 2010 March 20 –28; Paphos, Cyprus. Berlin, Heidelberg: Springer-Verlag; 2010. DOI: 10.1007/978-3-642-11970-5_14.
9. Katz GJ, Kider J. All-pairs shortest-paths for large graphs on the GPU. In: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware; 2008 June 20 –21; Sarajevo, Bosnia and Herzegovina. Geneve: Eurographics Association; 2008. p. 47–55.
10. Lund BD, Smith JW. A Multi-Stage {CUDA} Kernel for Floyd-Warshall. CoRR [Internet]. 2010;abs/1001.4108. Available from: http://arxiv.org/abs/1001.4108.
11. Адуцкевич ЕВ, Лиходед НА, Сикорский АО. К распараллеливанию последовательных программ: распределение массивов между процессорами и структуризация коммуникаций. Кибернетика и системный анализ. 2012;48(1):144 –163.
12. Воеводин ВВ. Информационная структура алгоритмов. Москва: МГУ; 1997.
13. Лиходед НА, Толстиков AА. Формализация коммуникационных операций многомерных циклов. Известия Национальной академии наук Беларуси. Серия физико-математических наук. 2010;3:109 –114.
Опубликован
2019-01-19

Просмотров аннотации: 135
Загрузок PDF: 39
Ключевые слова: параллельные вычисления, графический процессор, тайлинг, приватизация элементов массива, регистры
Поддерживающие организации Работа выполнена в рамках государственной программы научных исследований Республики Беларусь «Конвергенция-2020» (подпрограмма «Методы математического моделирования сложных систем»).
Как цитировать
Лиходед Н. А., Полещук М. А. Условия приватизации элементов массива потоками вычислений // Журнал Белорусского государственного университета. Математика. Информатика. 2019. 3. С. 59-67.