Computación paralela

IBM Blue Gene/P supercomputadora masivamente paralela

La computación paralela es un tipo de computación en la que se llevan a cabo muchos cálculos o procesos simultáneamente. Los problemas grandes a menudo se pueden dividir en otros más pequeños, que luego se pueden resolver al mismo tiempo. Hay varias formas diferentes de computación paralela: nivel de bit, nivel de instrucción, datos y paralelismo de tareas. El paralelismo se ha empleado durante mucho tiempo en la informática de alto rendimiento, pero ha ganado un mayor interés debido a las limitaciones físicas que impiden el escalado de frecuencia. Dado que el consumo de energía (y, en consecuencia, la generación de calor) por parte de las computadoras se ha convertido en una preocupación en los últimos años, la computación paralela se ha convertido en el paradigma dominante en la arquitectura de computadoras, principalmente en forma de procesadores multinúcleo.

La computación paralela está estrechamente relacionada con la computación concurrente: se usan juntas con frecuencia y, a menudo, se combinan, aunque las dos son distintas: es posible tener paralelismo sin simultaneidad y simultaneidad sin paralelismo (como multitarea mediante tiempo compartido en una CPU de un solo núcleo). En la computación paralela, una tarea computacional generalmente se divide en varias, a menudo muchas, subtareas muy similares que se pueden procesar de forma independiente y cuyos resultados se combinan luego, una vez completadas. Por el contrario, en la informática concurrente, los diversos procesos a menudo no abordan tareas relacionadas; cuando lo hacen, como es típico en la computación distribuida, las tareas separadas pueden tener una naturaleza variada y, a menudo, requieren cierta comunicación entre procesos durante la ejecución.

Las computadoras paralelas se pueden clasificar aproximadamente según el nivel en el que el hardware admite el paralelismo, con computadoras multinúcleo y multiprocesador que tienen múltiples elementos de procesamiento dentro de una sola máquina, mientras que los clústeres, MPP y grids usan varias computadoras para trabajar. en la misma tarea. Las arquitecturas informáticas paralelas especializadas a veces se utilizan junto con los procesadores tradicionales para acelerar tareas específicas.

En algunos casos, el paralelismo es transparente para el programador, como en el paralelismo a nivel de bit o de instrucción, pero los algoritmos paralelos explícitos, particularmente aquellos que usan concurrencia, son más difíciles de escribir que los secuenciales, porque la concurrencia introduce varios algoritmos nuevos. clases de posibles errores de software, de los cuales las condiciones de carrera son las más comunes. La comunicación y la sincronización entre las diferentes subtareas suelen ser algunos de los mayores obstáculos para obtener un rendimiento óptimo del programa paralelo.

La ley de Amdahl proporciona un límite superior teórico en la aceleración de un solo programa como resultado de la paralelización, que establece que está limitado por la fracción de tiempo durante el cual se puede utilizar la paralelización.

Antecedentes

Tradicionalmente, el software de computadora se ha escrito para computación en serie. Para resolver un problema, se construye e implementa un algoritmo como un flujo de instrucciones en serie. Estas instrucciones se ejecutan en una unidad central de procesamiento en una computadora. Solo se puede ejecutar una instrucción a la vez: una vez que finaliza esa instrucción, se ejecuta la siguiente.

La computación paralela, por otro lado, utiliza múltiples elementos de procesamiento simultáneamente para resolver un problema. Esto se logra dividiendo el problema en partes independientes para que cada elemento de procesamiento pueda ejecutar su parte del algoritmo simultáneamente con los demás. Los elementos de procesamiento pueden ser diversos e incluir recursos como una sola computadora con múltiples procesadores, varias computadoras en red, hardware especializado o cualquier combinación de los anteriores. Históricamente, la computación paralela se utilizó para la computación científica y la simulación de problemas científicos, particularmente en las ciencias naturales y de ingeniería, como la meteorología. Esto condujo al diseño de hardware y software paralelos, así como a la computación de alto rendimiento.

La escala de frecuencia fue la razón dominante para las mejoras en el rendimiento de la computadora desde mediados de la década de 1980 hasta 2004. El tiempo de ejecución de un programa es igual a la cantidad de instrucciones multiplicada por el tiempo promedio por instrucción. Manteniendo todo lo demás constante, el aumento de la frecuencia del reloj disminuye el tiempo promedio que se tarda en ejecutar una instrucción. Por lo tanto, un aumento en la frecuencia reduce el tiempo de ejecución de todos los programas vinculados a la computación. Sin embargo, el consumo de energía P de un chip viene dado por la ecuación P = C × V ² × F, donde C es la capacitancia que se cambia por ciclo de reloj (proporcional al número de transistores cuyas entradas cambian), V es el voltaje y F es la frecuencia del procesador (ciclos por segundo). Los aumentos en la frecuencia aumentan la cantidad de energía utilizada en un procesador. El aumento del consumo de energía del procesador condujo en última instancia a la cancelación de Intel el 8 de mayo de 2004 de sus procesadores Tejas y Jayhawk, que generalmente se cita como el final de la escala de frecuencia como el paradigma de arquitectura informática dominante.

Para lidiar con el problema del consumo de energía y el sobrecalentamiento, los principales fabricantes de unidades de procesamiento central (CPU o procesador) comenzaron a producir procesadores de bajo consumo con varios núcleos. El núcleo es la unidad informática del procesador y, en los procesadores multinúcleo, cada núcleo es independiente y puede acceder a la misma memoria al mismo tiempo. Los procesadores multinúcleo han llevado la computación paralela a las computadoras de escritorio. Por lo tanto, la paralelización de programas en serie se ha convertido en una tarea de programación principal. En 2012, los procesadores de cuatro núcleos se convirtieron en estándar para las computadoras de escritorio, mientras que los servidores tienen procesadores de más de 10 núcleos. A partir de la ley de Moore, se puede predecir que la cantidad de núcleos por procesador se duplicará cada 18 a 24 meses. Esto podría significar que después de 2020, un procesador típico tendrá docenas o cientos de núcleos, sin embargo, en realidad el estándar está en algún lugar en la región de 4 a 16 núcleos, con algunos diseños que tienen una combinación de núcleos de rendimiento y eficiencia (como ARM's big.LITTLE design) debido a restricciones térmicas y de diseño.

Un sistema operativo puede garantizar que diferentes tareas y programas de usuario se ejecuten en paralelo en los núcleos disponibles. Sin embargo, para que un programa de software en serie aproveche al máximo la arquitectura multinúcleo, el programador necesita reestructurar y paralelizar el código. Ya no se logrará acelerar el tiempo de ejecución del software de la aplicación a través del escalado de frecuencia, sino que los programadores deberán paralelizar su código de software para aprovechar el poder de cómputo cada vez mayor de las arquitecturas multinúcleo.

La ley de Amdahl y la ley de Gustafson

Una representación gráfica de la ley de Amdahl. La aceleración de un programa de paralelización está limitada por cuánto del programa puede ser paralelizado. Por ejemplo, si el 90% del programa puede ser paralizado, la velocidad máxima teórica usando computación paralela sería 10 veces sin importar cuántos procesadores se utilicen.

Supongamos que una tarea tiene dos partes independientes, A y B. Parte B toma aproximadamente el 25% del tiempo de la computación entera. Al trabajar muy duro, uno puede ser capaz de hacer esta parte 5 veces más rápido, pero esto sólo reduce el tiempo para toda la computación por un poco. En cambio, es posible que necesite realizar menos trabajo para hacer parte A Sé el doble de rápido. Esto hará que el cálculo sea mucho más rápido que mediante la optimización de la parte B, aunque parte B 's speedup es mayor por ratio, (5 veces contra 2 veces).

En condiciones óptimas, la aceleración de la paralelización sería lineal: duplicar la cantidad de elementos de procesamiento debería reducir a la mitad el tiempo de ejecución, y duplicarlo por segunda vez debería nuevamente reducir a la mitad el tiempo de ejecución. Sin embargo, muy pocos algoritmos paralelos logran una aceleración óptima. La mayoría de ellos tienen una aceleración casi lineal para una pequeña cantidad de elementos de procesamiento, que se reduce a un valor constante para una gran cantidad de elementos de procesamiento.

La aceleración potencial de un algoritmo en una plataforma informática paralela viene dada por la ley de Amdahl

Slatencia()s)=11− − p+ps=ss+p()1− − s){displaystyle S_{text{latency}(s)={frac {1}{1-p+{frac {} {fn}}={fnMic} {s}{s+p(1-s)}}

dónde

• S_latencia es la posibilidad de acelerar la ejecución de toda la tarea;
• s es la aceleración de la latencia de la ejecución de la parte paralelizable de la tarea;
• p es el porcentaje del tiempo de ejecución de toda la tarea relativa a la parte paralelisible de la tarea antes de la paralización.

Desde la S_latencia < 1/(1 - p), muestra que una pequeña parte del programa que no se puede paralelizar limitará la aceleración general disponible de la paralelización. Un programa que resuelve un gran problema matemático o de ingeniería normalmente constará de varias partes paralelizables y varias partes no paralelizables (serie). Si la parte no paralelizable de un programa representa el 10 % del tiempo de ejecución (p = 0,9), no podemos obtener una aceleración de más de 10 veces, independientemente de cuántos procesadores se agreguen. Esto pone un límite superior a la utilidad de agregar más unidades de ejecución paralelas. "Cuando una tarea no se puede dividir debido a restricciones secuenciales, la aplicación de más esfuerzo no tiene efecto en el cronograma. El parto de un niño toma nueve meses, no importa cuántas mujeres se asignen."

Una representación gráfica de la ley de Gustafson

La ley de Amdahl solo se aplica a los casos en los que el tamaño del problema es fijo. En la práctica, a medida que hay más recursos informáticos disponibles, tienden a usarse en problemas más grandes (conjuntos de datos más grandes), y el tiempo dedicado a la parte paralelizable a menudo crece mucho más rápido que el trabajo inherentemente en serie. En este caso, la ley de Gustafson da una evaluación menos pesimista y más realista del desempeño paralelo:

Slatencia()s)=1− − p+sp.{displaystyle S_{text{latency}(s)=1-p+sp.}

Tanto la ley de Amdahl como la ley de Gustafson suponen que el tiempo de ejecución de la parte serial del programa es independiente del número de procesadores. La ley de Amdahl asume que todo el problema tiene un tamaño fijo, de modo que la cantidad total de trabajo a realizar en paralelo también es independiente del número de procesadores, mientras que la ley de Gustafson asume que la cantidad total de trabajo a realizar en paralelo varía linealmente con el número de procesadores.

Dependencias

Comprender las dependencias de datos es fundamental para implementar algoritmos paralelos. Ningún programa puede ejecutarse más rápido que la cadena más larga de cálculos dependientes (conocida como ruta crítica), ya que los cálculos que dependen de cálculos anteriores en la cadena deben ejecutarse en orden. Sin embargo, la mayoría de los algoritmos no consisten simplemente en una larga cadena de cálculos dependientes; normalmente hay oportunidades para ejecutar cálculos independientes en paralelo.

Sean P_i y P_j ser dos segmentos de programa. Las condiciones de Bernstein describen cuándo los dos son independientes y se pueden ejecutar en paralelo. Para P_i, sea I_i todas las variables de entrada y O_i las variables de salida, y lo mismo para P _j. P_i y P_j son independientes si ellos satisfacen

Ij∩ ∩ Oi=∅ ∅ ,{displaystyle I_{j}cap O_{i}=varnothing}

Ii∩ ∩ Oj=∅ ∅ ,{displaystyle I_{i}cap O_{j}=varnothing}

Oi∩ ∩ Oj=∅ ∅ .{displaystyle O_{i}cap Nada.

La 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 antidependencia, cuando el segundo segmento produce una variable que necesita el primer segmento. La tercera y última condición representa una dependencia de salida: cuando dos segmentos escriben en la misma ubicación, el resultado proviene del último segmento ejecutado lógicamente.

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: función final

En este ejemplo, la instrucción 3 no se puede ejecutar antes (o incluso en paralelo con) la instrucción 2, porque la instrucción 3 usa un resultado de la instrucción 2. Viola la condición 1 y, por lo tanto, introduce una dependencia de flujo.

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

En este ejemplo, no hay dependencias entre las instrucciones, por lo que todas se pueden ejecutar en paralelo.

Las condiciones de Bernstein no permiten compartir memoria entre diferentes procesos. Para ello, es necesario algún medio de hacer cumplir un ordenamiento entre accesos, como semáforos, barreras o algún otro método de sincronización.

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

Las subtareas en un programa paralelo a menudo se denominan subprocesos. Algunas arquitecturas de computadoras paralelas usan versiones más pequeñas y livianas de subprocesos conocidas como fibras, mientras que otras usan versiones más grandes conocidas como procesos. Sin embargo, "subprocesos" es generalmente aceptado como un término genérico para subtareas. Los subprocesos a menudo necesitarán acceso sincronizado a un objeto u otro recurso, por ejemplo, cuando deben actualizar una variable que se comparte entre ellos. Sin sincronización, las instrucciones entre los dos hilos pueden intercalarse en cualquier orden. Por ejemplo, considere el siguiente programa:

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 producirá datos incorrectos. Esto se conoce como condición de carrera. El programador debe utilizar un bloqueo para proporcionar exclusión mutua. Un bloqueo es una construcción del lenguaje de programación que permite que un subproceso tome el control de una variable y evite que otros subprocesos la lean o escriban, hasta que esa variable se desbloquee. El subproceso 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 finaliza. Por lo tanto, para garantizar la ejecución correcta del programa, el programa anterior se puede reescribir para usar bloqueos:

Un subproceso bloqueará con éxito la variable V, mientras que el otro subproceso se bloqueará y no podrá continuar hasta que V se desbloquee nuevamente. Esto garantiza la correcta ejecución del programa. Los bloqueos pueden ser necesarios para garantizar la ejecución correcta del programa cuando los subprocesos deben serializar el acceso a los recursos, pero su uso puede ralentizar mucho un programa y afectar su confiabilidad.

Bloquear múltiples variables usando bloqueos no atómicos introduce la posibilidad de bloqueo del programa. Un bloqueo atómico bloquea múltiples variables a la vez. Si no puede bloquearlos a todos, no bloquea ninguno. Si dos subprocesos necesitan cada uno bloquear las mismas dos variables utilizando bloqueos no atómicos, es posible que un subproceso bloquee uno de ellos y el segundo subproceso bloquee la segunda variable. En tal caso, ninguno de los subprocesos puede completarse y se produce un interbloqueo.

Muchos programas paralelos requieren que sus subtareas actúen en sincronía. Esto requiere el uso de una barrera. Las barreras normalmente se implementan mediante un candado o un semáforo. Una clase de algoritmos, conocida como algoritmos sin bloqueo y sin espera, evita por completo 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 toda la paralelización da como resultado una aceleración. En general, a medida que una tarea se divide en más y más subprocesos, esos subprocesos pasan una parte cada vez mayor de su tiempo comunicándose entre sí o esperando entre sí para acceder a los recursos. Una vez que la sobrecarga de la contención de recursos o la comunicación domina el tiempo dedicado a otros cálculos, la paralelización adicional (es decir, dividir la carga de trabajo en más subprocesos) aumenta en lugar de disminuir la cantidad de tiempo necesario para finalizar. Este problema, conocido como ralentización paralela, se puede mejorar en algunos casos mediante el análisis y rediseño del software.

Paralelismo vergonzoso, de grano fino y de grano grueso

Las aplicaciones a menudo se clasifican según la frecuencia con la que sus subtareas necesitan sincronizarse o comunicarse entre sí. Una aplicación exhibe un paralelismo de grano fino si sus subtareas deben comunicarse muchas veces por segundo; exhibe un paralelismo de grano grueso si no se comunican muchas veces por segundo, y exhibe un paralelismo vergonzoso si rara vez o nunca tienen que comunicarse. Vergonzosamente, las aplicaciones paralelas se consideran las más fáciles de paralelizar.

Taxonomía de Flynn

Michael J. Flynn creó uno de los primeros sistemas de clasificación para computadoras y programas paralelos (y secuenciales), ahora conocido como la taxonomía de Flynn. Flynn clasificó los programas y las computadoras según si estaban operando usando un solo conjunto o múltiples conjuntos de instrucciones, y si esas instrucciones usaban o no un solo conjunto o múltiples conjuntos de datos.

La clasificación de instrucción única, datos únicos (SISD) es equivalente a un programa completamente secuencial. La clasificación de instrucción única-datos múltiples (SIMD) es análoga a hacer la misma operación repetidamente en un gran conjunto de datos. Esto se hace comúnmente en aplicaciones de procesamiento de señales. Multiple-instruction-single-data (MISD) es una clasificación que rara vez se usa. Si bien se idearon arquitecturas informáticas para hacer frente a esto (como los arreglos sistólicos), se materializaron pocas aplicaciones que encajaran en esta clase. Los programas de múltiples instrucciones y múltiples datos (MIMD) son, con mucho, 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, pero este modelo clásico ha sobrevivido porque es simple, fácil de entender y ofrece una buena primera aproximación. También es, quizás debido a su comprensibilidad, el esquema más utilizado."

Tipos de paralelismo

Paralelismo a nivel de bits

Taiwania 3 de Taiwán, un dispositivo de supercomputación paralelo que se unió a la investigación COVID-19.

Desde el advenimiento de la tecnología de fabricación de chips informáticos de integración a muy gran escala (VLSI) en la década de 1970 hasta aproximadamente 1986, la aceleración de la arquitectura informática estuvo impulsada por la duplicación del tamaño de las palabras informáticas: la cantidad de información que el procesador puede manipular. por ciclo. Aumentar el tamaño de la palabra reduce el número de instrucciones que el procesador debe ejecutar para realizar una operación en variables cuyo tamaño es mayor que la longitud de la palabra. Por ejemplo, cuando un procesador de 8 bits debe sumar dos enteros de 16 bits, el procesador primero debe sumar los 8 bits de orden inferior de cada entero usando la instrucción de suma estándar, luego sumar los 8 bits de orden superior usando un add-with -instrucción de acarreo y el bit de acarreo de la suma de orden inferior; por lo tanto, un procesador de 8 bits requiere dos instrucciones para completar una sola operación, mientras que un procesador de 16 bits podría completar la operación con una sola instrucción.

Históricamente, los microprocesadores de 4 bits fueron reemplazados por microprocesadores de 8 bits, luego de 16 bits y luego de 32 bits. Esta tendencia generalmente llegó a su fin con la introducción de procesadores de 32 bits, que ha sido un estándar en la informática de uso general durante dos décadas. No fue sino hasta principios de la década de 2000, con el advenimiento de las arquitecturas x86-64, que los procesadores de 64 bits se volvieron comunes.

Paralelismo a nivel de instrucción

Un procesador canónico sin gasoducto. Se necesitan cinco ciclos de reloj para completar una instrucción y por lo tanto el procesador puede emitir rendimiento subscalar (IPC = 0,2).

Un programa de computadora es, en esencia, un flujo de instrucciones ejecutadas por un procesador. Sin paralelismo a nivel de instrucciones, un procesador solo puede emitir menos de una instrucción por ciclo de reloj (IPC < 1). Estos procesadores se conocen como procesadores subescalares. Estas instrucciones se pueden reordenar y combinar en grupos que luego se ejecutan en paralelo sin cambiar el resultado del programa. Esto se conoce como paralelismo a nivel de instrucción. Los avances en el paralelismo a nivel de instrucción dominaron la arquitectura informática desde mediados de la década de 1980 hasta mediados de la década de 1990.

Un procesador de cinco etapas canónico. En el mejor escenario de caso, se necesita un ciclo de reloj para completar una instrucción y por lo tanto el procesador puede emitir un rendimiento escalar (IPC = 1).

Todos los procesadores modernos tienen canalizaciones de instrucciones de varias etapas. Cada etapa de la tubería corresponde a una acción diferente que el procesador realiza en esa instrucción en esa etapa; un procesador con una canalización de N etapas puede tener hasta N instrucciones diferentes en diferentes etapas de finalización y, por lo tanto, puede emitir una instrucción por ciclo de reloj (IPC = 1). Estos procesadores se conocen como procesadores escalares. El ejemplo canónico de un procesador segmentado es un procesador RISC, con cinco etapas: obtención de instrucciones (IF), decodificación de instrucciones (ID), ejecución (EX), acceso a memoria (MEM) y escritura de registro (WB). El procesador Pentium 4 tenía una canalización de 35 etapas.

Un procesador de cinco etapas canónico con dos unidades de ejecución. En el mejor escenario de caso, se necesita un ciclo de reloj para completar dos instrucciones y por lo tanto el procesador puede emitir rendimiento superscalar (IPC = 2 ± 1).

La mayoría de los procesadores modernos también tienen varias unidades de ejecución. Por lo general, combinan esta función con canalización y, por lo tanto, pueden emitir más de una instrucción por ciclo de reloj (IPC > 1). Estos procesadores se conocen como procesadores superescalares. Los procesadores superescalares se diferencian de los procesadores multinúcleo en que las diversas unidades de ejecución no son procesadores completos (es decir, unidades de procesamiento). Las instrucciones se pueden agrupar juntas solo si no hay dependencia de datos entre ellas. Scoreboarding y el algoritmo Tomasulo (que es similar al scoreboarding pero utiliza el cambio de nombre de registros) son dos de las técnicas más comunes para implementar la ejecución fuera de orden y el paralelismo a nivel de instrucción.

Paralelismo de tareas

Los paralelismos de tareas son la característica de un programa paralelo de que "se pueden realizar cálculos completamente diferentes en el mismo o en diferentes conjuntos de datos". Esto contrasta con el paralelismo de datos, donde el mismo cálculo se realiza en el mismo o en diferentes conjuntos de datos. El paralelismo de tareas implica la descomposición de una tarea en subtareas y luego asignar cada subtarea a un procesador para su ejecución. Luego, los procesadores ejecutarían estas subtareas al mismo tiempo y, a menudo, en forma cooperativa. El paralelismo de tareas no suele escalar con el tamaño de un problema.

Paralelismo a nivel de superpalabras

El paralelismo a nivel de superpalabras es una técnica de vectorización basada en el desenrollado de bucles y la vectorización básica de bloques. Se diferencia de los algoritmos de vectorización de bucles en que puede explotar el paralelismo del código en línea, como la manipulación de coordenadas, canales de color o bucles desenrollados a mano.

Hardware

Memoria y comunicación

La memoria principal en una computadora paralela es memoria compartida (compartida entre todos los elementos de procesamiento en un solo espacio de direcciones) o memoria distribuida (en la que cada elemento de procesamiento tiene su propio espacio de direcciones local). La memoria distribuida se refiere al hecho de que la memoria está distribuida lógicamente, pero a menudo implica que también está distribuida físicamente. La memoria compartida distribuida y la virtualización de memoria combinan los dos enfoques, donde el elemento de procesamiento tiene su propia memoria local y acceso a la memoria en procesadores no locales. Los accesos a la memoria local suelen ser más rápidos que los accesos a la memoria no local. En las supercomputadoras, el espacio de memoria compartida distribuida se puede implementar utilizando el modelo de programación como PGAS. Este modelo permite que los procesos en un nodo de cómputo accedan de manera transparente a la memoria remota de otro nodo de cómputo. Todos los nodos de cómputo también están conectados a un sistema de memoria compartida externa a través de una interconexión de alta velocidad, como Infiniband, este sistema de memoria compartida externa se conoce como búfer de ráfaga, que generalmente se construye a partir de matrices de memoria no volátil distribuidas físicamente a través de múltiples I/ O nodos.

Una visión lógica de una arquitectura de acceso a la memoria no uniforme (NUMA). Los procesadores en un directorio pueden acceder a la memoria de ese directorio con menos latencia de lo que pueden acceder a la memoria en la memoria del otro directorio.

Las arquitecturas informáticas en las que se puede acceder a cada elemento de la memoria principal con la misma latencia y ancho de banda se conocen como sistemas de acceso uniforme a la memoria (UMA). Por lo general, eso solo se puede lograr mediante un sistema de memoria compartida, en el que la memoria no se distribuye físicamente. Un sistema que no tiene esta propiedad se conoce como arquitectura de acceso a memoria no uniforme (NUMA). Los sistemas de memoria distribuida tienen acceso a la memoria no uniforme.

Los sistemas informáticos utilizan cachés: memorias pequeñas y rápidas ubicadas cerca del procesador que almacenan copias temporales de los valores de la memoria (cercanas tanto en el sentido físico como lógico). Los sistemas informáticos paralelos tienen dificultades con las memorias caché que pueden almacenar el mismo valor en más de una ubicación, con la posibilidad de ejecución incorrecta del programa. Estas computadoras requieren un sistema de coherencia de caché, que realiza un seguimiento de los valores almacenados en caché y los purga estratégicamente, asegurando así la ejecución correcta del programa. La indagación de bus es uno de los métodos más comunes para realizar un seguimiento de los valores a los que se accede (y, por lo tanto, deben eliminarse). El diseño de grandes sistemas de coherencia de caché de alto rendimiento es un problema muy difícil en la arquitectura informática. Como resultado, las arquitecturas informáticas de memoria compartida no escalan tan bien como los sistemas de memoria distribuida.

La comunicación procesador-procesador y procesador-memoria se puede implementar en el hardware de varias maneras, incluso a través de memoria compartida (ya sea multipuerto o multiplexada), un interruptor de barra transversal, un bus compartido o una red de interconexión de una miríada de topologías que incluyen estrella, anillo, árbol, hipercubo, hipercubo gordo (un hipercubo con más de un procesador en un nodo) o malla n-dimensional.

Las computadoras paralelas basadas en redes interconectadas deben tener algún tipo de enrutamiento para permitir el paso de mensajes entre nodos que no están conectados directamente. Es probable que el medio utilizado para la comunicación entre los procesadores sea jerárquico en grandes máquinas multiprocesador.

Clases de computadoras paralelas

Las computadoras paralelas se pueden clasificar aproximadamente según el nivel en el que el hardware admite el paralelismo. Esta clasificación es ampliamente análoga a la distancia entre los nodos informáticos básicos. Estos no son mutuamente excluyentes; por ejemplo, los grupos de multiprocesadores simétricos son relativamente comunes.

Informática multinúcleo

Un procesador multinúcleo es un procesador que incluye varias unidades de procesamiento (llamadas "núcleos") en el mismo chip. Este procesador difiere de un procesador superescalar, que incluye múltiples unidades de ejecución y puede emitir múltiples instrucciones por ciclo de reloj desde un flujo de instrucciones (hilo); por el contrario, un procesador multinúcleo puede emitir múltiples instrucciones por ciclo de reloj desde múltiples flujos de instrucciones. El microprocesador Cell de IBM, diseñado para su uso en Sony PlayStation 3, es un destacado procesador multinúcleo. Cada núcleo en un procesador multinúcleo también puede ser potencialmente superescalar, es decir, en cada ciclo de reloj, cada núcleo puede emitir múltiples instrucciones desde un hilo.

Los subprocesos múltiples simultáneos (de los cuales Hyper-Threading de Intel es el más conocido) fue una forma temprana de pseudo-multi-coreísmo. Un procesador capaz de subprocesos múltiples simultáneos incluye múltiples unidades de ejecución en la misma unidad de procesamiento, es decir, tiene una arquitectura superescalar, y puede emitir múltiples instrucciones por ciclo de reloj desde múltiples subprocesos. El subprocesamiento múltiple temporal, por otro lado, incluye una sola unidad de ejecución en la misma unidad de procesamiento y puede emitir una instrucción a la vez desde múltiples subprocesos.

Multiprocesamiento simétrico

Un multiprocesador simétrico (SMP) es un sistema informático con varios procesadores idénticos que comparten memoria y se conectan a través de un bus. La contención de bus evita que las arquitecturas de bus se escalen. Como resultado, los SMP generalmente no comprenden más de 32 procesadores. Debido al pequeño tamaño de los procesadores y la reducción significativa en los requisitos de ancho de banda del bus logrados por las grandes cachés, estos multiprocesadores simétricos son extremadamente rentables, siempre que exista una cantidad suficiente de ancho de banda de memoria.

Informática distribuida

Una computadora distribuida (también conocida como multiprocesador de memoria distribuida) es un sistema informático de memoria distribuida en el que los elementos de procesamiento están conectados por una red. Las computadoras distribuidas son altamente escalables. Los términos "computación concurrente", "computación paralela" y "computación distribuida" tienen mucha superposición, y no existe una distinción clara entre ellos. El mismo sistema puede caracterizarse tanto como "paralelo" y "distribuido"; los procesadores en un sistema distribuido típico se ejecutan simultáneamente en paralelo.

Computación en clúster

A Beowulf cluster

Un clúster es un grupo de computadoras débilmente acopladas que trabajan juntas estrechamente, de modo que, en algunos aspectos, pueden considerarse como una sola computadora. Los clústeres se componen de varias máquinas independientes conectadas por una red. Si bien las máquinas en un clúster no tienen que ser simétricas, el equilibrio de carga es más difícil si no lo son. El tipo más común de clúster es el clúster Beowulf, que es un clúster implementado en múltiples computadoras comerciales idénticas conectadas con una red de área local Ethernet TCP/IP. La tecnología Beowulf fue desarrollada originalmente por Thomas Sterling y Donald Becker. El 87% de todas las supercomputadoras Top500 son clústeres. El resto son procesadores masivamente paralelos, que se explican a continuación.

Debido a que los sistemas de computación en cuadrícula (descritos a continuación) pueden manejar fácilmente problemas embarazosamente paralelos, los clústeres modernos generalmente están diseñados para manejar problemas más difíciles, problemas que requieren que los nodos compartan resultados intermedios entre sí con mayor frecuencia. Esto requiere un gran ancho de banda y, lo que es más importante, una red de interconexión de baja latencia. Muchas supercomputadoras históricas y actuales utilizan hardware de red personalizado de alto rendimiento diseñado específicamente para la computación en clúster, como la red Cray Gemini. A partir de 2014, la mayoría de las supercomputadoras actuales utilizan algún hardware de red estándar listo para usar, a menudo Myrinet, InfiniBand o Gigabit Ethernet.

Computación masivamente paralela

Un gabinete del Blue Gene/L de IBM supercomputer masivamente paralelo

Un procesador masivamente paralelo (MPP) es una sola computadora con muchos procesadores en red. Los MPP tienen muchas de las mismas características que los clústeres, pero los MPP tienen redes de interconexión especializadas (mientras que los clústeres utilizan hardware básico para la creación de redes). Los MPP también tienden a ser más grandes que los clústeres y, por lo general, tienen "mucho más" de 100 procesadores. En un MPP, "cada CPU contiene su propia memoria y copia del sistema operativo y la aplicación. Cada subsistema se comunica con los demás a través de una interconexión de alta velocidad."

Blue Gene/L de IBM, la quinta supercomputadora más rápida del mundo según el ranking TOP500 de junio de 2009, es un MPP.

Computación en red

La computación grid es la forma más distribuida de computación paralela. Hace uso de computadoras que se comunican a través de Internet para trabajar en un problema determinado. Debido al bajo ancho de banda y la latencia extremadamente alta disponible en Internet, la computación distribuida generalmente solo se ocupa de problemas embarazosamente paralelos.

La mayoría de las aplicaciones de grid computing utilizan middleware (software que se ubica entre el sistema operativo y la aplicación para administrar los recursos de la red y estandarizar la interfaz del software). El middleware de computación grid más común es la Infraestructura Abierta de Berkeley para Computación en Red (BOINC). A menudo, el software informático voluntario hace uso de "ciclos de repuesto", realizando cálculos en momentos en que una computadora está inactiva.

Ordenadores paralelos especializados

Dentro de la computación paralela, existen dispositivos paralelos especializados que siguen siendo áreas de interés específicas. Si bien no son específicos de un dominio, tienden a ser aplicables solo a unas pocas clases de problemas paralelos.

Informática reconfigurable con arreglos de puertas programables en campo

La computación reconfigurable es el uso de una matriz de puertas programables en campo (FPGA) como coprocesador de una computadora de uso general. Un FPGA es, en esencia, un chip de computadora que puede reconfigurarse para una tarea determinada.

Los FPGA se pueden programar con lenguajes de descripción de hardware como VHDL o Verilog. Sin embargo, la programación en estos lenguajes puede resultar tediosa. Varios proveedores han creado lenguajes C a HDL que intentan emular la sintaxis y la semántica del lenguaje de programación C, con el que la mayoría de los programadores están familiarizados. Los lenguajes C a HDL más conocidos son Mitrion-C, Impulse C y Handel-C. También se pueden usar subconjuntos específicos de SystemC basados en C++ para este propósito.

La decisión de AMD de abrir su tecnología HyperTransport a proveedores externos se ha convertido en la tecnología habilitadora para la computación reconfigurable de alto rendimiento. Según Michael R. D'Amour, director de operaciones de DRC Computer Corporation, "cuando entramos por primera vez en AMD, nos llamaron 'los ladrones de sockets'. Ahora nos llaman sus socios."

Informática de propósito general en unidades de procesamiento de gráficos (GPGPU)

Tesla de Nvidia Tarjeta GPGPU

La computación de propósito general en unidades de procesamiento de gráficos (GPGPU) es una tendencia bastante reciente en la investigación de ingeniería informática. Las GPU son coprocesadores que se han optimizado en gran medida para el procesamiento de gráficos por computadora. El procesamiento de gráficos por computadora es un campo dominado por las operaciones paralelas de datos, en particular las operaciones matriciales de álgebra lineal.

En los primeros días, los programas GPGPU usaban las API de gráficos normales para ejecutar programas. Sin embargo, se han creado varios lenguajes y plataformas de programación nuevos para realizar cálculos de propósito general en GPU con entornos de programación lanzados por Nvidia y AMD con CUDA y Stream SDK, respectivamente. Otros lenguajes de programación de GPU incluyen BrookGPU, PeakStream y RapidMind. Nvidia también ha lanzado productos específicos para computación en su serie Tesla. El consorcio de tecnología Khronos Group ha lanzado la especificación OpenCL, que es un marco para escribir programas que se ejecutan en plataformas que consisten en CPU y GPU. AMD, Apple, Intel, Nvidia y otros son compatibles con OpenCL.

Circuitos integrados específicos de la aplicación

Se han ideado varios enfoques de circuitos integrados específicos de la aplicación (ASIC) para tratar con aplicaciones paralelas.

Debido a que un ASIC es (por definición) específico para una aplicación determinada, puede optimizarse completamente para esa aplicación. Como resultado, para una aplicación dada, un ASIC tiende a superar a una computadora de propósito general. Sin embargo, los ASIC se crean mediante fotolitografía UV. Este proceso requiere un conjunto de máscaras, que puede ser extremadamente costoso. Un juego de máscaras puede costar más de un millón de dólares estadounidenses. (Cuanto más pequeños sean los transistores necesarios para el chip, más costosa será la máscara). Mientras tanto, los aumentos de rendimiento en la computación de propósito general a lo largo del tiempo (como se describe en la ley de Moore) tienden a eliminar estas ganancias en una sola vez. o dos generaciones de chips. El alto costo inicial y la tendencia a ser superada por la computación de propósito general impulsada por la ley de Moore han hecho que los ASIC sean inviables para la mayoría de las aplicaciones de computación paralela. Sin embargo, algunos han sido construidos. Un ejemplo es la máquina PFLOPS RIKEN MDGRAPE-3 que utiliza ASIC personalizados para la simulación de dinámica molecular.

Procesadores vectoriales

El Cray-1 es un procesador vectorial

Un procesador vectorial es una CPU o un sistema informático que puede ejecutar la misma instrucción en grandes conjuntos de datos. Los procesadores vectoriales tienen operaciones de alto nivel que funcionan en matrices lineales de números o vectores. Un ejemplo de operación vectorial es A = B × C, donde A, B y C son vectores de 64 elementos de números de coma flotante de 64 bits. Están estrechamente relacionados con la clasificación SIMD de Flynn.

Las computadoras Cray se hicieron famosas por sus computadoras de procesamiento de vectores en las décadas de 1970 y 1980. Sin embargo, los procesadores vectoriales, tanto como CPU como como sistemas informáticos completos, en general han desaparecido. Los conjuntos de instrucciones de procesadores modernos incluyen algunas instrucciones de procesamiento de vectores, como AltiVec de Freescale Semiconductor y Streaming SIMD Extensions (SSE) de Intel.

Software

Lenguajes de programación paralelos

Se han creado lenguajes de programación concurrentes, bibliotecas, API y modelos de programación paralela (como esqueletos algorítmicos) para programar computadoras paralelas. Estos generalmente se pueden dividir en clases según las suposiciones que hacen sobre la arquitectura de memoria subyacente: memoria compartida, memoria distribuida o memoria distribuida compartida. Los lenguajes de programación de memoria compartida se comunican mediante la manipulación de variables de memoria compartida. La memoria distribuida utiliza el paso de mensajes. POSIX Threads y OpenMP son dos de las API de memoria compartida más utilizadas, mientras que la interfaz de paso de mensajes (MPI) es la API del sistema de paso de mensajes más utilizada. Un concepto utilizado en la programación de programas paralelos es el concepto de futuro, donde una parte de un programa promete entregar un dato requerido a otra parte de un programa en algún momento futuro.

Los esfuerzos para estandarizar la programación paralela incluyen un estándar abierto llamado OpenHMPP para la programación paralela híbrida de múltiples núcleos. El modelo de programación basado en directivas de OpenHMPP ofrece una sintaxis para descargar de manera eficiente los cálculos en los aceleradores de hardware y para optimizar el movimiento de datos hacia/desde la memoria del hardware mediante llamadas a procedimientos remotos.

El auge de las GPU de consumo ha dado lugar a la compatibilidad con los núcleos informáticos, ya sea en las API de gráficos (conocidas como sombreadores informáticos), en las API dedicadas (como OpenCL) o en otras extensiones de lenguaje.

Paralelización automática

La paralelización automática de un programa secuencial por parte de un compilador es el "santo grial" de la computación paralela, especialmente con el límite antes mencionado de la frecuencia del procesador. A pesar de décadas de trabajo por parte de los investigadores de compiladores, la paralelización automática ha tenido un éxito limitado.

Los lenguajes de programación paralelos convencionales siguen siendo explícitamente paralelos o (en el mejor de los casos) parcialmente implícitos, en los que un programador le da al compilador directivas para la paralelización. Existen algunos lenguajes de programación paralelos totalmente implícitos: SISAL, Parallel Haskell, SequenceL, System C (para FPGA), Mitrion-C, VHDL y Verilog.

Punto de control de la aplicación

A medida que aumenta la complejidad de un sistema informático, el tiempo medio entre fallos suele disminuir. El control de aplicaciones es una técnica mediante la cual el sistema informático toma una "instantánea" de la aplicación—un registro de todas las asignaciones de recursos actuales y estados variables, similar a un volcado del núcleo—; esta información se puede utilizar para restaurar el programa si la computadora falla. El punto de control de la aplicación significa que el programa debe reiniciarse solo desde el último punto de control en lugar del principio. Si bien los puntos de control brindan beneficios en una variedad de situaciones, son especialmente útiles en sistemas altamente paralelos con una gran cantidad de procesadores utilizados en computación de alto rendimiento.

Métodos algorítmicos

A medida que las computadoras paralelas se vuelven más grandes y más rápidas, ahora podemos resolver problemas que anteriormente tomaban demasiado tiempo para ejecutarse. Campos tan variados como la bioinformática (para el plegamiento de proteínas y el análisis de secuencias) y la economía (para las finanzas matemáticas) se han beneficiado de la computación paralela. Los tipos comunes de problemas en aplicaciones de cómputo paralelo incluyen:

• Álgebra lineal Dense
• Álgebra lineal
• Métodos espectrales (como Cooley–Tukey Fast Fourier transform)
• Problemas del cuerpo (como la simulación Barnes-Hut)
• problemas de rejilla estructurados (como los métodos Lattice Boltzmann)
• Problemas de rejilla no estructurados (como se encuentra en el análisis de elementos finitos)
• Método Monte Carlo
• Lógica combinada (como técnicas criptográficas de fuerza bruta)
• Traversal Gráfico (como algoritmos de clasificación)
• Programación dinámica
• Métodos de rama y límites
• Modelos gráficos (como detectar modelos ocultos de Markov y construir redes Bayesian)
• simulación de máquina de estado finito

Tolerancia a fallos

La computación paralela también se puede aplicar al diseño de sistemas informáticos tolerantes a fallas, particularmente a través de sistemas lockstep que realizan la misma operación en paralelo. Esto proporciona redundancia en caso de que falle un componente y también permite la detección automática de errores y la corrección de errores si los resultados difieren. Estos métodos se pueden utilizar para ayudar a prevenir alteraciones de un solo evento causadas por errores transitorios. Si bien es posible que se requieran medidas adicionales en sistemas integrados o especializados, este método puede proporcionar un enfoque rentable para lograr una redundancia modular n en sistemas comerciales listos para usar.

Historia

ILLIAC IV, "el más famoso de los supercomputadores"

Los orígenes del paralelismo verdadero (MIMD) se remontan a Luigi Federico Menabrea y su Sketch of the Analytic Engine Invented by Charles Babbage.

En abril de 1958, Stanley Gill (Ferranti) habló sobre la programación paralela y la necesidad de ramificación y espera. También en 1958, los investigadores de IBM John Cocke y Daniel Slotnick discutieron por primera vez el uso del paralelismo en los cálculos numéricos. Burroughs Corporation presentó la D825 en 1962, una computadora de cuatro procesadores que accedía a hasta 16 módulos de memoria a través de un interruptor de barra transversal. En 1967, Amdahl y Slotnick publicaron un debate sobre la viabilidad del procesamiento paralelo en la Conferencia de la Federación Estadounidense de Sociedades de Procesamiento de la Información. Fue durante este debate que se acuñó la ley de Amdahl para definir el límite de aceleración debido al paralelismo.

En 1969, Honeywell presentó su primer sistema Multics, un sistema multiprocesador simétrico capaz de ejecutar hasta ocho procesadores en paralelo. C.mmp, un proyecto de multiprocesador de la Universidad Carnegie Mellon en la década de 1970, fue uno de los primeros multiprocesadores con más de unos pocos procesadores. El primer multiprocesador conectado por bus con cachés espía fue el Synapse N+1 en 1984.

Las computadoras paralelas SIMD se remontan a la década de 1970. La motivación detrás de las primeras computadoras SIMD era amortizar el retardo de puerta de la unidad de control del procesador en varias instrucciones. En 1964, Slotnick había propuesto construir una computadora masivamente paralela para el Laboratorio Nacional Lawrence Livermore. Su diseño fue financiado por la Fuerza Aérea de EE. UU., que fue el primer esfuerzo de computación paralela SIMD, ILLIAC IV. La clave de su diseño fue un paralelismo bastante alto, con hasta 256 procesadores, lo que permitió que la máquina trabajara con grandes conjuntos de datos en lo que luego se conocería como procesamiento vectorial. Sin embargo, ILLIAC IV fue llamada 'la más infame de las supercomputadoras', porque el proyecto solo se completó una cuarta parte, pero tomó 11 años y costó casi cuatro veces la estimación original. Cuando finalmente estuvo listo para ejecutar su primera aplicación real en 1976, fue superado por las supercomputadoras comerciales existentes, como la Cray-1.

Cerebro biológico como computadora masivamente paralela

A principios de la década de 1970, en el Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT, Marvin Minsky y Seymour Papert comenzaron a desarrollar la teoría de la Sociedad de la Mente, que considera el cerebro biológico como una computadora masivamente paralela. En 1986, Minsky publicó La sociedad de la mente, que afirma que “la mente está formada por muchos pequeños agentes, cada uno sin mente por sí mismo”. La teoría intenta explicar cómo lo que llamamos inteligencia podría ser producto de la interacción de partes no inteligentes. Minsky dice que la mayor fuente de ideas sobre la teoría provino de su trabajo al intentar crear una máquina que usa un brazo robótico, una cámara de video y una computadora para construir con bloques de niños.

Modelos similares (que también ven el cerebro biológico como una computadora masivamente paralela, es decir, el cerebro está formado por una constelación de agentes independientes o semiindependientes) también fueron descritos por:

• Thomas R. Blakeslee,
• Michael S. Gazzaniga,
• Robert E. Ornstein,
• Ernest Hilgard,
• Michio Kaku,
• George Ivanovich Gurdjieff,
• Modelo cerebral neurocluster.