1 | dom | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
2 | dom | 2 | 3 | 4 | 5 | 6 | |
3 | dom | 3 | |||||
4 | dom | 4 | |||||
5 | dom | 5 | |||||
6 | dom | 6 | |||||
Relación de dominación correspondiente | |||||||
Los nodos grises no están estrictamente dominados | |||||||
Los nodos rojos se dominan inmediatamente |
En la informática , en los gráficos de flujo de control , un nodo d domina un nodo n si cada camino desde el nodo de entrada a n debe pasar por d . Notacionalmente, esto se escribe como d dom n (oa veces d n ). Por definición, cada nodo se domina a sí mismo.
Hay varios conceptos relacionados:
- Un nodo d domina estrictamente a un nodo n si d domina n y d no es igual a n .
- El dominador inmediato o idom de un nodo n es el nodo único que domina estrictamente n pero no domina estrictamente ningún otro nodo que domine estrictamente n . Cada nodo, excepto el nodo de entrada, tiene un dominador inmediato. [1]
- La frontera de dominancia de un nodo d es el conjunto de todos los nodos n i tal que d domina a un predecesor inmediato de n i , pero d no domina estrictamente n i . Es el conjunto de nodos donde se detiene el dominio de d .
- Un árbol dominador es un árbol donde los hijos de cada nodo son los nodos que domina inmediatamente. Debido a que el dominador inmediato es único, es un árbol. El nodo de inicio es la raíz del árbol.
Historia
La dominancia fue introducida por primera vez por Reese T. Prosser en un artículo de 1959 sobre análisis de diagramas de flujo. [2] Prosser no presentó un algoritmo para computar el dominio, que tuvo que esperar diez años para Edward S. Lowry y CW Medlock. [3] Ron Cytron y col. reavivó el interés en el dominio en 1989 cuando lo aplicaron al problema de calcular de manera eficiente la ubicación de las funciones φ, que se utilizan en forma estática de asignación única . [4]
Aplicaciones
Los dominadores, y las fronteras de dominancia en particular, tienen aplicaciones en compiladores para calcular la forma de asignación única estática . Varias optimizaciones del compilador también pueden beneficiarse de los dominadores. El diagrama de flujo en este caso comprende bloques básicos .
La paralelización automática se beneficia de las fronteras de posdominio. Este es un método eficiente para calcular la dependencia del control, que es fundamental para el análisis.
El análisis de uso de memoria puede beneficiarse del árbol de dominador para encontrar fácilmente fugas e identificar un alto uso de memoria. [5]
En los sistemas de hardware, los dominadores se utilizan para calcular las probabilidades de la señal para la generación de pruebas, estimar las actividades de conmutación para el análisis de potencia y ruido y seleccionar puntos de corte en la verificación de equivalencia. [6] En los sistemas de software, se utilizan para reducir el tamaño del conjunto de pruebas en técnicas de pruebas estructurales como declaraciones y cobertura de sucursales. [7]
Algoritmos
Dejar ser el nodo de origen en el gráfico de flujo de control . Los dominadores de un nodo están dadas por la solución máxima a las siguientes ecuaciones de flujo de datos:
El dominador del nodo inicial es el propio nodo inicial. El conjunto de dominadores para cualquier otro nodo. es la intersección del conjunto de dominadores para todos los predecesores de . El nodo también está en el conjunto de dominadores para .
Un algoritmo para la solución directa es:
// el dominador del nodo de inicio es el inicio mismo Dom (n 0 ) = {n 0 } // para todos los demás nodos, establezca todos los nodos como dominadores para cada n en N - {n 0 } Dom (n) = N; // eliminar iterativamente los nodos que no son dominantes while cambios en cualquier Dom (n) para cada n en N - {n 0 }: Dom (n) = {n} unión con intersección sobre Dom (p) para todo p en pred (n)
La solución directa es cuadrática en el número de nodos u O ( n 2 ). Lengauer y Tarjan desarrollaron un algoritmo que es casi lineal, [1] y en la práctica, excepto por unos pocos gráficos artificiales, el algoritmo y una versión simplificada del mismo son tan rápidos o más rápidos que cualquier otro algoritmo conocido para gráficos de todos los tamaños y su La ventaja aumenta con el tamaño del gráfico. [8]
Keith D. Cooper , Timothy J. Harvey y Ken Kennedy de Rice University describen un algoritmo que esencialmente resuelve las ecuaciones de flujo de datos anteriores, pero utiliza estructuras de datos bien diseñadas para mejorar el rendimiento. [9]
Postdominancia
De manera análoga a la definición de dominancia anterior, se dice que un nodo z posdomina un nodo n si todas las rutas al nodo de salida del gráfico que comienzan en n deben pasar por z . De manera similar, el posdominador inmediato de un nodo n es el posdominador de n que no posdomina estrictamente a ningún otro posdominador estricto de n .
Ver también
Referencias
- ^ a b Lengauer, Thomas ; Tarjan, Robert Endre (julio de 1979). "Un algoritmo rápido para encontrar dominadores en un diagrama de flujo". Transacciones ACM sobre lenguajes y sistemas de programación . 1 (1): 121-141. CiteSeerX 10.1.1.117.8843 . doi : 10.1145 / 357062.357071 .
- ^ Prosser, Reese T. (1959). "Aplicaciones de matrices booleanas al análisis de diagramas de flujo" . Conferencias informáticas conjuntas de la AFIPS: ponencias presentadas en la conferencia informática conjunta IRE-AIEE-ACM del este del 1 al 3 de diciembre de 1959 . IRE-AIEE-ACM '59 (Este): 133-138. doi : 10.1145 / 1460299.1460314 .
- ^ Lowry, Edward S .; Medlock, Cleburne W. (enero de 1969). "Optimización del código de objeto". Comunicaciones de la ACM . 12 (1): 13-22. doi : 10.1145 / 362835.362838 .
- ^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K .; Wegman, Mark N .; Zadeck, F. Kenneth (1989). "Un método eficiente de cálculo de formulario de asignación única estática" . Actas del 16º Simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . POPL '89: 25–35. doi : 10.1145 / 75277.75280 . ISBN 0897912942.
- ^ "Dominator Tree" . eclipse.org . SAP AG e IBM Corporation. 2012 [2008] . Consultado el 21 de junio de 2013 .
- ^ Teslenko, Maxim; Dubrova, Elena (2005). Un algoritmo eficiente para encontrar dominadores de doble vértice en gráficos de circuito . Conferencia Proceedings of Design and Test in Europe . Fecha '05. págs. 406–411. CiteSeerX 10.1.1.598.3053 . doi : 10.1109 / FECHA.2005.53 . ISBN 9780769522883.
- ^ Dubrova, Elena (2005). Pruebas estructurales basadas en núcleos mínimos . Conferencia Proceedings of Design and Test in Europe . Fecha '05. págs. 1168-1173. CiteSeerX 10.1.1.583.5547 . doi : 10.1109 / FECHA.2005.284 . ISBN 9780769522883.
- ^ Georgiadis, Loukas; Tarjan, Robert E .; Werneck, Renato F. (2006). "Encontrar dominadores en la práctica" (PDF) .
- ^ Cooper, Keith D .; Harvey, Timothy J; Kennedy, Ken (2001). "Un algoritmo de dominancia simple y rápido" (PDF) .
enlaces externos
- La biblioteca de análisis de flujo de control Machine-SUIF