Ejercicios
Escribe una implementación en punto fijo del generador de Mandelbrot.
a.
Notarás que el rendimiento es inconsistente entre diferentes píxeles y diferentes cuadros. ¿Por qué ocurre esto?
b.
¿Cuál es la intensidad aritmética del cuerpo del bucle más interno, en operaciones por byte accedido desde la memoria? ¿Cuál es el límite de rendimiento correspondiente para su CPU ARM? ¿Cómo se compara con el rendimiento observado?
c.
Mida las siguientes métricas de rendimiento para el cuerpo del bucle más interno:
▪
instrucciones por iteración
▪
instrucciones por operación
▪
CPI
▪
tasa de fallos de caché
d.
Utilice el ensamblaje en línea para implementar el cuerpo del bucle más interno y mida el impacto en el rendimiento con respecto a las métricas de la parte c. ¿Cuál es el aumento de velocidad en comparación con el código generado por el compilador?
Paralelice el generador del conjunto de Mandelbrot utilizando OpenMP. Aplique la directiva parallel-for al bucle más externo (fila).
a.
Medir el número medio de ciclos necesarios para cada iteración del bucle más interno (para evaluar el polinomio) para un hilo y dos hilos para el cuadro inicial. Utilice estas mediciones para calcular el aumento de velocidad, en términos de píxeles por segundo, de dos hilos sobre un hilo.
b.
Medir el tiempo para calcular todos los píxeles en el primer cuadro cuando se utiliza el programa dinámico en comparación con el programa estático.
¿Qué dificulta la aplicación de la operación SIMD para el generador del conjunto de Mandelbrot? ¿Cuál es el método más eficiente para aplicar la operación SIMD para el generador de conjuntos de Mandelbrot?
Medir el rendimiento efectivo de escritura para el Framebuffer de Linux. ¿Es equivalente al rendimiento de escritura de una matriz de memoria asignada desde el montón?
Calcule la intensidad aritmética del programa de transformación de imágenes en operaciones por píxel. ¿Cuál es su límite de rendimiento dado el rendimiento efectivo de la memoria de su CPU ARM? ¿Cómo se compara con el rendimiento observado?
Usa OpenMP para añadir soporte multinúcleo al programa de transformación de imágenes de punto fijo. Para ello, aplique el pragma parallel for al bucle más externo (fila).
Mida su rendimiento en una CPU ARM de cuatro núcleos. ¿Cómo se escala su rendimiento cuando se ejecuta con uno, dos, tres y cuatro hilos?
Utiliza intrínsecos para añadir soporte NEON SIMD a la versión de punto fijo del programa de transformación de imágenes. Utiliza operaciones de cuatro hilos para realizar los siguientes cálculos para un grupo de cuatro píxeles: localización del píxel de origen, extracción de la fracción y cálculo del peso. ¿En qué medida mejora esto el rendimiento?
No podemos optimizar fácilmente el programa generador de Mandelbrot utilizando instrucciones SIMD, ya que los píxeles vecinos pueden requerir un número diferente de evaluaciones del polinomio y cada iteración del polinomio depende de la evaluación anterior. Un enfoque alternativo es implementar el bucle en ensamblaje en línea, desenrollar por lo menos cuatro, y luego utilizar el pipelining de software para mejorar el CPI del bucle. En este caso, debemos evitar las ramas condicionales dentro del bucle desenrollado. Dado que los valores c divergentes continuarán divergiendo con las evaluaciones posteriores, podemos esperar a comprobar la condición de salida del bucle después de cada grupo de cuatro iteraciones. Sin embargo, realizar evaluaciones adicionales del polinomio después de que un Pc() diverja potencialmente fuera del círculo de radio-2 requerirá que tengamos en cuenta los requisitos de rango adicionales para nuestro formato de punto fijo. Vuelva a calcular los requisitos de rango de punto fijo para esta optimización y determine hasta qué punto esto reducirá el nivel máximo de zoom.
Las principales ventajas del punto fijo son la reducción de la latencia de las operaciones y la posibilidad de evitar las conversiones de tipo en ciertos tipos de códigos gráficos. El capítulo 2 destaca un programa de ejemplo cuyo rendimiento es sensible a la latencia de las operaciones, el método de Horner. Suponiendo que podemos tolerar las limitaciones de rango del punto fijo en nuestro código del método de Horner, ¿convertirlo a punto fijo mejoraría el rendimiento? Explique su respuesta.
En la sección 3.6.5 se mostraron dos implementaciones diferentes de una macro de preprocesador de suma generalizada en punto fijo. La primera fue generada por gcc bajo optimización máxima, la segunda fue codificada a mano usando lenguaje ensamblador en línea. Ambas implementaciones requirieron aproximadamente el mismo número de instrucciones.
a.
Muestra las dependencias de datos de lectura y escritura en ambas implementaciones. Suponiendo que el procesador utiliza una sola instrucción, en orden de emisión, y suponiendo que la latencia de todas las operaciones aritméticas de números enteros es de cuatro ciclos, cuántos comparan el número de ciclos de paralización de datos necesarios para ambas implementaciones.
b.
Reescriba la versión en ensamblador en línea de la macro de adición de punto fijo para programar las instrucciones de forma que las instrucciones dependientes estén separadas lo máximo posible. ¿Hasta qué punto se reducen las paradas, asumiendo la latencia dada en la parte a?
c.
Escriba un código que demuestre cómo se pueden caracterizar las tres implementaciones (generada por el compilador, ensamblaje en línea y ensamblaje en línea programado) para el rendimiento.
En esta pregunta examinamos la implementación en ensamblador en línea de la multiplicación generalizada en punto fijo descrita en la Sección 3.6.6.
a.
¿Cómo se compara, en términos de número de instrucciones y rendimiento en tiempo de ejecución, con el código equivalente generado por el compilador para:
res = (((long long)op1 * (long long)op2) >> (rp1>rp2?rp1:rp2)) +(rp1>rp2 ? ((((long long)op1 * (long long)op2) >> (rp1-1))&1) :
((((long long)op1 * (long long)op2) >> (rp2-1))&1));
Asegúrese de utilizar los modificadores «-O3» y «-marm» al compilar con gcc.
b.
Programa las instrucciones de la versión de ensamblaje en línea de la macro multiplicativa para minimizar las paradas por dependencia de datos. Mida su rendimiento en relación con la versión dada en la Sección 3.6.6.
c.
Para la implementación de ensamblaje en línea, ¿cuánto más se logra a lo largo si se cambia de tal manera que las posiciones de los puntos radicales sean fijas en lugar de variables como en el código? Para esta pregunta, utilice tanto el número de instrucciones como el comportamiento real en tiempo de ejecución.
Calcular los valores de los píxeles para un conjunto de Mandelbrot requiere una función para convertir el recuento de iteraciones a los canales de color R, G y B. Establecer los tres canales al mismo valor generará una imagen gris, por lo que la pendiente de cada función de canal de color debe ser única, y cualquiera que sea la mayor pendiente determinará el tono de la imagen.
Como se describe en la Sección 3.8.1, el número de evaluaciones del polinomio puede exceder el valor que excede el rango de un canal de color. Para evitar un posible desbordamiento, debe utilizar la aritmética de saturación al calcular el valor de cada píxel. De esta manera, si el valor calculado excede el valor máximo permitido, se establece en el valor máximo.
Escriba una macro en C que realice una multiplicación saturante de 8 bits sin signo. La función tomará dos operandos de 8 bits y producirá un producto de 8 bits establecido en 255 si el producto es superior a 255. La macro no debe incluir instrucciones de bifurcación y estar programada para las dependencias de datos.
Este ejercicio explorará el aumento de la precisión de los tipos de punto fijo para el generador de Mandelbrot a 64 bits.
a.
Usando una tasa de zoom de 1,5zoom, ¿a qué nivel se puede ampliar el cuadro antes de exceder esta precisión?
b.
Defina una macro en C para sumar dos valores de punto fijo (64,56). La macro puede realizar la suma de 128 bits utilizando cuatro sumas de 32 bits y utilizar el indicador de acarreo para implementar los acarreos de cada grupo de 32 bits al siguiente grupo más significativo de 32 bits.
c.
Defina una macro en C para multiplicar dos valores de punto fijo (64,56). Construya esta macro sobre la macro de suma de 64 bits de la parte b.
Como se muestra en la figura 3.6, una forma sencilla de realizar una multiplicación de 64 bits es realizar una serie de cuatro operaciones de multiplicación/desplazamiento/acumulación de 32 bits que producen cada una un resultado de 64 bits.
Figura 3.6. Un multiplicador de 8 bits implementado con multiplicadores de 4 bits.
En la figura, dos valores de 4 bits A y B que mantienen los valores 1110 y 1410 se separan cada uno en dos porciones superior e inferior de 2 bits, denominadas A1, A0 y B1 y B0. Suponiendo que los productos son de 4 bits, el producto de 8 bits se calcula como (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
Para aplicar esto a una multiplicación de 64 bits, cada uno de los dos valores de 64 bits debe mantenerse en dos registros de 32 bits. Cada multiplicación genera un resultado de 64 bits, permitiendo un producto final de 128 bits.
d.
Usando estas macros, implemente un generador de conjuntos de Mandelbrot de 64 bits y mida la diferencia de rendimiento resultante.
e.
Implemente ambas macros en lenguaje ensamblador en línea y mida el aumento de velocidad del resultado del generador de Mandelbrot en comparación con el de la parte d.