17 Лиходед Н. А. параллельные вычисления графический процессор бродкаст пространственная локальность 2022 2022-10-12 10.29235/1561-2430-2022-58-3-292-299 Известия Национальной академии наук Беларуси. Серия физико-математических наук В качестве компьютера, на котором требуется реализовать параллельную версию алгоритма, рассматриваются графические процессоры (GPU). Множество операций алгоритма для выполнения на GPU должно быть разбито на потоки вычислений; потоки должны быть сгруппированы в блоки вычислений, выполняющиеся атомарно на мультипроцессорах. Потоки одного блока выполняются на мультипроцессоре частями-пулами, называемыми варпами (warps); потоки варпа выполняются одновременно. Эффективность параллельного алгоритма зависит от способа размещения данных в памяти GPU. Если все потоки варпа запрашивают при выполнении текущего оператора один и тот же элемент массива, то его желательно размещать в разделяемой или константной памяти GPU; в этом случае его распределение по ядрам мультипроцессора реализуется фактически посредством бродкаста (broadcast). Если потоки варпа запрашивают близко расположенные в памяти данные, то в этом случае имеет место их пространственная локальность, что делает целесообразным размещение этих данных в текстурной памяти GPU. Реализация бродкаста или пространственной локальности за счет размещения данных в памяти соответствующего вида позволяет существенно снизить трафик при обмене ими между уровнями памяти графического процессора. В работе сформулированы и доказаны необходимые и достаточные условия, при которых возможно выполнение бродкаста или имеет место пространственная локальность данных. Условия даны в терминах функций, определяющих использование элементов массивов на вхождениях в операторы алгоритма, и функций, задающих информационные зависимости алгоритма. Полученные результаты могут быть использованы для оптимизации параллельных алгоритмов при их реализации на GPU. https://www.academjournals.by/publication/12738 https://www.academjournals.by/files/12704