Reunir/dispersar (direccionamiento vectorial)

Tipo de direccionamiento de memoria

Reunir/dispersar es un tipo de direccionamiento de memoria que al mismo tiempo recopila (reúne) o almacena (dispersa) datos en múltiples índices arbitrarios. Ejemplos de su uso incluyen operaciones dispersas de álgebra lineal , ^[1] algoritmos de clasificación, 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 , en el que la recopilación implica lecturas indexadas y las escrituras indexadas y dispersas. Los procesadores vectoriales (y algunas unidades SIMD en las CPU ) tienen soporte de hardware para operaciones de recopilación y dispersión, 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 a la E/S vectorial , que a veces también se denomina E/S de dispersión. Este sistema se diferencia en que se utiliza para mapear múltiples fuentes de datos de estructuras contiguas en una única secuencia 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 de longitud densamente poblados ; que contiene los elementos no vacíos de y proporciona el índice donde se encuentra el elemento. La reunión de en , denotada , asigna haber ya sido calculada. ^[4] Suponiendo que no haya alias de puntero entre x[], y[],idx[], una implementación en 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 escasa que se indica 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/reunió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, el Cray-1 tenía ocho registros vectoriales de 64 palabras, por lo que los datos que contenían valores que no tenían ningún efecto en el resultado, como ceros en una suma, consumían un espacio valioso que sería mejor utilizado. Al reunir valores distintos de cero en los registros y dispersar los resultados, los registros podrían usarse de manera mucho más eficiente, lo que conduciría a un mayor rendimiento. Estas máquinas generalmente implementaban dos modelos de acceso, dispersión/reunión y "zancada", 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 básicas comenzaron a agregar unidades de procesamiento vectorial. Al principio, estos tendían a ser simples, 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 y luego superaron las unidades de las supercomputadoras de alta gama. En ese momento, se habían agregado instrucciones de dispersión/reunió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 compensaciones 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 no válidos a la memoria 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. ^{[8] [9]} InfiniBand tiene soporte de hardware para recopilación/dispersión. ^[10]

Sin recopilación/dispersión a nivel de instrucción, es posible que sea necesario ajustar las implementaciones eficientes para lograr un rendimiento óptimo, por ejemplo, con captación previa ; bibliotecas como OpenMPI pueden proporcionar tales primitivas. ^{[2] [8]}

Ver 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 acumulación/dispersión de hardware en la eliminación gaussiana escasa". Revista SIAM de Computación Científica y Estadística . 9 (2): 304–311. doi :10.1137/0909019.
2. Él, 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, José; Pattnaik, Pratap; Cuerno, WP; Jann, Joefon; Tanase, Gabriel (septiembre de 2016). "Implementación eficiente de operaciones de dispersión para análisis de gráficos a gran escala". Conferencia de Computación Extrema de Alto Rendimiento (HPEC) de IEEE 2016 . 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).
6. Kusswurm, Daniel (2022). Programación paralela moderna con C++ y lenguaje ensamblador: desarrollo SIMD X86 utilizando AVX, AVX2 y AVX-512 . Medios de prensa. ISBN 978-1-4842-7917-5.
7. Hossain, doctor Maruf; Saule, Erik (9 de agosto de 2021). "Impacto de las instrucciones AVX-512 en los problemas de partición de gráficos". Taller de la 50ª Conferencia Internacional sobre Procesamiento Paralelo . págs. 1–9. doi :10.1145/3458744.3473362. ISBN 9781450384414. S2CID  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ústeres, en la nube y en 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?". Desarrollador ARM . Consultado el 19 de noviembre de 2022 .
10. Gainaru, Ana; Graham, Richard L.; Poliakov, Artem; Shainer, Gilad (25 de septiembre de 2016). "Uso de las capacidades de recopilación y dispersión del hardware InfiniBand para optimizar MPI en su totalidad". 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.