Dominador (teoría de grafos)

Dominador en la teoría de grafos es una relación binaria en los nodos de un gráfico dirigido con un nodo de entrada distinguido, que muestra la ventaja al pasar la ruta desde el nodo de entrada: el nodo del gráfico domina el nodo (escrito como o ) si hay alguna ruta desde el gráfico nodo de entrada a pasa a través . En particular, cada nodo se domina a sí mismo. $d$ $norte$ $d\,\mathrm{dom}\,n$ $d\ggn$ $norte$ $d$

El uso más generalizado es en los gráficos de flujo de control utilizados en la teoría de la construcción de compiladores.

Una forma útil de representar información sobre los dominadores es un árbol llamado árbol de dominadores , donde el nodo de entrada es la raíz y cada nodo domina solo a sus hijos en el árbol [1] . $d$

Historia

El dominio en informática fue introducido por primera vez por Reese T. Prosser en 1959 [2] , el algoritmo de cálculo de dominio fue publicado por primera vez 10 años después por Lowry y Medlock ( ES Lowry , CW Medlock ) [3] . El interés renovado en el uso de la relación de dominancia proviene del artículo de 1989 de Ron Cytron , que usa esta relación para calcular eficientemente las funciones φ que se usan en la representación SSA [4] .

Propiedades de relación

La observación clave sobre los dominadores es que si tomamos cualquier ruta acíclica desde el nodo de entrada hasta el nodo , todos los dominadores se ubicarán en esta ruta, además, se ubicarán en el mismo orden a lo largo de cualquier ruta. $norte$ $norte$

Transitividad : si y , entonces , $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,c$ $a\,\mathrm{dom}\,c$
Antisimetría : si , entonces la ejecución simultánea de y es imposible . $a \ neq b$ $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,a$

Si y y son dominadores de , entonces , o . De ello se deduce que cada nodo , excepto el nodo de entrada, debe tener un solo dominador inmediato, es decir, el dominador más cercano a lo largo de cualquier ruta acíclica desde el nodo de entrada hasta [5] . $a$ $b$ $norte$ $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,a$ $norte$ $norte$ $norte$

Aplicación

La dominancia se usa en los compiladores para formar la representación SSA . Varias optimizaciones del compilador también pueden beneficiarse del uso de dominadores. Para la paralelización automática, es beneficioso conocer todos los nodos dominados por un nodo determinado. El análisis del uso de la memoria puede beneficiarse de un árbol dominador, que facilita la búsqueda de fugas y la identificación del uso excesivo de la memoria. En los sistemas de software, se utilizan para reducir el tamaño del conjunto de prueba [6] .

El dominador del gráfico de implicación se busca en los solucionadores de problemas de satisfacibilidad de fórmulas booleanas de CDCL cuando se analiza la estructura del conflicto [7] .

Notas

↑ Compiladores: principios, tecnologías y herramientas, 2008 , p. 787.
↑ Prosser, Reese T. Aplicaciones de matrices booleanas al análisis de diagramas de flujo // Conferencias informáticas conjuntas de AFIPS: documentos presentados en la conferencia informática conjunta IRE-AIEE-ACM del este del 1 al 3 de diciembre de 1959: revista. - Boston, MA: ACM, 1959. - P. 133-138 .
↑ Lowry, Edward S.; y Medlock, Cleburne W. Optimización de código de objeto // Comunicaciones de la ACM : revista. - 1969. - Enero ( vol. 12 , no. 1 ). - P. 13-22 .
↑ Citron, Ron; Hind, Michael; y Hsieh, Wilson. Generación Automática de Paralelismo DAG (indefinido) // Actas de la Conferencia ACM SIGPLAN 89 sobre Diseño e Implementación de Lenguajes de Programación. - 1989. - S. 54-68 .
↑ Compiladores: principios, tecnologías y herramientas, 2008 , p. 788.
↑ Dubrova, Elena. Ensayos Estructurales Basados en Núcleos Mínimos (indefinidos) // Actas de Diseño y Ensayo en la Conferencia Europea. - 2005. - S. 1168-1173 .
↑ Armin Biere, Marijn Heule, Hans van Maaren y Toby Walsch. Capítulo 4. Solucionadores del SAT de aprendizaje de cláusulas basadas en conflictos // Manual de satisfacibilidad. - Prensa IOS, 2008. - Pág. 135.

Literatura

Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Compiladores: Principios, Técnicas y Herramientas = Compiladores: Principios, Técnicas y Herramientas. - Editorial Williams, 2008. - ISBN 0-321-48681-1 .