Práctica #9: Combinación de imágenes usando SIMD

Objetivos

Durante esta actividad el alumno será capaz de:

Resolver un problema vectorial en lenguaje C y ensamblador utilizando instrucciones SIMD para la arquitectura x86-64.

Esta actividad promueve las siguientes habilidades, valores y actitudes: análisis y síntesis, capacidad de resolver problemas, creatividad, y uso eficiente de la informática y las telecomunicaciones.

Descripción de la actividad

Esta práctica puede ser elaborada de manera individual o en parejas.

Deseamos combinar dos imágenes usando disolución alfa:

Sea FORE y BACK dos secuencias de n bytes cada una, en donde cada secuencia representa una imagen. FORE es la imagen de primer plano y BACK es la imagen de fondo.
Cada byte de las secuencias es un entero entre 0 y 255. Cada pixel de las imágenes se almacena en tres bytes (24 bits) consecutivos que conforman los valores RGB (rojo, verde, azul) correspondientes.
Sea alpha una constante arbitraria entre 0 y 255 que representa la intensidad de la imagen de primer plano.
El siguiente algoritmo produce una nueva secuencia llamada RESULT de tamaño n. FORE_i, BACK_i y RESULT_i representan un byte específico, donde 0 ≤ i ≤ n – 1:
- Para i de 0 a n – 1, hacer lo siguiente:
  
  RESULT_i = (FORE_i × alpha) ÷ 256 + (BACK_i × (255 – alpha)) ÷ 256

Como ejemplo, supongamos que tenemos las siguientes dos imágenes del mismo tamaño:

Al combinar scarlett.png y flores.png con alpha = 155 obtenemos la siguiente imagen:

Si combinamos scarlett.png y flores.png con alpha = 77 obtenemos ahora esta otra imagen:

Usando la biblioteca de imágenes STB escribe dos versiones del algoritmo de combinación de imágenes a través de disolución alfa: una versión secuencial normal en lenguaje C y una versión paralela usando instrucciones SIMD (Single Instruction Multiple Data) en lenguaje ensamblador para la arquitectura x86-64. Utiliza las enormes imágenes contenidas en el archivo imagenes.tgz para probar tus programas.

Al implementar el algoritmo usando tecnología SIMD, sigue los pasos que se enumeran en la siguiente tabla.

NOTA 1: En las siguientes descripciones, un byte consta de 8 bits mientras que una palabra o word consta de 16 bits.

NOTA 2: Se presupone que el CPU a utilizar soporta instrucciones SSE4.1. Puedes utilizar la instrucción cpuid para verficar si efectivamente así es.

Descripción	Instrucción SIMD a utilizar
Copia de memoria a un registro SIMD los siguientes ocho bytes de la imagen de primer plano (`FORE`).	movq
Desempaca en paralelo los ocho bytes del paso anterior convirtiéndolos a ocho palabras, extendiendo sus valores con ceros. NOTA: El paso 3 requiere hacer multiplicaciones. Dado que no hay instrucciones SIMD para multiplicar bytes, se requiere primero convertir los bytes a palabras.	pmovzxbw
Multiplica en paralelo cada una de esas ocho palabras por alpha, conservando solo la mitad menos significativa de los resultados.	pmullw
Divide en paralelo las ocho palabras resultantes del paso anterior entre 256 usando corrimientos a la derecha e insertando ceros.	psrlw
Repite los pasos del 1 al 4 para la imagen de fondo (`BACK`), pero en el paso 3 multiplica cada palabra por (255 – alpha).
Suma en paralelo las ocho palabras obtenidas en el paso 4 más las ocho palabras obtenidas en el paso 5.	paddw
Usando saturación, empaca los resultados del paso anterior convirtiendo las ocho palabras a ocho bytes.	packuswb
Almacena en memoria los ocho bytes menos significativos resultantes del paso anterior.	movq
Repite los pasos del 1 al 8 hasta terminar de procesar todos los bytes.

Contrasta los tiempos de ejecución de la versión secuencial contra la versión paralela. Escribe un reporte con tus resultados tal como se indica en: Reportes de prácticas.

¿Qué se debe entregar?

Coloca en un archivo tarball llamado practica9.tgz todos los archivos fuentes de tu programa así como el reporte correspondiente (debes incluir los archivos .adoc y .pdf de tu reporte escrito en AsciiDoctor).

✔ Instrucciones para subir archivo

Para entregar el archivo practica9.tgz, ingresa los siguientes datos:

Solicitar NIP

La fecha límite es el viernes, 28 de abril.

Evaluación

Esta práctica será evaluada usando los siguientes criterios:

50%	Implementación de los requerimientos.
50%	Reporte de la práctica.
DA	El programa y/o reporte es un plagio.

Programación multinúcleo