Transformada rápida de Fourier para procesar imágenes en DirectX* 11

Descargar PDF

Descargar el ejemplo de código de FFT

Introducción

La transformada rápida de Fourier (FFT) es una implementación de la transformada de Fourier discreta (DFT) que utiliza un enfoque que podríamos describir con la frase “divide y triunfarás”. La transformada de Fourier discreta puede transformar cualquier señal discreta, como por ejemplo una imagen, hacia y desde el dominio de la frecuencia. Estando ya en el dominio de la frecuencia, muchos efectos que por lo general son costosos en el dominio de la imagen, se vuelven triviales y nada costosos. Las transformaciones entre el dominio de la imagen y el de la frecuencia pueden generar una sobrecarga considerable. En este ejemplo se muestra una FFT que usa sombreadores de cálculo (compute shaders) y memoria local compartida (SLM) para mejorar el rendimiento mediante la reducción del ancho de banda de memoria.

También se analizan dos técnicas para realizar la transformada rápida de Fourier. La primera técnica se llama UAV, que hace saltar datos repetidamente entre vistas de acceso no ordenadas (Unordered Access Views, UAV). La segunda técnica, SLM (siglas en inglés de “memoria local compartida”) es un método que apunta más a la eficiencia del ancho de banda de memoria y permite obtener mejoras de rendimiento considerables en cuellos de botella de ancho de banda de memoria.

El ejemplo anterior, Implementación de transformada rápida de Fourier para procesar imágenes en DirectX 10, pone en práctica la técnica UAV con sombreadores de píxeles. Se puede consultar ese ejemplo para conocer información relacionada con la técnica UAV y el algoritmo de FFT en general.

Técnica UAV

La técnica UAV, descrita en el ejemplo original, realiza pasadas que se conocen como pasadas de mariposa. Cada pasada exige hacer un muestreo de las texturas de entrada reales e imaginarias dos veces y escribir en las texturas de salida reales e imaginarias una vez. Según la arquitectura de caché que se utilice, este método puede causar problemas de rendimiento por hiperpaginación del caché. La Figura 1 muestra las llamadas de distribución (dispatch calls) que requiere la técnica UAV.

Graphics Performance Analyzer
Figura 1: Llamadas de distribución de sombreador de cálculo con el uso de la técnica UAV, capturadas en Graphics Performance Analyzer (GPA)

Técnica SLM

La técnica SLM emplea una sola distribución por cada pasada de eje de la FFT. Distribuye un grupo de subprocesos (thread group) por cada fila de la textura, y cada grupo de subprocesos crea un subproceso para por columna de la textura. Cada fila está representada por un grupo de subprocesos y cada píxel de la fila es procesado por un único subproceso. Cada subproceso realiza todas las pasadas de mariposa para su píxel respectivo. Debido a la dependencia entre pasadas, todos los subprocesos de cada grupo de subprocesos deben completar cada una de las pasadas antes de que algún subproceso pueda pasar a la siguiente. En la Figura 2 se muestra el flujo de trabajo de un grupo de subprocesos.

Thread Group Workflow
Figura 2: Flujo de trabajo de un grupo de subprocesos. Se crea un grupo de subprocesos por cada fila de la textura de entrada.

Se puede utilizar la función GroupMemoryBarrierWithGroupSync después de que cada subproceso realiza una pasada de mariposa, para imponer esta sincronización.

Los resultados de cada pasada se guardan en índices alternos en un arreglo de SLM. Los valores de entrada de la textura de origen se cargan inicialmente en la primera mitad del arreglo y cada pasada siguiente escribe valores en la otra mitad. En esencia, los saltos en ping-pong entre las texturas que se utilizan en la técnica UAV siguen ocurriendo, pero dentro de la SLM.

Las operaciones que se realizan en cada subproceso por cada pasada son:

  1. Calcular dos índices para indexar en la salida de la pasada anterior.
  2. Calcular dos pesos para cambiar la escala de los valores en cada índice.
  3. Realizar operaciones aritméticas básicas con índices y pesos, y escribir el resultado en el otro lado del arreglo de SLM.
  4. Llamar a GroupMemoryBarrierWithGroupSync para sincronizar con otro subproceso.
  5. Repetir.

Las operaciones descritas están representadas en el código de sombreador de cálculo de la Figura 3. La Figura 4 muestra las llamadas de distribución que requiere la técnica SLM.

groupshared float3 pingPongArray[4][LENGTH];
void ButterflyPass(int passIndex, uint x, uint t0, uint t1, out float3 resultR, out float3 resultI)
{
	uint2 Indices;
	float2 Weights;
	GetButterflyValues( passIndex, x, Indices, Weights );

	float3 inputR1 = pingPongArray[t0][Indices.x];
	float3 inputI1 = pingPongArray[t1][Indices.x];

	float3 inputR2 = pingPongArray[t0][Indices.y];
	float3 inputI2 = pingPongArray[t1][Indices.y];

	resultR = inputR1 + Weights.x * inputR2 - Weights.y * inputI2;
	resultI = inputI1 + Weights.y * inputR2 + Weights.x * inputI2;
}

[numthreads( WIDTH, 1, 1 )]
void ButterflySLM(uint3 position : SV_DispatchThreadID)
{
	// Load entire row or column into scratch array
	pingPongArray[0][position.x].xyz = TextureSourceR[position];
	pingPongArray[1][position.x].xyz = TextureSourceI[position];
	
	uint4 textureIndices = uint4(0, 1, 2, 3);

	for( int i = 0; i < BUTTERFLY_COUNT-1; i++ )
	{
		GroupMemoryBarrierWithGroupSync();
		ButterflyPass( i, position.x, textureIndices.x, textureIndices.y,
        pingPongArray[textureIndices.z][position.x].xyz,
        pingPongArray[textureIndices.w][position.x].xyz );
		textureIndices.xyzw = textureIndices.zwxy;
	}

	// Final butterfly will write directly to the target texture
	GroupMemoryBarrierWithGroupSync();
	ButterflyPass(BUTTERFLY_COUNT - 1, position.x, textureIndices.x, textureIndices.y, TextureTargetR[position], TextureTargetI[position]);
}

Figura 3: Implementación de la técnica SLM

SLM Technique
Figura 4: Llamadas de distribución de sombreador de cálculo con el uso de la técnica SLM, capturadas en Graphics Performance Analyzer (GPA)

El algoritmo se puede transponer, con modificaciones mínimas, para utilizarlo también en el eje y.

Análisis de ancho de banda de memoria

Cada componente de color de una imagen del dominio de la frecuencia se representa con un plano real y uno complejo (imaginario). Estos planos requieren de mucha precisión, y por lo tanto, del uso de R32G32B32A32 de 128 bits.

Las fórmulas de la Figura 5 se pueden usar para calcular el ancho de banda de memoria correspondiente a una FFT en el eje x con la técnica UAV. BytesRead se multiplica por 2, porque cada pasada de mariposa requiere de 4 muestras de textura, 2 reales y 2 imaginarias.

TextureSize = Width * Height * 16
PassCount = log2(Width)
BytesRead = TextureSize * PassCount * 2 * 2
BytesWritten = TextureSize * PassCount * 2

Figura 5: Ancho de banda de memoria correspondiente a la técnica UAV

La Figura 6 muestra que, con el uso de estas fórmulas, los cálculos del ancho de banda de memoria de una textura de 512 x 256 son:

TextureSize = 512 * 256 * 16 = 2097152
PassCount = log2(512) = 9
BytesRead = 2097152 * 9 * 2 * 2 = 75497472
BytesWritten = 2097152 * 9 * 2 = 37748736

Figura 6: Ancho de banda de memoria correspondiente a una textura de 512 x 256 con la técnica UAV

Esto significa que solo para la pasada en el eje x, se requieren 72 MB de lecturas de textura y 32 MB de escrituras de textura. La transformada en el eje y y las transformadas inversas aumentan aún más el ancho de banda de memoria.

Lo que hace la técnica SLM es reducir este ancho de banda, y para ello aprovecha que cada fila se puede procesar de manera independiente. También usa sombreadores de cálculo para leer una fila entera en la memoria local compartida, realizar todas las pasadas de mariposa y luego escribir los resultados una sola vez en las texturas de salida.

La Figura 7 muestra las fórmulas simples para calcular el ancho de banda de memoria de la técnica SLM; leen y escriben cada textura una vez y no las afecta la cantidad de pasadas.

TextureSize = Width * Height * 4
BytesRead = TextureSize * 2
BytesWritten = TextureSize * 2

Figura 7: Ancho de banda de memoria con la técnica SLM

TextureSize = 512 * 256 * 16 = 2097152
BytesRead = 2097152 * 2 = 4194304
BytesWritten = 2097152 * 2 = 4194304

Figura 8: Ancho de banda de memoria correspondiente a una textura de 512 x 256 con la técnica SLM

Los 4 MB de ancho de banda de lectura y escritura calculados en la Figura 8 se pueden mejorar todavía más si se evita la lectura inicial de la textura imaginaria, ya que es siempre cero. Ello lleva el ancho de banda de lectura a 2 MB y el de escritura a 4 MB. Para la FFT en el eje x, la técnica SLM reduce los anchos de banda de lectura y escritura a un treintaiseisavo y un octavo, respectivamente.

El uso de una textura lookup de mariposa con pesos e índices precalculados mejora aún más el ancho de banda. Esta textura almacena dos índices y dos pesos en un formato R32G32B32A32. Cada grupo de subprocesos consume la totalidad de la textura en el transcurso de todas las pasadas de mariposa, y hay un grupo de subprocesos por cada fila de la textura de origen. En la Figura 9 se muestran las fórmulas para usar una textura lookup de mariposa al transformar una textura de 512 x 256. El resultado es aproximadamente 18 MB de lecturas de textura adicionales (Figura 10).

PassCount = log2(Width)
ButterflyTextureSize = Width * PassCount * 16
BytesRead = ButterflyTextureSize * Height

Figura 9: Fórmulas genéricas para calcular el ancho de banda de memoria por el uso de una textura lookup de mariposa

PassCount = log2(512) = 9
ButterflyTextureSize = 512 * 9 * 16 = 73728
BytesRead = 73728 * 256 = 18874368

Figura 10: Ancho de banda adicional de memoria necesario para usar una textura lookup de mariposa en una textura de origen de 512 x 256

Los cálculos de esta sección proporcionan un valor aproximado del ancho de banda de memoria ideal sin considerar las lecturas adicionales que se realizan cuando se efectúan escrituras parciales. Estas lecturas pueden llegar a ser considerables y varían según el hardware implementado.

Textura lookup de mariposa 

Los cálculos de los índices y pesos que se usarán en cada pasada por cada píxel se pueden calcular con anterioridad y almacenar en una textura. El uso de una textura de mariposa reduce la cantidad de cálculos, pero aumenta notablemente el ancho de banda de memoria. Después de aplicar cada mariposa, cada fila habrá, en esencia, muestreado toda la textura de mariposa de 128 bits. Según la arquitectura de GPU que se utilice, usar una textura de mariposa puede llegar a reducir el rendimiento, como se muestra en la Figura 11.

Graphics Performance Analyzer
Figura 11: Los resultados de ejecutar Graphics Performance Analyzer (GPA) en un procesador Intel® Core™ i5-4300U muestran una reducción de la detención de sombreadores de cálculo, lecturas de memoria, y duración.

En la Figura 12 se muestra una función para calcular los índices y pesos de mariposa en HLSL dado un índice de pasada y un desplazamiento.

void GetButterflyValues( uint passIndex, uint x, out uint2 indices, out float2 weights )
{
	int sectionWidth = 2 << passIndex;
	int halfSectionWidth = sectionWidth / 2;

	int sectionStartOffset = x & ~(sectionWidth - 1);
	int halfSectionOffset = x & (halfSectionWidth - 1);
	int sectionOffset = x & (sectionWidth - 1);

	sincos( 2.0*PI*sectionOffset / (float)sectionWidth, weights.y, weights.x );
	weights.y = -weights.y;

	indices.x = sectionStartOffset + halfSectionOffset;
	indices.y = sectionStartOffset + halfSectionOffset + halfSectionWidth;

	if( passIndex == 0 )
	{
		indices = reversebits(indices) >> (32 - BUTTERFLY_COUNT) & (LENGTH - 1);
	}
}

Figura 12: Cálculo de los índices y pesos de mariposa en un sombreador de cálculo

Rendimiento

La técnica SLM muestra una ventaja de rendimiento considerable en comparación con la técnica UAV en múltiples GPU, tanto de Intel® como de AMD*. En la Figura 13 se incluyen los tiempos de transformación de una textura de 512 x 512 hacia y desde el dominio de la frecuencia, con diversas configuraciones.

SLM Technique Performance Chart
Figura 13: Tiempo combinado en milisegundos de las transformadas directa e inversa en ambos ejes

Otras optimizaciones

Algunas optimizaciones más se hicieron evidentes en el proceso de escribir este ejemplo, pero las omitimos por cuestiones de simplicidad.

Empaquetamiento de componentes

Otra optimización sería empaquetar los datos de UAV para eliminar el canal alfa no utilizado. Lamentablemente, las UAV de formato de textura están restringidas y no hay compatibilidad con texturas de precisión de 32 bits de 3 componentes (R32G32B32). Sin embargo, los planos real e imaginario se podrían empaquetar en una textura R32G32B32A32 y una textura R32B32. Podrían almacenarse todos los componentes del número real en el RGB de la primera textura y dividir los componentes imaginarios de modo que uno quede en el componente alfa de la textura ARGB y los otros dos en la R32B32.

Packing Components
Figura 14: Ejemplo de empaquetamiento de los valores reales e imaginarios en una textura R32G32B32A32 y una textura R32G32

Es mejor evitar las texturas de gran precisión innecesarias

Para simplificar la muestra, la imagen de entrada se copia a la textura R32G32B32A32 real antes de la transformación. Las salidas de la transformada inversa también tienen ese mismo formato de textura. Leer directamente de la textura de origen sin la copia reduciría el ancho de banda de memoria. El resultado invertido también se podría escribir en un formato de textura de menor precisión.

Conclusión

El uso de SLM en la memoria de trabajo en un algoritmo de FFT permitió lograr un aumento de rendimiento sustancial en la GPU integrada que se analizó. Debería considerarse usar SLM para todo algoritmo multipaso enlazado a memoria que almacene datos temporales en texturas. Para determinar cuál es la técnica más apropiada, se puede analizar el rendimiento en otras GPU mediante el uso del código de ejemplo . Debido a las similitudes entre ambas técnicas, apenas debería ser necesario hacer cambios en el código para admitir las dos.

1 El software y las cargas de trabajo usados en la pruebas de rendimiento puede que hayan sido optimizados para rendimiento en microprocesadores Intel solamente. Las pruebas de rendimiento, tales como SYSmark* y MobileMark*, se miden con sistemas informáticos, componentes, software, operaciones y funciones específicos. Todo cambio en cualquiera de esos factores puede hacer que varíen los resultados. Debe consultar más información y otras pruebas de rendimiento que lo ayuden a evaluar íntegramente las compras que contemple hacer, incluido el rendimiento del producto al combinarlo con otros.

Configuraciones:
Encontrará más información en http://www.intel.com/performance

 

Para obtener información más completa sobre las optimizaciones del compilador, consulte nuestro Aviso de optimización.