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.
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
para ( i = 0 ; i < N ; ++ i ) x [ i ] = y [ idx [ i ]]; 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 .
para ( i = 0 ; i < N ; ++ i ) y [ idx [ i ]] = x [ i ]; 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 sobre el resultado, como los ceros en una suma, estaban utilizando un espacio valioso que podría utilizarse mejor. Al reunir valores distintos de cero en los registros y dispersar los resultados de nuevo, los registros podían usarse 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 recolección y dispersión en elementos de 8, 16, 32 y 64 bits. [8] [9] InfiniBand tiene soporte de hardware para recolecció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]