Recopilar/dispersar (direccionamiento vectorial)

Gather/scatter es un tipo de direccionamiento de memoria que recopila (gathers) o almacena (scatter) datos en múltiples índices de memoria arbitrarios. Ejemplos de su uso incluyen operaciones de álgebra lineal dispersa , ^[¹^] algoritmos de ordenación, transformadas rápidas de Fourier , ^[²^] y algunos problemas de teoría de grafos computacional. ^[³^] Es el equivalente vectorial del direccionamiento indirecto de registros , donde gather implica lecturas indexadas y scatter, escrituras indexadas. Los procesadores vectoriales (y algunas unidades SIMD en las CPU ) tienen soporte de hardware para operaciones gather y scatter, al igual que muchos sistemas de entrada/salida , lo que permite transferir grandes conjuntos de datos a la memoria principal más rápidamente.

El concepto es similar a la E/S vectorizada , también conocida como E/S de dispersión-recolección. Este sistema se diferencia en que se utiliza para mapear múltiples fuentes de datos de estructuras contiguas en un único flujo para lectura o escritura. Un ejemplo común es la escritura de una serie de cadenas , que en la mayoría de los lenguajes de programación se almacenarían en ubicaciones de memoria separadas.

Definiciones

Recolectar

Un vector escasamente poblado $y$ (con dimensión $M$ ) tenencia $N$ Los elementos no vacíos pueden representarse mediante dos vectores densamente poblados de longitud $N$ ; $x$ que contiene los elementos no vacíos de $y$ , y $idx$ dando el índice en $y$ dónde $x$ El elemento de está ubicado. La reunión de $y$ en $x$ , denotado $x\leftarrow y|_{x}$ , asigna $x(i)=y(idx(i))$ con $idx$ habiendo sido ya calculado. ^{[ 4 ]} Suponiendo que no hay alias de punteros entre x[], y[],idx[], una implementación en C es

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

Dispersión

La dispersión escasa, denotada $y|_{x}\leftarrow x$ es la operación inversa. Copia los valores de $x$ en las ubicaciones correspondientes en el vector escasamente poblado $y$ , es decir $y(idx(i))=x(i)$ .

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

Apoyo

Las unidades de dispersión/recolección también formaban parte de la mayoría de las computadoras vectoriales, especialmente la Cray X-MP y sus sucesoras. En este caso, el propósito era almacenar valores de manera eficiente en el recurso limitado de los registros vectoriales. Por ejemplo, la Cray-1 tenía ocho registros vectoriales de 64 palabras, por lo que los datos que contenían valores que no afectaban el resultado, como los ceros en una suma, ocupaban un valioso espacio que podría utilizarse mejor. Al recopilar valores distintos de cero en los registros y dispersar los resultados, los registros podían utilizarse de forma mucho más eficiente, lo que se traducía en un mayor rendimiento. Sin embargo, las instrucciones de referencia de memoria vectorial de la Cray-1 solo podían acceder a la memoria con un "paso constante", lo que permitía un acceso rápido a datos contiguos (paso 1) o mediante algún otro incremento constante. Con la introducción de las instrucciones de recolección y dispersión en la X-MP, esta restricción se eliminó. ^{[ 5 ]} Este diseño básico se copió ampliamente en diseños de supercomputadoras posteriores , especialmente en la variedad de modelos de Japón.

A medida que el diseño de microprocesadores mejoró durante la década de 1990, las CPU comerciales comenzaron a incorporar unidades de procesamiento vectorial. Al principio, estas solían ser sencillas, a veces superponiéndose a los registros de propósito general de la CPU, pero con el tiempo evolucionaron hasta convertirse en sistemas cada vez más potentes que igualaron e incluso superaron a las unidades de las supercomputadoras de gama alta. Para entonces, ya se habían añadido instrucciones de dispersión/recolección a muchos de estos diseños.

Las CPU x86-64 que admiten el conjunto de instrucciones AVX2 pueden recopilar elementos de 32 y 64 bits con desplazamientos de memoria desde una dirección base. Un segundo registro determina si el elemento en particular está cargado y se suprimen los fallos que se producen por accesos a memoria no válidos por parte de elementos enmascarados. ^{[ 6 ]}^{: 503–4} El conjunto de instrucciones AVX-512 también contiene operaciones de dispersión (potencialmente enmascaradas). ^{[ 6 ]}^{: 539}^{[ 7 ]} La extensión vectorial escalable del conjunto de instrucciones ARM incluye operaciones de recopilación y dispersión en elementos de 8, 16, 32 y 64 bits. ^[⁸^]^[⁹^] InfiniBand tiene soporte de hardware para recopilación/dispersión. ^[¹⁰^]

Sin la función de recolección/dispersión a nivel de instrucción, las implementaciones eficientes podrían necesitar ser ajustadas para un rendimiento óptimo, por ejemplo, con precarga ; bibliotecas como OpenMPI podrían proporcionar tales primitivas. ^{[ 2 ]}^{[ 8 ]}

Véase también

Referencias

↑ Lewis, John G.; Simon, Horst D. (1 de marzo de 1988). "El impacto de la recolección/dispersión de hardware en la eliminación gaussiana dispersa". SIAM Journal on Scientific and Statistical Computing . 9 (2): 304– 311. doi : 10.1137/0909019 .
1 2 He, Bingsheng; Govindaraju, Naga K.; Luo, Qiong; Smith, Burton (2007). "Operaciones eficientes de recopilación y dispersión en procesadores gráficos". Actas de la conferencia ACM/IEEE de 2007 sobre supercomputación (PDF) . págs. 1–12 . doi : 10.1145/1362622.1362684 . ISBN 9781595937643. S2CID 2928233 .
↑ Kumar, Manoj; Serrano, Mauricio; Moreira, Jose; Pattnaik, Pratap; Horn, WP; Jann, Joefon; Tanase, Gabriel (septiembre de 2016). "Implementación eficiente de operaciones de dispersión-recolección para análisis de grafos a gran escala". 2016 IEEE High Performance Extreme Computing Conference (HPEC) . págs. 1–7 . doi : 10.1109/HPEC.2016.7761578 . ISBN 978-1-5090-3525-0. S2CID 10566760 .
↑ Estándar del Foro Técnico BLAS, Capítulo 3: BLAS disperso.
↑ Bell, Gordon (25 de enero de 1998). Una perspectiva de Seymour Cray (Informe técnico).
1 2 Kusswurm, Daniel (2022). Programación paralela moderna con C++ y lenguaje ensamblador : desarrollo SIMD X86 usando AVX, AVX2 y AVX-512 . Apress Media. ISBN 978-1-4842-7917-5.
↑ Hossain, Md Maruf; Saule, Erik (9 de agosto de 2021). «Impacto de las instrucciones AVX-512 en los problemas de partición de grafos». 50.ª Conferencia Internacional sobre Procesamiento Paralelo, Taller . págs. 1-9 . doi : 10.1145/3458744.3473362 . ISBN 9781450384414. S2CID 237350994 .
1 2 Zhong, Dong; Shamis, Pavel; Cao, Qinglei; Bosilca, George; Sumimoto, Shinji; Miura, Kenichi; Dongarra, Jack (mayo de 2020). "Uso de la extensión de vector escalable de Arm para optimizar OPEN MPI" (PDF) . 2020 20.º Simposio Internacional IEEE/ACM sobre Computación en Clúster, Nube e Internet (CCGRID) . págs. 222–231 . doi : 10.1109/CCGrid49817.2020.00-71 . ISBN 978-1-7281-6095-5. S2CID 220604878 .
↑ "¿Qué es la extensión vectorial escalable?" . ARM Developer . Consultado el 19 de noviembre de 2022 .
↑ Gainaru, Ana; Graham, Richard L.; Polyakov, Artem; Shainer, Gilad (25 de septiembre de 2016). «Uso de las capacidades de recolección-dispersión de hardware InfiniBand para optimizar MPI All-to-All». Actas de la 23.ª Reunión del Grupo Europeo de Usuarios de MPI . págs. 167–179 . doi : 10.1145/2966884.2966918 . ISBN 9781450342346. S2CID 15880901 .

[1] Lewis, John G.; Simon, Horst D. (1 de marzo de 1988). "El impacto de la recolección/dispersión de hardware en la eliminación gaussiana dispersa". SIAM Journal on Scientific and Statistical Computing . 9 (2): 304– 311. doi : 10.1137/0909019 .

[he-2] 1 2 He, Bingsheng; Govindaraju, Naga K.; Luo, Qiong; Smith, Burton (2007). "Operaciones eficientes de recopilación y dispersión en procesadores gráficos". Actas de la conferencia ACM/IEEE de 2007 sobre supercomputación (PDF) . págs. 1–12 . doi : 10.1145/1362622.1362684 . ISBN 9781595937643. S2CID 2928233 .

[3] Kumar, Manoj; Serrano, Mauricio; Moreira, Jose; Pattnaik, Pratap; Horn, WP; Jann, Joefon; Tanase, Gabriel (septiembre de 2016). "Implementación eficiente de operaciones de dispersión-recolección para análisis de grafos a gran escala". 2016 IEEE High Performance Extreme Computing Conference (HPEC) . págs. 1–7 . doi : 10.1109/HPEC.2016.7761578 . ISBN 978-1-5090-3525-0. S2CID 10566760 .

[4] Estándar del Foro Técnico BLAS, Capítulo 3: BLAS disperso.

[5] Bell, Gordon (25 de enero de 1998). Una perspectiva de Seymour Cray (Informe técnico).

[kusswurm-6] 1 2 Kusswurm, Daniel (2022). Programación paralela moderna con C++ y lenguaje ensamblador : desarrollo SIMD X86 usando AVX, AVX2 y AVX-512 . Apress Media. ISBN 978-1-4842-7917-5.

[hossain-7] Hossain, Md Maruf; Saule, Erik (9 de agosto de 2021). «Impacto de las instrucciones AVX-512 en los problemas de partición de grafos». 50.ª Conferencia Internacional sobre Procesamiento Paralelo, Taller . págs. 1-9 . doi : 10.1145/3458744.3473362 . ISBN 9781450384414. S2CID 237350994 .

[zhong-8] 1 2 Zhong, Dong; Shamis, Pavel; Cao, Qinglei; Bosilca, George; Sumimoto, Shinji; Miura, Kenichi; Dongarra, Jack (mayo de 2020). "Uso de la extensión de vector escalable de Arm para optimizar OPEN MPI" (PDF) . 2020 20.º Simposio Internacional IEEE/ACM sobre Computación en Clúster, Nube e Internet (CCGRID) . págs. 222–231 . doi : 10.1109/CCGrid49817.2020.00-71 . ISBN 978-1-7281-6095-5. S2CID 220604878 .

[9] "¿Qué es la extensión vectorial escalable?" . ARM Developer . Consultado el 19 de noviembre de 2022 .

[10] Gainaru, Ana; Graham, Richard L.; Polyakov, Artem; Shainer, Gilad (25 de septiembre de 2016). «Uso de las capacidades de recolección-dispersión de hardware InfiniBand para optimizar MPI All-to-All». Actas de la 23.ª Reunión del Grupo Europeo de Usuarios de MPI . págs. 167–179 . doi : 10.1145/2966884.2966918 . ISBN 9781450342346. S2CID 15880901 .

[

[

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[

[

[