Forma de gráfico paralelo escalonado

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 17 de julio de 2014; las comprobaciones requieren 4 ediciones .

Una forma de gráfico paralelo escalonado (JPF) es una división de los vértices de un gráfico acíclico dirigido en subconjuntos renumerados , de modo que si el arco va de vértice a vértice , entonces necesariamente . $V_i$ $mi$ ${\displaystyle v_{1}\en V_{j))$ $v_{2}\en V_{k}$ ${\ estilo de visualización j<k}$

Cada uno de los conjuntos se denomina nivel JPF , su número , el número de vértices en el nivel es su ancho . El número de niveles en el JPF se llama su altura , y el ancho máximo de sus niveles es el ancho del JPF . $V_i$ $i$ ${\ estilo de visualización \ izquierda | V_ {i} \ derecha |}$

Para el LPF del grafo del algoritmo, es importante que las operaciones a las que corresponden los vértices de un nivel no dependan entre sí (no están en relación ), y por lo tanto ciertamente existe una implementación paralela del algoritmo , en la que se pueden realizar en paralelo en diferentes dispositivos informáticos . Por lo tanto, el LPF del gráfico del algoritmo se puede utilizar para preparar una implementación paralela del algoritmo .

La altura mínima de todos los NPF posibles de un gráfico es su camino crítico . Es imposible construir un NPF con una altura menor que la ruta crítica.

Si un nivel puede contener vértices que están en diferentes relaciones (por ejemplo, paralelismo o alternativas , que es típico de los esquemas gráficos de algoritmos paralelos ), el nivel se denomina sección y el CPF se denomina conjunto de secciones. La presencia de más de una relación entre los vértices de la sección complica significativamente la mayoría de los algoritmos de procesamiento [1] [2] .

Véase también clasificación topológica .

Notas

↑ Organización y síntesis de microprogramas multimicrocontroladores / I.V. Zotov, V. A. Koloskov, V. S. Titov [i dr.]. Kursk: Editorial "Kursk", 1999. 368 p. ISBN 5-7277-0253-4
↑ Problemas lógicos-combinatorios de sintetizar particiones de algoritmos de control de lógica paralela en el diseño de multicontroladores lógicos / E.I. Vatutin, IV. Zotov, V. S. Titov [i dr.]. Kursk: editorial de la Universidad Técnica Estatal de Kursk, 2010. 200 p. ISBN 978-5-7681-0523-5 .