Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Entendiendo el Paralelismo - Dependencias

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Imagine una orquesta sinfónica donde cada músico toque sin tomar en cuenta al director o a lo otros músicos. Al primer movimiento de la batuta del director, cada músico recorre toda su partitura. Algunos finalizan mucho antes que otros, dejan el escenario y se van a casa. La cacofonía resultante no parece música (pensándolo bien, recuerdo algo al jazz experimental), porque carece por completo de coordinación. Por supuesto, esta no es la forma en que se interpreta la música. Un programa de computadora, como una pieza musical, se teje en un telar que lo despliega conforme avanza el tiempo (aunque tal vez lo teje menos compactamente). Ciertas cosas deben suceder antes que otras, y hay una tasa de ejecución para el proceso en su conjunto.

En los programas de computadora, cuando un evento A debe suceder antes de otro evento B, se dice que B es dependiente de A. Llamamos a esta relación entre ellos una dependencia. En ocasiones las dependencias se deben a cálculos o accesos a memoria, en cuyo caso les denominamos dependencias de datos. En otras ocasiones estamos a la espera de que ocurra un salto o la salida de un ciclo, en cuyo caso les denominamos dependencias de control. Cada tipo está presente en cada programa, sólo que en grados distintos. El objetivo es eliminar tantas de ellas como sea posible. Reacomodar el código, de forma que dos segmentos sean menos dependientes entre sí, expone el paralelismo, o las oportunidades de hacer muchas cosas a la vez.

Dependencias de Control

Tal como la asignación de variables puede depender de otras asignaciones, el valor de una variable puede depender también del flujo de control del programa. Por ejemplo, una asignación adentro de una sentencia condicional sólo puede ocurrir si la condición se evalúa como verdadera. Lo mismo puede decirse de una asignación al interior de un ciclo; si nunca se entra en dicho ciclo, ninguna sentencia en su interior se ejecutará.

Cuando los cálculos ocurren como consecuencia del flujo de control, decimos que se trata de una dependencia de control, tal como en el código que aparece más abajo y que se explica gráficamente en Figure 1. La asignación ubicada dentro del bloque condicional puede o no ejecutarse, dependiendo del resultado de la prueba X .NE. 0. En otras palabras, el valor de Y depende del flujo de control en el código a su alrededor. Nuevamente, esto puede sonarle a usted como un asunto que sólo le importa a los diseñadores de compiladores, y no a los programadores, cosa que es mayormente cierta. Pero hay veces que usted deseará mover tales instrucciones dependientes del control, para así quitar del camino costosos cálculos (suponiendo que su compilador no sea lo suficientemente inteligente para hacerlo por usted). Por ejemplo, digamos que Figure 2 representa una pequeña sección de su programa. El flujo de control inicia en la parte superior y avanza a lo largo de dos decisiones. Por otro lado, digamos que hay una operación de raíz cuadrada en el punto de entrada, y que el flujo de control casi siempre inicia en la parte de arriba y baja por la rama que contiene la sentencia A=0.0. Ello significa que el resultado del cálculo A=SQRT(B) casi siempre se descargará, porque A obtiene un nuevo valor de 0.0 cada vez. Una operación de raíz cuadrada siempre es "cara", porque toma mucho tiempo en ejecutarse. El problema es que usted no puede simplemente quitarla de ahí, puesto que ocasionalmente se requiere. Sin embargo, puede quitarla del camino y continuar observando las dependencias e control, haciendo dos copias de la operación de raíz cuadrada a lo largo de la bifurcación menos recorrida, como se muestra en Figure 3. De esta forma el código SQRT sólo se ejecutará a lo largo de tales rutas cuando realmente se requiera.

Figure 1
Dependencia de control
Esta figura es una caja conteniendo cuatro líneas de código, con una flecha que va del centro de una línea al inicio de la siguiente.
Figure 2
Una pequeña sección de nuestro programa
Esta figura muestra una línea etiquetada A = SQRT(B) que se bifurca en dos puntos, con una rama etiquetada A = 0.0.

Esta clase de planificación de instrucciones irá apareciendo en los compiladores (e incluso en el hardware) más y más conforme pase el tiempo. Una variante de esta técnica es calcular los resultados que se requieran en aquellos momentos donde haya una brecha en el flujo de instrucciones (debido a las dependencias), usando así algunos ciclos sobrantes, que de otro modo se desperdiciarían.

Figure 3
La operación cara se movió, de forma que se ejecute pocas veces
Esta figura muestra una línea con bifurcaciones en dos puntos, con una rama etiquetada A = 0.0, y las otras dos etiquetadas A = SQRT(B).

Dependencia de Datos

Un cálculo que está ligado en cierta forma con uno previo, se dice que presenta dependencia de los datos con respecto a este último. En el código siguiente, el valor de B es dependiente de los datos con respecto de A. Ello se debe a que no puede usted calcular B hasta que el valor de A esté disponible:


A = X + Y + COS(Z) B = A * C

Esta dependencia es fácil de reorganizar, pero otras no lo son tanto. En otras ocasiones, deberá usted ser cuidadoso de no reescribir una variable con un nuevo valor antes de que otro cálculo haya terminado de usar el valor previo. Podemos agrupar todas las dependencias de datos en tres categorías: (1) dependencias del flujo, (2) antidependencias, y (3) dependencias de la salida. Figure 4 contiene algunos ejemplos sencillos que demuestran cada tipo de dependencia. En cada ejemplo, usamos una flecha que inicia en el origen de la dependencia, y termina en la sentencia que debe retrasarse por causa de la dependencia. El problema clave en cada una de esas dependencias, es que la segunda sentencia no puede ejecutarse hasta que se haya completado la primera. Obviamente en el ejemplo de dependencia de salida en particular, el primer cálculo es código muerto y puede eliminarse, a menos que intervenga algún código que requiera de esos valores. Hay otras técnicas para eliminar ya sean las dependencias de salida o las antidependencias. El siguiente ejemplo contiene una dependencia de flujo seguida por una dependencia de salida:

Figure 4
Tipos de dependencias de datos
Esta figura muestra tres cajas, etiquetadas dependencia de flujo, antidependencia y dependencia de salida. La dependencia de flujo muestra flechas moviendo las variables A y B a la derecha entre tres ecuaciones. La antidependencia muestra movimiento de sólo la variable A hacia la izquierda. La dependencia de salida muestra movimiento directamente hacia abajo sobre las tres ecuaciones para la variable A.

X = A / B Y = X + 2.0 X = D - E

Aunque no podamos eliminar la dependencia de flujo, sí podemos lograrlo con la dependencia de salida agregando una variable nueva:


Xtemp = A/B Y = Xtemp + 2.0 X = D - E

Conforme crece el número de sentencias e interacciones entre ellas, necesitamos una forma mejor de identificar y procesar tales dependencias.Figure 5 muestra cuatro sentencias con cuatro dependencias.

Figure 5
Dependencias múltiples
Esta figura muestra una caja conteniendo cuatro ecuaciones, X = A + B, D = X * 17, A = B + C, y X = C + E. Hay flechas entre ciertas variables en cada ecuación, y las ecuaciones están etiquetadas de arriba hacia abajo, flujo, anti, anti y salida.

Ninguna de las instrucciones, de la segunda hasta la cuarta, pueden iniciarse antes de que se complete la primera instrucción.

Formando un GAD

Un método para analizar una secuencia de instrucciones, es organizarlas en ungrafo acíclico dirigido (GAD).1 Tal como las instrucciones que representa, un GAD describe todos los cálculos y relaciones entre variables. El flujo de datos en el GAD procede en una sola dirección; la mayoría de las ocasiones el GAD se construye de arriba hacia abajo. Los identificadores y las constantes se colocan en los nodos "hoja" -los que están en la parte superior. Las operaciones, posiblemente con los nombres de las variables adjuntos, se encuentran en los nodos internos. Las variables aparecen en sus estados finales en la parte inferior. Las aristas del GAD ordenan las relaciones entre las variables y las operaciones entre ellas. Todo el flujo de datos transcurre de arriba hacia abajo.

Para construir un GAD, el compilador toma cada tupla de lenguaje intermedio y lo mapea sobre uno o más nodos. Por ejemplo, aquellas tuplas que representan operaciones binarias, tales como suma (X=A+B), forman una porción del GAD con dos entradas (A y B) enlazadas por una operación (+). El resultado de la operación puede alimentarse a su vez en otras operaciones en el bloque básico (y el GAD), como se muestra en Figure 6.

Figure 6
Un grafo de flujo de datos trivial
Esta figura contiene una ecuación, X = A + B, y una línea conectando el punto A al punto B, y el punto X al punto B.

Si se trata de un bloque de código básico, construimos nuestro GAD en el orden de las instrucciones. El GAD de para las cuatro instrucciones previas se muestra en Figure 7. Este ejemplo en particular tiene muchas dependencias, así que no hay mucha oportunidad para el paralelismo. Figure 8 muestra un ejemplo más sencillo sobre cómo construir un GAD permite identificar el paralelismo.

A partir de este GAD, podemos determinar que las instrucciones 1 y 2 pueden ejecutarse en paralelo. Dado que vemos los cálculo que se realizan sobre los valores A y B durante el procesamiento de la instrucción 4, podemos eliminar una subexpresión común durante la construcción del GAD. Si podemos determinar que Z es la única variable que se usa afuera de este pequeño bloque de código, podemos asumir que el cálculo de Y es código muerto.

Figure 7
Un grafo de flujo de datos más complejo
Esta figura contiene ecuaciones, X = A + B, D = X * 17, A = B + C, y X = C + E, y a la derecha de esas ecuaciones está un diagrama de flujo expresando tales ecuaciones juntas.

Al construir el GAD, tomamos una secuencia de instrucciones y determinamos cuáles deben ejecutarse en un orden particular, y cuáles pueden ejecutarse en paralelo. Este tipo de análisis de flujo de datos es muy importante en la fase de generación de código en los procesadores superescalares. Hemos introducido el concepto de dependencias y cómo usar el flujo de datos para encontrar oportunidades de paralelismo en secuencias de código adentro de un bloque básico. También podemos usar el análisis de flujo de datos para identificar dependencias, oportunidades para el paralelismo, y código muerto al interior de bloques básicos.

Usos y Definiciones

Conforme se construye el GAD, el compilador puede crear listas de usos y definiciones de variables, así como otra información, y aplicarlas a las optimizaciones globales a través de muchos bloques básicos tomados junto. Al revisar el GAD en Figure 8, podemos ver que las variables definidas son Z, Y, X, C, y D, y que las variables usadas son A y B. Al tomar en cuenta muchos bloques como uno solo, podemos decir cuan lejos alcanza la definición de una variable particular —dónde puede verse su valor. A partir de esto podemos reconocer situaciones en las cuales se descartan cálculos, lugares donde dos usos de una variable dada son completamente independientes, o dónde podemos reescribir valores residentes en registros sin tener que regresarlos a memoria. Llamamos a este tipo de investigación análisis de flujo de datos.

Figure 8
Extracting parallelism from a DAG
This figure contains equations, X = A + B, Y = B + 3, D = X * 7, C = A + B, and Z = D + C, with a flowchart to the right expressing the relationship between the equations.

Para ilustrarlo, supongamos que tenemos el grafo de flujo de Figure 9. Junto a cada bloque básico hemos listado las variables que usa y las variables que define. ¿Qué nos puede decir al respecto el análisis del flujo de datos?

Observe que el valor de A se definió en el bloque X, pero sólo se usó en el bloque Y. Ello significa que A está muerto hasta la salida del bloque Y o inmediatamente antes de tomar la rama derecha al dejar X; ninguno de los otros bloques básicos usan el valor de A. Ello nos dice que cualesquiera recursos asociados, tales como un registro, pueden liberarse para otros usos.

En la Figure 9 podemos ver que D está definida en el bloque básico X, pero jamás utilizada. Ello significa que los cálculos que definen a D pueden descartarse.

Algo interesante está sucediendo con la variable G. Tanto el bloque X como el W la utilizan, pero si observa detenidamente verá que los dos usos son distintos, significando que pueden tratarse como dos variables independientes.

Un compilador que instrumente técnicas avanzadas para la planificación adelantada de instrucciones, debe notar que W es el único bloque que usa el valor de E, y así mover los cálculos que definen E fuera del bloque Y y dentro de W, donde se requieren.

Figure 9
Grafo de flujo para análisis de flujo de datos.
Esta figura es un grafo de flujo de cuatro renglones, con una caja en cada renglón y flechas mostrando las relaciones entre las cajas, que están etiquetadas X, Y, W, y Z. A la derecha de las cajas, en sus respectivos renglones, hay listas de letras bajo categorías, Defines, y Uses.

Además de recopilar datos acerca de las variables, el compilador también puede mantener información acerca de subexpresiones. Al examinarlas juntas, puede reconocer casos donde se hacen cálculos redundantes (a lo largo de bloques básicos), y sustituirlos por cálculos previamente realizados. Si, por ejemplo, la expresión H*I aparece en los bloques X, Y, y W, puede calcularse sólo una vez en el bloque X, y propagarse a los otros que la usan.

Footnotes

  1. Un grafo es una colección de nodos conectados por aristas. Por dirigido nos referimos a que sólo pueden recorrerse las aristas en direcciones específicas. La palabra acíclico significa que no hay ciclos en el grafo, esto es, que no puede pasar dos veces por el mismo nodo.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

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