Computación paralela para niños

La computación paralela es una forma especial de usar las computadoras. Imagina que tienes un problema muy grande que resolver. En lugar de que una sola persona (o una sola parte de la computadora) lo resuelva paso a paso, la computación paralela divide ese problema en muchas partes más pequeñas. Luego, muchas "personas" (o partes de la computadora) trabajan al mismo tiempo en esas partes pequeñas para resolver el problema mucho más rápido.

Este método se ha usado por mucho tiempo en computadoras muy potentes, llamadas supercomputadoras. Hoy en día, es aún más importante porque los chips de las computadoras no pueden hacerse más rápidos tan fácilmente como antes. Además, el calor que generan es un problema. Por eso, las computadoras modernas, como las que tienen varios núcleos (procesadores) en un solo chip, usan la computación paralela para ser más eficientes.

Las computadoras paralelas pueden ser de varios tipos. Algunas tienen muchos procesadores dentro de una misma máquina. Otras usan varias computadoras conectadas en red, como los "clústeres" o las "granjas de computadoras", para trabajar juntas en la misma tarea.

Escribir programas para computadoras paralelas es más complicado que para las computadoras normales. Esto se debe a que, al trabajar varias partes a la vez, pueden surgir errores si no se coordinan bien. La comunicación y la sincronización entre las diferentes partes del programa son clave para que funcione correctamente.

La velocidad máxima que se puede lograr al usar la computación paralela en un programa se explica con algo llamado la ley de Amdahl.

Conceptos básicos de la computación paralela

Tradicionalmente, los programas de computadora se escribían para funcionar de forma "secuencial". Esto significa que la computadora seguía una lista de instrucciones una por una. Solo se ejecutaba una instrucción a la vez, y la siguiente no empezaba hasta que la anterior terminaba.

La computación paralela, en cambio, usa varias partes de la computadora al mismo tiempo para resolver un problema. Esto se logra dividiendo el problema en partes que no dependen una de la otra. Así, cada parte de la computadora puede trabajar en su pedazo del problema al mismo tiempo que las otras. Estas partes pueden ser procesadores dentro de una misma computadora, varias computadoras conectadas en red, o incluso hardware especial.

Durante muchos años, las computadoras se hicieron más rápidas aumentando su "frecuencia" (como la velocidad del reloj interno). Esto hacía que cada instrucción se ejecutara más rápido. Sin embargo, aumentar la frecuencia también aumenta el consumo de energía y el calor que produce el chip. Por eso, los fabricantes de chips tuvieron que buscar otras formas de hacer las computadoras más potentes, y la computación paralela se convirtió en la solución principal.

La ley de Moore dice que la cantidad de transistores en un chip se duplica cada cierto tiempo. Como ya no se podían usar esos transistores extra para aumentar la frecuencia, se empezaron a usar para añadir más partes que permitieran la computación paralela.

¿Qué son la Ley de Amdahl y la Ley de Gustafson?

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

Idealmente, si duplicas el número de partes que trabajan en paralelo, el tiempo para resolver el problema debería reducirse a la mitad. Pero en la realidad, esto casi nunca ocurre perfectamente. La mayoría de los programas paralelos se aceleran mucho al principio, pero luego la mejora se vuelve más lenta, incluso si añades más partes.

La ley de Amdahl, creada por Gene Amdahl, explica por qué. Dice que si una pequeña parte de un programa no se puede dividir para trabajar en paralelo (es decir, tiene que ejecutarse de forma secuencial), esa parte limitará la velocidad máxima que puedes lograr. Por ejemplo, si el 10% de un programa siempre tiene que ejecutarse de forma secuencial, el programa nunca podrá ser más de 10 veces más rápido, sin importar cuántos procesadores uses. Es como si una tarea no se puede dividir, añadir más personas no la hará más rápida.

La ley de Gustafson es otra ley relacionada. Esta ley considera que, a medida que tienes más procesadores, puedes resolver problemas más grandes. Si el tamaño del problema aumenta con el número de procesadores, entonces la aceleración puede ser mucho mayor.

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

¿Qué son las dependencias en los programas?

Para que un programa paralelo funcione bien, es importante entender las "dependencias de datos". Esto significa que algunas partes de un programa necesitan el resultado de otras partes antes de poder empezar. La parte más larga de cálculos que dependen unos de otros se llama "ruta crítica", y el programa no puede ir más rápido que esa ruta. Sin embargo, la mayoría de los programas tienen muchas partes que no dependen entre sí y que pueden ejecutarse al mismo tiempo.

Imagina dos pasos en un programa. Si el segundo paso necesita el resultado del primero, no pueden ejecutarse en paralelo. Esto se llama "dependencia de flujo". También hay "anti-dependencias" y "dependencias de salida" cuando los pasos intentan usar o escribir en el mismo lugar al mismo tiempo.

Para evitar problemas cuando varias partes del programa comparten información, se usan herramientas como los "bloqueos" o "barreras".

Condiciones de carrera y bloqueos

Las partes más pequeñas de un programa paralelo se llaman a menudo "hilos". Estos hilos a veces necesitan cambiar la misma información (variables) que comparten. Si dos hilos intentan cambiar la misma variable al mismo tiempo sin coordinación, el resultado puede ser incorrecto. Esto se llama una "condición de carrera".

Para evitar esto, los programadores usan "bloqueos". Un bloqueo permite que un hilo tome el control de una variable y evite que otros hilos la lean o escriban hasta que termine. Así, se asegura que el programa funcione correctamente. Sin embargo, usar bloqueos puede hacer que el programa se ralentice.

Si se usan muchos bloqueos de forma incorrecta, puede ocurrir un "bloqueo mutuo" (deadlock). Esto pasa cuando dos hilos se quedan esperando el uno al otro para liberar un recurso, y ninguno puede avanzar.

Muchos programas paralelos también necesitan que sus partes trabajen al mismo tiempo en ciertos puntos. Para esto se usan las "barreras". Una barrera hace que todos los hilos esperen en un punto hasta que todos hayan llegado, y luego continúan juntos.

A veces, dividir una tarea en demasiados hilos puede hacer que el programa se ralentice en lugar de acelerarse. Esto ocurre porque los hilos pasan demasiado tiempo comunicándose entre sí, y esa comunicación se vuelve más lenta que el trabajo que hacen. Esto se conoce como "desaceleración paralela".

Tipos de paralelismo: Fino, grueso y vergonzoso

Las aplicaciones paralelas se clasifican según la frecuencia con la que sus partes se comunican:

• Paralelismo de grano fino: Las partes se comunican muy a menudo (muchas veces por segundo).
• Paralelismo de grano grueso: Las partes no se comunican tan a menudo.
• Paralelismo vergonzoso: Las partes casi nunca necesitan comunicarse entre sí. Estas son las más fáciles de hacer paralelas.

Modelos de consistencia

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

Los lenguajes y computadoras paralelas necesitan un "modelo de consistencia de datos". Esto es como un conjunto de reglas que dice cómo se guardan y se leen los datos en la memoria de la computadora, y cómo se aseguran los resultados correctos.

Un modelo importante es la "consistencia secuencial", definida por Leslie Lamport. Significa que, aunque el programa se ejecute en paralelo, los resultados son los mismos que si se hubiera ejecutado de forma secuencial, una instrucción tras otra.

Taxonomía de Flynn

Michael J. Flynn creó un sistema para clasificar las computadoras y programas, llamado la taxonomía de Flynn. Clasifica los programas según si usan una o varias instrucciones, y si esas instrucciones trabajan con uno o varios conjuntos de datos.

• SISD (Instrucción Única, Dato Único): Es como un programa normal, que se ejecuta paso a paso.
• SIMD (Instrucción Única, Datos Múltiples): Se hace la misma operación muchas veces sobre un grupo grande de datos. Es común en el procesamiento de imágenes o señales.
• MISD (Instrucción Múltiple, Dato Único): Es una categoría poco común.
• MIMD (Instrucción Múltiple, Datos Múltiples): Es el tipo más común de programas paralelos, donde muchas partes trabajan en diferentes datos al mismo tiempo.

Tipos de paralelismo

Paralelismo a nivel de bit

Hace años, las computadoras se hicieron más rápidas duplicando el "tamaño de la palabra" que podían manejar. Esto significa la cantidad de información que el procesador puede manejar en un solo paso. Por ejemplo, un procesador de 8 bits necesitaba dos pasos para sumar dos números de 16 bits, mientras que uno de 16 bits lo hacía en un solo paso.

Esta tendencia llevó a procesadores de 32 bits y luego de 64 bits, que son el estándar hoy en día.

Paralelismo a nivel de instrucción

Un pipeline canónico de cinco etapas en una máquina RISC (IF = Pedido de Instrucción, ID = Decodificación de instrucción, EX = Ejecutar, MEM = Acceso a la memoria, WB = Escritura)

Un programa es una secuencia de instrucciones. El "paralelismo a nivel de instrucción" permite que estas instrucciones se reorganicen y se agrupen para ejecutarse al mismo tiempo sin cambiar el resultado del programa. Esto fue muy importante para mejorar la velocidad de las computadoras entre los años 80 y 90.

Los procesadores modernos usan algo llamado "pipeline" (tubería de instrucciones). Imagina una cadena de montaje: cada etapa del pipeline hace una parte diferente del trabajo en una instrucción. Así, un procesador puede tener varias instrucciones en diferentes etapas de finalización al mismo tiempo.

Un procesador superescalar con pipeline de cinco etapas, capaz de ejecutar dos instrucciones por ciclo. Puede tener dos instrucciones en cada etapa del pipeline, para un total de hasta 10 instrucciones (se muestra en verde) ejecutadas simultáneamente.

Además, algunos procesadores pueden ejecutar más de una instrucción a la vez. Se les llama procesadores "superescalares". Las instrucciones solo se pueden agrupar si no dependen una de la otra.

Paralelismo de datos

El paralelismo de datos se encuentra en programas que repiten la misma operación muchas veces sobre diferentes partes de un conjunto grande de datos. Por ejemplo, si tienes que aplicar un filtro a cada píxel de una imagen, cada píxel se puede procesar en paralelo.

Si una parte del programa (como un ciclo) depende del resultado de la parte anterior, no se puede paralelizar. Por ejemplo, calcular la Sucesión de Fibonacci no se puede hacer en paralelo porque cada número depende de los dos anteriores.

Paralelismo de tareas

El paralelismo de tareas ocurre cuando diferentes cálculos se realizan en diferentes conjuntos de datos. A diferencia del paralelismo de datos, donde se hace lo mismo a muchos datos, aquí se hacen cosas distintas. Por ejemplo, en un programa de edición de video, una tarea podría ser procesar el audio y otra tarea, procesar el video, al mismo tiempo.

Hardware para computación paralela

Memoria y comunicación

La memoria principal en una computadora paralela puede ser "compartida" (todos los procesadores acceden a la misma memoria) o "distribuida" (cada procesador tiene su propia memoria). Acceder a la memoria propia suele ser más rápido que acceder a la memoria de otro procesador.

Una vista lógica de una arquitectura con acceso a memoria no uniforme (NUMA). Los procesadores en un directorio pueden acceder a la memoria de su directorio con una menor latencia de la que pueden acceder a la memoria del directorio de otro.

Las computadoras también usan "cachés", que son memorias pequeñas y rápidas cerca del procesador. En sistemas paralelos, es un desafío mantener la "coherencia de caché", es decir, asegurarse de que todos los procesadores tengan la versión más reciente de los datos.

La forma en que los procesadores se comunican entre sí puede variar. Puede ser a través de memoria compartida, un bus compartido o redes especiales que conectan muchos procesadores.

Clases de computadoras paralelas

Las computadoras paralelas se clasifican según cómo el hardware soporta el paralelismo.

Computación multinúcleo

Un procesador multinúcleo es un chip que tiene varias "unidades de ejecución" (llamadas núcleos) en su interior. Cada núcleo puede ejecutar instrucciones de forma independiente. Así, un procesador multinúcleo puede ejecutar muchas instrucciones de diferentes programas al mismo tiempo.

El microprocesador Cell de IBM, usado en la consola Sony PlayStation 3, es un ejemplo famoso de procesador multinúcleo.

Multiprocesamiento simétrico

Un "multiprocesador simétrico" (SMP) es una computadora con varios procesadores idénticos que comparten la misma memoria y se conectan a través de un bus. Estos sistemas son muy eficientes para un número limitado de procesadores (generalmente menos de 32).

Computación en clúster

Un clúster Beowulf.

Un "clúster" es un grupo de computadoras separadas que trabajan juntas tan de cerca que parecen una sola. Están conectadas por una red. El tipo más común es el "clúster Beowulf", que usa muchas computadoras normales conectadas por una red Ethernet. La mayoría de las supercomputadoras más potentes del mundo son clústeres.

Procesamiento paralelo masivo

Un "procesador paralelo masivo" (MPP) es una sola computadora con muchísimos procesadores conectados en red. Son como clústeres, pero usan redes de interconexión especiales y suelen ser mucho más grandes, con cientos o miles de procesadores. Cada procesador tiene su propia memoria y su propia copia del sistema operativo.

Un gabinete de Blue Gene/L, clasificado como el cuarto mejor superordenador del mundo de acuerdo a la clasificación TOP500 en 11/2008. Blue Gene/L es un procesador masivamente paralelo.

Computación distribuida

La computación distribuida es la forma más extendida de computación paralela. Utiliza computadoras que se comunican a través de Internet para resolver un problema. Debido a que Internet es más lento, la computación distribuida se usa para problemas que son "vergonzosamente paralelos" (donde las partes casi no necesitan comunicarse). Ejemplos famosos son SETI@home (que busca señales extraterrestres) y Folding@home (que estudia el plegamiento de proteínas).

Estos programas suelen usar un software intermedio llamado middleware, como BOINC, que ayuda a gestionar los recursos de la red. A menudo, aprovechan los "ciclos de repuesto" de las computadoras, es decir, cuando el procesador no está haciendo nada.

Computadoras paralelas especializadas

Existen dispositivos paralelos diseñados para tareas muy específicas.

Cómputo reconfigurable con FPGAs

El "cómputo reconfigurable" usa un FPGA como coprocesador. Un FPGA es un chip que se puede reconfigurar para una tarea específica. Son muy flexibles, pero programarlos puede ser complicado.

Cómputo de propósito general en unidades de procesamiento gráfico (GPGPU)

Tarjeta Nvidia Tesla GPGPU

El "cómputo de propósito general en unidades de procesamiento gráfico" (GPGPU) es una tendencia reciente. Las GPUs (tarjetas gráficas) están diseñadas para procesar gráficos, lo que implica muchas operaciones paralelas. Los investigadores descubrieron que podían usar las GPUs para resolver otros problemas que también requieren muchas operaciones paralelas, como cálculos matemáticos complejos.

Empresas como Nvidia y AMD han creado herramientas (como CUDA y Stream SDK) para que los programadores puedan usar las GPUs para tareas que no son de gráficos.

Circuitos integrados de aplicación específica (ASIC)

Los "circuitos integrados de aplicación específica" (ASIC) son chips diseñados para una sola aplicación. Son extremadamente eficientes para esa tarea específica, pero son muy caros de fabricar y se vuelven obsoletos rápidamente debido a los avances en los chips de propósito general. Un ejemplo es el MDGRAPE-3, usado para simular el movimiento de moléculas.

Procesadores vectoriales

Cray-1 es el procesador vectorial más famoso.

Un "procesador vectorial" es un tipo de procesador que puede ejecutar la misma instrucción en grandes grupos de datos a la vez. Las computadoras Cray fueron famosas por esto en los años 70 y 80. Hoy en día, los procesadores modernos tienen instrucciones especiales (como SSE) que permiten hacer cálculos vectoriales.

Software para computación paralela

Lenguajes de programación en paralelo

Se han creado lenguajes de programación, librerías y herramientas especiales para programar computadoras paralelas. Estos se dividen según si la memoria es compartida o distribuida. Para memoria compartida, se usan herramientas como POSIX Threads y OpenMP. Para memoria distribuida, la herramienta más común es Message Passing Interface (MPI).

Paralelización automática

El sueño de la computación paralela es que un programa normal pueda ser convertido automáticamente a un programa paralelo por un "compilador" (el programa que traduce el código). Aunque se ha investigado mucho, esto ha tenido un éxito limitado.

La mayoría de los lenguajes de programación paralelos requieren que el programador indique explícitamente qué partes del código deben ejecutarse en paralelo.

Punto de control

Cuando un sistema informático es muy complejo, es más probable que falle. Un "punto de control" es una técnica donde el sistema guarda una "instantánea" del programa (como una foto de su estado actual). Si la computadora falla, el programa puede reiniciarse desde ese punto de control en lugar de empezar desde cero. Esto es muy útil en supercomputadoras con muchos procesadores.

Métodos algorítmicos

A medida que las computadoras paralelas se vuelven más potentes, pueden resolver problemas que antes eran imposibles. La computación paralela se usa en muchos campos, desde la bioinformática (para estudiar proteínas) hasta la economía (para cálculos financieros). Algunos tipos de problemas que se benefician de la computación paralela son:

• Cálculos con matrices y vectores.
• Simulaciones de partículas.
• Problemas de "grids" (como en el análisis de elementos finitos).
• Simulaciones de Montecarlo (que usan números aleatorios).
• Problemas de lógica y búsqueda (como la fuerza bruta en criptografía).
• Recorridos en grafos (como los algoritmos de ordenamiento).
• Programación dinámica.
• Modelos en grafos (como las redes bayesianas).
• Simulación de autómatas finitos.

Historia de la computación paralela

ILLIAC IV, «quizás el más infame de los superordenadores»

Las ideas de la computación paralela existen desde hace mucho tiempo. En 1954, IBM lanzó el IBM 704, una de las primeras computadoras comerciales con operaciones matemáticas automáticas.

En 1958, investigadores de IBM, John Cocke y Daniel Slotnick, hablaron por primera vez de usar el paralelismo en cálculos. En 1962, Burroughs Corporation lanzó una computadora con cuatro procesadores. En 1967, Gene Amdahl y Slotnick debatieron sobre la viabilidad del procesamiento paralelo, y fue entonces cuando se formuló la ley de Amdahl.

En 1969, Honeywell lanzó un sistema con varios procesadores que podían trabajar en paralelo. En los años 70, la Universidad Carnegie Mellon desarrolló el C.mmp, uno de los primeros multiprocesadores con más de unos pocos procesadores.

Las computadoras paralelas SIMD (Instrucción Única, Datos Múltiples) también surgieron en los años 70. La idea era que una sola unidad de control pudiera manejar muchas instrucciones a la vez. En 1964, Slotnick propuso una computadora masivamente paralela. Su diseño fue financiado por la Fuerza Aérea de los Estados Unidos y se llamó ILLIAC IV. Aunque fue un proyecto ambicioso, tardó mucho tiempo y costó mucho dinero, y cuando estuvo listo en 1976, ya había sido superado por otras supercomputadoras como el Cray-1.

¿Qué es una computadora paralela?

Una computadora paralela es una máquina que tiene varios procesadores. Cada procesador trabaja en una parte diferente de un problema, y todos los procesadores pueden intercambiar información entre sí para resolver el problema de forma conjunta.

Ventajas de las computadoras paralelas

• Rendimiento y memoria: Son capaces de resolver problemas que necesitan ser resueltos muy rápido o que requieren una gran cantidad de memoria.

Beneficios de las computadoras paralelas

• Datos: Pueden manejar grandes cantidades de datos o buscar soluciones en áreas muy extensas.
• Pasos de tiempo: Permiten simulaciones más largas o con mayor detalle en el tiempo.
• Ejecución (rápida): Reducen los tiempos de espera, pueden encontrar muchas soluciones al mismo tiempo o realizar simulaciones largas en tiempo real.

Véase también

En inglés: Parallel computing Facts for Kids