Algoritmo paralelo - Introducción

Un algorithmes una secuencia de pasos que toman entradas del usuario y luego de algunos cálculos, producen una salida. UNparallel algorithm es un algoritmo que puede ejecutar varias instrucciones simultáneamente en diferentes dispositivos de procesamiento y luego combinar todas las salidas individuales para producir el resultado final.

Procesamiento concurrente

La fácil disponibilidad de las computadoras junto con el crecimiento de Internet ha cambiado la forma en que almacenamos y procesamos los datos. Vivimos en una época en la que los datos están disponibles en abundancia. Todos los días tratamos con grandes volúmenes de datos que requieren una computación compleja y eso también, en poco tiempo. A veces, necesitamos obtener datos de eventos similares o interrelacionados que ocurren simultáneamente. Aquí es donde requerimosconcurrent processing que puede dividir una tarea compleja y procesarla en varios sistemas para producir la salida en un tiempo rápido.

El procesamiento simultáneo es esencial cuando la tarea implica procesar una gran cantidad de datos complejos. Los ejemplos incluyen: acceso a grandes bases de datos, pruebas de aeronaves, cálculos astronómicos, física atómica y nuclear, análisis biomédico, planificación económica, procesamiento de imágenes, robótica, pronóstico del tiempo, servicios basados ​​en la web, etc.

¿Qué es el paralelismo?

Parallelismes el proceso de procesar varios conjuntos de instrucciones simultáneamente. Reduce el tiempo computacional total. El paralelismo se puede implementar usandoparallel computers,es decir, una computadora con muchos procesadores. Las computadoras paralelas requieren algoritmos paralelos, lenguajes de programación, compiladores y sistemas operativos que admitan la multitarea.

En este tutorial, discutiremos solo sobre parallel algorithms. Antes de seguir adelante, analicemos primero los algoritmos y sus tipos.

¿Qué es un algoritmo?

Un algorithmes una secuencia de instrucciones que se siguen para resolver un problema. Al diseñar un algoritmo, debemos considerar la arquitectura de la computadora en la que se ejecutará el algoritmo. Según la arquitectura, hay dos tipos de computadoras:

  • Computadora secuencial
  • Computadora paralela

Dependiendo de la arquitectura de las computadoras, tenemos dos tipos de algoritmos:

  • Sequential Algorithm - Un algoritmo en el que se ejecutan algunos pasos consecutivos de instrucciones en orden cronológico para resolver un problema.

  • Parallel Algorithm- El problema se divide en subproblemas y se ejecutan en paralelo para obtener salidas individuales. Posteriormente, estas salidas individuales se combinan para obtener la salida final deseada.

No es fácil dividir un gran problema en sub-problems. Los subproblemas pueden tener dependencia de datos entre ellos. Por lo tanto, los procesadores deben comunicarse entre sí para resolver el problema.

Se ha descubierto que el tiempo que necesitan los procesadores para comunicarse entre sí es mayor que el tiempo real de procesamiento. Por lo tanto, al diseñar un algoritmo paralelo, se debe considerar la utilización adecuada de la CPU para obtener un algoritmo eficiente.

Para diseñar un algoritmo correctamente, debemos tener una idea clara de los model of computation en una computadora paralela.

Modelo de Computación

Tanto las computadoras secuenciales como las paralelas operan en un conjunto (flujo) de instrucciones llamadas algoritmos. Este conjunto de instrucciones (algoritmo) instruye a la computadora sobre lo que tiene que hacer en cada paso.

Según el flujo de instrucciones y el flujo de datos, las computadoras se pueden clasificar en cuatro categorías:

  • Computadoras de flujo de instrucción único, flujo de datos único (SISD)
  • Computadoras de flujo de instrucciones único, flujo de datos múltiples (SIMD)
  • Computadoras de flujo de instrucciones múltiples, flujo de datos único (MISD)
  • Computadoras de flujo de instrucciones múltiples, flujo de datos múltiples (MIMD)

Computadoras SISD

Las computadoras del SISD contienen one control unit, one processing unit, y one memory unit.

En este tipo de computadoras, el procesador recibe un único flujo de instrucciones de la unidad de control y opera con un único flujo de datos de la unidad de memoria. Durante el cálculo, en cada paso, el procesador recibe una instrucción de la unidad de control y opera con un solo dato recibido de la unidad de memoria.

Computadoras SIMD

Las computadoras SIMD contienen one control unit, multiple processing units, y shared memory or interconnection network.

Aquí, una sola unidad de control envía instrucciones a todas las unidades de procesamiento. Durante el cálculo, en cada paso, todos los procesadores reciben un único conjunto de instrucciones de la unidad de control y operan con diferentes conjuntos de datos de la unidad de memoria.

Cada una de las unidades de procesamiento tiene su propia unidad de memoria local para almacenar tanto datos como instrucciones. En las computadoras SIMD, los procesadores deben comunicarse entre sí. Esto es hecho porshared memory o por interconnection network.

Mientras que algunos de los procesadores ejecutan un conjunto de instrucciones, los procesadores restantes esperan su siguiente conjunto de instrucciones. Las instrucciones de la unidad de control deciden qué procesador seactive (ejecutar instrucciones) o inactive (espere la siguiente instrucción).

Computadoras de MISD

Como sugiere el nombre, las computadoras de MISD contienen multiple control units, multiple processing units, y one common memory unit.

Aquí, cada procesador tiene su propia unidad de control y comparten una unidad de memoria común. Todos los procesadores reciben instrucciones individualmente de su propia unidad de control y operan en un solo flujo de datos según las instrucciones que han recibido de sus respectivas unidades de control. Este procesador funciona simultáneamente.

Computadoras MIMD

Las computadoras MIMD tienen multiple control units, multiple processing units, y un shared memory o interconnection network.

Aquí, cada procesador tiene su propia unidad de control, unidad de memoria local y unidad aritmética y lógica. Reciben diferentes conjuntos de instrucciones de sus respectivas unidades de control y operan con diferentes conjuntos de datos.

Nota

  • Una computadora MIMD que comparte una memoria común se conoce como multiprocessors, mientras que aquellos que utilizan una red de interconexión se conocen como multicomputers.

  • Según la distancia física de los procesadores, los multicomputadoras son de dos tipos:

    • Multicomputer - Cuando todos los procesadores están muy cerca unos de otros (por ejemplo, en la misma habitación).

    • Distributed system - Cuando todos los procesadores están lejos unos de otros (por ejemplo, en las diferentes ciudades)