7.1 Entendiendo el paralelismo - dependencias  (Page 2/3)

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.

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:

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. [link] 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:

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

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

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 un grafo acíclico dirigido (GAD). 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. 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.