Algoritmo de red-Ullman

Algoritmo de red-Ullman
Lleva el nombre de Ravi Sethi [d] yJeffrey Ullman
objetivo buscar el orden de traducción óptimo de una expresión
Estructura de datos grafico

El algoritmo Network-Ullman es un algoritmo para traducir árboles de sintaxis abstracta en código de máquina que utiliza la menor cantidad de registros posible . El algoritmo lleva el nombre de sus desarrolladores Ravi Seti y Jeffrey Ullman ,

Resumen

Al generar código para expresiones aritméticas , el compilador debe decidir cuál es la mejor manera de traducir la expresión en términos de la cantidad de instrucciones utilizadas, así como la cantidad de registros necesarios para evaluar un subárbol en particular. Especialmente en el caso de que el número de registros libres sea pequeño, el orden de ejecución puede ser importante para la longitud del código generado, ya que un orden diferente de evaluación puede resultar en valores más o menos intermedios que se desalojan en la memoria y luego restaurado. El algoritmo Network-Ullman (también conocido como numeración Network-Ullmann ) tiene la propiedad de producir código que requiere el mínimo número de instrucciones así como el mínimo número de referencias a memoria (asumiendo que al menos las operaciones son conmutativas y asociativas , pero el ley distributiva , es decir , no se cumple). Tenga en cuenta que el algoritmo tiene éxito incluso si no se produce conmutatividad ni asociatividad en la expresión y, por lo tanto, no se pueden aplicar transformaciones aritméticas. El algoritmo tampoco utiliza la detección de subexpresiones comunes o el uso explícito de gráficos acíclicos dirigidos generales en lugar de árboles.

Un algoritmo simple de Net-Ullman

El algoritmo Simple Network-Ullmann funciona de la siguiente manera (para la arquitectura de carga/almacenamiento ):

  1. Recorriendo el árbol de sintaxis abstracta hacia adelante o hacia atrás
    1. Asignamos 1 a cualquier nodo hoja no constante (es decir, necesitamos 1 registro para almacenar una variable/campo/etc.). A cualquier hoja constante (el lado derecho de la operación - literales, valores) se le asignará 0.
    2. A cualquier nodo que no sea hoja n se le asigna el número de registros necesarios para calcular el subárbol n correspondiente . Si el número de registros necesarios en el subárbol izquierdo ( l ) no es igual al número de registros necesarios en el subárbol derecho ( r ), el número de registros necesarios en el nodo actual n es max(l, r). Si l == r , entonces el número de registros necesarios para el nodo actual es .
  2. Codigo de GENERACION
    1. Si la cantidad de registros necesarios para calcular el subárbol izquierdo del nodo n es mayor que la cantidad de registros para el subárbol derecho, entonces se calcula primero el subárbol izquierdo (porque es posible que se requiera un registro adicional para almacenar el resultado del subárbol derecho, superpuesto por el registro del subárbol izquierdo). Si el subárbol derecho requiere más registros que el izquierdo, entonces se evalúa primero el árbol derecho. Si ambos subárboles requieren el mismo número de registros, entonces el orden de ejecución no importa.

Ejemplo

Para una expresión aritmética , el árbol de sintaxis abstracta se ve así:

= / \ a * / \ / \ ++ / \ / \ /\d3 + * / \ / \ bcfg

Para ejecutar el algoritmo, solo necesitamos verificar la expresión aritmética , es decir solo necesitamos mirar el subárbol derecho del destino '=':

* / \ / \ ++ / \ / \ /\d3 + * / \ / \ bcfg

Ahora comenzamos el recorrido del árbol asignando el número de registros necesarios para evaluar cada subárbol (tenga en cuenta que el último término de la expresión es una constante):

* 2 / \ / \ + 2 + 1 / \ / \ / \ re 1 3 0 + 1 * 1 / \ / \ segundo 1 do 0 f 1 gramo 0

De este árbol, puede ver que necesitamos 2 registros para calcular el subárbol izquierdo de '*', pero solo necesitamos un registro para calcular el subárbol derecho. Los nodos 'c' y 'g' no necesitan registros por las siguientes razones: Si T es una hoja del árbol, entonces el número de registros para evaluar T es 1 o 0 dependiendo de si T está en el subárbol izquierdo o derecho (porque operaciones como agregar R1, A, pueden procesar el componente correcto de A directamente sin registrarlo). Por lo tanto, debemos comenzar ejecutando el subárbol izquierdo, ya que podemos terminar con una situación en la que solo tenemos dos registros para evaluar la expresión completa. Si primero calculamos el subárbol derecho (que requiere solo un registro), tendríamos que almacenar el resultado del subárbol derecho mientras calculamos el subárbol izquierdo (que todavía necesita 2 registros), por lo que se necesitan 3 registros. La evaluación del subárbol izquierdo requiere dos registros, pero el resultado se puede almacenar en un registro, y dado que el subárbol derecho requiere un registro para evaluar, la expresión se puede evaluar con solo dos registros.

Algoritmo de Net-Ullman mejorado

En una versión mejorada del algoritmo Network-Ullman, las expresiones aritméticas se convierten primero utilizando las propiedades aritméticas de los operadores utilizados.

Véase también

Notas

Literatura

Enlaces