Paralelismo

  • Frank Sebastian Naranjo Castillo
  • Laura Alejandra Babativa Rojas

Cuando hablamos de paralelismo nos referimos a como el procesador se encarga de ejecutar varias tareas al mismo tiempo, operación que en años anteriores se consideraba casi que imposible, pues para entonces los procesadores con los que contábamos solo eran capaces de procesar instrucciones según su capacidad la cual no era mayor cosa, una de las principales dificultades presentes era el tamaño de la memoria de acceso aleatorio.

Con el gran avance en las últimas décadas se logró contar con hardware lo suficientemente optimo como para desempeñar dichas múltiples tareas.

Al tener dichos avances en el hardware el paralelismo ha tomado gran auge, pues gracias a este se nos facilitó la solución de varios problemas que para tiempos previos resultaban costosos y complicados de resolver. La implementación de este se debe acoplar a características específicas que permitan la ejecución en paralelo, si no se hace de manera correcta no se ejecutara de manera eficaz perdiendo así la idea principal del paralelismo, en ciertos programas existen datos que dependen de otros datos, si lo dicho anteriormente está presente se debe tomar en cuenta que esto hace parte de las principales problemáticas, pues de esta forma no se podría realizar la predicción de instrucciones las cuales son vitales para la continuidad de la ejecución del programa.

Se pueden evaluar algoritmos en paralelo con preguntas como ¿Qué tan rápido se puede resolver un problema usando una maquina paralela? o ¿Con que eficiencia se usan esos procesadores? Pues encontramos que si la solución a estas preguntas son las más coherentes y eficaces a la hora de satisfacer la problemática estamos hablando de un algoritmo de paralelismo adecuado y listo para su implementación.

Glosario

Algoritmo: Conjunto ordenado de operaciones sistemáticas que permite hacer un cálculo y hallar la solución de un tipo de problemas.

Arquitectura(Computadores): Es el diseño conceptual y la estructura operacional fundamental de un sistema de computadoras.​

Framework: Es un conjunto estandarizado de conceptos, prácticas y criterios para enfocar un tipo de problemática particular que sirve como referencia, para enfrentar y resolver nuevos problemas de índole similar.

Hardware: Conjunto de elementos físicos o materiales que constituyen una computadora o un sistema informático.

Instrucción: Acción elemental que se da a una computadora a fin de que efectúe una determinada operación.

OpenMP: interfaz de programación de aplicaciones (API) para la programación multiproceso de memoria compartida en múltiples plataformas. 

Proceso paralelo: Un proceso paralelo es aquel que se realiza al mismo tiempo que otro, siendo ejecutados ambos de modo simultáneo.

Procesador: Componente electrónico donde se realizan los procesos lógicos.

Software: Conjunto de programas y rutinas que permiten a la computadora realizar determinadas tareas.

Sistema empotrado: Sistema de computación diseñado para realizar una o algunas pocas funciones dedicadas,​​ frecuentemente en un sistema de computación en tiempo real. 

¿Que es el paralelismo?

El Paralelismo, en la arquitectura de computadores consiste en que se pueden hacer varios procesos al mismo tiempo, quiere decir que es un proceso simultaneo. Con la función de poder dividir los problemas a una menor complejidad.

Hace unos años las CPU’S tenían la necesidad de utilizar el silicio por la limitación del hardware, pero el silicio no es un buen semiconductor, porque gastaba mucha energía para las instrucciones de la cache. Existen computadores con multi-nucleos, es decir, que contiene varias CPU’S en un equipo. El hardware paralelo hace diferentes tareas simultáneamente.

Hablando históricamente un poco, la gráfica muestra la evolución de los computadores desde el año 1993.

Para el mejoramiento el rendimiento del software en multi-nucleos depende de los recursos paralelos para su funcionabilidad.

F = fracción de código paralelizable.

Variables principales para un multi-núcleo:

  1. Hardware:
    • Cantidad de núcleos de procesador en el chip.
    • Nivel de memoria cache.
    • Espacio que ocupa la cache compartida.
  2. Software:
    • Secuencial y paralela.
    • Hacer uso de los recursos paralelos para su funcionabilidad.

Principales características:

  • Se habla de mayor o menor grado de paralelismo en la medida en que un algoritmo sea más o menos divisible en partes independientes con igual coste computacional.
  • Diseño de algoritmos eficientes. No hay ganancia si los algoritmos no se diseñan adecuadamente.
  • Lenguajes para computadores paralelos, flexibles para permitir una implementación eficiente y que sean fáciles de programar.

También debemos tener en cuenta los siguientes aspectos del paralelismo:

  • Paralelismo a nivel procesador: la ejecución de diversas actividades simultáneamente en varios procesadores.
  • Paralelismo a nivel de maquina: La computación paralela es una forma de cómputo en la que muchas instrucciones se ejecutan simultáneamente.

Evolución

Evolución de la Arquitectura de Computadores.

Clasificación

Clasificación según Flynn:

(En 1996 Flynn propuso una clasificación de computadores según el flujo de instrucciones y el flujo de datos)

  • Flujos: El control funciona según el orden de la memoria y los datos ejecutaran las instrucciones cuando los operandos estén disponibles.
  • Reducción: Es una clase de los flujos, que ejecuta las instrucciones que otra necesite sus resultados.
  • SISD: Uni-Procesador (Sistemas monoprocesadores), Arquitectura Von Neumann. Esta es la representación del gran porcentaje de ordenadores actuales. Las instrucciones se procesan de manera secuencial.  Un ordenador de este tipo puede tener más de una unidad funcional, y todo bajo supervisión de una única unidad de control.
  • SIMD: Es una unidad de control que realiza varias funciones aritméticas y lógicas. La misma instrucción se ejecuta en varios procesadores sobre datos distintos. Ejemplo: procesadores vectoriales. Para este caso hay múltiples unidades de proceso, controladas por una unidad de control. Todos los procesadores reciben la misma instrucción, pero cada uno trabaja sobre datos distintos.
  • MISD:  Es una arquitectura no implementada. Tiene varias unidades de control más la unidad aritmética y lógica que realizan partes de la operación en un flujo de datos. Como se dijo anteriormente tiene x procesadores, cada uno de ellos obtiene instrucciones diferentes, pero trabajan sobre los mismos datos, para resumir, se puede decir que la salida de un procesador es la entrada del siguiente. Hasta el momento no hay ninguna maquinas que siga este tipo de clasificación. (Esta estructura ha sido implementadas solo para fines de investigación).
  • MIMD: Multiprocesador de varios flujos. Cada procesador coge sus instrucciones y opera con sus propios datos. Entre sus principales características tenemos en Sistemas multiprocesadores una memoria compartida entre x elementos de proceso y en sistemas multicomputador una memoria distribuida.

Tipos

Interno o implícito: Lenguaje secuencial y compilador, su funcionabilidad es paralelizar y asignar recursos.

Ejemplo: Pipeline, procesos vectoriales.

Externo o explícito: Usa dialectos paralelos de programación, su función es quedar visible al usuario (SIMD, MISD, MIMD).

Paralelismo a nivel Bit: Reduce el número de las instrucciones.

Paralelismo a nivel de instrucción: Conjunto de instrucciones que se ejecutan paralelamente sin cambiar el resultado final del programa.

Paralelismo de Datos: Los datos se reparten en diferentes nodos de cómputo para que se ejecute paralelamente y da un solo resultado.

Paralelismo de Tareas: Diferentes cálculos se ejecutan en el mismo o diferentes datos.

Espacio de direcciones de memoria

Multiprocesadores:

Estos se caracterizan por compartir la memoria, un valor escrito en memoria por un procesador puede ser leído directamente por cualquier otro. NYU ultracomputer hace parte de los primeros computadores con este tipo de arquitectura.

Tipos:

UMA: En es arquitectura todos los procesadores comparten el mismo espacio de memoria y tardan el mismo tiempo en acceder a cualquier posición de memoria de ahí su nombre, arquitectura de acceso a memoria uniforme

NUMA: Arquitectura multiprocesador de memoria compartida, todos los procesadores comparten el mismo espacio de direcciones de memoria.

COMA: Es un caso dentro de los NUMA. El acceso a todas las posiciones de memoria no es uniforme, y se tarda menos tiempo e acceder a las memorias que a las otras memorias.

Multicomputadores:

En este caso cada procesador dispone de su propia memoria, local o privada, independiente del resto y accesible solo por su procesador. La comunicación se realiza por paso de mensajes. El primero debe construir un mensaje por software, enviarlo a través de una red de interconexión y le segundo debe recibirlo.

Ejemplos

Luego de conocer la importancia del paralelismo entramos a ver en detalle ejemplos de este que encontramos casi que en nuestra vida cotidiana. En algunas ocasiones nos topamos con sistemas empotrados cuya función es dar una respuesta en tiempo real, actualmente se puede diseñar el sistema con varios procesadores muy simples que realizan siempre la misma operación colaborando entre ellos. Se suelen utilizar FPGA (Field Programmable Gate Array) o DSP (Digital Signal Processors).

Llamamos Cloud Computing a una computación paralela donde se distribuyen los recursos de todo tipo, el usuario podrá acceder simultáneamente a cualquier elemento que conforme esta combinación, dicha combinación necesita de herramientas que permitan la virtualización.

En las LAN (Local Area Networks) se enlazan varios procesadores por medio de una red de conexión de alta velocidad, formándose un cluster, que se utiliza con programación por paso de mensajes, pero puede llegar a poderse utilizar OpenMP si se desarrollan versiones eficientes que distribuyan automáticamente los datos en la memoria y generen las comunicaciones necesarias para acceder a los datos.

Algunos sistemas combinan una CPU y varios núcleos en una GPU; siendo la CPU más veloz, disponiendo de más memoria y con mayor precisión en la representación de los datos. Por otro lado, las GPU son mucho más baratas y más rápidas si se utilizan muchos elementos computacionales que permiten trabajar a muchos threads simultáneamente. El ideal es que también en los sistemas de memoria compartida encontremos sistemas heterogéneos, con núcleos de distinta arquitectura en un mismo chip.

También podemos mencionar la supercomputación, lo cual se refiere a los sistemas computacionales más potentes de los problemas que demandan de más computación. Como tradición la resolución de estos se lleva a cabo en grandes centros, pero debido a la innovación presente se han llevado a ámbitos de sistemas distribuidos, por lo que se pueden considerar la red como mayor supercomputador actual.

Eso hablando de manera general, pero si hablamos de una manera un poco más específica podemos hablar de:

  • El Cray T3E: Siendo este el mayor exponente de la segunda generación de multiprocesadores la cuela dio inicio con el Cray T3D. La red de interconexión en ambos sistemas es un toro 3-D. Cada unidad de proceso cuenta con características tales como:
  • Un DEC Alpha 21164
  • 2 Gbytes de memoria
  • Un router de comunicación

Sus procesadores son capaces de procesar instrucciones por periodo de reloj

  • Procesadores de 300Mhz con un pico de 600Mflops.
  • Procesadores de 450Mhz con un pico de 900Mflops.
  • Myrinet: Es una red de interconexión ideada para NOWs (Network Of Workstation) de una red LAN con características particulares para su utilización en NOWs

Elementos principales:

  • Red
  • Conmutadores

Ambos elementos se pueden combinar de diversas formar topologías irregulares.

Actualmente grandes empresas de desarrollo de software y hardware están diseñando librerías y frameworks para facilitar la programación en paralelo pues sabemos que esta es bastante complicada de manipular (Empresas como Intel y Microsoft).

También existen organizaciones como la OpenMP que creo una API para el desarrollo de software concurrente y paralelo.

Además de liberaría existen varios lenguajes de programación que incorporan a la concurrencia como núcleo central incluyendo soporte nativo, palabras claves, etc. Entre ellos podemos nombrar a Erlang, Clojure, y el nuevo lenguaje de Microsoft Axum.

Hablando de una manera más global, abarcando otras áreas de nuestra vida cotidiana tenemos:

  • Proyectos de ingeniería: Análisis de elementos finitos, aerodinámica computacional, inteligencia artificial y más.
  • Exploración de recursos energéticos: Modelización de yacimientos, seguridad de reactores nucleares
  • Investigación medica: Tomografía computarizada, síntesis de proteínas y más.

Referencias

  • Frank Sebastian Naranjo Castillo
  • Laura Alejandra Babativa Rojas