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

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

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

Определения

Собирать

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

for (i = 0; i < N; ++i)
    x[i] = y[idx[i]];

Разброс

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

for (i = 0; i < N; ++i)
    y[idx[i]] = x[i];

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

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

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

Процессоры 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. дои : 10.1137/0909019 .
^ Jump up to: ^а ^б Он, Биншэн; Говиндараджу, Нага К.; Ло, Цюн; Смит, Бертон (2007). «Эффективные операции сбора и разброса на графических процессорах». Материалы конференции ACM/IEEE 2007 г. по суперкомпьютерам (PDF) . стр. 1–12. дои : 10.1145/1362622.1362684 . ISBN 9781595937643 . S2CID 2928233 .
^ Кумар, Манодж; Серрано, Маурисио; Морейра, Хосе; Паттнаик, Пратап; Хорн, В.П.; Янн, Джоефон; Танасе, Габриэль (сентябрь 2016 г.). «Эффективная реализация операций сбора и разброса для крупномасштабной графовой аналитики». Конференция IEEE по высокопроизводительным экстремальным вычислениям (HPEC) 2016 . стр. 1–7. дои : 10.1109/HPEC.2016.7761578 . ISBN 978-1-5090-3525-0 . S2CID 10566760 .
^ Стандарт Технического форума BLAS, Глава 3: Разреженный BLAS.
^ Белл, Гордон (25 января 1998 г.). Перспектива Сеймура Крея (Технический отчет).
^ Jump up to: ^а ^б Куссвурм, Дэниел (2022). Современное параллельное программирование на языке C++ и ассемблере: разработка SIMD X86 с использованием AVX, AVX2 и AVX-512 . Апресс Медиа. ISBN 978-1-4842-7917-5 .
^ Хоссейн, доктор Маруф; Сауле, Эрик (9 августа 2021 г.). «Влияние инструкций AVX-512 на проблемы разделения графов». 50-я Международная конференция по параллельной обработке . стр. 1–9. дои : 10.1145/3458744.3473362 . ISBN 9781450384414 . S2CID 237350994 .
^ Jump up to: ^а ^б Чжун, Донг; Шамис, Павел; Цао, Цинлэй; Босилка, Джордж; Сумимото, Синдзи; Миура, Кеничи; Донгарра, Джек (май 2020 г.). «Использование масштабируемого векторного расширения Arm для оптимизации OPEN MPI» (PDF) . 2020 20-й Международный симпозиум IEEE/ACM по кластерным, облачным и интернет-вычислениям (CCGRID) . стр. 222–231. дои : 10.1109/CCGrid49817.2020.00-71 . ISBN 978-1-7281-6095-5 . S2CID 220604878 .
^ «Что такое масштабируемое векторное расширение?» . ARM-разработчик . Проверено 19 ноября 2022 г.
^ Гайнару, Ана; Грэм, Ричард Л.; Поляков Артем; Шайнер, Гилад (25 сентября 2016 г.). «Использование аппаратных возможностей сбора-рассеяния InfiniBand для комплексной оптимизации MPI». Материалы 23-го собрания европейской группы пользователей MPI . стр. 167–179. дои : 10.1145/2966884.2966918 . ISBN 9781450342346 . S2CID 15880901 .

[1] Льюис, Джон Г.; Саймон, Хорст Д. (1 марта 1988 г.). «Влияние аппаратного сбора/рассеяния на разреженное гауссово исключение». Журнал SIAM по научным и статистическим вычислениям . 9 (2): 304–311. дои : 10.1137/0909019 .

[he-2] Jump up to: ^а ^б Он, Биншэн; Говиндараджу, Нага К.; Ло, Цюн; Смит, Бертон (2007). «Эффективные операции сбора и разброса на графических процессорах». Материалы конференции ACM/IEEE 2007 г. по суперкомпьютерам (PDF) . стр. 1–12. дои : 10.1145/1362622.1362684 . ISBN 9781595937643 . S2CID 2928233 .

[3] Кумар, Манодж; Серрано, Маурисио; Морейра, Хосе; Паттнаик, Пратап; Хорн, В.П.; Янн, Джоефон; Танасе, Габриэль (сентябрь 2016 г.). «Эффективная реализация операций сбора и разброса для крупномасштабной графовой аналитики». Конференция IEEE по высокопроизводительным экстремальным вычислениям (HPEC) 2016 . стр. 1–7. дои : 10.1109/HPEC.2016.7761578 . ISBN 978-1-5090-3525-0 . S2CID 10566760 .

[4] Стандарт Технического форума BLAS, Глава 3: Разреженный BLAS.

[5] Белл, Гордон (25 января 1998 г.). Перспектива Сеймура Крея (Технический отчет).

[kusswurm-6] Jump up to: ^а ^б Куссвурм, Дэниел (2022). Современное параллельное программирование на языке C++ и ассемблере: разработка SIMD X86 с использованием AVX, AVX2 и AVX-512 . Апресс Медиа. ISBN 978-1-4842-7917-5 .

[hossain-7] Хоссейн, доктор Маруф; Сауле, Эрик (9 августа 2021 г.). «Влияние инструкций AVX-512 на проблемы разделения графов». 50-я Международная конференция по параллельной обработке . стр. 1–9. дои : 10.1145/3458744.3473362 . ISBN 9781450384414 . S2CID 237350994 .

[zhong-8] Jump up to: ^а ^б Чжун, Донг; Шамис, Павел; Цао, Цинлэй; Босилка, Джордж; Сумимото, Синдзи; Миура, Кеничи; Донгарра, Джек (май 2020 г.). «Использование масштабируемого векторного расширения Arm для оптимизации OPEN MPI» (PDF) . 2020 20-й Международный симпозиум IEEE/ACM по кластерным, облачным и интернет-вычислениям (CCGRID) . стр. 222–231. дои : 10.1109/CCGrid49817.2020.00-71 . ISBN 978-1-7281-6095-5 . S2CID 220604878 .

[9] «Что такое масштабируемое векторное расширение?» . ARM-разработчик . Проверено 19 ноября 2022 г.

[10] Гайнару, Ана; Грэм, Ричард Л.; Поляков Артем; Шайнер, Гилад (25 сентября 2016 г.). «Использование аппаратных возможностей сбора-рассеяния InfiniBand для комплексной оптимизации MPI». Материалы 23-го собрания европейской группы пользователей MPI . стр. 167–179. дои : 10.1145/2966884.2966918 . ISBN 9781450342346 . S2CID 15880901 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]