Descripción general
En informática, el análisis de algoritmos paralelos es el proceso de encontrar la complejidad computacional de los 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 complicado porque uno debe razonar sobre el comportamiento de múltiples subprocesos de ejecución que cooperan. 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 llamado tiempo de trabajo (WT) (a veces llamado profundidad de trabajo o lapso de trabajo) para conceptualizar y describir algoritmos paralelos. En el marco de 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 suprimir varias cuestiones. Por ejemplo, no es necesario que quede claro el número de operaciones en cada ronda, no es necesario mencionar los procesadores y no es necesario contabilizar cualquier información que pueda ayudar con la asignación de procesadores a los 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 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 fue adoptado como 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 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
Suponga que los cálculos se ejecutan en una máquina que tiene p procesadores. Sea T p el tiempo que transcurre entre el inicio del cálculo y su final. 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, denominado T 1 .
- La profundidad o tramo es la longitud de la serie más larga de operaciones que deben realizarse secuencialmente debido a dependencias de datos (la ruta crítica ). La profundidad también se puede llamar la longitud de la ruta crítica del cálculo. [7] Minimizar la profundidad / tramo es importante en el diseño de algoritmos paralelos, porque la profundidad / tramo determina el tiempo de ejecución más corto posible. [8] Alternativamente, el lapso se puede definir como el tiempo T ∞ dedicado a la computación 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 computación como en espera. [6]
Varios resultados útiles se derivan de las definiciones de trabajo, duración y costo:
- Derecho laboral . El costo es siempre al menos el trabajo: pT p ≥ T 1 . Esto se deriva del hecho de que p procesadores pueden realizar como máximo p operaciones en paralelo. [6] [9]
- Ley de extensión . Un número finito p de procesadores no puede superar a un número infinito, de modo que T p ≥ T ∞ . [9]
Usando estas definiciones y leyes, se pueden dar las siguientes medidas de desempeño:
- Speedup es la ganancia de velocidad obtenida por la ejecución paralela en comparación con la ejecución secuencial: S p = T 1 ∕ T p . Cuando la aceleración es Ω ( n ) para el tamaño de entrada n (usando la notación O grande ), la aceleración es lineal, lo cual es óptimo en modelos simples de cálculo porque la ley de trabajo implica que T 1 ∕ T p ≤ p ( aceleración superlineal puede ocurrir en la práctica debido a los efectos de la jerarquía de la memoria ). La situación T 1 ∕ T p = p se llama aceleración lineal perfecta. [9] Se dice que un algoritmo que exhibe una aceleración lineal es escalable . [6]
- La eficiencia es la aceleración por procesador, S p ∕ p . [6]
- El paralelismo es la relación T 1 ∕ T ∞ . Representa la máxima aceleración posible en cualquier número de procesadores. Según la ley del intervalo, el paralelismo limita la aceleración: si p > T 1 ∕ T ∞ , entonces:
. [9]
- La holgura es T 1 ∕ ( pT ∞ ) . Una holgura menor que uno implica (según la ley del intervalo) que la aceleración lineal perfecta es imposible en los procesadores p . [9]
Ejecución en un número limitado de procesadores
El análisis de algoritmos paralelos se realiza normalmente 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 dejando que cada procesador ejecute múltiples unidades de trabajo. Un resultado llamado ley de Brent establece que se puede realizar tal "simulación" en el tiempo T p , delimitado por [10]
o, menos precisamente, [6]
Un enunciado alternativo de la ley limita T p arriba y abajo por
- .
mostrando que el tramo (profundidad) T ∞ 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 2 log n )". Revista de algoritmos . 3 (2): 128-146. doi : 10.1016 / 0196-6774 (82) 90013-X .
- ^ a b Brent, Richard P. (1 de abril de 1974). "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ásicos de datos paralelos, 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.
- ^ a b c d e f 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 una computación eficiente . Elsevier. págs. 4-5.
- ^ a b c d e f 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.
- ^ Gustafson, John L. (2011). "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.