<< Chapter < Page Chapter >> Page >

La forma más básica de optimización de bucles es desenrollarlos. Es algo tan básico que casi todos los compiladores actuales lo hacen automáticamente, si da la impresión de que repercutirá benéficamente. En nombre del desenrollado de bucles, se introdujo gran cantidad de desorden en los antiguos programas FORTRAN ahora cubiertos de polvo, que sólo sirve para confundir y despistar a los compiladores de hoy.

No estamos sugiriendo que deba usted desenrollar los bucles a mano. El propósito de esta sección es doble: primero, una vez que esté familiarizado con el desenrollado de bucles, podrá reconocer código que desenrolló el programador (no usted) tiempo atrás, y simplificarlo; y segundo, necesita entender los conceptos del desenrollado de bucles, de modo que cuando vea el código máquina generado, pueda reconocerlos.

El beneficio primario de desenrollar bucles, es realizar más cálculos por iteración. Al final de cada una, el valor índice debe incrementarse, probarse y bifurcar el control de regreso al inicio del ciclo, si todavía faltan iteraciones por procesar. Al desenrollar el bucle, hay menos "finales de bucle" en la ejecución de cada ciclo. Desenrollar también reduce significativamente el número total de bifurcaciones, y da al procesador más instrucciones entre ellas (i.e., incrementa el tamaño de los bloques básicos).

A modo de ilustración, considere el siguiente bucle. Es una sentencia simple envuelta en un ciclo:


DO I=1,N A(I) = A(I) + B(I) * CENDDO

Usted puede desenrollar el bucle, como haremos en el ejemplo siguiente, reescribiendo las mismas operaciones mediante menos iteraciones y con menos sobrecarga en el ciclo. Imagine cómo ayudará esto en cualquier computadora. Dado que los cálculos en una iteración no dependen de los cálculos en otras, los primeros y los segundos pueden ejecutarse juntos. En un procesador superescalar, ciertas porciones de estas cuatro sentencias pueden ejecutarse en paralelo:


DO I=1,N,4 A(I) = A(I) + B(I) * CA(I+1) = A(I+1) + B(I+1) * C A(I+2) = A(I+2) + B(I+2) * CA(I+3) = A(I+3) + B(I+3) * C ENDDO

Sin embargo, este ciclo no es exactamente el mismo que el anterior, pues se desenrolló cuatro veces, pero ¿qué pasa si N no es divisible entre 4? Habrá una, dos o tres iteraciones sobrantes que no se ejecutarán. Para manejar tales iteraciones extras, agregamos otro pequeño bucle para absorberlas. El ciclo extra se llama un bucle precondicionante :


II = IMOD (N,4) DO I=1,IIA(I) = A(I) + B(I) * C ENDDODO I=1+II,N,4A(I) = A(I) + B(I) * C A(I+1) = A(I+1) + B(I+1) * CA(I+2) = A(I+2) + B(I+2) * C A(I+3) = A(I+3) + B(I+3) * CENDDO

El número de iteraciones requeridas en el ciclo precondicionante es el residuo de dividir el número total de iteraciones entre la cantidad de veces que se desenrolló. Si, a tiempo de ejecución, N resulta ser divisible entre 4, no habrá iteraciones sobrantes, y el ciclo precondicionante no se ejecutará.

La ejecución especulativa en las arquitecturas post RISC puede reducir o eliminar la necesidad de desenrollar un bucle que operará sobre valores que deben recuperarse de la memoria principal. Dado que las operaciones de carga pueden tomar mucho tiempo relativo a los cálculos, el ciclo se desenrolla naturalmente. Mientras que el procesador está esperando a que finalice la primera carga, puede ejecutar especulativamente tres o cuatro iteraciones del ciclo adelante de la primera carga, desenrollando efectivamente el ciclo en el Buffer de Reordenamiento de Instrucciones.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Cómputo de alto rendimiento. OpenStax CNX. Sep 02, 2011 Download for free at http://cnx.org/content/col11356/1.2
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Cómputo de alto rendimiento' conversation and receive update notifications?

Ask