Recopilar/dispersar (direccionamiento vectorial)

Tipo de direccionamiento de memoria

Gather/scatter es un tipo de direccionamiento de memoria que recopila (reúne) o almacena (dispersa) datos en múltiples índices arbitrarios. Algunos ejemplos de su uso incluyen operaciones de álgebra lineal dispersa , ^[1] algoritmos de ordenamiento, transformadas rápidas de Fourier , ^[2] y algunos problemas de teoría de grafos computacionales. ^[3] Es el equivalente vectorial del direccionamiento indirecto de registros , con gather que implica lecturas indexadas y scatter, escrituras indexadas. Los procesadores vectoriales (y algunas unidades SIMD en CPU ) tienen soporte de hardware para operaciones de 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 algo similar al de E/S vectorizada , que a veces también se denomina 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 solo flujo para lectura o escritura. Un ejemplo común es escribir 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 que contiene elementos no vacíos se puede representar mediante dos vectores densamente poblados de longitud ; que contienen los elementos no vacíos de , y que dan el índice en donde se encuentra el elemento de . La agrupación de into , denotada , asigna con habiéndose calculado ya. ^[4] Suponiendo que no hay alias de puntero entre x[], y[], idx[], una implementación de C es ${\displaystyle y}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle idx}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x\leftarrow y|_{x}}$ ${\displaystyle x(i)=y(idx(i))}$ ${\displaystyle idx}$

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

Dispersión

La dispersión dispersa, denotada como , es la operación inversa. Copia los valores de en las ubicaciones correspondientes en el vector escasamente poblado , es decir . ${\displaystyle y|_{x}\leftarrow x}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle 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, en particular la Cray-1 . 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 tenían efecto en el resultado, como los ceros en una suma, estaban utilizando un espacio valioso que se podría utilizar mejor. Al reunir valores distintos de cero en los registros y dispersar los resultados de nuevo, los registros se podían utilizar de manera mucho más eficiente, lo que conducía a un mayor rendimiento. Estas máquinas generalmente implementaban dos modelos de acceso, dispersión/recolección y "paso", este último diseñado para cargar rápidamente datos contiguos. ^[5] Este diseño básico fue ampliamente copiado en diseños de supercomputadoras posteriores , especialmente en la variedad de modelos de Japón.

A medida que el diseño de los microprocesadores mejoró durante la década de 1990, las CPU de consumo masivo comenzaron a incorporar unidades de procesamiento vectorial. Al principio, estas tendían a ser simples, a veces superpuestas 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 y luego superaron a las unidades de las supercomputadoras de alta gama. Para entonces, se habían agregado instrucciones de dispersión/recolección a muchos de estos diseños.

Las CPU x86-64 que admiten el conjunto de instrucciones AVX2 pueden reunir 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 a partir de accesos a memoria no válidos por 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 de vector escalable del conjunto de instrucciones ARM incluye operaciones de reunión y dispersión en elementos de 8, 16, 32 y 64 bits. ^{[8] [9]} InfiniBand tiene soporte de hardware para reunión/dispersión. ^[10]

Sin recopilación/dispersión a nivel de instrucción, puede ser necesario ajustar las implementaciones eficientes para lograr un rendimiento óptimo, por ejemplo, con precarga ; bibliotecas como OpenMPI pueden proporcionar dichas primitivas. ^{[2] [8]}

Véase también

• SIMD
• Vectorización
• Núcleo de cómputo
• Patrón de acceso a la memoria

Referencias

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". Revista SIAM sobre computación científica y estadística . 9 (2): 304–311. doi :10.1137/0909019.
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.S2CID2928233  .​
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 gráficos a gran escala". Conferencia de computación extrema de alto rendimiento IEEE 2016 (HPEC) . pp. 1–7. doi :10.1109/HPEC.2016.7761578. ISBN . 978-1-5090-3525-0.S2CID10566760  .​
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).
6. Kusswurm, Daniel (2022). Programación paralela moderna con C++ y lenguaje ensamblador: desarrollo de SIMD X86 con AVX, AVX2 y AVX-512 . Apress Media. ISBN 978-1-4842-7917-5.
7. Hossain, Md Maruf; Saule, Erik (9 de agosto de 2021). "Impacto de las instrucciones AVX-512 en los problemas de particionamiento de gráficos". Taller de la 50.ª Conferencia Internacional sobre Procesamiento Paralelo . págs. 1–9. doi :10.1145/3458744.3473362. ISBN 9781450384414. Número de identificación del sujeto  237350994.
8. Zhong, Dong; Shamis, Pavel; Cao, Qinglei; Bosilca, George; Sumimoto, Shinji; Miura, Kenichi; Dongarra, Jack (mayo de 2020). "Uso de la extensión vectorial escalable de Arm para optimizar OPEN MPI" (PDF) . 2020 20.º Simposio internacional IEEE/ACM sobre computación en clúster, en la nube e Internet (CCGRID) . págs. 222–231. doi :10.1109/CCGrid49817.2020.00-71. ISBN . 978-1-7281-6095-5.S2CID220604878  .​
9. "¿Qué es la extensión de vector 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 capacidades de recopilación y dispersión de hardware InfiniBand para optimizar MPI All-to-All". Actas de la 23.ª reunión del grupo de usuarios de MPI europeo . págs. 167–179. doi :10.1145/2966884.2966918. ISBN . 9781450342346.S2CID15880901  .​