Собрать/рассеять (векторная адресация)

Сбор/разброс — это тип адресации памяти , который одновременно собирает (собирает) данные из нескольких произвольных индексов или сохраняет (разбрасывает) их. Примерами его использования являются разреженные операции линейной алгебры , ^[1] алгоритмы сортировки, быстрые преобразования Фурье , ^[2] и некоторые задачи теории вычислительных графов. ^[3] Это векторный эквивалент косвенной адресации регистров , при этом сбор включает индексированные чтения, а разброс — индексированные записи. Векторные процессоры (и некоторые блоки SIMD в ЦП ) имеют аппаратную поддержку для операций сбора и разброса, как и многие системы ввода/вывода , что позволяет быстрее передавать большие наборы данных в основную память .

Концепция несколько похожа на векторный ввод-вывод , который иногда также называют вводом-выводом типа scatter-gather. Эта система отличается тем, что она используется для отображения нескольких источников данных из смежных структур в один поток для чтения или записи. Распространенным примером является запись серии строк , которые в большинстве языков программирования будут храниться в отдельных ячейках памяти.

Определения

Собирать

Редко заполненный вектор, содержащий непустые элементы, может быть представлен двумя плотно заполненными векторами длины ; содержащими непустые элементы , и дающими индекс в , где расположен элемент . Сборка в , обозначенная , присваивает с уже вычисленным. ^[4] Предполагая, что нет псевдонимов указателей между x[], y[], idx[], реализация C выглядит следующим образом: $у$ $N$ $N$ $x$ $у$ $idx$ $у$ $x$ $у$ $x$ $x\leftarrow y|_{x}$ $x(i)=y(idx(i))$ $idx$

для ( i = 0 ; i < N ; ++ i ) x [ i ] = y [ idx [ i ]];

Разброс

Разреженный разброс, обозначенный как , является обратной операцией. Он копирует значения в соответствующие места в разреженно заполненном векторе , т.е. . $y|_{x}\leftarrow x$ $x$ $у$ $y(idx(i))=x(i)$

для ( i = 0 ; i < N ; ++ i ) y [ idx [ i ]] = x [ i ];

Поддерживать

Устройства Scatter/gather также были частью большинства векторных компьютеров, в частности Cray-1 . В этом случае целью было эффективное хранение значений в ограниченном ресурсе векторных регистров. Например, Cray-1 имел восемь векторных регистров по 64 слова, поэтому данные, содержащие значения, не влияющие на результат, например нули при сложении, занимали ценное пространство, которое можно было бы использовать с большей пользой. Собирая ненулевые значения в регистрах и рассеивая результаты обратно, регистры можно было использовать гораздо эффективнее, что приводило к более высокой производительности. Такие машины обычно реализовывали две модели доступа: scatter/gather и «stride», последняя была разработана для быстрой загрузки смежных данных. ^[5] Эта базовая схема широко копировалась в более поздних конструкциях суперкомпьютеров , особенно в различных моделях из Японии.

По мере совершенствования конструкции микропроцессоров в 1990-х годах в массовые ЦП начали добавляться векторные процессоры. Сначала они были простыми, иногда перекрывая регистры общего назначения ЦП, но со временем они превратились во все более мощные системы, которые соответствовали, а затем и превосходили блоки в высокопроизводительных суперкомпьютерах. К этому времени во многие из этих конструкций были добавлены инструкции scatter/gather.

Процессоры x86-64 , поддерживающие набор инструкций AVX2, могут собирать 32- и 64-битные элементы со смещениями памяти от базового адреса. Второй регистр определяет, загружен ли конкретный элемент, и подавляются сбои, возникающие из-за недопустимого доступа к памяти замаскированными элементами. ^[6]^{: 503–4} Набор инструкций AVX-512 также содержит (потенциально замаскированные) операции рассеивания. ^[6]^{: 539}^[7]Масштабируемое векторное расширение набора инструкций ARM включает операции сбора и рассеивания на 8-, 16-, 32- и 64-битных элементах. ^[8][ ^9]InfiniBand имеет аппаратную поддержку сбора/рассеивания. ^[10]

Без сбора/рассеивания на уровне инструкций эффективные реализации могут нуждаться в настройке для оптимальной производительности, например, с предварительной выборкой ; библиотеки, такие как OpenMPI, могут предоставлять такие примитивы. ^[2]^[8]

Смотрите также

Ссылки

^ Льюис, Джон Г.; Саймон, Хорст Д. (1 марта 1988 г.). «Влияние аппаратного сбора/рассеивания на разреженное исключение Гаусса». Журнал SIAM по научным и статистическим вычислениям . 9 (2): 304–311. doi :10.1137/0909019.
^ ab He, Bingsheng; Govindaraju, Naga K.; Luo, Qiong; Smith, Burton (2007). "Эффективные операции сбора и рассеивания на графических процессорах". Труды конференции ACM/IEEE 2007 года по суперкомпьютерам (PDF) . стр. 1–12. doi :10.1145/1362622.1362684. ISBN 9781595937643. S2CID 2928233.
^ Кумар, Манодж; Серрано, Маурисио; Морейра, Хосе; Патнаик, Пратап; Хорн, ВП; Янн, Джофон; Танасе, Габриэль (сентябрь 2016 г.). «Эффективная реализация операций сбора-разброса для крупномасштабной графовой аналитики». Конференция IEEE по высокопроизводительным экстремальным вычислениям (HPEC) 2016 г. стр. 1–7. doi :10.1109/HPEC.2016.7761578. ISBN 978-1-5090-3525-0. S2CID 10566760.
^ Стандарт Технического форума BLAS, Глава 3: Разреженный BLAS.
↑ Белл, Гордон (25 января 1998 г.). Перспектива Сеймура Крэя (технический отчет).
^ ab Kusswurm, Daniel (2022). Современное параллельное программирование на языке C++ и ассемблера: разработка X86 SIMD с использованием AVX, AVX2 и AVX-512 . Apress Media. ISBN 978-1-4842-7917-5.
^ Хоссейн, Мд Маруф; Сауле, Эрик (9 августа 2021 г.). «Влияние инструкций AVX-512 на проблемы разбиения графов». 50-я Международная конференция по параллельной обработке, семинар . стр. 1–9. doi :10.1145/3458744.3473362. ISBN 9781450384414. S2CID 237350994.
^ ab Zhong, Dong; Shamis, Pavel; Cao, Qinglei; Bosilca, George; Sumimoto, Shinji; Miura, Kenichi; Dongarra, Jack (май 2020 г.). «Использование масштабируемого векторного расширения Arm для оптимизации OPEN MPI» (PDF) . 2020 20-й Международный симпозиум IEEE/ACM по кластерным, облачным и интернет-вычислениям (CCGRID) . стр. 222–231. doi :10.1109/CCGrid49817.2020.00-71. ISBN 978-1-7281-6095-5. S2CID 220604878.
^ «Что такое масштабируемое векторное расширение?». Разработчик ARM . Получено 19 ноября 2022 г.
^ Gainaru, Ana; Graham, Richard L.; Polyakov, Artem; Shainer, Gilad (25 сентября 2016 г.). «Использование InfiniBand Hardware Gather-Scatter Capabilities для оптимизации MPI All-to-All». Труды 23-й Европейской встречи группы пользователей MPI . стр. 167–179. doi :10.1145/2966884.2966918. ISBN 9781450342346. S2CID 15880901.