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

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

Аннотация

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

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

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

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

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

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

Литература

  1. Voevodin VlV, Voevodin VadV. [The fortunate locality of supercomputers]. Otkrytye sistemy [Open systems]. 2013;9:12–15. Russian.
  2. Buluc A, Gilberta JR, Budak C. Solving path problems on the GPU. Parallel Computing. 2010;36(5– 6):241–253.
  3. Likhoded NA, Paliashchuk MA. [Estimate of locality of parallel algorithms implemented on GPUs]. Vestnik Yuzhno-Ural’skogo gosudarstvennogo universiteta. Seriya: Vychislitel’naya matematika i informatika [Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering]. 2016:5(3):96 –111. Russian. DOI: 10.14529/cmse160307.
  4. Likhoded NA, Poleshchuk MA. Method of ranking tiles size parameters of parallel algorithm. Doklady of the National Academy of Sciences of Belarus. 2015;59(4):25–33. Russian.
  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. Poleshchuk MA, Likhoded NA. [Array privatization by computing threads]. In: CSIST’2016. Mezhdunarodnyi kongress po informatike: informatsionnye sistemy i tekhnologii; 24 –27 oktyabrya 2016 g.; Minsk, Belarus’ [CSIST’2016. International Congress on Computer Science: Information Systems and Technologies; 2016 October 24 –27; Minsk, Belarus]. Minsk: Belarusian State University; 2016. p. 883–888. Russian.
  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. Adutskevich EV, Likhoded NA, Sikorsky AO. [Parallelization of sequential programs: distribution of arrays among processors and structurization of communications]. Kibernetika i sistemnyi analiz [Cybernetics and System Analysis]. 2012;48(1):144 –163. Russian.
  12. Voevodin VV. Informatsionnaya struktura algoritmov [Informational structure of algorithms]. Moscow: MGU; 1997. Russian.
  13. Likhoded NA, Tolstikov AA. Formalization of communication operations of multidimensional loops. Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series. 2010;3:109 –114. Russian.
Опубликован
2019-01-19
Ключевые слова: параллельные вычисления, графический процессор, тайлинг, приватизация элементов массива, регистры
Поддерживающие организации Работа выполнена в рамках государственной программы научных исследований Республики Беларусь «Конвергенция-2020» (подпрограмма «Методы математического моделирования сложных систем»).
Как цитировать
Лиходед, Н. А., & Полещук, М. А. (2019). Условия приватизации элементов массива потоками вычислений. Журнал Белорусского государственного университета. Математика. Информатика, 3, 59-67. Доступно по https://journals.bsu.by/index.php/mathematics/article/view/1013
Выпуск
№ 3 (2018): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Вычислительная математика

Copyright (c) 2018 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).