Условия существования бродкаста и пространственной локальности в потоках вычислений
https://doi.org/10.29235/1561-2430-2022-58-3-292-299
Аннотация
В качестве компьютера, на котором требуется реализовать параллельную версию алгоритма, рассматриваются графические процессоры (GPU). Множество операций алгоритма для выполнения на GPU должно быть разбито на потоки вычислений; потоки должны быть сгруппированы в блоки вычислений, выполняющиеся атомарно на мультипроцессорах. Потоки одного блока выполняются на мультипроцессоре частями-пулами, называемыми варпами (warps); потоки варпа выполняются одновременно. Эффективность параллельного алгоритма зависит от способа размещения данных в памяти GPU. Если все потоки варпа запрашивают при выполнении текущего оператора один и тот же элемент массива, то его желательно размещать в разделяемой или константной памяти GPU; в этом случае его распределение по ядрам мультипроцессора реализуется фактически посредством бродкаста (broadcast). Если потоки варпа запрашивают близко расположенные в памяти данные, то в этом случае имеет место их пространственная локальность, что делает целесообразным размещение этих данных в текстурной памяти GPU. Реализация бродкаста или пространственной локальности за счет размещения данных в памяти соответствующего вида позволяет существенно снизить трафик при обмене ими между уровнями памяти графического процессора. В работе сформулированы и доказаны необходимые и достаточные условия, при которых возможно выполнение бродкаста или имеет место пространственная локальность данных. Условия даны в терминах функций, определяющих использование элементов массивов на вхождениях в операторы алгоритма, и функций, задающих информационные зависимости алгоритма. Полученные результаты могут быть использованы для оптимизации параллельных алгоритмов при их реализации на GPU.
Ключевые слова
Об авторе
Н. А. Лиходед
Белорусский государственный университет
Беларусь
Беларусь
Лиходед Николай Александрович – доктор физико-математических наук, профессор
пр. Независимости, 4, 220030, Минск
Список литературы
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
Рецензия
Просмотров: 448
Послать статью по эл. почте 