10.7: Instrucciones SIMD

Desafortunadamente, es imposible lograr un rendimiento casi máximo en los procesadores populares actuales mientras se usa solo código C portátil. En cambio, solo se puede acceder a una parte significativa de la potencia informática disponible utilizando instrucciones SIMD especializadas (datos múltiples de instrucción única), que realizan la misma operación en paralelo en un vector de datos. Por ejemplo, todos los procesadores “x86” modernos pueden ejecutar instrucciones aritméticas sobre “vectores” de cuatro valores de precisión simple (instrucciones SSE) o dos valores de doble precisión (instrucciones SSE2) a la vez, suponiendo que los operandos están dispuestos consecutivamente en la memoria y satisfacen una restricción de alineación de 16 bytes. Afortunadamente, debido a que casi todo el código de bajo nivel de FFTW es producido por genfft, las instrucciones específicas de la máquina podrían explotarse modificando el generador; las mejoras se propagan automáticamente a todos los códigos de FFTW, y en particular no se limitan a un pequeño conjunto de tamaños como potencias de dos .

Las instrucciones SIMD son superficialmente similares a los “procesadores vectoriales”, que están diseñados para realizar la misma operación en paralelo en todos los elementos de una matriz de datos (un “vector”). El rendimiento de los procesadores vectoriales “tradicionales” fue mejor para vectores largos que se almacenan en ubicaciones de memoria contigua, y se desarrollaron algoritmos especiales para implementar el DFT de manera eficiente en este tipo de hardware. A diferencia de los procesadores vectoriales, sin embargo, la longitud del vector SIMD es pequeña y fija (generalmente 2 o 4). Debido a que los microprocesadores dependen de cachés para el rendimiento, no se pueden usar ingenuamente instrucciones SIMD para simular un algoritmo de vector largo: mientras que en las máquinas vectoriales los vectores largos generalmente producen un mejor rendimiento, el rendimiento de un microprocesador disminuye tan pronto como los vectores de datos exceden la capacidad de la caché. En consecuencia, las instrucciones SIMD se ven mejor como una forma restringida de paralelismo a nivel de instrucción que como un sabor degenerado de paralelismo vectorial, y se requieren diferentes algoritmos de DFT.

La técnica utilizada para explotar las instrucciones SIMD en genfft se entiende más fácilmente para vectores de longitud dos (por ejemplo, SSE2). En este caso, vemos un DFT complejo como un par de DFT reales:

\[\text{DFT}(A+i.B)=\text{DFT}(A)+i.\text{DFT}(B) \nonumber \]

donde\(A\) y\(B\) son dos matrices reales. Nuestro algoritmo calcula las dos DFT reales en paralelo usando instrucciones SIMD, y luego combina las dos salidas de acuerdo con la ecuación. Este algoritmo SIMD tiene dos propiedades importantes. Primero, si los datos se almacenan como una matriz de números complejos, a diferencia de dos matrices reales e imaginarias separadas, las cargas SIMD y las tiendas siempre operan en ubicaciones contiguas correctamente alineadas, incluso si los números complejos en sí tienen una zancada no unitaria. En segundo lugar, debido a que el algoritmo encuentra paralelismo bidireccional en las partes real e imaginaria de una sola DFT (a diferencia de realizar dos DFT en paralelo), podemos paralelizar completamente las DFT de cualquier tamaño, no solo tamaños pares o potencias de 2.

Colaborador

• ContribeeBurrus