Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » Cómputo de Alto Rendimiento » Optimización de Ciclos - Calificando a los Candidatos para el Desenrollado de Ciclos

Navigation

Table of Contents

Recently Viewed

This feature requires Javascript to be enabled.
 

Optimización de Ciclos - Calificando a los Candidatos para el Desenrollado de Ciclos

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

Based on: Loop Optimizations - Qualifying Candidates for Loop Unrolling by Charles Severance, Kevin Dowd

Asumiendo un valor grande de N, el ciclo previo era un candidato ideal para desenrollarse. Las iteraciones pueden ejecutarse en cualquier orden, y las entrañas del ciclo eran pequeñas. Pero como tal vez sospeche, éste no siempre es el caso; ciertas clases de ciclos no pueden desenrollarse tan fácilmente. Adicionalmente, la forma en que se usa un ciclo cuando el programa se ejecuta puede descalificarlo para desenrollado de ciclos, incluso aunque parezca prometedor.

En esta sección vamos a discutir unas pocas categorías de ciclos que no son generalmente buenos candidatos para el desenrollado, y le daremos algunas ideas de qué puede usted hacer al respecto. Ya hablamos acerca de varias de ellas en el capítulo previo, pero nuevamente resultan relevantes.

Ciclos con Bajo Conteo de Repeticiones

Para resultar efectivo, el desenrollado de ciclos requiere que el original tenga un número bastante grande de iteracionesl. Para comprender por qué, visualicemos qué sucede si el conteo total de iteraciones es bajo, tal vez menor a 10, o incluso menor que 4. Con un conteo de repeticiones tan bajo, el ciclo precondicionante está llevando a cabo una cantidad proporcionalmente alta de trabajo. Y no se supone que deba ser así, pues éste debe hacerse cargo de las pocas iteraciones sobrantes olvidadas por el ciclo principal desenrollado. Sin embargo, cuando el conteo de repeticiones es bajo, puede que esté usted haciendo una o dos pasadas por el ciclo desenrollado, mas una o dos pasadas a través del ciclo precondicionante. En otras palabras, tiene usted entre manos un mayor desorden; simplemente, el ciclo no debió haberse desenrollado.

Probablemente, la única ocasión en que tiene sentido desenrollar un ciclo con un conteo de repeticiones bajo, es cuando el número de iteraciones es constante y se conoce a tiempo de compilación. Por ejemplo, suponga que tiene el siguiente ciclo:


PARAMETER (NITER = 3) DO I=1,NITER A(I) = B(I) * C ENDDO

Dado que NITER vale constantemente 3, puede usted desenrollar de forma segura hasta una profundidad de 3 sin preocuparse por el ciclo precondicionante. De hecho, puede desechar completamente la estructura del ciclo y quedarse sólo con el ciclo desenrollado en el interior:


PARAMETER (NITER = 3) A(1) = B(1) * C A(2) = B(2) * C A(3) = A(3) * C

Por supuesto, si el contador del número de repeticiones es bajo, probablemente no contribuya significativamente al tiempo de ejecución global, a menos que se trate de un ciclo en el centro de otro más grande. Entonces probablemente quiera usted desenrollarlo completamente, o dejarlo solo.

Ciclos Gruesos

El desenrollado de ciclos ayuda al rendimiento porque engruesa cada uno con más cálculos por iteración. Por la misma razón, si un ciclo particular ya es grueso, desenrollarlo no será de mucha ayuda, pues su sobrecarga ya está distribuida sobre un número grande de instrucciones. De hecho, desenrollar un ciclo grueso puede incluso volver más lento su programa, porque incrementará el tamaño del segmento de texto, colocando una carga adicional sobre el sistema de memoria (lo explicaremos con más detalle un poco más adelante). Una buena regla empírica consiste en ir en busca de rendimiento en cualquier otra parte cuando el ciclo interno excede tres o cuatro sentencias.

Ciclos que Contienen Llamados a Procedimientos

Tal como sucede con los ciclos gruesos, aquellos que contienen llamados a subrutinas o funciones generalmente no son buenos candidatos para el desenrollado, debido a varias razones. Primero, a menudo ya contienen un buen número de instrucciones. Y si la subrutina que se está invocando es gruesa, también engruesa al ciclo que la invoca. El tamaño del ciclo puede no parecerlo cuando usted lo revisa, pero la invocación a la función puede ocultar muchas más instrucciones.

Segundo, cuando la rutina invocadora y la subrutina se compilan por separado, es imposible que el compilador entremezcle las instrucciones. Un ciclo que se desenrolla en una serie de llamados a funciones se comporta de forma muy parecida a como lo hacía el ciclo original antes de desenrollarse.

Por último, la sobrecarga por invocar la función es cara: deben salvarse los valores de los registros; debe prepararse la lista de argumentos. El tiempo gastado en invocar a y retornar de una subrutina puede ser mucho mayor que el provocado por el del ciclo. Desenrollar el ciclo para amortizar su costo entre varias invocaciones no resulta lo suficiente como para justificar el esfuerzo.

La regla general cuando intervienen procedimientos, es primero tratar de eliminarlos durante la fase de "remoción de desorden", y cuando dicha fase ha concluido, comprobar si el desenrollado proporciona una mejora de rendimiento adicional.

Ciclos con Bifurcaciones en su Interior

(Reference) mostramos cómo eliminar ciertos tipos de bifurcaciones, pero por supuesto no podemos deshacernos de todas. En el caso de aquéllas independientes de la iteración, podemos obtener cierto beneficio de desenrollar el ciclo. La condición de la sentencia IF se vuelve parte de las operaciones que deben contarse para determinar el valor del desenrollado del ciclo. Abajo presentamos un ciclo doblemente anidado. El interno prueba el valor de B(J,I):


DO I=1,N DO J=1,N IF (B(J,I) .GT. 1.0) A(J,I) = A(J,I) + B(J,I) * C ENDDO ENDDO

Cada iteración es independiente de cualesquiera otra, así que desenrollarlo no representa un problema. Sólo debemos mantener el ciclo externo inalterado:


II = IMOD (N,4) DO I=1,N DO J=1,II IF (B(J,I) .GT. 1.0) + A(J,I) = A(J,I) + B(J,I) * C ENDDO DO J=II+1,N,4 IF (B(J,I) .GT. 1.0) + A(J,I) = A(J,I) + B(J,I) * C IF (B(J+1,I) .GT. 1.0) + A(J+1,I) = A(J+1,I) + B(J+1,I) * C IF (B(J+2,I) .GT. 1.0) + A(J+2,I) = A(J+2,I) + B(J+2,I) * C IF (B(J+3,I) .GT. 1.0) + A(J+3,I) = A(J+3,I) + B(J+3,I) * C ENDDO ENDDO

Este enfoque funciona particularmente bien si el procesador que está usted usando soporta ejecución condicional. Como se describió con anterioridad, la ejecución condicional puede reemplazar una bifurcación y una operación, por una única sentencia ejecutada condicionalmente. En procesadores superescalares con ejecución condicional, tales ciclos desenrollados se ejecutan muy bien.

Collection Navigation

Content actions

Download module as:

Add:

Collection 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

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