La computación paralela es un tipo de computación en el que muchos cálculos o procesos se llevan a cabo simultáneamente. [1] Los problemas grandes a menudo se pueden dividir en problemas más pequeños, que luego se pueden resolver al mismo tiempo. Hay varias formas diferentes de computación paralela: a nivel de bits , a nivel de instrucciones , de datos y de tareas . El paralelismo se ha empleado durante mucho tiempo en la computación de alto rendimiento , pero ha ganado un interés más amplio debido a las restricciones físicas que impiden el escalado de frecuencia . [2] Como 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, [3] la computación paralela se ha convertido en el paradigma dominante en la arquitectura informática , principalmente en forma de procesadores multinúcleo . [4]
En informática , el paralelismo y la concurrencia son dos cosas diferentes: un programa paralelo utiliza múltiples núcleos de CPU , cada uno de los cuales realiza una tarea de forma independiente. Por otro lado, la concurrencia permite que un programa se ocupe de múltiples tareas incluso en un único núcleo de CPU; el núcleo cambia entre tareas (es decir, subprocesos ) sin completar necesariamente cada una de ellas. Un programa puede tener ambas, ninguna o una combinación de características de paralelismo y concurrencia. [5]
Las computadoras paralelas se pueden clasificar de forma general según el nivel en el que el hardware admite el paralelismo: las computadoras multinúcleo y multiprocesador tienen múltiples elementos de procesamiento dentro de una sola máquina, mientras que los clústeres , los MPP y las redes utilizan múltiples computadoras para trabajar en la misma tarea. A veces se utilizan arquitecturas especializadas de computadoras paralelas junto con procesadores tradicionales para acelerar tareas específicas.
En algunos casos, el paralelismo es transparente para el programador, como en el paralelismo a nivel de bits o de instrucciones, pero los algoritmos explícitamente paralelos , en particular los que utilizan concurrencia, son más difíciles de escribir que los secuenciales , [6] porque la concurrencia introduce varias nuevas clases de posibles errores de software , de los cuales las condiciones de carrera son los 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 establece un límite superior teórico para la aceleración de un solo programa como resultado de la paralelización : establece que está limitada por la fracción de tiempo durante la cual se puede utilizar la paralelización.
Tradicionalmente, el software de computadora se ha escrito para computación en serie . Para resolver un problema, se construye un algoritmo y se implementa como un flujo serial de instrucciones. Estas instrucciones se ejecutan en una unidad de procesamiento central en una computadora. Solo se puede ejecutar una instrucción a la vez; una vez que esa instrucción termina, se ejecuta la siguiente. [7]
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. [7] 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 . [8]
El escalamiento de frecuencia fue la razón principal para las mejoras en el rendimiento de las computadoras desde mediados de la década de 1980 hasta 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, aumentar la frecuencia de reloj disminuye el tiempo promedio que lleva ejecutar una instrucción. Un aumento en la frecuencia, por lo tanto, disminuye el tiempo de ejecución para todos los programas vinculados a la computación . [9] Sin embargo, el consumo de energía P por un chip está dado por la ecuación P = C × V 2 × F , donde C es la capacitancia que se conmuta 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). [10] Los aumentos en la frecuencia aumentan la cantidad de energía utilizada en un procesador. El aumento del consumo de energía del procesador llevó finalmente a la cancelación de Intel el 8 de mayo de 2004 de sus procesadores Tejas y Jayhawk , lo que generalmente se cita como el fin del escalamiento de frecuencia como el paradigma dominante de la arquitectura informática. [11]
Para lidiar con el problema del consumo de energía y el sobrecalentamiento, los principales fabricantes de unidades centrales de procesamiento (CPU o procesador) comenzaron a producir procesadores energéticamente eficientes con múltiples núcleos. El núcleo es la unidad de cómputo del procesador y en los procesadores multinúcleo cada núcleo es independiente y puede acceder a la misma memoria simultáneamente. Los procesadores multinúcleo han traído 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 general. 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 mezcla de núcleos de rendimiento y eficiencia (como el diseño big.LITTLE de ARM ) debido a restricciones térmicas y de diseño. [12] [ cita requerida ]
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 serial aproveche al máximo la arquitectura multinúcleo, el programador necesita reestructurar y paralelizar el código. Ya no se logrará una aceleración del tiempo de ejecución del software de aplicación mediante el escalado de frecuencias, sino que los programadores necesitarán paralelizar su código de software para aprovechar la creciente potencia de procesamiento de las arquitecturas multinúcleo. [13]
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 duplicarla una segunda vez debería reducirlo a la mitad nuevamente. 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 estabiliza en un valor constante para una gran cantidad de elementos de procesamiento.
La aceleración potencial de un algoritmo en una plataforma de computación paralela viene dada por la ley de Amdahl [14]
dónde
Como la latencia S < 1/(1 - p ) , se demuestra que una pequeña parte del programa que no se puede paralelizar limitará la aceleración total disponible a partir 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 (en 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 mayor que 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 particionar debido a restricciones secuenciales, la aplicación de más esfuerzo no tiene efecto sobre el cronograma. Tener un hijo lleva nueve meses, sin importar cuántas mujeres se asignen". [15]
La ley de Amdahl sólo se aplica a los casos en los que el tamaño del problema es fijo. En la práctica, a medida que se dispone de más recursos informáticos, estos tienden a utilizarse en problemas más grandes (conjuntos de datos más grandes), y el tiempo dedicado a la parte paralelizable suele crecer mucho más rápido que el trabajo inherentemente serial. [16] En este caso, la ley de Gustafson ofrece una evaluación menos pesimista y más realista del rendimiento paralelo: [17]
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 supone que todo el problema es de 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 supone que la cantidad total de trabajo a realizar en paralelo varía linealmente con el número de procesadores .
Comprender las dependencias de los 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 solo en una larga cadena de cálculos dependientes; generalmente existen oportunidades para ejecutar cálculos independientes en paralelo.
Sean P i y P j dos segmentos de programa. Las condiciones de Bernstein [18] describen cuándo los dos son independientes y pueden ejecutarse en paralelo. Para P i , sean 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 satisfacen
La violación de la primera condición introduce una dependencia de flujo, que corresponde a que el primer segmento produzca 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. [19]
Considere las siguientes funciones, que demuestran varios tipos de dependencias:
1: función Dep(a, b)2: c := a * b3:d:= 3*c4: 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 utiliza 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 * b3:d := 3 * b4: e := a + b5: función final
En este ejemplo, no hay dependencias entre las instrucciones, por lo que todas pueden ejecutarse en paralelo.
Las condiciones de Bernstein no permiten que la memoria sea compartida entre distintos procesos, por lo que es necesario algún medio que imponga un orden entre accesos, como semáforos , barreras o algún otro método de sincronización .
Las subtareas de un programa paralelo suelen denominarse subprocesos . Algunas arquitecturas informáticas paralelas utilizan versiones más pequeñas y ligeras de subprocesos, conocidas como fibras , mientras que otras utilizan versiones más grandes, conocidas como procesos . Sin embargo, "subprocesos" se acepta generalmente como un término genérico para las subtareas. [20] Los subprocesos a menudo necesitarán acceso sincronizado a un objeto u otro recurso , por ejemplo, cuando deben actualizar una variable que comparten. Sin sincronización, las instrucciones entre los dos subprocesos 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 usar un bloqueo para proporcionar exclusión mutua . Un bloqueo es una construcción del lenguaje de programación que permite a un hilo tomar el control de una variable y evitar que otros hilos la lean o escriban, hasta que esa variable se desbloquee. 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 de desbloquear los datos cuando finalice. Por lo tanto, para garantizar la ejecución correcta del programa, el programa anterior se puede reescribir para usar bloqueos:
Un hilo bloqueará con éxito la variable V, mientras que el otro hilo quedará bloqueado (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 correcta ejecución del programa cuando los hilos deben serializar el acceso a los recursos, pero su uso puede ralentizar considerablemente un programa y afectar su confiabilidad . [21]
El bloqueo de múltiples variables mediante bloqueos no atómicos introduce la posibilidad de un bloqueo del programa . Un bloqueo atómico bloquea múltiples variables a la vez. Si no puede bloquearlas todas, no bloquea ninguna de ellas. Si dos subprocesos necesitan bloquear las mismas dos variables mediante bloqueos no atómicos, es posible que un subproceso bloquee una de ellas y el segundo subproceso bloquee la segunda variable. En tal caso, ninguno de los subprocesos puede completar la ejecución y se produce un bloqueo. [22]
Muchos programas paralelos requieren que sus subtareas actúen en sincronía . Esto requiere el uso de una barrera . Las barreras se implementan típicamente usando un candado o un semáforo . [23] Una clase de algoritmos, conocidos como algoritmos sin bloqueo y sin espera , evitan 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. [24]
No toda paralelización da como resultado una aceleración. Generalmente, 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 el acceso a los recursos. [25] [26] Una vez que la sobrecarga de la contención de recursos o la comunicación domina el tiempo dedicado a otros cálculos, una mayor paralelización (es decir, dividir la carga de trabajo entre aún más subprocesos) aumenta en lugar de disminuir la cantidad de tiempo necesario para finalizar. Este problema, conocido como desaceleración paralela , [27] se puede mejorar en algunos casos mediante el análisis y el rediseño del software. [28]
Las aplicaciones suelen clasificarse según la frecuencia con la que sus subtareas necesitan sincronizarse o comunicarse entre sí. Una aplicación muestra un paralelismo de grano fino si sus subtareas deben comunicarse muchas veces por segundo; muestra un paralelismo de grano grueso si no se comunican muchas veces por segundo y muestra un paralelismo vergonzoso si rara vez o nunca tienen que comunicarse. Las aplicaciones vergonzosamente paralelas se consideran las más fáciles de paralelizar.
Michael J. Flynn creó uno de los primeros sistemas de clasificación para computadoras y programas paralelos (y secuenciales), conocido actualmente como taxonomía de Flynn . Flynn clasificaba los programas y las computadoras en función de si funcionaban utilizando un solo conjunto o varios conjuntos de instrucciones, y de si esas instrucciones utilizaban un solo conjunto o varios 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 realizar la misma operación repetidamente sobre un conjunto de datos grande. Esto se hace comúnmente en aplicaciones de procesamiento de señales . La clasificación de instrucción múltiple, datos únicos (MISD) es una clasificación que rara vez se usa. Si bien se idearon arquitecturas de computadora para lidiar con esto (como las matrices sistólicas ), se materializaron pocas aplicaciones que se ajustaran a esta clase. Los programas de instrucción múltiple, datos múltiples (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 da una buena primera aproximación. También es, quizás debido a su comprensibilidad, el esquema más utilizado". [30]
Desde la llegada 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 en la arquitectura informática fue impulsada por la duplicación del tamaño de palabra de la computadora (la cantidad de información que el procesador puede manipular por ciclo). [31] Aumentar el tamaño de palabra reduce la cantidad de instrucciones que el procesador debe ejecutar para realizar una operación en variables cuyos tamaños son mayores 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 utilizando la instrucción de suma estándar, luego sumar los 8 bits de orden superior utilizando una instrucción de suma con 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, donde 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 los procesadores de 32 bits, que han sido un estándar en la informática de propósito general durante dos décadas. No fue hasta principios de la década de 2000, con la llegada de las arquitecturas x86-64 , que los procesadores de 64 bits se volvieron comunes.
Un programa de ordenador es, en esencia, un flujo de instrucciones ejecutadas por un procesador. Sin paralelismo a nivel de instrucción, un procesador sólo 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 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. [32]
Todos los procesadores modernos tienen secuencias de instrucciones de varias etapas . Cada etapa de la secuencia corresponde a una acción diferente que el procesador realiza sobre esa instrucción en esa etapa; un procesador con una secuencia 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 reescritura de registros (WB). El procesador Pentium 4 tenía una secuencia de 35 etapas. [33]
La mayoría de los procesadores modernos también tienen múltiples unidades de ejecución . Por lo general, combinan esta característica con la segmentació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 solo si no hay dependencia de datos entre ellas. El sistema de tableros de resultados y el algoritmo Tomasulo (que es similar al sistema de tableros de resultados pero hace uso del 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.
El paralelismo de tareas es una característica de un programa paralelo que permite realizar "cálculos completamente diferentes sobre el mismo conjunto de datos o sobre conjuntos diferentes". [34] Esto contrasta con el paralelismo de datos, en el que el mismo cálculo se realiza sobre el mismo conjunto de datos o sobre conjuntos diferentes. El paralelismo de tareas implica la descomposición de una tarea en subtareas y la posterior asignación de cada subtarea a un procesador para su ejecución. Los procesadores ejecutarían entonces estas subtareas de forma concurrente y, a menudo, de forma cooperativa. El paralelismo de tareas no suele escalar con el tamaño de un problema. [35]
El paralelismo a nivel de superpalabra es una técnica de vectorización basada en el desenrollado de bucles y la vectorización básica de bloques. Se distingue 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 en bucles desenrollados manualmente. [36]
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). [37] 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 forma 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 externo 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áfagas , que generalmente se construye a partir de matrices de memoria no volátil distribuidas físicamente en varios nodos de E/S.
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, esto solo se puede lograr mediante un sistema de memoria compartida , en el que la memoria no está distribuida físicamente. Un sistema que no tiene esta propiedad se conoce como arquitectura de acceso no uniforme a la memoria (NUMA). Los sistemas de memoria distribuida tienen un acceso no uniforme a la memoria.
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 en el lógico). Los sistemas informáticos paralelos tienen dificultades con cachés que pueden almacenar el mismo valor en más de una ubicación, con la posibilidad de una ejecución incorrecta del programa. Estos ordenadores 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 correcta ejecución del programa. El espionaje 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, se deben purgar). El diseño de sistemas de coherencia de caché grandes y 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. [37]
La comunicación procesador-procesador y procesador-memoria se puede implementar en hardware de varias maneras, incluso a través de una memoria compartida (ya sea multipuerto o multiplexada ), un conmutador de barra cruzada , un bus compartido o una red de interconexión de una gran variedad de topologías, incluidas la estrella , el anillo , el árbol , el hipercubo , el hipercubo grueso (un hipercubo con más de un procesador en un nodo) o una malla n-dimensional .
Los ordenadores paralelos basados en redes interconectadas necesitan tener algún tipo de enrutamiento que permita el paso de mensajes entre nodos que no están conectados directamente. El medio utilizado para la comunicación entre los procesadores es probable que sea jerárquico en las grandes máquinas multiprocesador.
Las computadoras paralelas se pueden clasificar de forma aproximada según el nivel en el que el hardware admite el paralelismo. Esta clasificación es análoga a la distancia entre los nodos básicos de computación. No son mutuamente excluyentes; por ejemplo, los clústeres de multiprocesadores simétricos son relativamente comunes.
Un procesador multinúcleo es un procesador que incluye múltiples unidades de procesamiento (llamadas "núcleos") en el mismo chip. Este procesador se diferencia 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 la PlayStation 3 de Sony , es un destacado procesador multinúcleo. Cada núcleo de 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.
El multithreading simultáneo (de los cuales el Hyper-Threading de Intel es el más conocido) fue una forma temprana de pseudo-multi-coreísmo. Un procesador capaz de multithreading concurrente 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 multithreading 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.
Un multiprocesador simétrico (SMP) es un sistema informático con múltiples procesadores idénticos que comparten memoria y se conectan a través de un bus . [38] La contención del bus impide que las arquitecturas de bus se escalen. Como resultado, los SMP generalmente no comprenden más de 32 procesadores. [39] 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 cachés grandes, estos multiprocesadores simétricos son extremadamente rentables, siempre que exista una cantidad suficiente de ancho de banda de memoria. [38]
Un ordenador distribuido (también conocido 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. Los ordenadores distribuidos son altamente escalables. Los términos " computación concurrente ", "computación paralela" y "computación distribuida" tienen muchas similitudes y no existe una distinción clara entre ellos. [40] El mismo sistema puede caracterizarse como "paralelo" y "distribuido"; los procesadores de un sistema distribuido típico funcionan simultáneamente en paralelo. [41]
Un clúster es un grupo de computadoras acopladas de forma flexible que trabajan juntas de manera estrecha, de modo que en algunos aspectos pueden considerarse como una sola computadora. [42] Los clústeres se componen de múltiples 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 de clúster más común es el clúster Beowulf , que es un clúster implementado en múltiples computadoras comerciales idénticas listas para usar conectadas con una red de área local Ethernet TCP/IP . [43] La tecnología Beowulf fue desarrollada originalmente por Thomas Sterling y Donald Becker . El 87% de todas las supercomputadoras Top500 son clústeres. [44] El resto son procesadores masivamente paralelos, que se explican a continuación.
Debido a que los sistemas de computación en red (descritos a continuación) pueden manejar fácilmente problemas vergonzosamente paralelos, los clústeres modernos suelen estar 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 de alto rendimiento personalizado diseñado específicamente para computación en clúster, como la red Cray Gemini. [45] 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 .
Un procesador masivamente paralelo (MPP) es una computadora individual con muchos procesadores conectados 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 conexión en red). 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. [46] 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". [47]
El Blue Gene/L de IBM , el quinto superordenador más rápido del mundo según el ranking TOP500 de junio de 2009 , es un MPP.
La computación en cuadrícula es la forma más distribuida de computación paralela. Utiliza 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 disponibles en Internet, la computación distribuida generalmente se ocupa únicamente de problemas vergonzosamente paralelos .
La mayoría de las aplicaciones de computación en red 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 en red más común es Berkeley Open Infrastructure for Network Computing (BOINC). A menudo, el software de computación voluntaria hace uso de "ciclos libres", realizando cálculos en momentos en que una computadora está inactiva. [48]
La ubicuidad de Internet trajo consigo la posibilidad de la computación en la nube a gran escala.
En el ámbito 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.
La computación reconfigurable es el uso de una matriz de puertas programables en campo (FPGA) como coprocesador de una computadora de propósito general. Una FPGA es, en esencia, un chip de computadora que puede reconfigurarse para una tarea determinada.
Los FPGAs se pueden programar con lenguajes de descripción de hardware como VHDL [49] o Verilog [50] . 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 utilizar 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 que permite la computación reconfigurable de alto rendimiento. [51] Según Michael R. D'Amour, director de operaciones de DRC Computer Corporation, "cuando entramos por primera vez en AMD, nos llamaban 'los ladrones de sockets '. Ahora nos llaman sus socios". [51]
La computación de propósito general en unidades de procesamiento gráfico (GPGPU) es una tendencia bastante reciente en la investigación de ingeniería informática. Las GPU son coprocesadores que han sido altamente optimizados para el procesamiento de gráficos por computadora . [52] El procesamiento de gráficos por computadora es un campo dominado por operaciones paralelas de datos, en particular 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, y tanto Nvidia como AMD lanzaron entornos de programación con CUDA y Stream SDK respectivamente. Otros lenguajes de programación de GPU incluyen BrookGPU , PeakStream y RapidMind . Nvidia también lanzó productos específicos para computación en su serie Tesla . El consorcio tecnológico Khronos Group lanzó 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 admiten OpenCL .
Se han ideado varios enfoques de circuitos integrados específicos de la aplicación (ASIC) para abordar aplicaciones paralelas. [53] [54] [55]
Debido a que un ASIC es (por definición) específico para una aplicación dada, 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 caro. Un conjunto de máscaras puede costar más de un millón de dólares estadounidenses. [56] (Cuanto más pequeños sean los transistores necesarios para el chip, más cara 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 solo una o dos generaciones de chips. [51] El alto costo inicial y la tendencia a ser superados 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, se han construido algunos. Un ejemplo es la máquina PFLOPS RIKEN MDGRAPE-3 que utiliza ASIC personalizados para la simulación de dinámica molecular .
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 punto flotante de 64 bits . [57] Están estrechamente relacionados con la clasificación SIMD de Flynn. [57]
Las computadoras Cray se hicieron famosas por sus computadoras de procesamiento vectorial en los años 1970 y 1980. Sin embargo, los procesadores vectoriales, tanto como CPU como sistemas informáticos completos, en general han desaparecido. Los conjuntos de instrucciones de procesadores modernos sí incluyen algunas instrucciones de procesamiento vectorial, como en el caso de AltiVec de Freescale Semiconductor y Streaming SIMD Extensions (SSE) de Intel .
Se han creado lenguajes de programación concurrente , 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 manipulando variables de memoria compartida. La memoria distribuida utiliza paso de mensajes . Los subprocesos POSIX 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 de sistema de paso de mensajes más utilizada. [58] 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 por 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 OpenHMPP ofrece una sintaxis para descargar de manera eficiente los cálculos en los aceleradores de hardware y optimizar el movimiento de datos hacia y desde la memoria del hardware mediante llamadas a procedimientos remotos .
El auge de las GPU de consumo ha llevado al soporte de núcleos de cómputo , ya sea en API de gráficos (conocidos como sombreadores de cómputo ), en API dedicadas (como OpenCL ) o en otras extensiones del lenguaje.
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 mencionado anteriormente de la frecuencia del procesador. A pesar de décadas de trabajo por parte de investigadores de compiladores, la paralelización automática ha tenido un éxito limitado. [59]
Los lenguajes de programación paralela más utilizados siguen siendo explícitamente paralelos o (en el mejor de los casos) parcialmente implícitos , en los que un programador da al compilador directivas para la paralelización. Existen algunos lenguajes de programación paralela totalmente implícitos: SISAL , Parallel Haskell , SequenceL , System C (para FPGAs ), Mitrion-C, VHDL y Verilog .
A medida que un sistema informático se vuelve más complejo, el tiempo medio entre fallos suele disminuir. La creación de puntos de 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 los estados de las variables, similar a un volcado de memoria ); esta información se puede utilizar para restaurar el programa si el ordenador falla. La creación de puntos de control de aplicaciones significa que el programa tiene que reiniciarse sólo desde su último punto de control en lugar de desde el principio. Si bien la creación de puntos de control proporciona beneficios en una variedad de situaciones, es especialmente útil en sistemas altamente paralelos con una gran cantidad de procesadores utilizados en la informática de alto rendimiento . [60]
A medida que las computadoras paralelas se hacen más grandes y más rápidas, ahora podemos resolver problemas que antes requerían 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 han sacado provecho de la computación paralela. Los tipos de problemas comunes en las aplicaciones de computación paralela incluyen: [61]
La computación paralela también se puede aplicar al diseño de sistemas informáticos tolerantes a fallos , en particular a través de sistemas sincronizados 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 y corrección automática 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. [63] Aunque pueden requerirse medidas adicionales en sistemas integrados o especializados, este método puede proporcionar un enfoque rentable para lograr redundancia n-modular en sistemas comerciales listos para usar.
Los orígenes del verdadero paralelismo (MIMD) se remontan a Luigi Federico Menabrea y su Bosquejo de la máquina analítica inventada por Charles Babbage . [65] [66] [67]
En 1957, la Compagnie des Machines Bull anunció la primera arquitectura informática diseñada específicamente para el paralelismo, la Gamma 60. [ 68] Utilizaba un modelo de bifurcación y un "distribuidor de programas" para enviar y recopilar datos hacia y desde unidades de procesamiento independientes conectadas a una memoria central. [69] [70]
En abril de 1958, Stanley Gill (Ferranti) discutió la programación paralela y la necesidad de ramificación y espera. [71] También en 1958, los investigadores de IBM John Cocke y Daniel Slotnick discutieron el uso del paralelismo en cálculos numéricos por primera vez. [72] Burroughs Corporation presentó el 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 cruzada . [73] 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 Información. [72] 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. [72] C.mmp , un proyecto 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 a bus con cachés de espionaje fue el Synapse N+1 en 1984. [66]
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 retraso de la puerta de la unidad de control del procesador en múltiples instrucciones. [74] En 1964, Slotnick había propuesto construir una computadora masivamente paralela para el Laboratorio Nacional Lawrence Livermore . [72] Su diseño fue financiado por la Fuerza Aérea de los EE. UU ., que fue el primer esfuerzo de computación paralela SIMD, ILLIAC IV . [72] La clave de su diseño fue un paralelismo bastante alto, con hasta 256 procesadores, lo que permitió que la máquina trabajara en grandes conjuntos de datos en lo que más tarde se conocería como procesamiento vectorial . Sin embargo, ILLIAC IV fue llamado "el más infame de los superordenadores", porque el proyecto solo se completó en una cuarta parte, pero tomó 11 años y costó casi cuatro veces la estimación original. [64] Cuando finalmente estuvo listo para ejecutar su primera aplicación real en 1976, fue superado por supercomputadoras comerciales existentes como la Cray-1 .
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 al 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 agentes pequeños, cada uno sin mente por sí mismo". [75] La teoría intenta explicar cómo lo que llamamos inteligencia podría ser un 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. [76]
Modelos similares (que también consideran al cerebro biológico como una computadora masivamente paralela, es decir, el cerebro está formado por una constelación de agentes independientes o semi-independientes) también fueron descritos por:
{{cite book}}: |website=ignorado ( ayuda ){{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )Todos los circuitos simulados se describieron en lenguaje de descripción de hardware (VHDL) de circuitos integrados de muy alta velocidad (VHSIC). El modelado de hardware se realizó en el FPGA Artix 7 xc7a200tfbg484-2 de Xilinx.
Sin embargo, el santo grial de este tipo de investigación (la paralelización automática de programas seriales) aún no se ha materializado. Si bien se ha demostrado la paralelización automática de ciertas clases de algoritmos, dicho éxito se ha limitado en gran medida a aplicaciones científicas y numéricas con control de flujo predecible (por ejemplo, estructuras de bucles anidados con recuentos de iteraciones determinados estáticamente) y patrones de acceso a memoria analizables estáticamente (por ejemplo, recorridos sobre grandes matrices multidimensionales de datos de punto flotante).
