Casi todos los algoritmos necesitan mejoras y éstas son uno de los elementos principales para resolver eficientemente un problema, deben contar con el estudio de la complejidad y del rendimiento del código. Es importante considerar que la mejora de un computador no implica, de forma directa, una mejora en las prestaciones proporcionales a dicha mejora.
En el supuesto de que utilicemos arquitecturas de múltiples procesadores, la mejora estaría limitada por la parte secuencial del programa, dado que la parte paralelizable es uniformemente distribuida entre el número de procesadores, este punto es importante, dado que cualquier computador presente dispone de la capacidad de cálculo en paralelo.
Para estudiar el rendimiento del código debemos tener en cuenta los siguientes trabajos:
- Ley de Gene Amdahl (1.967), se basa en la carga fija de trabajo o en un problema de tamaño fijo. Esta ley permite representar matemáticamente cómo influye una mejora sobre uno o varios componentes del algoritmo que ejecutamos, establece que la mejora obtenida está limitada por la cantidad de tiempo que se utiliza dicha mejora (Componente) y define la ganancia de rendimiento o aceleración que puede lograrse al utilizar una característica particular como:
Rendimiento (Aceleración) = Rendimiento del proceso utilizando la mejora / Rendimiento del proceso sin mejora
de otra forma
Rendimiento (Aceleración) =Tiempo de ejecución sin utilizar la mejora / Tiempo de ejecución utilizando la mejora
La mejora de un componente se puede cuantificar mediante la siguiente ecuación:
A = Aceleración
Fm = Fracción de tiempo de la mejora introducida.
Am = Factor de mejora.
- Ruby B. Lee (1.980) publicó “Empirical Results on the Speed, Efficiency, Redundancy and Quality of Parallel Computations”, donde definió varios parámetros para evaluar el proceso en paralelo:
Ruby B. Lee
Rapidez y Eficiencia del sistema
Escalabilidad
Redundancia
Calidad del paralelismo
- Ley de John Gustafson – Barsis (1.987) se aplica a problemas escalables donde el tamaño del problema se incrementa al aumentar el tamaño de la máquina o, se dispone de un tiempo fijo para realizar una determinada tarea.
s es la fracción de tiempo que pasa un cálculo paralelo usando procesadores en la realización de operaciones exclusivamente secuenciales.
n es el tamaño del problema
p es la cantidad de procesadores
Más específicamente,
La aceleración Ψ esperada es:
Pongamos un ejemplo: Una aplicación se ejecuta en 64 procesadores y usa el 6% del tiempo total en cálculos no paralelos. ¿Cuál es la aceleración esperada?
- Métricas de Karp – Flatt ( Alan H. Karp y Horace P. Flatt) (1.990). Esta métrica es una indicación de la medida en la cual se paraleliza el código de un computador en particular. Dado un proceso en paralelo que muestra aumento de velocidad en los procesadores, la fracción determinada experimentalmente se define como la métrica de Karp-Flatt:
Cuanto menor sea el valor de e mejor es la paralelización.
- David A. Patterson – John L. Hennessy (1.990). Desarrollaron una ecuación de rendimiento donde el tiempo de ejecución de un algoritmo depende de tres factores:
El número de instrucciones que se ejecutan ( NI ).
El promedio de ciclos empleados en cada instrucción ( CPI ).
El tiempo del ciclo (frecuencia de reloj del computador (Tciclo ).
Además de los factores anteriores debemos definir los dos siguientes conceptos:
El tiempo de respuesta o de ejecución. Es el tiempo transcurrido entre el comienzo y el final de una acción, algunos lo llaman de latencia.
El rendimiento o productividad. Es la cantidad total de trabajo realizado en un tiempo determinado.
Ambos conceptos son recíprocos, es decir, incrementar el rendimiento hace decrecer el tiempo de ejecución.
- Xian-He Sun – Lionel M. Ni (1993) Su modelo de aceleración se aplica a problemas escalables limitados por la capacidad de lamemoria del sistema, se entiende que la memoria es distribuida, compartida y toda ella se utiliza en el problema. Engloba a las leyes de Amdahl y Gustavson-Barsis.
Xian-He Sun – Lionel M. Ni
Por nuestra parte aportamos un procedimiento empírico básico pero eficiente, tened en cuenta que el tamaño sí importa:
- Limpiad el equipo (Aplicaciones, servicios, red, wifi, fragmentación de disco, memoria…).
- Hemos simplificado la programación orientada a objetos, ralentiza y le damos un enfoque procedimental que se ajusta más al problema.
- Ejecutar varias veces el programa con puntos de control.
- Observamos cuáles son los pasos que se están llevando el tiempo del proceso.
- Identificar los pasos a optimizar.
- Por cada paso identificado
- ¿Se puede mejorar el algoritmo?
- Eliminar o cambiar de lugar instrucciones. (crear/iniciar variables fuera de bucles), …
- Cambiar tipo de datos. (S.O. de 32/64 bits), (long < BigInteger), …
- Cambiar estructuras del lenguaje (while, for,…), (largos if – else por case), …
- En función del tipo de acceso a datos:
- ¿Es viable cargar datos en tabla?.
- Evitar instrucciones de acceso a ficheros sin memoria intermedia.
- Si accedemos a una base de datos comercial, con la iglesia hemos topado, hay que estudiarla con paciencia.
- Por cada modificación.
- Estudiarla de forma aislada y evaluar su mejora. Pasar a (3)
- Estudiarla con el resto de pasos. (Podemos mejorar un paso y sobrecargar otro). Pasar a (3)
Después de todo esto o antes, utilizar herramientas para la optimización de código, memoria, procesador, … Utilizarlas preferiblemente después de vuestras optimizaciones, en caso contrario nos haremos vagos y el cerebro está para algo. No somos partidarios de recomendar herramientas, pueden ser efectivas durante un tiempo y en siguientes versiones perder su atractivo, también aparecer nuevas y quedarnos clavados en el pasado. En función del entorno deberéis buscar las vuestras, nosotros hemos utilizado las siguientes que no implican que sean las mejores:
- Analizador de código: SONAR, PMD, …
- Analizador del procesador: tanto AMD como Intel ofrecen las suyas
- Qué hace nuestra máquina: Process Monitor
Después de todo esto buscar una máquina con “chorrocientos” MIPS, procesadores o gigas de memoria y a correr.