- Procesador: Intel Core i7-10700 2.90 GHz
- Ram: 16,0 GB
- Sistema Operativo: Ubuntu 20.04 nativo
a. El algoritmo quadratic1.c computa las raíces de esta ecuación empleando los tipos de datos float y double. Compile y ejecute el código. ¿Qué diferencia nota en el resultado?
La diferencia se encuentra en la precision del resultado, el double es un tipo de dato con mayor bits de precision que el float.
b. El algoritmo quadratic2.c computa las raíces de esta ecuación, pero en forma repetida. Compile y ejecute el código variando la constante TIMES. ¿Qué diferencia nota en la ejecución?
QUAD2 TIMES 50
CLUSTER
SIN OPTIMIZAR
Tiempo requerido solucion Double: 19.441738
Tiempo requerido solucion Float: 18.744871
OPTIMIZADO
Tiempo requerido solucion Double: 2.693236
Tiempo requerido solucion Float: 2.421828
LOCAL
SIN OPTIMIZAR
Tiempo requerido solucion Double: 12.147080
Tiempo requerido solucion Float: 13.480428
OPTIMIZADO
Tiempo requerido solucion Double: 0.708603
Tiempo requerido solucion Float: 0.627858
QUAD2 TIMES 100
CLUSTER
SIN OPTIMIZAR
Tiempo requerido solucion Double: 39.253563
Tiempo requerido solucion Float: 37.839327
OPTIMIZADO
Tiempo requerido solucion Double: 6.817833
Tiempo requerido solucion Float: 4.702941
LOCAL
SIN OPTIMIZAR
Tiempo requerido solucion Double: 23.427781
Tiempo requerido solucion Float: 26.285536
OPTIMIZADO
Tiempo requerido solucion Double: 1.416524
Tiempo requerido solucion Float: 1.187522
La mayor diferencia que se encuentra es que en el CLUSTER tarda mas el double que el float pero en Local pasa lo contrario. Esto se debe a que ciertas arquitecturas de hardware benefician mas a float y otras benefician mas a los double.
c. El algoritmo quadratic3.c computa las raíces de esta ecuación, pero en forma repetida. Compile y ejecute el código variando la constante TIMES. ¿Qué diferencia nota en la ejecución? ¿Qué diferencias puede observar en el código con respecto a quadratic2.c?
QUAD3 TIMES 50
CLUSTER
SIN OPTIMIZAR
Tiempo requerido solucion Double: 19.441738
Tiempo requerido solucion Float: 18.744871
OPTIMIZADO
Tiempo requerido solucion Double: 3.149339
Tiempo requerido solucion Float: 1.870756
LOCAL
SIN OPTIMIZAR
Tiempo requerido solucion Double: 12.090996
Tiempo requerido solucion Float: 8.014069
OPTIMIZADO
Tiempo requerido solucion Double: 0.661828
Tiempo requerido solucion Float: 0.409379
QUAD3 TIMES 100
CLUSTER
SIN OPTIMIZAR
Tiempo requerido solucion Double: 38.889745
Tiempo requerido solucion Float: 55.777811
OPTIMIZADO
Tiempo requerido solucion Double: 4.657589
Tiempo requerido solucion Float: 3.162098
LOCAL
SIN OPTIMIZAR
Tiempo requerido solucion Double: 23.522227
Tiempo requerido solucion Float: 15.528005
OPTIMIZADO
Tiempo requerido solucion Double: 1.303832
Tiempo requerido solucion Float: 0.787573
Tarda menos respecto al punto B. En este caso se nota una tendencia a que las resoluciones con float tarden menos, esto se debe a que se utilizan constantes en Float en vez de “castearlas” a Float desde Double y en que se utilizan funciones especificas del tipo Float como powf() y sqrtf()
Empezaremos lo mas explicito y simple posible sin esforzarnos demasiado en encontrar ninguna optimizacion, de esta forma podriamos documentar las optimizaciones y sus cambios en el tiempo de ejecucion.
Como excepcion a esto, comenzamos con una extraccion de una multiplicacion (RA + RB) -> R(A + B), sencillamente porque nos resulto mas sencillo contruirlo directamente de esta forma.
Escribimos un pequeño test bash para asegurar la correctitud del programa a medida que vamos agregando optimizaciones.
Resultados del algoritmo base en PC:
Tiempo en segundos 0.5465590954 para 512
Tiempo en segundos 5.0782840252 para 1024
Tiempo en segundos 114.8600111008 para 2048
La primera optimizacion que implementamos fue la de almacenar valores en variables auxiliares en vez de realizar el mismo calculo varias veces.
Esto lo realizamos con el calculo del indice y con el acceso a elementos de las matrices, pero no vimos mejora y hasta en ciertos casos empeoraba por lo que descatamos esta optimizacion.
Resultados del algoritmo V2 en PC:
Tiempo en segundos 0.5131499767 para 512
Tiempo en segundos 9.0782840252 para 1024
Eliminamos el almacenamiento del calculo de los indices de las matrices pero mantuvimos el almacenamiento de los accesos a la matrices durante el calculo de R donde si vimos una mejora significativa.
Resultados del algoritmo V2.2 en PC:
Tiempo en segundos 0.4950668812 para 512
Tiempo en segundos 4.0553719997 para 1024
Tiempo en segundos 62.7206149101 para 2048
Probamos usar una matriz para almacenar el resultado en vez de usar R mismo. No presento mejoras, y hasta cierta desmejora.
Resultados del algoritmo V3 en PC:
Tiempo en segundos 0.5233290195 para 512
Tiempo en segundos 4.0354280472 para 1024
Tiempo en segundos 66.0288639069 para 2048
Para realizar esta optimizacion tomamos ventaja de que en C el 0 se considera falso para combinar el decremento y la condicion del for en una sola expresion. Para esto tuvimos que invertir todos los for, se observo una mejora.
Resultados del algoritmo V4 en PC:
Tiempo en segundos 0.4419710636 para 512
Tiempo en segundos 3.7746620178 para 1024
Tiempo en segundos 52.0080058575 para 2048
Finalmente, accedimos por columna en los operandos derechos de las multiplicacion de matrices para asi realizarlas mas eficientemente. Esto se debe a que para el calculo de un elemento del resultado de una multiplicaion se debe recorrer la fila de la matriz izquierda y la columna de la matriz derecha, por lo que acceder a la matriz derecha por filas es extremadamente ineficiente. La mejora fue tan significativa que nos dejo satisfechos y dimos por finalizado el proceso de optimizacion.
Para esto debimos incluir una nueva matriz resultado pero aun asi se mantuvo la mejora.
Resultados del algoritmo V5 en PC:
Tiempo en segundos 0.2881238461 512
Tiempo en segundos 2.2192440033 1024
Tiempo en segundos 18.6206161976 2048
Resultados del algoritmo V5 optimizado con O3 en PC:
Tiempo en segundos 0.1262190342 en 512
Tiempo en segundos 1.0131981373 en 1024
Tiempo en segundos 8.9814372063 en 2048
Tiempo en segundos 71.7591030598 en 4096
Resultados del algoritmo V5 en CLUSTER:
Tiempo en segundos 0.9209411144 para 512
Tiempo en segundos 7.8719360828 para 1024
Tiempo en segundos 66.6019508839 para 1024
Resultados del algoritmo V5 optimizado con O3 en CLUSTER:
Tiempo en segundos 0.2335169315 para 512
Tiempo en segundos 3.9887001514 para 1024
Tiempo en segundos 33.6858358383 para 2048
Tiempo en segundos 289.3322269917 para 4096
- Especificamos el Sistema Operativo.
- Removimos el printf en la parte cronometrada.
- Accedimos a A y B por columna.
- Subimos la declaracion de las variables a la parte superior del codigo.
- Liberamos la memoria de las matrices
En la primer entrega no vimos mejoras con esta optimizacion, pero probamos nuevamente bajo estas nuevas circustancias y en el cluster. En local la mejora es insignificante pero en el cluster es considerable. Eso nos muestra la importancia de testear las distintas optimizaciones en el cluster.
Resultados del algoritmo V6 con O3 en PC:
Tiempo en segundos 0.1241769791 512 (-0.002s)
Tiempo en segundos 0.9895720482 1024 (-0.03s)
Tiempo en segundos 8.7864239216 2048 (-0.1s)
Resultados del algoritmo V6 con O3 en CLUSTER:
Tiempo en segundos 0.2390909195 para 512 (-0.06s)
Tiempo en segundos 3.2064399719 para 1024 (-0.7s)
Tiempo en segundos 26.1121909618 para 2048 (-6s)
Previamente segun nuestros tests la utilizacion del For negativo era superior al For positivo. El Loop Unrolling toma provecho de los for positivos pero unicamente poseen esta tecnica los compiladores que optimizan ya que realiza un trade off de espacio por velocidad. Al presentarse unicamente en compiladores que optimizan de ahora en adelante nuestras pruebas serán con las optimizaciones activadas para asi no perdernos posibles mejoras unicamente disponibles con optimizaciones del compilador.
Hubo mejora en local aunque baja, en el cluster con los numeros mas grande se vio una gran mejora.
Resultados del algoritmo V7 con O3 en PC:
Tiempo en segundos 0.1217939854 512 (-0.003s)
Tiempo en segundos 0.9604120255 1024 (-0.02s)
Tiempo en segundos 8.5703060627 2048 (-0.2s)
Resultados del algoritmo V7 con O3 en CLUSTER:
Tiempo en segundos 0.2272150517 512 (-0.01s)
Tiempo en segundos 3.0225861073 1024 (-0.2s)
Tiempo en segundos 25.9561238289 2048 (-1s)
Tiempo en segundos 246.7201778889 4096 (-43s)
En vez de calcular R y luego recorrer R para calcular el promedio de sus elementos, vamos a ir promediando a medida que calculamos R. Que mejore es logico ya que nos ahorramos todo un recorrido a la matriz R.
Hemos notado que en N de bajo tamaño los cambio de performance pueden llegar a ser aleatorio por eso a partir de esta optimizacion incluiremos la medida de N 4096 para PC hogareña
Resultados del algoritmo V8 con O3 en PC:
Tiempo en segundos 0.1222889423 512 (-0.001s)
Tiempo en segundos 0.9899148941 1024 (-0.02s)
Tiempo en segundos 8.6328001022 2048 (-0.1s)
Tiempo en segundos 68.7034969330 4096
Resultados del algoritmo V8 con O3 en CLUSTER:
Tiempo en segundos 0.2291181087 512 (+0.002s)
Tiempo en segundos 2.5515639782 1024 (-0.5s)
Tiempo en segundos 27.6058239937 2048 (+1s)
Tiempo en segundos 177.7153198719 4096 (-69s)
Este es un algoritmo mas eficiente para el calculo de matrices.
A y B por columna
LOCAL CON O3 con N 512, 1024, 2048, 4096 BLOCK SIZE = 64 N=512 Tiempo en segundos 0.1228930950 N=1024 Tiempo en segundos 0.9109921455 N=2048 Tiempo en segundos 7.4957959652 N=4096 Tiempo en segundos 62.3854839802
BLOCK SIZE = 32 N =512 Tiempo en segundos 0.1025271416 N = 1024 Tiempo en segundos 0.7395899296 N = 2048 Tiempo en segundos 6.3410418034 N = 4096 Tiempo en segundos 55.8242478371
BLOCK SIZE = 16 N =512 Tiempo en segundos 0.0834891796 N = 1024 Tiempo en segundos 0.6646518707 N = 2048 Tiempo en segundos 5.3521339893 N = 4096 Tiempo en segundos 57.6838190556
BLOCK SIZE = 8 N = 512 Tiempo en segundos 0.1095681190 N = 1024 Tiempo en segundos 0.8257339001 N = 2048 Tiempo en segundos 6.7357931137 N = 4096 Tiempo en segundos 54.0443139076
BLOCK_SIZE = 4 N=512 Tiempo en segundos 0.0889801979 N = 1024 Tiempo en segundos 0.5906310081 N = 2048 Tiempo en segundos 4.6603698730 N = 4096 Tiempo en segundos 37.2843301296
BLOCK_SIZE = 2 N=512 Tiempo en segundos 0.1124119759 N = 1024 Tiempo en segundos 0.8261470795 N = 2048 Tiempo en segundos 6.8966259956 N = 4096 Tiempo en segundos 53.8338119984
CLUSTER CON O3 64 32 16 8
CLUSTER: BLOQUE 2: [0.40,3.34,26.52,211.66]
BLOQUE 4: [0.29,2.30,18.34,144.32]
BLOQUE 8: [0.28,2.19,17.42,136.98]
BLOQUE 16: [0.26,2.13,16.99,175.40]
BLOQUE 32: [0.25,2.07,20.20,152.64]
Bloque 64: [0.26,2.31,18.86,147.40]