¿Qué es la "vectorización"?

190

Varias veces, he encontrado este término en matlab, fortran ... algún otro ... pero nunca he encontrado una explicación de qué significa y qué hace. Entonces, estoy preguntando, ¿qué es la vectorización y qué significa, por ejemplo, que "un ciclo está vectorizado"?

Thomas Geritzma
fuente
1
@geoffspear El enlace parece haberse movido a en.wikipedia.org/wiki/Array_programming
Me gusta codificar el

Respuestas:

225

Muchas CPU tienen conjuntos de instrucciones "vectoriales" o "SIMD" que aplican la misma operación simultáneamente a dos, cuatro o más datos. Los chips x86 modernos tienen las instrucciones SSE, muchos chips PPC tienen las instrucciones "Altivec", e incluso algunos chips ARM tienen un conjunto de instrucciones vectoriales, llamado NEON.

La "vectorización" (simplificada) es el proceso de reescribir un bucle para que, en lugar de procesar un solo elemento de una matriz N veces, procese (digamos) 4 elementos de la matriz simultáneamente N / 4 veces.

(Elegí 4 porque es lo que es más probable que el hardware moderno admita directamente; el término "vectorización" también se usa para describir una transformación de software de nivel superior en la que simplemente puede abstraer el bucle por completo y simplemente describir el funcionamiento en matrices en lugar de los elementos que los comprende)


La diferencia entre la vectorización y el desenrollado del bucle: considere el siguiente bucle muy simple que agrega los elementos de dos matrices y almacena los resultados en una tercera matriz.

for (int i=0; i<16; ++i)
    C[i] = A[i] + B[i];

Desenrollar este bucle lo transformaría en algo como esto:

for (int i=0; i<16; i+=4) {
    C[i]   = A[i]   + B[i];
    C[i+1] = A[i+1] + B[i+1];
    C[i+2] = A[i+2] + B[i+2];
    C[i+3] = A[i+3] + B[i+3];
}

Vectorizarlo, por otro lado, produce algo como esto:

for (int i=0; i<16; i+=4)
    addFourThingsAtOnceAndStoreResult(&C[i], &A[i], &B[i]);

Donde "addFourThingsAtOnceAndStoreResult" es un marcador de posición para cualquier intrínseco (s) que su compilador use para especificar instrucciones vectoriales. Tenga en cuenta que algunos compiladores pueden vectorizar automáticamente bucles muy simples como este, que a menudo se pueden habilitar a través de una opción de compilación. Los algoritmos más complejos aún requieren la ayuda del programador para generar un buen código vectorial.

Stephen Canon
fuente
11
¿Cuál es la diferencia entre esto y desenrollar / desenrollar bucles?
Jeremy Powell
1
¿No es cierto que un compilador tendría un trabajo más fácil auto-vectorizando el ciclo desenrollado?
Nikos Athanasiou
@NikosAthanasiou: Es plausible, pero en general un compilador debería ser capaz de autovectorizar cualquiera de los bucles, ya que ambos son bastante simples.
Stephen Canon
1
@StephenCanon, ¿cómo se puede verificar si algunas líneas se han vectorizado o no? Si uno usara objdump, ¿qué buscaría en la salida de objdump?
user1823664
3
@Shuklaswag: la vectorización es algo que los compiladores pueden hacer por usted, pero también es algo que los programadores hacen explícitamente. El sistema operativo no está involucrado.
Stephen Canon
32

Vectorización es el término para convertir un programa escalar en un programa vectorial. Los programas vectorizados pueden ejecutar múltiples operaciones desde una sola instrucción, mientras que el escalar solo puede operar en pares de operandos a la vez.

De wikipedia :

Enfoque escalar:

for (i = 0; i < 1024; i++)
{
   C[i] = A[i]*B[i];
}

Enfoque vectorizado:

for (i = 0; i < 1024; i+=4)
{
   C[i:i+3] = A[i:i+3]*B[i:i+3];
}
Anders
fuente
¿No es eso en esencia lo mismo que el enfoque escalar? Su sintaxis y avance de bucle es diferente, pero debajo todavía lo está multiplicando 4 veces. Pero de alguna manera será más rápido, probablemente la CPU tiene instrucciones que hacen un truco llamado Vectorización.
mskw
Parece que responderé mi propia pregunta aquí. La sintaxis en el enfoque de vectorización cuando el compilador ve eso, lo traducirá en instrucciones de CPU optimizadas que multiplican los vectores. Como SIMD.
mskw
10

Se refiere a la capacidad de realizar operaciones matemáticas únicas en una lista, o "vector", de números en un solo paso. Lo ves a menudo con Fortran porque eso está asociado con la informática científica, que está asociada con la supercomputación, donde apareció por primera vez la aritmética vectorizada. Hoy en día, casi todas las CPU de escritorio ofrecen alguna forma de aritmética vectorizada, a través de tecnologías como SSE de Intel. Las GPU también ofrecen una forma de aritmética vectorizada.

Warren Young
fuente
7

La vectorización se usa en gran medida en la informática científica, donde se deben procesar grandes cantidades de datos de manera eficiente.

En una aplicación de programación real, sé que se usa en NUMPY (no estoy seguro de otra cosa).

Numpy (paquete para computación científica en python), usa la vectorización para la manipulación rápida de la matriz n-dimensional, que generalmente es más lenta si se realiza con opciones de python incorporadas para manejar matrices.

aunque hay toneladas de explicación por ahí, AQUÍ ESTÁ LA VECTORIZACIÓN DEFINIDA COMO EN LA PÁGINA DE NUMPIA DOCUMENTACIÓN

La vectorización describe la ausencia de cualquier bucle explícito, indexación, etc., en el código; estas cosas están ocurriendo, por supuesto, solo "detrás de escena" en un código C precompilado optimizado. El código vectorizado tiene muchas ventajas, entre las que se encuentran:

  1. el código vectorizado es más conciso y más fácil de leer

  2. menos líneas de código generalmente significa menos errores

  3. el código se asemeja más a la notación matemática estándar (lo que facilita, por lo general, codificar correctamente construcciones matemáticas)

  4. la vectorización da como resultado más código "Pitónico". Sin vectorización, nuestro código estaría lleno de bucles ineficientes y difíciles de leer.

mal programador
fuente
4

Vectorización, en palabras simples, significa optimizar el algoritmo para que pueda utilizar las instrucciones SIMD en los procesadores.

AVX, AVX2 y AVX512 son los conjuntos de instrucciones (intel) que realizan la misma operación en múltiples datos en una sola instrucción. por ej. AVX512 significa que puede operar con 16 valores enteros (4 bytes) a la vez. Lo que eso significa es que si tiene un vector de 16 enteros y desea duplicar ese valor en cada número entero y luego agregarle 10. Puede cargar valores en el registro general [a, b, c] 16 veces y realizar la misma operación o puede realizar la misma operación cargando los 16 valores en los registros SIMD [xmm, ymm] y realizar la operación una vez. Esto permite acelerar el cálculo de los datos vectoriales.

En la vectorización, usamos esto para nuestra ventaja, al remodelar nuestros datos para que podamos realizar operaciones SIMD en él y acelerar el programa.

El único problema con la vectorización son las condiciones de manejo. Porque las condiciones ramifican el flujo de ejecución. Esto se puede manejar enmascarando. Al modelar la condición en una operación aritmética. p.ej. si queremos agregar 10 al valor si es mayor que 100. podemos hacerlo.

if(x[i] > 100) x[i] += 10; // this will branch execution flow.

o podemos modelar la condición en operación aritmética creando un vector de condición c,

c[i] = x[i] > 100; // storing the condition on masking vector
x[i] = x[i] + (c[i] & 10) // using mask

Sin embargo, este es un ejemplo muy trivial ... por lo tanto, c es nuestro vector de enmascaramiento que usamos para realizar operaciones binarias en función de su valor. Esto evita la ramificación del flujo de ejecución y permite la vectorización.

La vectorización es tan importante como la paralelización. Por lo tanto, debemos utilizarlo lo más posible. Todos los procesadores modernos tienen instrucciones SIMD para cargas de trabajo informáticas pesadas. Podemos optimizar nuestro código para usar estas instrucciones SIMD usando vectorización, esto es similar a la paralelización de nuestro código para que se ejecute en múltiples núcleos disponibles en procesadores modernos.

Me gustaría irme con la mención de OpenMP, que me permite vectorizar el código usando pragmas. Lo considero un buen punto de partida. Lo mismo puede decirse de OpenACC.

Cola de mercado
fuente
0

Por la gente de Intel, creo que es fácil de entender.

La vectorización es el proceso de convertir un algoritmo de operar en un solo valor a la vez a operar en un conjunto de valores a la vez . Las CPU modernas brindan soporte directo para operaciones vectoriales donde se aplica una sola instrucción a múltiples datos (SIMD).

Por ejemplo, una CPU con un registro de 512 bits podría contener 16 dobles de precisión simple de 32 bits y hacer un solo cálculo.

16 veces más rápido que ejecutar una sola instrucción a la vez. Combinar esto con subprocesos y CPU de varios núcleos conduce a ganancias de rendimiento de órdenes de magnitud.

Enlace https://software.intel.com/en-us/articles/vectorization-a-key-tool-to-improve-performance-on-modern-cpus

En Java hay una opción para que esto se incluya en Jdk 15 de 2020 o tarde en JDK 16 en 2021.

https://bugs.openjdk.java.net/browse/JDK-8201271

chiperortiz
fuente
-4

Ver las dos respuestas anteriores. Solo quería agregar que la razón para querer hacer la vectorización es que estas operaciones pueden realizarse fácilmente en paralelo por supercomputadoras y multiprocesadores, produciendo una gran ganancia de rendimiento. En las computadoras de un solo procesador no habrá ganancia de rendimiento.

Larry Watanabe
fuente
12
"En las computadoras con un solo procesador no habrá ganancia de rendimiento": no es cierto. La mayoría de los procesadores modernos tienen soporte de hardware (limitado) para la vectorización (SSE, Altivec. Etc., como lo llama la stephentyrone), lo que puede proporcionar una aceleración significativa cuando se usa.
sleske
gracias, olvidé que la paralelización se puede hacer también a ese nivel.
Larry Watanabe