La computación paralela es un tipo de computación en la que se realizan muchos cálculos o procesos simultáneamente. [1] Los problemas grandes a menudo se pueden dividir en otros más pequeños, que luego pueden resolverse al mismo tiempo. Hay varias formas diferentes de computación paralela: nivel de bits , nivel de instrucciones , datos y paralelismo de tareas . El paralelismo se ha empleado durante mucho tiempo en la informática de alto rendimiento , pero ha ganado un interés más amplio debido a las limitaciones físicas que impiden el escalado de frecuencia . [2] 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, [3] la computación paralela se ha convertido en el paradigma dominante en la arquitectura de las computadoras , principalmente en forma de procesadores multinúcleo . [4]
La computación paralela está estrechamente relacionada con la computación concurrente : con frecuencia se usan juntas y a menudo se combinan, aunque las dos son distintas: es posible tener paralelismo sin concurrencia y concurrencia sin paralelismo (como la multitarea mediante el tiempo compartido en una sola computadora). CPU central). [5] [6] 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 posteriormente, al finalizar. Por el contrario, en la computación concurrente, los diversos procesos a menudo no abordan tareas relacionadas; cuando lo hacen, como es típico en la informática distribuida , las tareas separadas pueden tener una naturaleza variada y a menudo requieren alguna 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: las computadoras multinúcleo y multiprocesador 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. A veces se utilizan arquitecturas informáticas paralelas especializadas 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 a nivel de instrucción, pero los algoritmos explícitamente paralelos , en particular aquellos que usan concurrencia, son más difíciles de escribir que los secuenciales , [7] porque la concurrencia introduce varias novedades. clases de posibles errores de software , de las 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 lograr un rendimiento óptimo del programa paralelo.
Un límite superior teórico para la aceleración de un solo programa como resultado de la paralelización viene dado por la ley de Amdahl , que establece que está limitada por la fracción de tiempo durante la cual se puede utilizar la paralelización.
Tradicionalmente, el software informático se ha escrito para el cálculo en serie . Para resolver un problema, se construye e implementa un algoritmo como un flujo en serie de instrucciones. Estas instrucciones se ejecutan en una unidad central de procesamiento en una computadora. Sólo se puede ejecutar una instrucción a la vez; una vez finalizada esa instrucción, se ejecuta la siguiente. [8]
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 de modo 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. [8] 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 llevó al diseño de hardware y software paralelos, así como a la informática de alto rendimiento . [9]
El escalado de frecuencia fue la razón dominante 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 del reloj disminuye el tiempo promedio que lleva ejecutar una instrucción. Por lo tanto, un aumento en la frecuencia disminuye el tiempo de ejecución de todos los programas vinculados a la computación . [10] Sin embargo, el consumo de energía P por un chip viene 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). [11] Los aumentos en la frecuencia aumentan la cantidad de energía utilizada en un procesador. El creciente consumo de energía del procesador llevó en última instancia 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 paradigma de arquitectura informática dominante. [12]
Para abordar el problema del consumo de energía y el sobrecalentamiento, los principales fabricantes de unidades centrales de procesamiento (CPU o procesadores) comenzaron a producir procesadores energéticamente eficientes con múltiples 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 tanto, la paralelización de programas en serie se ha convertido en una tarea de programación habitual. 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 el número 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 la región de 4 a 16 núcleos, y algunos diseños tienen una combinación de núcleos de rendimiento y eficiencia (como los grandes de ARM. POCO diseño) debido a limitaciones térmicas y de diseño. [13] [ cita necesaria ]
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 mediante el escalado de frecuencia, sino que los programadores necesitarán paralelizar su código de software para aprovechar la creciente potencia informática de las arquitecturas multinúcleo. [14]
De manera óptima, la aceleración de la paralelización sería lineal: duplicar el número de elementos de procesamiento debería reducir a la mitad el tiempo de ejecución, y duplicarlo por segunda vez debería reducir nuevamente 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 aplana hasta convertirse en 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 [15]
dónde
Dado que la latencia S < 1/(1 - p ) , muestra que una pequeña parte del programa que no se puede paralelizar limitará la aceleración general 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 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 limitaciones secuenciales, la aplicación de más esfuerzo no tiene ningún efecto en el cronograma. Tener un hijo lleva nueve meses, sin importar cuántas mujeres se asignen". [dieciséis]
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 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. [17] En este caso, la ley de Gustafson ofrece una evaluación menos pesimista y más realista del desempeño paralelo: [18]
Tanto la ley de Amdahl como la ley de Gustafson suponen que el tiempo de ejecución de la parte en serie 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ápidamente 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 sólo en una larga cadena de cálculos dependientes; Por lo general, existen oportunidades para ejecutar cálculos independientes en paralelo.
Sean P i y P j dos segmentos de programa. Las condiciones de Bernstein [19] 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 del flujo, correspondiente 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. [20]
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) de 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 * b3: d := 3 * segundo4: mi := a + b5: 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 que la memoria sea compartida entre diferentes procesos. Para eso es necesario algún medio que haga cumplir un ordenamiento entre accesos, como semáforos , barreras o algún otro método de sincronización .
Las subtareas en un programa paralelo a menudo se denominan subprocesos . Algunas arquitecturas informáticas paralelas utilizan versiones más pequeñas y ligeras de subprocesos conocidos como fibras , mientras que otras utilizan versiones más grandes conocidas como procesos . Sin embargo, "hilos" se acepta generalmente como término genérico para subtareas. [21] Los subprocesos a menudo necesitarán acceso sincronizado a un objeto u otro recurso , por ejemplo, cuando deben actualizar una variable que comparten entre ellos. Sin sincronización, las instrucciones entre los dos subprocesos pueden entrelazarse 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 evita que otros subprocesos la lean o escriban, hasta que esa variable se desbloquee. El hilo que sostiene el candado 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 haya terminado. 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 enormemente un programa y afectar su confiabilidad . [22]
El bloqueo de múltiples variables mediante bloqueos no atómicos introduce la posibilidad de que el programa se bloquee . Un bloqueo atómico bloquea múltiples variables a la vez. Si no puede bloquearlos a todos, no bloquea ninguno. Si dos subprocesos necesitan 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 bloqueo. [23]
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 . [24] 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. [25]
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 dedican una parte cada vez mayor de su tiempo a comunicarse entre sí o a esperarse unos a otros para acceder a los recursos. [26] [27] 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 en aún más subprocesos) aumenta en lugar de disminuir la cantidad de tiempo necesario para finalizar. Este problema, conocido como desaceleración paralela , [28] puede mejorarse en algunos casos mediante análisis y rediseño del software. [29]
Las aplicaciones a menudo se clasifican según la frecuencia con la que sus subtareas deben sincronizarse o comunicarse entre sí. Una aplicación muestra un paralelismo detallado si sus subtareas deben comunicarse muchas veces por segundo; exhibe un paralelismo burdo si no se comunican muchas veces por segundo, y exhibe un paralelismo embarazoso 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), ahora conocido como taxonomía de Flynn . Flynn clasificó los programas y las computadoras según si operaban 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 y datos únicos (SISD) equivale a un programa completamente secuencial. La clasificación de una sola instrucción y múltiples datos (SIMD) es análoga a realizar la misma operación repetidamente en un gran conjunto de datos. Esto se hace comúnmente en aplicaciones de procesamiento de señales . Múltiples instrucciones y datos únicos (MISD) es una clasificación que rara vez se utiliza. Si bien se idearon arquitecturas informáticas para abordar esto (como las matrices sistólicas ), se materializaron pocas aplicaciones que se ajusten a esta clase. Los programas de múltiples instrucciones y múltiples datos (MIMD) son, con diferencia, 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... tal vez debido a su comprensibilidad: el esquema más utilizado". [31]
Desde la llegada de la tecnología de fabricación de chips de computadora de integración a muy gran escala (VLSI) en la década de 1970 hasta aproximadamente 1986, la aceleración en la arquitectura de la computadora fue impulsada por la duplicación del tamaño de las palabras de la computadora : la cantidad de información que el procesador puede manipular por ciclo. [32] 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 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 usando la instrucción de suma estándar, luego sumar los 8 bits de orden superior usando una suma con -instrucciones 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. En general, esta tendencia 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 uso 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 computadora es, en esencia, un flujo de instrucciones ejecutadas por un procesador. Sin paralelismo a nivel de instrucciones, 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 el paralelismo a nivel de instrucción dominaron la arquitectura informática desde mediados de los años 80 hasta mediados de los 90. [33]
Todos los procesadores modernos tienen canales de instrucción de varias etapas . Cada etapa del proceso corresponde a una acción diferente que el procesador realiza en esa instrucción en esa etapa; un procesador con una tubería 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 canalizado es un procesador RISC , con cinco etapas: búsqueda 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 tubería de 35 etapas. [34]
La mayoría de los procesadores modernos también tienen múltiples unidades de ejecución . Por lo general, combinan esta característica 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 distintas unidades de ejecución no son procesadores completos (es decir, unidades de procesamiento). Las instrucciones se pueden agrupar solo si no existe dependencia de datos entre ellas. El marcador y el algoritmo Tomasulo (que es similar al marcador pero utiliza el cambio de nombre de registros ) son dos de las técnicas más comunes para implementar ejecución desordenada y paralelismo a nivel de instrucción.
Los paralelismos de tareas son la característica de un programa paralelo en el que "se pueden realizar cálculos completamente diferentes en el mismo o en diferentes conjuntos de datos". [35] 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 de forma simultánea y, a menudo, de forma cooperativa. El paralelismo de tareas no suele escalar con el tamaño de un problema. [36]
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 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. [37]
La memoria principal en una computadora paralela es memoria compartida (compartida entre todos los elementos de procesamiento en un único espacio de direcciones ) o memoria distribuida (en la que cada elemento de procesamiento tiene su propio espacio de direcciones local). [38] 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 la 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 un modelo de programación como PGAS . Este modelo permite que los procesos en un nodo informático accedan de forma transparente a la memoria remota de otro nodo informático. Todos los nodos de computación 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 buffer de ráfaga , que generalmente se construye a partir de matrices de memoria no volátil distribuidas físicamente en múltiples I/. Oh nodos.
Las arquitecturas informáticas en las que se puede acceder a cada elemento de la memoria principal con igual latencia y ancho de banda se conocen como sistemas de acceso uniforme a la memoria (UMA). Normalmente, esto sólo puede lograrse 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 a memoria no uniforme (NUMA). Los sistemas de memoria distribuida tienen un 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 cachés que pueden almacenar el mismo valor en más de una ubicación, con la posibilidad de que el programa se ejecute incorrectamente. 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 correcta ejecución del programa. El espionaje del bus es uno de los métodos más comunes para realizar un seguimiento de a qué valores se accede (y, por lo tanto, se deben eliminar). Diseñar 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 se escalan tan bien como lo hacen los sistemas de memoria distribuida. [38]
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 conmutador de barra cruzada , un bus compartido o una red de interconexión de una infinidad de topologías que incluyen estrella , anillo y á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 necesitan 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.
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 nodos informáticos básicos. Estos no son mutuamente excluyentes; por ejemplo, los grupos 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 Sony PlayStation 3 , es un destacado procesador multinúcleo. Cada núcleo en un procesador multinúcleo también puede ser 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 pseudomulticoreísmo. Un procesador capaz de realizar 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. Por otro lado, el multiproceso temporal incluye una única unidad de ejecución en la misma unidad de procesamiento y puede emitir una instrucción a la vez desde varios 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 . [39] La contención del bus impide que las arquitecturas de bus escale. Como resultado, los SMP generalmente no constan de más de 32 procesadores. [40] Debido al pequeño tamaño de los procesadores y a la reducción significativa de los requisitos de ancho de banda del bus que se consigue con las grandes cachés, estos multiprocesadores simétricos son extremadamente rentables, siempre que exista una cantidad suficiente de ancho de banda de memoria. [39]
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" se superponen mucho y no existe una distinción clara entre ellos. [41] El mismo sistema puede caracterizarse como "paralelo" y "distribuido"; Los procesadores en un sistema distribuido típico se ejecutan simultáneamente en paralelo. [42]
Un clúster es un grupo de computadoras débilmente acopladas que trabajan juntas en estrecha colaboración, de modo que en algunos aspectos pueden considerarse como una sola computadora. [43] Los clústeres se componen de múltiples máquinas independientes conectadas por una red. Si bien las máquinas de un clúster no tienen por qué 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 conectadas con una red de área local Ethernet TCP/IP . [44] La tecnología Beowulf fue desarrollada originalmente por Thomas Sterling y Donald Becker . El 87% de todas las supercomputadoras Top500 son clústeres. [45] Los restantes son procesadores masivamente paralelos, que se explican a continuación.
Debido a que los sistemas de computación grid (que se describen a continuación) pueden manejar fácilmente problemas vergonzosamente paralelos, los clusters 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 más 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 computación en clúster, como la red Cray Gemini. [46] A partir de 2014, la mayoría de las supercomputadoras actuales utilizan algún hardware de red estándar disponible en el mercado, a menudo Myrinet , InfiniBand o Gigabit Ethernet .
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 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 suelen tener "muchos más" de 100 procesadores. [47] 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". [48]
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 grid 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 informática distribuida normalmente sólo se ocupa de problemas vergonzosamente paralelos .
La mayoría de las aplicaciones de computación grid utilizan middleware (software que se encuentra 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 para Computación en Red de Berkeley (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. [49]
La ubicuidad de Internet trajo la posibilidad de la computación en la nube a gran escala.
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 sólo 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 uso general. Una FPGA es, en esencia, un chip de computadora que puede reconectarse a sí mismo para una tarea determinada.
Los FPGA se pueden programar con lenguajes de descripción de hardware como VHDL [50] o Verilog . [51] 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 habilitadora para la informática reconfigurable de alto rendimiento. [52] 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". [52]
La computación de propósito general en unidades de procesamiento de gráficos (GPGPU) es una tendencia bastante reciente en la investigación en ingeniería informática. Las GPU son coprocesadores que se han optimizado en gran medida para el procesamiento de gráficos por computadora . [53] El procesamiento de gráficos por computadora es un campo dominado por operaciones paralelas de datos, particularmente operaciones matriciales de álgebra lineal .
Al principio, los programas GPGPU utilizaban 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 lanzan 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 ha lanzado productos específicos para computación en su serie Tesla . El consorcio tecnológico Khronos Group ha lanzado la especificación OpenCL , que es un marco para escribir programas que se ejecutan en plataformas que constan de CPU y GPU. AMD , Apple , Intel , Nvidia y otros soportan OpenCL .
Se han ideado varios enfoques de circuitos integrados de aplicaciones específicas (ASIC) para tratar aplicaciones paralelas. [54] [55] [56]
Debido a que un ASIC es (por definición) específico para una aplicación determinada, se puede optimizar completamente para esa aplicación. Como resultado, para una aplicación determinada, un ASIC tiende a superar a una computadora de uso general. Sin embargo, los ASIC se crean mediante fotolitografía UV . Este proceso requiere un juego de mascarillas, lo que puede resultar extremadamente costoso. Un juego de mascarillas puede costar más de un millón de dólares estadounidenses. [57] (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 informática de propósito general con el tiempo (como lo describe la ley de Moore ) tienden a eliminar estas ganancias en sólo uno o Dos generaciones de chips. [52] 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 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 . [58] Están estrechamente relacionados con la clasificación SIMD de Flynn. [58]
Las computadoras Cray se hicieron famosas por sus computadoras de procesamiento de vectores en los años 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 vectorial, como AltiVec de Freescale Semiconductor y Streaming SIMD Extensions (SSE) de Intel .
Se han creado lenguajes de programación concurrentes , bibliotecas , API y modelos de programación paralela (como esqueletos algorítmicos ) para programar computadoras paralelas. Por lo general, estos 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 el paso de mensajes . POSIX Threads y OpenMP son dos de las API de memoria compartida más utilizadas, mientras que Message Passing Interface (MPI) es la API del sistema de transferencia de mensajes más utilizada. [59] Un concepto utilizado en la programación de programas paralelos es el concepto 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 OpenHMPP ofrece una sintaxis para descargar de manera eficiente los cálculos en 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 a la compatibilidad con núcleos de cómputo , ya sea en API de gráficos (denominadas sombreadores de cómputo ), en API dedicadas (como OpenCL ) o en otras extensiones de lenguaje.
La paralelización automática de un programa secuencial mediante un compilador es el "santo grial" de la computación paralela, especialmente con el límite de frecuencia del procesador antes mencionado. A pesar de décadas de trabajo por parte de investigadores de compiladores, la paralelización automática ha tenido sólo un éxito limitado. [60]
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 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 .
A medida que un sistema informático crece en complejidad, 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 de 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 únicamente 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 . [61]
A medida que las computadoras paralelas se vuelven más grandes y más rápidas, ahora podemos resolver problemas que antes demoraban demasiado en 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 ) han aprovechado la computación paralela. Los tipos comunes de problemas en aplicaciones de computación paralela incluyen: [62]
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 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 perturbaciones de un solo evento causadas por errores transitorios. [64] Aunque pueden ser necesarias medidas adicionales en sistemas integrados o especializados, este método puede proporcionar un enfoque rentable para lograr una redundancia n-modular en sistemas comerciales disponibles en el mercado.
Los orígenes del paralelismo verdadero (MIMD) se remontan a Luigi Federico Menabrea y su Bosquejo de la máquina analítica inventada por Charles Babbage . [66] [67] [68]
En 1957, la Compagnie des Machines Bull anunció la primera arquitectura informática diseñada específicamente para el paralelismo, la Gamma 60 . [69] Utilizó un modelo de unión 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. [70] [71]
En abril de 1958, Stanley Gill (Ferranti) discutió la programación paralela y la necesidad de bifurcación y espera. [72] 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. [73] 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 . [74] 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. [73] 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. [73] C.mmp , un proyecto multiprocesador de la Universidad Carnegie Mellon en la década de 1970, estuvo entre los primeros multiprocesadores con más de unos pocos procesadores. El primer multiprocesador conectado a un bus con cachés de vigilancia fue el Synapse N+1 en 1984. [67]
Los ordenadores paralelos SIMD se remontan a los años 1970. La motivación detrás de las primeras computadoras SIMD fue amortizar el retardo de puerta de la unidad de control del procesador en múltiples instrucciones. [75] En 1964, Slotnick había propuesto construir una computadora masivamente paralela para el Laboratorio Nacional Lawrence Livermore . [73] 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 . [73] La clave de su diseño fue un paralelismo bastante alto, con hasta 256 procesadores, lo que permitía a la máquina trabajar 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 sólo estaba completado en una cuarta parte, pero tomó 11 años y costó casi cuatro veces la estimación original. [65] Cuando finalmente estuvo listo para ejecutar su primera aplicación real en 1976, fue superado en rendimiento por las 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 el cerebro biológico como una computadora masivamente paralela . En 1986, Minsky publicó La sociedad de la mente , que afirma que "la mente se forma a partir de muchos pequeños agentes, cada uno de ellos sin sentido en sí mismo". [76] 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 utiliza un brazo robótico, una cámara de video y una computadora para construir con bloques de niños. [77]
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:
{{cite book}}: Mantenimiento CS1: fecha y año ( enlace ){{cite book}}: |website=ignorado ( ayuda ){{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )Todos los circuitos simulados se describieron en el lenguaje de descripción de hardware (VHDL) de circuitos integrados de muy alta velocidad (VHSIC).
El modelado de hardware se realizó en Xilinx FPGA Artix 7 xc7a200tfbg484-2.
Sin embargo, el santo grial de dicha investigación (la paralelización automática de programas en serie) aún no se ha materializado. Si bien se ha demostrado la paralelización automatizada 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 bucle anidado con recuentos de iteraciones determinados estáticamente) y patrones de acceso a memoria estáticamente analizables. (por ejemplo, camina sobre grandes conjuntos multidimensionales de datos de punto flotante).
