Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Optimización de Ciclos - Desenrollado Básico de Ciclos

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Optimización de Ciclos - Desenrollado Básico de Ciclos

Module by: José Enrique Alvarez Estrada. E-mail the authorTranslated By: José Enrique Alvarez Estrada

Based on: Loop Optimizations - Basic Loop Unrolling by Charles Severance, Kevin Dowd

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) * C ENDDO

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) * C A(I+1) = A(I+1) + B(I+1) * C A(I+2) = A(I+2) + B(I+2) * C A(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,II A(I) = A(I) + B(I) * C ENDDO DO I=1+II,N,4 A(I) = A(I) + B(I) * C A(I+1) = A(I+1) + B(I+1) * C A(I+2) = A(I+2) + B(I+2) * C A(I+3) = A(I+3) + B(I+3) * C ENDDO

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.

Content actions

Download module as:

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks