Análisis de algoritmos paralelos

En informática, el análisis de algoritmos paralelos es el proceso de encontrar la complejidad computacional de algoritmos ejecutados en paralelo (la cantidad de tiempo, almacenamiento u otros recursos necesarios para ejecutarlos). En muchos aspectos, el análisis de algoritmos paralelos es similar al análisis de algoritmos secuenciales , pero generalmente es más complejo porque se debe razonar sobre el comportamiento de múltiples subprocesos de ejecución que cooperan entre sí. Uno de los objetivos principales del análisis paralelo es comprender cómo cambia el uso de recursos (velocidad, espacio, etc.) de un algoritmo paralelo a medida que cambia el número de procesadores.

Fondo

^{Shiloach y Vishkin [1]} introdujeron originalmente un marco de trabajo denominado tiempo de trabajo (WT) (a veces llamado profundidad de trabajo o duración del trabajo) para conceptualizar y describir algoritmos paralelos. En el marco de trabajo WT, un algoritmo paralelo se describe primero en términos de rondas paralelas. Para cada ronda, se caracterizan las operaciones que se realizarán, pero se pueden suprimir varios aspectos. Por ejemplo, no es necesario que esté claro el número de operaciones en cada ronda, no es necesario mencionar los procesadores y no es necesario tener en cuenta ninguna información que pueda ayudar con la asignación de procesadores a trabajos. En segundo lugar, se proporciona la información suprimida. La inclusión de la información suprimida está guiada por la prueba de un teorema de programación debido a Brent, ^[2] que se explica más adelante en este artículo. El marco de trabajo WT es útil ya que, si bien puede simplificar en gran medida la descripción inicial de un algoritmo paralelo, insertar los detalles suprimidos por esa descripción inicial a menudo no es muy difícil. Por ejemplo, el marco WT se adoptó como el marco de presentación básico en los libros de algoritmos paralelos (para el modelo PRAM de máquina de acceso aleatorio paralelo ) ^[3] y ^[4] , así como en las notas de clase. ^[5] La siguiente descripción general 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 se ejecutan cálculos en una máquina que tiene $p$ procesadores. Sea $T p$ el tiempo que transcurre entre el inicio y el final del cálculo. El análisis del tiempo de ejecución del cálculo se centra en los siguientes conceptos:

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 por 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 amplitud es la longitud de la serie más larga de operaciones que deben realizarse secuencialmente debido a las dependencias de datos (laLa profundidad también puede denominarselongitud de la ruta crítica del cálculo.^[7]Minimizar la profundidad/intervalo es importante al diseñar algoritmos paralelos, porque la profundidad/intervalo determina el tiempo de ejecución más corto posible.^[8]Alternativamente, el intervalo 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ómputo es la cantidad $pT p$ . Esto expresa el tiempo total empleado, por todos los procesadores, tanto en el cómputo como en la espera. ^[6]

De las definiciones de trabajo, duración y coste se desprenden varios resultados útiles:

Ley de trabajo . El coste 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 amplitud . Un número finito $p$ de procesadores no puede superar a un número infinito, de modo que $T p \geq T \infty$ . ^[9]

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

La aceleración es la ganancia de velocidad que se logra con la ejecución paralela 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 simples de computación porque la ley de trabajo implica que $T 1 / T p \leq p$ ( la aceleración superlineal puede ocurrir en la práctica debido a los efectos de la jerarquía de memoria ). La situación $T 1 / T p = p$ se llama aceleración lineal perfecta.^[9] Un algoritmo que exhibe aceleración lineal se dice que 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 relación $T 1 / T \infty$ . Representa la aceleración máxima posible en cualquier número de procesadores. Por la ley de amplitud, 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 amplitud) 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 lleva a cabo generalmente bajo el supuesto de que se dispone de un número ilimitado de procesadores. Esto no es realista, pero no es un problema, ya que cualquier cálculo que pueda ejecutarse en paralelo en $N$ procesadores se puede ejecutar en $p < N$ procesadores permitiendo que cada procesador ejecute múltiples unidades de trabajo. Un resultado llamado ley de Brent establece que se puede realizar una "simulación" de este tipo 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 por

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

mostrando que el lapso (profundidad) $T \infty$ y el trabajo $T 1$ juntos proporcionan límites razonables en el tiempo de cálculo. ^[2]

Referencias

^ Shiloach, Yossi; Vishkin, Uzi (1982). "Un algoritmo de flujo máximo paralelo O ( n ² log n )". Revista de algoritmos . 3 (2): 128–146. doi :10.1016/0196-6774(82)90013-X.
^ ab Brent, Richard P. (1974-04-01). "La evaluación paralela de expresiones aritméticas generales". Revista de la 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). Pensar en paralelo: algunos algoritmos y técnicas básicas de datos paralelos, 104 páginas (PDF) . Apuntes de clases de cursos sobre algoritmos paralelos impartidos desde 1992 en la Universidad de Maryland, College Park, la Universidad de Tel Aviv y el Technion.
^ abcdef Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). Algoritmos paralelos . Prensa CRC. pag. 10. CiteSeerX 10.1.1.466.8142 .
^ Blelloch, Guy (1996). "Programación de algoritmos paralelos" (PDF) . Comunicaciones de la 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 computación eficiente . Elsevier. págs. 4-5.
^ abcdef 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 libro de ejercicios de matemáticas discretas: un manual complementario que utiliza Python . Textos en informática (2.ª ed.). Cham, Suiza: Springer Naturel. ISBN 978-3-030-42220-2.
^ Gustafson, John L. (2011). "Teorema de Brent". Enciclopedia de computación paralela . pp. 182–185. doi :10.1007/978-0-387-09766-4_80. ISBN . 978-0-387-09765-7.