Computación paralela

La supercomputadora Cray-2 fue la más rápida del mundo desde 1985 hasta 1989.
La supercomputadora paralela Blue Gene de IBM.

La computación paralela es una forma de cómputo en la que muchas instrucciones se ejecutan simultáneamente,[4]

Las computadoras paralelas pueden clasificarse según el nivel de paralelismo que admite su hardware: equipos con procesadores multinúcleo y multi-procesador que tienen múltiples elementos de procesamiento dentro de una sola máquina y los clústeres, MPPS y grids que utilizan varios equipos para trabajar en la misma tarea. Muchas veces, para acelerar tareas específicas, se utilizan arquitecturas especializadas de computación en paralelo junto a procesadores tradicionales.

Los programas informáticos paralelos son más difíciles de escribir que los secuenciales,[5] porque la concurrencia introduce nuevos tipos de errores de software, siendo las condiciones de carrera los más comunes. La comunicación y sincronización entre diferentes subtareas son algunos de los mayores obstáculos para obtener un buen rendimiento del programa paralelo.

La máxima aceleración posible de un programa como resultado de la paralelización se conoce como la ley de Amdahl.

Conceptos básicos

Tradicionalmente, los programas informáticos se han escrito para el cómputo en serie. Para resolver un problema, se construye un algoritmo y se implementa como un flujo en serie de instrucciones. Estas instrucciones se ejecutan en una unidad central de procesamiento en un ordenador. Sólo puede ejecutarse una instrucción a la vez y un tiempo después de que la instrucción ha terminado, se ejecuta la siguiente.[6]

La computación en paralelo, por el contrario, utiliza simultáneamente múltiples elementos de procesamiento para resolver un problema. Esto se logra mediante la división del problema en partes independientes de modo que cada elemento de procesamiento pueda ejecutar su parte del algoritmo de manera simultánea con los otros. Los elementos de procesamiento son diversos e incluyen recursos tales como una computadora con múltiples procesadores, varios ordenadores en red, hardware especializado, o cualquier combinación de los anteriores.[6]

El aumento de la frecuencia fue la razón dominante de las mejoras en el rendimiento de las computadoras desde mediados de 1980 hasta el año 2004. El tiempo de ejecución de un programa es igual al número de instrucciones multiplicado por el tiempo promedio por instrucción. Manteniendo todo lo demás constante, el aumento de la frecuencia de reloj reduce el tiempo medio que tarda en ejecutarse una instrucción, por tanto un aumento en la frecuencia reduce el tiempo de ejecución de los programas de cómputo.[7]

Sin embargo, el consumo de energía de un chip está dada por la ecuación P = C × V2 × F, donde P es la potencia, C es el cambio de capacitancia por ciclo de reloj —proporcional al número de transistores cuyas entradas cambian—, V es la tensión, y F es la frecuencia del procesador (ciclos por segundo).[9]

La ley de Moore es la observación empírica de que la densidad de transistores en un microprocesador se duplica cada 18 a 24 meses.[10] A pesar de los problemas de consumo de energía, y las repetidas predicciones de su fin, la ley de Moore sigue vigente. Con el fin del aumento de la frecuencia, estos transistores adicionales —que ya no se utilizan para el aumento de la frecuencia— se pueden utilizar para añadir hardware adicional que permita la computación paralela.

Ley de Amdahl y ley de Gustafson

Representación gráfica de la ley de Amdahl. La mejora en la velocidad de ejecución de un programa como resultado de la paralelización está limitada por la porción del programa que no se puede paralelizar. Por ejemplo, si el 10% del programa no puede paralelizarse, el máximo teórico de aceleración utilizando la computación en paralelo sería de 10x no importa cuántos procesadores se utilicen.

Idealmente, la aceleración a partir de la paralelización es lineal, doblar el número de elementos de procesamiento debe reducir a la mitad el tiempo de ejecución y doblarlo por segunda vez debe nuevamente reducir el tiempo a la mitad. Sin embargo, muy pocos algoritmos paralelos logran una aceleración óptima. La mayoría tienen una aceleración casi lineal para un pequeño número de elementos de procesamiento, y pasa a ser constante para un gran número de elementos de procesamiento.

La aceleración potencial de un algoritmo en una plataforma de cómputo en paralelo está dada por la ley de Amdahl, formulada originalmente por Gene Amdahl en la década de 1960.[11] Esta señala que una pequeña porción del programa que no pueda paralelizarse va a limitar la aceleración que se logra con la paralelización. Los programas que resuelven problemas matemáticos o ingenieriles típicamente consisten en varias partes paralelizables y varias no paralelizables (secuenciales). Si es la fracción de tiempo que un programa gasta en partes no paralelizables, luego

es la máxima aceleración que se puede alcanzar con la paralelización del programa. Si la parte secuencial del programa abarca el 10% del tiempo de ejecución, se puede obtener no más de 10× de aceleración, independientemente de cuántos procesadores se añadan. Esto pone un límite superior a la utilidad de añadir más unidades de ejecución paralelas. «Cuando una tarea no puede divididirse debido a las limitaciones secuenciales, la aplicación de un mayor esfuerzo no tiene efecto sobre la programación. La gestación de un niño toma nueve meses, no importa cuántas mujeres se le asigne».[12]

La ley de Gustafson es otra ley en computación que está en estrecha relación con la ley de Amdahl.[13] Señala que el aumento de velocidad con procesadores es

Supongamos que una tarea tiene dos partes independientes, A y B. B tarda aproximadamente 25% del tiempo total. Con esfuerzo adicional, un programador puede hacer esta parte cinco veces más rápida, pero esto reduce el tiempo de cálculo global por muy poco. Por otro lado, puede que sea necesario poco trabajo para hacer que la parte A sea doble de rápida. Esto haría el cálculo mucho más rápido que mediante la optimización de la parte B, a pesar de que B tiene una mayor aceleración (5x frente a 2×).

Ambas leyes asumen que el tiempo de funcionamiento de la parte secuencial del programa es independiente del número de procesadores. La ley de Amdahl supone que todo el problema es de tamaño fijo, por lo que la cantidad total de trabajo que se hará en paralelo también es independiente del número de procesadores, mientras que la ley de Gustafson supone que la cantidad total de trabajo que se hará en paralelo varía linealmente con el número de procesadores.

Dependencias

Entender la dependencia de datos es fundamental en la implementación de algoritmos paralelos. Ningún programa puede ejecutar más rápidamente que la cadena más larga de cálculos dependientes (conocida como la ruta crítica), ya que los cálculos que dependen de cálculos previos en la cadena deben ejecutarse en orden. Sin embargo, la mayoría de los algoritmos no consisten sólo de una larga cadena de cálculos dependientes; generalmente hay oportunidades para ejecutar cálculos independientes en paralelo.

Sea Pi y Pj dos segmentos del programa. Las condiciones de Bernstein[14] describen cuando los dos segmentos son independientes y pueden ejecutarse en paralelo. Para Pi, sean Ii todas las variables de entrada y Oi las variables de salida, y del mismo modo para Pj. P i y Pj son independientes si satisfacen

Una violación de la primera condición introduce una dependencia de flujo, correspondiente al primer segmento que produce un resultado utilizado por el segundo segmento. La segunda condición representa una anti-dependencia, cuando el segundo segmento (Pj) produce una variable que necesita el primer segmento (Pi). La tercera y última condición representa una dependencia de salida: Cuando dos segmentos escriben en el mismo lugar, el resultado viene del último segmento ejecutado.[15]

Considere las siguientes funciones, que demuestran varios tipos de dependencias:

1: función Dep(a, b)
2: c: = a · b
3: d: = 3 · c
4: fin función

La operación 3 en Dep(a, b) no puede ejecutarse antes de —o incluso en paralelo con— la operación 2, ya que en la operación 3 se utiliza un resultado de la operación 2. Esto viola la condición 1, y por tanto introduce una dependencia de flujo.

1: función NoDep (a, b)
2: c: = a · b
3: d: b = 3 ·
4: e: = a + b
5: fin función

En este ejemplo, no existen dependencias entre las instrucciones, por lo que todos ellos se pueden ejecutar en paralelo.

Las condiciones de Bernstein no permiten que la memoria se comparta entre los diferentes procesos. Por esto son necesarios algunos medios que impongan un ordenamiento entre los accesos tales como semáforos, barreras o algún otro método de sincronización.

Condiciones de carrera, exclusión mutua, sincronización, y desaceleración paralela

Las subtareas en un programa paralelo a menudo son llamadas hilos. Algunas arquitecturas de computación paralela utilizan versiones más pequeñas y ligeras de hilos conocidas como hebras, mientras que otros utilizan versiones más grandes conocidos como procesos. Sin embargo, «hilos» es generalmente aceptado como un término genérico para las subtareas. Los hilos a menudo tendrán que actualizar algunas variables que se comparten entre ellos. Las instrucciones entre los dos programas pueden entrelazarse en cualquier orden. Por ejemplo, considere el siguiente programa:

Hilo A Hilo B
1A: Lee variable V 1B: Lee variable V
2A: Añadir 1 a la variable V 2B: Añadir 1 a la variable V
3A: Escribir en la variable V 3B: Escribir en la variable V

Si la instrucción 1B se ejecuta entre 1A y 3A, o si la instrucción 1A se ejecuta entre 1B y 3B, el programa va a producir datos incorrectos. Esto se conoce como una condición de carrera. El programador debe utilizar un bloqueo (lock) para proporcionar exclusión mutua. Un bloqueo es una construcción del lenguaje de programación que permite a un hilo de tomar el control de una variable y evitar que otros hilos la lean o escriban, hasta que la variable esté desbloqueado. El hilo que mantiene el bloqueo es libre de ejecutar su sección crítica —la sección de un programa que requiere acceso exclusivo a alguna variable—, y desbloquear los datos cuando termine. Por lo tanto, para garantizar la correcta ejecución del programa, el programa anterior se puede reescribir usando bloqueos:

Hilo A Hilo B
1A: Bloquear variable V 1B: Bloquear variable V
2A: Lee variable V 2B: Lee variable V
3A: Añadir 1 a la variable V 3B: Añadir 1 a la variable V
4A: Escribir en la variable V 4B: Escribir en la variable V
5A: Desbloquear variable V 5B: Desbloquear variable V

Un hilo bloqueará con éxito la variable V, mientras que el otro hilo no podrá continuar hasta que V se desbloquee. Esto garantiza la correcta ejecución del programa. Si bien los bloqueos son necesarios para asegurar la ejecución correcta del programa, pueden ralentizar en gran medida un programa.

Bloquear múltiples variables utilizando cerraduras no atómicas introduce la posibilidad de que el programa alcance un bloqueo mutuo (deadlock). Un bloqueo atómico bloquea múltiples variables a la vez, si no puede bloquearlas todas, no se bloquea ninguna de ellas. Si hay dos hilos y cada uno necesita bloquear las mismas dos variables utilizando cerraduras no atómicas, es posible que un hilo bloquee uno de ellas y el otro bloquee la segunda variable. En tal caso se produce un bloqueo mutuo donde ningún hilo puede completar la ejecución.

Muchos programas paralelos requieren que sus subtareas actúen en sincronía. Esto requiere el uso de una barrera. Las barreras se implementan normalmente mediante un bloqueo. Una clase de algoritmos, conocida como algoritmos libres de bloqueo y libres de espera, evitan el uso de bloqueos y barreras. Sin embargo, este enfoque es generalmente difícil de implementar y requiere estructuras de datos correctamente diseñadas.

No todas las paralelizaciones conllevan una aceleración. Por lo general, mientras una tarea se divida en cada vez más hilos, estos hilos pasan una porción cada vez mayor de su tiempo comunicándose entre sí. Eventualmente, la sobrecarga de comunicación domina el tiempo empleado para resolver el problema, y ​​la paralelización adicional —dividir la carga de trabajo entre incluso más hilos— aumenta la cantidad de tiempo requerido para terminar. Esto se conoce como desaceleración paralela.

Paralelismo de grano fino, grano grueso y paralelismo vergonzoso

Las aplicaciones a menudo se clasifican según la frecuencia con que sus subtareas se sincronizan o comunican entre sí. Una aplicación muestra un paralelismo de grano fino si sus subtareas deben comunicase muchas veces por segundo, se considera paralelismo de grano grueso si no se comunican muchas veces por segundo, y es vergonzosamente paralelo si nunca o casi nunca se tienen que comunicar. Aplicaciones vergonzosamente paralelas son consideradas las más fáciles de paralelizar.

Modelos de consistencia

Leslie Lamport definió por primera vez el concepto de consistencia secuencial. También es conocido por su trabajo en el desarrollo del software LaTeX.

Los lenguajes de programación en paralelo y computadoras paralelas deben tener un modelo de consistencia de datos —también conocido como un modelo de memoria—. El modelo de consistencia define reglas para las operaciones en la memoria del ordenador y cómo se producen los resultados.

Uno de los primeros modelos de consistencia fue el modelo de consistencia secuencial de Leslie Lamport. La consistencia secuencial es la propiedad de un programa en la que su ejecución en paralelo produce los mismos resultados que un programa secuencial. Específicamente, es un programa secuencial consistente si «... los resultados de una ejecución son los mismos que se obtienen si las operaciones de todos los procesadores son ejecutadas en un orden secuencial, y las operaciones de cada procesador individual aparecen en esta secuencia en el orden especificado por el programa».[16]

La memoria transaccional es un tipo de modelo de consistencia. La memoria transaccional toma prestado de la teoría de base de datos el concepto de transacciones atómicas y las aplica a los accesos a memoria.

Matemáticamente, estos modelos se pueden representar de varias maneras. Las Redes de Petri, que se introdujeron en 1962 como tesis doctoral de Carl Adam Petri, fueron un primer intento de codificar las reglas de los modelos de consistencia. Más tarde fueron creadas las arquitecturas de flujo de datos para implementar físicamente las ideas de la teoría del flujo de datos. A principios de la década de 1970, los cálculos de procesos tales como la Comunicación de Sistemas y Comunicación de Procesos Secuenciales se desarrollaron para permitir un razonamiento algebraico sobre sistemas compuestos por elementos que interactúan entre sí. Adiciones más recientes a la familia de cálculo de proceso, como el cálculo-π, han añadido la capacidad para razonar acerca de las topologías dinámicas. Lógicas tales como la TLA+ de Lamport, y modelos matemáticos se han desarrollado para describir el comportamiento de sistemas concurrentes.

Taxonomía de Flynn

Michael J. Flynn creó uno de los primeros sistemas de clasificación de computadoras, programas paralelos y secuenciales, ahora conocida como la taxonomía de Flynn. Flynn clasifica los programas y computadoras atendiendo a si están operando con uno o varios conjuntos de instrucciones y si esas instrucciones se utilizan en una o varias series de datos.

Instrucción individual Instrucción múltiple
Datos individuales SISD MISD
Múltiples datos SIMD MIMD

La clasificación instrucción-única-dato-único ( SISD) es equivalente a un programa totalmente secuencial. La clasificación instrucción-única-datos-múltiples ( SIMD) es análoga a hacer la misma operación varias veces sobre un conjunto de datos grande. Esto se hace comúnmente en aplicaciones de procesamiento de señales. Instrucciones-múltiples-dato-único ( MISD) es una clasificación que rara vez se utiliza. A pesar de que se diseñaron arquitecturas de computadoras en esta categoría —como arreglos sistólicos—, muy pocas aplicaciones se materializaron. Los programas instrucciones-múltiples-datos-múltiples ( MIMD) constituyen el tipo más común de programas paralelos.

Según David A. Patterson y John L. Hennessy, «Algunas máquinas son híbridos de estas categorías, por supuesto, este modelo clásico ha sobrevivido porque es simple, fácil de entender, y da una buena primera aproximación. Además, es, tal vez por su comprensibilidad, el esquema más utilizado.»[17]

Other Languages
azərbaycanca: Paralel hesablama
Bahasa Indonesia: Komputasi paralel
日本語: 並列計算
한국어: 병렬 컴퓨팅
română: Calcul paralel
Simple English: Parallel computing
slovenščina: Vzporedna obdelava
српски / srpski: Паралелна обрада
Tiếng Việt: Tính toán song song
中文: 并行计算