Условия существования бродкаста и пространственной локальности в потоках вычислений
https://doi.org/10.29235/1561-2430-2022-58-3-292-299
Анатацыя
В качестве компьютера, на котором требуется реализовать параллельную версию алгоритма, рассматриваются графические процессоры (GPU). Множество операций алгоритма для выполнения на GPU должно быть разбито на потоки вычислений; потоки должны быть сгруппированы в блоки вычислений, выполняющиеся атомарно на мультипроцессорах. Потоки одного блока выполняются на мультипроцессоре частями-пулами, называемыми варпами (warps); потоки варпа выполняются одновременно. Эффективность параллельного алгоритма зависит от способа размещения данных в памяти GPU. Если все потоки варпа запрашивают при выполнении текущего оператора один и тот же элемент массива, то его желательно размещать в разделяемой или константной памяти GPU; в этом случае его распределение по ядрам мультипроцессора реализуется фактически посредством бродкаста (broadcast). Если потоки варпа запрашивают близко расположенные в памяти данные, то в этом случае имеет место их пространственная локальность, что делает целесообразным размещение этих данных в текстурной памяти GPU. Реализация бродкаста или пространственной локальности за счет размещения данных в памяти соответствующего вида позволяет существенно снизить трафик при обмене ими между уровнями памяти графического процессора. В работе сформулированы и доказаны необходимые и достаточные условия, при которых возможно выполнение бродкаста или имеет место пространственная локальность данных. Условия даны в терминах функций, определяющих использование элементов массивов на вхождениях в операторы алгоритма, и функций, задающих информационные зависимости алгоритма. Полученные результаты могут быть использованы для оптимизации параллельных алгоритмов при их реализации на GPU.
Спіс літаратуры
1. Лиходед, Н. А. Характеристика локальности параллельных реализаций многомерных циклов / Н. А. Лиходед // Докл. Нац. акад. наук Беларуси. – 2010. – Т. 54, № 1. – С. 26–32.
2. Адуцкевич, Е. В. К распараллеливанию последовательных программ: распределение массивов между процессорами и структуризация коммуникаций / Е. В. Адуцкевич, Н. А. Лиходед, А. О. Сикорский // Кибернетика и систем. анализ. – 2012. – № 1. – С. 144–163.
3. Лиходед, Н. А. Метод ранжирования параметров размера блоков вычислений параллельного алгоритма / Н. А. Лиходед, М. А. Полещук // Докл. Нац. акад. наук Беларуси. – 2015. – Т. 59, № 4. – С. 25–33.
4. Лиходед, Н. А. Оценка локальности параллельных алгоритмов, реализуемых на графических процессорах / Н. А. Лиходед, М. А. Полещук // Вестн. Юж.-Урал. гос. ун-та. Сер.: «Вычисл. математика и информатика». – 2016. – Т. 5. № 3. – С. 96–111. https://doi.org/10.14529/cmse160307
5. Лиходед, Н. А. Условия приватизации элементов массива потоками вычислений / Н. А. Лиходед, М. А. Полещук // Журн. Белорус. гос. ун-та. Математика. Информатика. – 2018. – № 3. – С. 59–67.
6. Воеводин, В. В. Параллельные вычисления / В. В. Воеводин. – СПб.: БХВ-Петербург, 2002. – 608 с.
7. 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_9
8. Xue, 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-4
9. Venkataraman, 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.996553
10. Lund, 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.4108
##reviewer.review.form##
Праглядаў: 388
Паслаць артыкул па эл. пошце 