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

Авторы

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

Ключевые слова:

параллельные вычисления, графический процессор, тайлинг, приватизация элементов массива, регистры
Поддерживающие организации
Работа выполнена в рамках государственной программы научных исследований Республики Беларусь «Конвергенция-2020» (подпрограмма «Методы математического моделирования сложных систем»).

Аннотация

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

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

  • Николай Александрович Лиходед, Белорусский государственный университет, пр. Независимости, 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

Выпуск

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

Раздел

Вычислительная математика

Лицензия

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

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

Как цитировать

[1]
Лиходед, Н.А. и Полещук, М.А. 2019. Условия приватизации элементов массива потоками вычислений. Журнал Белорусского государственного университета. Математика. Информатика. 3 (янв. 2019), 59–67.