Análisis de algoritmos paralelos

En informática , el análisis de algoritmos paralelos consiste en determinar la complejidad computacional de los algoritmos ejecutados en paralelo : el tiempo, el almacenamiento y otros recursos necesarios para su ejecución. En muchos aspectos, el análisis de algoritmos paralelos es similar al de algoritmos secuenciales , pero suele ser más complejo, ya que requiere analizar el comportamiento de múltiples hilos de ejecución que cooperan entre sí. Uno de los objetivos principales del análisis paralelo es comprender cómo varía el uso de recursos (velocidad, espacio, etc.) de un algoritmo paralelo al cambiar el número de procesadores.

Fondo

El marco denominado tiempo de trabajo (WT) (a veces llamado profundidad de trabajo o duración del trabajo) fue introducido originalmente por Shiloach y Vishkin ^{[ 1 ]} para conceptualizar y describir algoritmos paralelos. En el marco WT, un algoritmo paralelo se describe primero en términos de rondas paralelas. Para cada ronda, se caracterizan las operaciones a realizar, pero se pueden omitir varios aspectos. Por ejemplo, no es necesario especificar el número de operaciones en cada ronda, no es necesario mencionar los procesadores ni tener en cuenta ninguna información que pueda ayudar con la asignación de procesadores a las tareas. En segundo lugar, se proporciona la información omitida. La inclusión de esta información se guía por la demostración de un teorema de planificación de Brent ^{[ 2 ]} , que se explica más adelante en este artículo. El marco WT es útil porque, si bien puede simplificar enormemente la descripción inicial de un algoritmo paralelo, insertar los detalles omitidos en dicha descripción inicial no suele ser muy difícil. Por ejemplo, el marco WT se adoptó como marco de presentación básico en los libros de algoritmos paralelos (para el modelo de máquina de acceso aleatorio paralelo PRAM) ^{[ 3 ]} y ^{[ 4 ]} , así como en los apuntes de clase. ^{[ 5 ]} La descripción general a continuación explica cómo se puede utilizar el marco WT para analizar algoritmos paralelos más generales, incluso cuando su descripción no está disponible dentro del marco WT.

Definiciones

Supongamos que los cálculos se ejecutan en una máquina con $p$ procesadores. Sea $T p$ el tiempo transcurrido entre el inicio y el final del cálculo. El análisis del tiempo de ejecución del cálculo se centra en las siguientes nociones:

El trabajo de un cálculo ejecutado por $p$ procesadores es el número total de operaciones primitivas que realizan los procesadores. ^{[ 6 ]} Ignorando la sobrecarga de comunicación de la sincronización de los procesadores, esto es igual al tiempo utilizado para ejecutar el cálculo en un solo procesador, denotado $T 1$ .
La profundidad o extensión es la longitud de la serie más larga de operaciones que deben realizarse secuencialmente debido a las dependencias de datos (laruta crítica ). La profundidad también puede denominarselongitud de la ruta críticadel cálculo.^{[ 7 ]} Minimizar la profundidad/extensión es importante en el diseño de algoritmos paralelos, ya que la profundidad/extensión determina el tiempo de ejecución más corto posible. $[$ ^{8 ] Alternativamente} , la extensión puede definirse como el tiempo $T\infty$ empleado en el cálculo utilizando una máquina idealizada con un número infinito de procesadores.^{[ 9 ]}
El costo del cálculo es la cantidad $pT p$ . Esto expresa el tiempo total empleado, por todos los procesadores, tanto en el cálculo como en la espera. ^{[ 6 ]}

De las definiciones de trabajo, alcance y coste se derivan varios resultados útiles:

Ley del trabajo . El costo es siempre al menos el trabajo: $pT p \geq T 1$ . Esto se deduce del hecho de que $p$ procesadores pueden realizar como máximo $p$ operaciones en paralelo. ^{[ 6 ]}^{[ 9 ]}
Ley de expansión . Un número finito $p$ de procesadores no puede superar el rendimiento de un número infinito, de modo que $T p \geq T \infty$ . ^{[ 9 ]}

Utilizando estas definiciones y leyes, se pueden establecer las siguientes medidas de desempeño:

La aceleración es la ganancia de velocidad que se obtiene mediante la ejecución en paralelo en comparación con la ejecución secuencial: $S p = T 1 / T p$ . Cuando la aceleración es $Ω(p)$ para $p$ procesadores (usando la notación O grande ), la aceleración es lineal, lo cual es óptimo en modelos de computación simples porque la ley del trabajo implica que $T 1 / T p \leq p$ ( en la práctica puede ocurrir una aceleración superlineal debido a los efectos de la jerarquía de memoria ). La situación $T 1 / T p = p$ se denomina aceleración lineal perfecta.^{[ 9 ]} Se dice que un algoritmo que exhibe una aceleración lineal es escalable .^{[ 6 ]} En este libro se presentan expresiones analíticas para la aceleración de muchos algoritmos paralelos importantes.^{[ 10 ]}
La eficiencia es la aceleración por procesador, $S p / p$ . ^{[ 6 ]}
El paralelismo es la razón $T 1 / T \infty$ . Representa la máxima aceleración posible en cualquier número de procesadores. Según la ley de rango, el paralelismo limita la aceleración: si $p > T 1 / T \infty$ , entonces: ^{[ 9 ]} ${\frac {T_{1}}{T_{p}}}\leq {\frac {T_{1}}{T_{\infty }}}<p.$
La holgura es $T 1 / (pT \infty)$ . Una holgura menor que uno implica (por la ley de intervalo) que la aceleración lineal perfecta es imposible en $p$ procesadores. ^{[ 9 ]}

Ejecución en un número limitado de procesadores

El análisis de algoritmos paralelos se suele realizar bajo el supuesto de que se dispone de un número ilimitado de procesadores. Esto no es realista, pero no supone un problema, ya que cualquier cálculo que pueda ejecutarse en paralelo en $N$ procesadores puede ejecutarse en $p < N$ procesadores permitiendo que cada procesador ejecute múltiples unidades de trabajo. Un resultado conocido como la ley de Brent establece que se puede realizar dicha "simulación" en un tiempo $T p$ , acotado por ^{[ 11 ].}

T_{p}\leq T_{N}+{\frac {T_{1}-T_{N}}{p}},

o, menos precisamente, ^{[ 6 ]}

T_{p}=O\left(T_{N}+{\frac {T_{1}}{p}}\right).

Una declaración alternativa de la ley limita $T p$ por encima y por debajo de

{\frac {T_{1}}{p}}\leq T_{p}\leq {\frac {T_{1}}{p}}+T_{\infty }

.

demostrando que el intervalo (profundidad) $T \infty$ y el trabajo $T 1$ juntos proporcionan límites razonables para el tiempo de cálculo. ^{[ 2 ]}

Referencias

↑ Shiloach, Yossi; Vishkin, Uzi (1982). "Un algoritmo de flujo máximo paralelo O ( n ² log n )". Journal of Algorithms . 3 (2): 128– 146. doi : 10.1016/0196-6774(82)90013-X .
1 2 Brent, Richard P. (1974-04-01). "La evaluación paralela de expresiones aritméticas generales". Journal of the ACM . 21 (2): 201– 206. CiteSeerX 10.1.1.100.9361 . doi : 10.1145/321812.321815 . ISSN 0004-5411 . S2CID 16416106 .
↑ JaJa, Joseph (1992). Introducción a los algoritmos paralelos . Addison-Wesley. ISBN 978-0-201-54856-3.
^ Keller, Jorg; Kessler, Cristoph W.; Traeff, Jesper L. (2001). Programación práctica de PRAM . Wiley-Interscience. ISBN 978-0-471-35351-5.
↑ Vishkin, Uzi (2009). Pensando en paralelo: algunos algoritmos y técnicas básicas de procesamiento paralelo de datos, 104 páginas (PDF) . Apuntes de clase de cursos sobre algoritmos paralelos impartidos desde 1992 en la Universidad de Maryland, College Park, la Universidad de Tel Aviv y el Technion.
1 2 3 4 5 6 Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). Algoritmos paralelos . CRC Press. pág. 10. CiteSeerX 10.1.1.466.8142 .
↑ Blelloch, Guy (1996). "Programación de algoritmos paralelos" (PDF) . Communications of the ACM . 39 (3): 85– 97. CiteSeerX 10.1.1.141.5884 . doi : 10.1145/227234.227246 . S2CID 12118850 .
↑ Michael McCool; James Reinders; Arch Robison (2013). Programación paralela estructurada: patrones para una computación eficiente . Elsevier. págs. 4–5 .
1 2 3 4 5 6 Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. págs. 779–784 . ISBN 0-262-03384-4.
↑ Kurgalin, Sergei; Borzunov, Sergei (2020). El cuaderno de ejercicios de matemáticas discretas: un manual complementario que utiliza Python . Textos en Ciencias de la Computación (2.ª ed.). Cham, Suiza: Springer Naturel. ISBN 978-3-030-42220-2.
↑ Gustafson, John L. (2011). «El teorema de Brent». Enciclopedia de computación paralela . págs. 182–185 . doi : 10.1007/978-0-387-09766-4_80 . ISBN 978-0-387-09765-7.

[shiloach-1] Shiloach, Yossi; Vishkin, Uzi (1982). "Un algoritmo de flujo máximo paralelo O ( n ² log n )". Journal of Algorithms . 3 (2): 128– 146. doi : 10.1016/0196-6774(82)90013-X .

[brent-2] 1 2 Brent, Richard P. (1974-04-01). "La evaluación paralela de expresiones aritméticas generales". Journal of the ACM . 21 (2): 201– 206. CiteSeerX 10.1.1.100.9361 . doi : 10.1145/321812.321815 . ISSN 0004-5411 . S2CID 16416106 .

[jaja-3] JaJa, Joseph (1992). Introducción a los algoritmos paralelos . Addison-Wesley. ISBN 978-0-201-54856-3.

[kkt-4] Keller, Jorg; Kessler, Cristoph W.; Traeff, Jesper L. (2001). Programación práctica de PRAM . Wiley-Interscience. ISBN 978-0-471-35351-5.

[uv-5] Vishkin, Uzi (2009). Pensando en paralelo: algunos algoritmos y técnicas básicas de procesamiento paralelo de datos, 104 páginas (PDF) . Apuntes de clase de cursos sobre algoritmos paralelos impartidos desde 1992 en la Universidad de Maryland, College Park, la Universidad de Tel Aviv y el Technion.

[casanova-6] 1 2 3 4 5 6 Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). Algoritmos paralelos . CRC Press. pág. 10. CiteSeerX 10.1.1.466.8142 .

[cacm-7] Blelloch, Guy (1996). "Programación de algoritmos paralelos" (PDF) . Communications of the ACM . 39 (3): 85– 97. CiteSeerX 10.1.1.141.5884 . doi : 10.1145/227234.227246 . S2CID 12118850 .

[spp-8] Michael McCool; James Reinders; Arch Robison (2013). Programación paralela estructurada: patrones para una computación eficiente . Elsevier. págs. 4–5 .

[clrs-9] 1 2 3 4 5 6 Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. págs. 779–784 . ISBN 0-262-03384-4.

[10] Kurgalin, Sergei; Borzunov, Sergei (2020). El cuaderno de ejercicios de matemáticas discretas: un manual complementario que utiliza Python . Textos en Ciencias de la Computación (2.ª ed.). Cham, Suiza: Springer Naturel. ISBN 978-3-030-42220-2.

[11] Gustafson, John L. (2011). «El teorema de Brent». Enciclopedia de computación paralela . págs. 182–185 . doi : 10.1007/978-0-387-09766-4_80 . ISBN 978-0-387-09765-7.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

8 ] Alternativamente

[ 9 ]

[ 10 ]

[ 11 ].

Fondo

Definiciones

Ejecución en un número limitado de procesadores

Referencias

Articulos relacionados