Dividir un gráfico

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 24 de marzo de 2017; las comprobaciones requieren 3 ediciones .

Particionar un gráfico en subgráficos ( eng.  Partición de gráficos ) (a veces el término cortar un gráfico también se usa en la literatura [1] ) es una representación del gráfico original como un conjunto de subconjuntos de vértices de acuerdo con ciertas reglas. Usualmente, según la condición del problema, se requiere que , es decir, todos los vértices del grafo original deben estar distribuidos entre subconjuntos, y . Por lo general, también se introduce adicionalmente el requisito de ortogonalidad de la partición , es decir, un mismo vértice no puede formar parte de diferentes subconjuntos. A veces, del conjunto de particiones posibles, se requiere elegir una que satisfaga las restricciones y sea óptima (o subóptima) según el criterio indicado, o probar que la partición requerida no existe (las restricciones son inconsistentes). La tarea de particionar un gráfico pertenece a la clase de NP-completo , la estimación superior del número de particiones está determinada por el número de Bell , sin embargo, generalmente no todas las particiones posibles son correctas (no violan las restricciones), es decir, el la estimación está sobreestimada. Cuando el número de vértices del grafo es superior a 15-20, la obtención de particiones óptimas suele ser imposible en un tiempo aceptable (a veces se utiliza el método branch andbound para ello ), por lo que, en la práctica, se limitan a soluciones subóptimas obtenidas mediante métodos heurísticos . algoritmos _

La necesidad de obtener una partición surge al resolver una serie de problemas:

  1. Problema de coloreado de gráficos  : cada conjunto de vértices consta de vértices del mismo color y los vértices del mismo color no tienen bordes incidentes comunes. Por lo general, uno está interesado en encontrar la coloración mínima, que en el caso general es un problema de clase NP (el criterio de optimización es ).
  2. El problema de determinar el número y la composición de los componentes conectados de un gráfico .
  3. Al diseñar la topología de una red local, su división en dominios de transmisión está determinada por los requisitos de rendimiento (el criterio de optimización es la cantidad de tráfico entre dominios que se transmite cuando se utilizan varios servidores y servicios de red (acceso a servidores de archivos , DHCP , WINS , DNS , etc. .), restricciones: la cantidad de puertos y el ancho de banda de los conmutadores , enrutadores y canales de comunicación, así como el costo).
  4. En el problema de rastrear las interconexiones de placas de circuito impreso o microcircuitos , es necesario dividir el circuito original en capas (cada una de las cuales es un gráfico plano ). Criterios de optimización: el número mínimo de capas e interconexiones (de hecho, el costo de producción), restricciones: dimensiones generales y requisitos para la compatibilidad térmica y electromagnética de los componentes electrónicos. [2]
  5. En la tarea de dividir el diagrama gráfico de un algoritmo en bloques con el propósito de implementarlo en un sistema multiprocesador o un multicontrolador lógico . Los criterios de optimización son el número mínimo de bloques, el grado mínimo de duplicación de señales de microoperación y condiciones lógicas, el número mínimo de transferencias de control entre módulos, el tráfico mínimo de control entre módulos y transferencias de datos; las restricciones están dictadas por la base del elemento utilizada. [3] [4] [5] [6]
  6. Representación de un gráfico en forma de una forma paralela escalonada o un esquema de gráfico de un algoritmo en forma de un conjunto de secciones (los conjuntos de vértices en las secciones pueden ser no ortogonales).
  7. Dividir el gráfico del algoritmo en subgráficos que no se cruzan con su ubicación posterior en elementos del procesador o elementos en el FPGA al implementar el procesamiento de canalización de datos (equilibrio de carga). [7] [8]

Métodos de partición de grafos [9]

Véase también

Notas

  1. ↑ Evstigneev V. A. Aplicación de la teoría de grafos en programación. M.: Nauka, 1985. 352 págs.
  2. ↑ Kureichik V. M., Glushan V. M., Shcherbakov L. I. Modelos y algoritmos de hardware combinatorios en CAD. Moscú: Radio y comunicación, 1990. 216 p.
  3. ↑ Baranov S. I., Zhuravina L. N., Peschansky V. A. Un método para representar esquemas gráficos paralelos de algoritmos mediante conjuntos de esquemas gráficos secuenciales // Automatización e informática. 1984. Nº 5. S. 74-81.
  4. ↑ Zotov I. V., Titov V. S., Koloskov V. A. [et al.] Organización y síntesis de microprogramas multimicrocontroladores. Kursk: editorial "Kursk", 1999. 368 p. ISBN 5-7277-0253-4
  5. ↑ Vatutin E. I., Zotov I. V., Titov V. S. [et al.] Problemas lógicos combinatorios de sintetizar particiones de algoritmos de control de lógica paralela en el diseño de multicontroladores lógicos. Kursk, editorial de la Universidad Técnica Estatal de Kursk, 2010. 200 p. ISBN 978-5-7681-0523-5
  6. ↑ Vatutin E. I. Diseño de multicontroladores lógicos. Síntesis de particiones de grafos-esquemas paralelos de algoritmos. Saarbrucken : Lambert Academic Publishing , 2011. 292 págs. ISBN 978-3-8433-1728-3
  7. ↑ Kalyaev I. A., Levin I. I., Semernikov E. A., Shmoylov V. I. Estructuras informáticas multicanal reconfigurables: 2.ª edición. Rostov n/a: YuNTs RAN, 2009. 344 p. ISBN 978-5-902982-61-6
  8. ↑ Kalyaev I. A., Levin I. I. Sistemas de computación multicanal reconfigurables para resolver problemas de flujo de procesamiento y control de información // Informes plenarios de la 5.ª Conferencia Internacional "Problemas de Computación y Control Paralelos" (PACO'10). M.: UIP RAN, 2010, pp. 23-37.
  9. ↑ INTUIT.ru: Curso: Teoría y práctica ..: Conferencia No. 10: Métodos paralelos en gráficos  (enlace inaccesible)