vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2022-58-3-292-299vestifm-665Research ArticleМАТЕМАТИКАMATHEMATICSУсловия существования бродкаста и пространственной локальности в потоках вычисленийConditions for the existence of broadcast and spatial locality in computation threadsЛиходедН. А.LikhodedN. A.

Лиходед Николай Александрович – доктор физико-математических наук, профессор

пр. Независимости, 4, 220030, Минск

Nikolai A. Likhoded – Dr. Sc. (Physics and Mathematics), Professor

4, Nezavisimosti Ave., 220030, Minsk

likhoded@bsu.byБелорусский государственный университетBelarusian State University202212102022583292299Copyright © Лиходед Н.А., 20222022Лиходед Н.А.Likhoded N.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/665

В качестве компьютера, на котором требуется реализовать параллельную версию алгоритма, рассматриваются графические процессоры (GPU). Множество операций алгоритма для выполнения на GPU должно быть разбито на потоки вычислений; потоки должны быть сгруппированы в блоки вычислений, выполняющиеся атомарно на мультипроцессорах. Потоки одного блока выполняются на мультипроцессоре частями-пулами, называемыми варпами (warps); потоки варпа выполняются одновременно. Эффективность параллельного алгоритма зависит от способа размещения данных в памяти GPU. Если все потоки варпа запрашивают при выполнении текущего оператора один и тот же элемент массива, то его желательно размещать в разделяемой или константной памяти GPU; в этом случае его распределение по ядрам мультипроцессора реализуется фактически посредством бродкаста (broadcast). Если потоки варпа запрашивают близко расположенные в памяти данные, то в этом случае имеет место их пространственная локальность, что делает целесообразным размещение этих данных в текстурной памяти GPU. Реализация бродкаста или пространственной локальности за счет размещения данных в памяти соответствующего вида позволяет существенно снизить трафик при обмене ими между уровнями памяти графического процессора. В работе сформулированы и доказаны необходимые и достаточные условия, при которых возможно выполнение бродкаста или имеет место пространственная локальность данных. Условия даны в терминах функций, определяющих использование элементов массивов на вхождениях в операторы алгоритма, и функций, задающих информационные зависимости алгоритма. Полученные результаты могут быть использованы для оптимизации параллельных алгоритмов при их реализации на GPU.

Graphics Processing Units (GPUs) are considered as the target computer for implementing parallel algorithms. The set of algorithm operations to be implemented on the GPU must be split into computation threads; the threads should be grouped into computation blocks that are performed atomically on stream processors. Threads of a single block are executed on a stream processor in parts-pools called warp; warp threads are executed simultaneously. The efficiency of the parallel algorithm depends on the way the data is stored in the GPU memory. If all warp threads request the same datum when executing the current operator, then it is desirable to place it in a shared or constant GPU memory; in this case, its distribution across the cores of the multiprocessor is actually realized by means of broadcast. If warp threads request data located close to the memory, then in this case there is a spatial locality of data, which makes it advisable to place this data in the GPU’s memory. The implementation of broadcast or spatial locality by placing data in a memory of the appropriate type allows one to significantly reduce traffic when exchanging data between the memory levels of the GPU. This paper formulates and proves the necessary and sufficient conditions under which it is possible to perform a broadcast or there is a spatial locality of data. The conditions are formulated in terms of functions that determine the use of array elements at occurrences in the algorithm operators and functions that define the information dependencies of the algorithm. The results of the work can be used to optimize parallel algorithms when they are implemented on the GPU.

параллельные вычисленияграфический процессорбродкастпространственная локальностьparallel computationsGPUbroadcastspatial localityReferencesЛиходед, Н. А. Характеристика локальности параллельных реализаций многомерных циклов / Н. А. Лиходед // Докл. Нац. акад. наук Беларуси. – 2010. – Т. 54, № 1. – С. 26–32.Likhoded N. A. Characterization of locality of the parallel implementations of imperfectly nested loops. Doklady Natsional’noi akademii nauk Belarus = Proceedings of the National Academy of Sciences of Belarus, 2010, vol. 54, no. 1, pp. 26–32 (in Russian).Адуцкевич, Е. В. К распараллеливанию последовательных программ: распределение массивов между процессорами и структуризация коммуникаций / Е. В. Адуцкевич, Н. А. Лиходед, А. О. Сикорский // Кибернетика и систем. анализ. – 2012. – № 1. – С. 144–163.Adutskevich N. A. Likhoded N. A., Sikorsky A. O. Parallelization of sequential programs: distribution of arrays among processors and structurization of communications. Cybernetics and System Analysis, 2012, vol. 48, no. 1, pp. 122–137. https:// doi.org/10.1007/s10559-012-9382-2Лиходед, Н. А. Метод ранжирования параметров размера блоков вычислений параллельного алгоритма / Н. А. Лиходед, М. А. Полещук // Докл. Нац. акад. наук Беларуси. – 2015. – Т. 59, № 4. – С. 25–33.Likhoded N. A., Paliashchuk M. A. Method of ranking tiles size parameters of parallel algorithm. Doklady Natsional’noi akademii nauk Belarus = Proceedings of the National Academy of Sciences of Belarus, 2015, vol. 59, no. 4, pp. 25–33 (in Russian).Лиходед, Н. А. Оценка локальности параллельных алгоритмов, реализуемых на графических процессорах / Н. А. Лиходед, М. А. Полещук // Вестн. Юж.-Урал. гос. ун-та. Сер.: «Вычисл. математика и информатика». – 2016. – Т. 5. № 3. – С. 96–111. https://doi.org/10.14529/cmse160307Likhoded N. A., Paliashchuk M. A. Estimate of locality of parallel algorithms implemented on GPUs. Vestnik YuzhnoUral’skogo gosudarstvennogo universiteta. Seriya: «Vychislitel’naya matematika i informatika» = Bulletin of the South Ural State University. Series: “Computational Mathematics and Software Engineering”, 2016, vol. 5, no. 3, pp. 96–111 (in Russian). https://doi.org/10.14529/cmse160307Лиходед, Н. А. Условия приватизации элементов массива потоками вычислений / Н. А. Лиходед, М. А. Полещук // Журн. Белорус. гос. ун-та. Математика. Информатика. – 2018. – № 3. – С. 59–67.Likhoded N. A., Paliashchuk M. A. Conditions for privatizing the elements of arrays by computing threads. Zhurnal Belorusskogo gosudarstvennogo universiteta. Matematika. Informatika = Journal of the Belarusian State University. Mathematics and Informatics, 2018, no. 3, pp. 59–67 (in Russian).Воеводин, В. В. Параллельные вычисления / В. В. Воеводин. – СПб.: БХВ-Петербург, 2002. – 608 с.Voevodin V. V. Parallel Computing. Saint Petersburg, BKhV-Petersburg Publ., 2002. 608 p. (in Russian).Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model / U. Bondhugula [et al.] // Lecture Notes in Computer Science. – Springer, 2008. – P. 132–146. – (LNTCS, vol. 4959). https://doi.org/10.1007/978-3-540-78791-4_9Bondhugula U., Baskaran M., Krishnamoorthy S., Ramanujam J., Rountev A., Sadayappan P. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. Lecture Notes in Computer Science. (LNTCS, vol. 4959), 2008, pp. 132–146. https://doi.org/10.1007/978-3-540-78791-4_9Xue, J. Loop Tiling for Parallelism / Xue J. – Springer Science & Business Media, 2000. – 256 p. – (LNTCS, vol. 575). https://doi.org/10.1007/978-1-4615-4337-4Xue J. Loop Tiling for Parallelism. (LNTCS, vol. 575). Springer Science & Business Media, 2000. 256 p. https://doi. org/10.1007/978-1-4615-4337-4Venkataraman, G. A blocked all-pairs shortest-paths algorithm / G. Venkataraman, S. Sahni, S. Mukhopadhyaya // ACM J. Exp. Algorithm. – 2003. – Vol. 8. – P. 2.2-es. https://doi.org/10.1145/996546.996553Venkataraman G., Sahni S., Mukhopadhyaya S. A blocked all-pairs shortest-paths algorithm. ACM Journal of Experimental Algorithmics, 2003, vol. 8, pp. 2.2-es. https://doi.org/10.1145/996546.996553Lund, B. D. A multi-stage cuda kernel for floyd-warshall [Electronic Resource] / B. D. Lund, J. W. Smith // Arxiv [Preprint]. – 2010. – Mode of access: https://arxiv.org/abs/1001.4108. https://doi.org/10.48550/arXiv.1001.4108Lund B. D., Smith J. W. A multi-stage cuda kernel for floyd-warshall. Arxiv [Preprint], 2010. Available at: https://arxiv. org/abs/1001.4108. https://doi.org/10.48550/arXiv.1001.4108

The authors declare that there are no conflicts of interest present.