Análisis de dependencias

Análisis de dependencias

Análisis de dependencias

En teoría de compiladores, el análisis de dependencias genera restricciones en el orden de ejecución de las instrucciones. Grosso modo, se dice una instrucción S2 depende de S1 si S1 debe ser ejecutada antes que S2. Una clasificación extensa divide las dependencias en dos tipos, dependencias de control y dependencias de datos.

El análisis de dependencias determina si es seguro o no reordenar o paralelizar instrucciones.

Contenido

Dependencias de control

Una instrucción S2 depende en cuanto a control de S1 (expresado como S1\ \delta^c\ S2) si y solo si la ejecución de S2 viene condicionada por S1. El siguiente código es un ejemplo de dependencia de control:

S1       if x > 2 goto L1
S2       y := 3   
S3   L1: z := y + 1

Aquí, S2 solamente es ejecutada si la condición de S1 es falsa.

Dependencias de datos

Una dependencia de datos surge entre dos instrucciones que pretenden acceder o modificar un mismo recurso.

Dependencia de flujo o verdadera

Una instrucción S2 posee dependencia verdadera o de flujo respecto de S1 (expresado como S1\ \delta^f\ S2) si y solo si S1 modifica un recurso que S2 lee y S1 precede a S2 en el orden de ejecución. El siguiente ejemplo muestra una dependencia verdadera:

S1       x := 10
S2       y := x + c

Antidependencia

Una instrucción S2 es antidependiente de S1 (expresado como S1\ \delta^a\ S2) si y solo si S2 modifica un recurso que S1 lee y S1 precede a S2 en el orden de ejecución. El siguiente ejemplo muestra una antidependencia:

S1       x := y + c
S2       y := 10

Aquí, S2 modifica el valor de y pero S1 lee un valor anterior de dicha variable.

Dependencia de salida

Una instrucción S2 presenta una dependencia de salida respecto de S1 (expresado como S1\ \delta^o\ S2) si y solo si S1 y S2 modifican el mismo recurso y S1 precede a S2 en el orden de ejecución. El siguiente ejemplo muestra una dependencia de salida:

S1       x := 10
S2       x := 20

Aquí, Tanto S2 como S1 modifican el valor de la variable x.

"Dependencia" de entrada

Una instrucción S2 presenta una "dependencia" de entrada respecto de S1 (expresado como S1\ \delta^i\ S2) si y solo si S1 y S2 leen el mismo recurso y S1 precede a S2 en el orden de ejecución:

S1       y := x + 3
S2       z := x + 5

Aquí, S2 y S1 acceden a la variable x. Esta no es una dependencia en la misma línea que las anteriores, ya que no prohíbe la reordenación de instrucciones.

Dependencias de bucles

El problema de las dependencias en bucles, algo significativo y nada trivial, es tratado por el análisis de dependencias de bucles.

Lecturas recomendadas

  • Cooper, Keith D.; & Torczon, Linda. (2005). Engineering a Compiler. Morgan Kaufmann. ISBN 1-55860-698-X.
  • Kennedy, Ken; & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0.
  • Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 1-55860-320-4.
Obtenido de "An%C3%A1lisis de dependencias"

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Análisis del camino — Saltar a navegación, búsqueda El análisis del camino (Path analysis) o análisis de pautas es un análisis de regresión múltiple más un diagrama de flujo de las interdependencia. Es una aplicación de la inferencia estadística y la teoría de grafos …   Wikipedia Español

  • Análisis sintáctico (lingüística) — Saltar a navegación, búsqueda El análisis sintáctico es el análisis de las funciones sintácticas o relaciones de concordancia y jerarquía que guardan las palabras agrupándose entre sí en sintagmas, oraciones simples y compuestas de proposiciones… …   Wikipedia Español

  • Análisis del camino — El análisis del camino (Path analysis o análisis de pautas es un análisis de regresión múltiple más un diagrama de flujo de las interdependencia. Es una aplicación de la inferencia estadística y la teoría de grafos. Primero se determina el orden… …   Enciclopedia Universal

  • Centro Nacional de Análisis y Documentación Judicial — Saltar a navegación, búsqueda El Centro Nacional de Análisis y Documentación Judicial (CENADOJ), es una entidad de apoyo judicial ubicada en Guatemala, (América Central). Es una entidad del gobierno, que funciona como parte del Organismo Judicial …   Wikipedia Español

  • Dependencia de datos — Saltar a navegación, búsqueda En informática, se conoce como dependencia de datos aquella situación en que las instrucciones de un programa se refieren a los resultados de otras anteriores que aún no han sido completadas. Si dichas dependencias… …   Wikipedia Español

  • SCons — Autor Steven Knight www.scons.org Información general Última versión estable 1.3.1 …   Wikipedia Español

  • Banco de Guatemala — Saltar a navegación, búsqueda Banco de Guatemala Tipo Banco Central Fundación 1950 …   Wikipedia Español

  • Presupuesto — Saltar a navegación, búsqueda Un presupuesto es la previsión de gastos e ingresos para un determinado lapso, por lo general un año. Permite a las empresas, los gobiernos, las organizaciones privadas y las familias establecer prioridades y evaluar …   Wikipedia Español

  • Operación Puerto — C/ Zurbano n.º 92 (Madrid, España): el panel Análisis Clínicos anuncia el laboratorio del Dr …   Wikipedia Español

  • Universidad Nacional de Colombia — Escudo Oficial Acrónimo UNAL Lema …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”