Máquinas de acceso aleatorio en paralelo

Parallel Random Access Machines (PRAM)es un modelo, que se considera para la mayoría de los algoritmos paralelos. Aquí, varios procesadores están conectados a un solo bloque de memoria. Un modelo PRAM contiene:

  • Un conjunto de procesadores de tipo similar.

  • Todos los procesadores comparten una unidad de memoria común. Los procesadores pueden comunicarse entre sí a través de la memoria compartida únicamente.

  • Una unidad de acceso a memoria (MAU) conecta los procesadores con la única memoria compartida.

Aquí, n número de procesadores puede realizar operaciones independientes en nnúmero de datos en una unidad de tiempo particular. Esto puede resultar en el acceso simultáneo de diferentes procesadores a la misma ubicación de memoria.

Para resolver este problema, se han aplicado las siguientes restricciones en el modelo PRAM:

  • Exclusive Read Exclusive Write (EREW) - Aquí no se permite que dos procesadores lean o escriban en la misma ubicación de memoria al mismo tiempo.

  • Exclusive Read Concurrent Write (ERCW) - Aquí no se permite que dos procesadores lean desde la misma ubicación de memoria al mismo tiempo, pero sí pueden escribir en la misma ubicación de memoria al mismo tiempo.

  • Concurrent Read Exclusive Write (CREW) - Aquí todos los procesadores pueden leer desde la misma ubicación de memoria al mismo tiempo, pero no pueden escribir en la misma ubicación de memoria al mismo tiempo.

  • Concurrent Read Concurrent Write (CRCW) - Todos los procesadores pueden leer o escribir en la misma ubicación de memoria al mismo tiempo.

Hay muchos métodos para implementar el modelo PRAM, pero los más destacados son:

  • Modelo de memoria compartida
  • Modelo de paso de mensajes
  • Modelo paralelo de datos

Modelo de memoria compartida

La memoria compartida enfatiza en control parallelism que en data parallelism. En el modelo de memoria compartida, varios procesos se ejecutan en diferentes procesadores de forma independiente, pero comparten un espacio de memoria común. Debido a cualquier actividad del procesador, si hay algún cambio en cualquier ubicación de la memoria, es visible para el resto de los procesadores.

A medida que varios procesadores acceden a la misma ubicación de memoria, puede suceder que en un momento determinado, más de un procesador acceda a la misma ubicación de memoria. Suponga que uno está leyendo esa ubicación y el otro está escribiendo en esa ubicación. Puede crear confusión. Para evitar esto, algún mecanismo de control, comolock / semaphore, se implementa para garantizar la exclusión mutua.

La programación de memoria compartida se ha implementado en lo siguiente:

  • Thread libraries- La biblioteca de subprocesos permite múltiples subprocesos de control que se ejecutan simultáneamente en la misma ubicación de memoria. La biblioteca de subprocesos proporciona una interfaz que admite subprocesos múltiples a través de una biblioteca de subrutinas. Contiene subrutinas para

    • Creando y destruyendo hilos
    • Programación de la ejecución del hilo
    • pasar datos y mensajes entre hilos
    • guardar y restaurar contextos de hilo

Entre los ejemplos de bibliotecas de subprocesos se incluyen: subprocesos de SolarisTM para Solaris, subprocesos POSIX implementados en Linux, subprocesos Win32 disponibles en Windows NT y Windows 2000 y subprocesos de JavaTM como parte del kit de desarrollo estándar de JavaTM (JDK).

  • Distributed Shared Memory (DSM) Systems- Los sistemas DSM crean una abstracción de la memoria compartida en una arquitectura débilmente acoplada para implementar la programación de la memoria compartida sin soporte de hardware. Implementan bibliotecas estándar y utilizan las funciones avanzadas de administración de memoria a nivel de usuario presentes en los sistemas operativos modernos. Los ejemplos incluyen Tread Marks System, Munin, IVY, Shasta, Brazos y Cashmere.

  • Program Annotation Packages- Esto se implementa en las arquitecturas que tienen características uniformes de acceso a memoria. El ejemplo más notable de paquetes de anotaciones de programas es OpenMP. OpenMP implementa el paralelismo funcional. Se centra principalmente en la paralelización de bucles.

El concepto de memoria compartida proporciona un control de bajo nivel del sistema de memoria compartida, pero tiende a ser tedioso y erróneo. Es más aplicable a la programación de sistemas que a la programación de aplicaciones.

Méritos de la programación de memoria compartida

  • El espacio de direcciones global brinda un enfoque de programación fácil de usar para la memoria.

  • Debido a la cercanía de la memoria a la CPU, el intercambio de datos entre procesos es rápido y uniforme.

  • No es necesario especificar claramente la comunicación de datos entre procesos.

  • La sobrecarga de comunicación del proceso es insignificante.

  • Es muy fácil de aprender.

Deméritos de la programación de memoria compartida

  • No es portátil.
  • La gestión de la localidad de datos es muy difícil.

Modelo de paso de mensajes

El paso de mensajes es el enfoque de programación paralela más utilizado en los sistemas de memoria distribuida. Aquí, el programador tiene que determinar el paralelismo. En este modelo, todos los procesadores tienen su propia unidad de memoria local e intercambian datos a través de una red de comunicación.

Los procesadores utilizan bibliotecas de paso de mensajes para comunicarse entre ellos. Junto con los datos que se envían, el mensaje contiene los siguientes componentes:

  • La dirección del procesador desde el que se envía el mensaje;

  • Dirección de inicio de la ubicación de la memoria de los datos en el procesador de envío;

  • Tipo de datos de los datos de envío;

  • Tamaño de los datos de envío;

  • La dirección del procesador al que se envía el mensaje;

  • Dirección de inicio de la ubicación de la memoria para los datos en el procesador receptor.

Los procesadores pueden comunicarse entre sí mediante cualquiera de los siguientes métodos:

  • Comunicación punto a punto
  • Comunicación colectiva
  • Interfaz de paso de mensajes

Comunicación punto a punto

La comunicación punto a punto es la forma más sencilla de transmitir mensajes. Aquí, se puede enviar un mensaje desde el procesador de envío a un procesador de recepción mediante cualquiera de los siguientes modos de transferencia:

  • Synchronous mode - El siguiente mensaje se envía solo después de recibir una confirmación de que su mensaje anterior ha sido entregado, para mantener la secuencia del mensaje.

  • Asynchronous mode - Para enviar el siguiente mensaje, no se requiere el recibo de la confirmación de la entrega del mensaje anterior.

Comunicación colectiva

La comunicación colectiva involucra más de dos procesadores para el paso de mensajes. Los siguientes modos permiten comunicaciones colectivas:

  • Barrier - El modo barrera es posible si todos los procesadores incluidos en las comunicaciones ejecutan un bloque en particular (conocido como barrier block) para el paso de mensajes.

  • Broadcast - La radiodifusión es de dos tipos -

    • One-to-all - Aquí, un procesador con una sola operación envía el mismo mensaje a todos los demás procesadores.

    • All-to-all - Aquí, todos los procesadores envían mensajes a todos los demás procesadores.

Los mensajes transmitidos pueden ser de tres tipos:

  • Personalized - Los mensajes únicos se envían a todos los demás procesadores de destino.

  • Non-personalized - Todos los procesadores de destino reciben el mismo mensaje.

  • Reduction - En la transmisión de reducción, un procesador del grupo recopila todos los mensajes de todos los demás procesadores del grupo y los combina en un solo mensaje al que pueden acceder todos los demás procesadores del grupo.

Méritos de la transmisión de mensajes

  • Proporciona un control de paralelismo de bajo nivel;
  • Es portátil;
  • Menos propenso a errores;
  • Menos gastos generales en sincronización paralela y distribución de datos.

Deméritos de la transmisión de mensajes

  • En comparación con el código de memoria compartida en paralelo, el código de paso de mensajes generalmente necesita más sobrecarga de software.

Bibliotecas de paso de mensajes

Hay muchas bibliotecas de paso de mensajes. Aquí, discutiremos dos de las bibliotecas de paso de mensajes más utilizadas:

  • Interfaz de paso de mensajes (MPI)
  • Máquina virtual paralela (PVM)

Interfaz de paso de mensajes (MPI)

Es un estándar universal para proporcionar comunicación entre todos los procesos concurrentes en un sistema de memoria distribuida. La mayoría de las plataformas de computación paralela comúnmente utilizadas proporcionan al menos una implementación de interfaz de paso de mensajes. Se ha implementado como la colección de funciones predefinidas llamadaslibrary y se puede llamar desde lenguajes como C, C ++, Fortran, etc. Los MPI son rápidos y portátiles en comparación con otras bibliotecas de paso de mensajes.

Merits of Message Passing Interface

  • Se ejecuta solo en arquitecturas de memoria compartida o arquitecturas de memoria distribuida;

  • Cada procesador tiene sus propias variables locales;

  • En comparación con las computadoras grandes con memoria compartida, las computadoras con memoria distribuida son menos costosas.

Demerits of Message Passing Interface

  • Se requieren más cambios de programación para el algoritmo paralelo;
  • A veces es difícil de depurar; y
  • No funciona bien en la red de comunicación entre los nodos.

Máquina virtual paralela (PVM)

PVM es un sistema de paso de mensajes portátil, diseñado para conectar máquinas host heterogéneas separadas para formar una sola máquina virtual. Es un único recurso informático paralelo manejable. Los grandes problemas computacionales como los estudios de superconductividad, las simulaciones de dinámica molecular y los algoritmos matriciales pueden resolverse de manera más rentable utilizando la memoria y la potencia agregada de muchas computadoras. Gestiona todo el enrutamiento de mensajes, conversión de datos, programación de tareas en la red de arquitecturas informáticas incompatibles.

Features of PVM

  • Muy fácil de instalar y configurar;
  • Varios usuarios pueden utilizar PVM al mismo tiempo;
  • Un usuario puede ejecutar varias aplicaciones;
  • Es un paquete pequeño;
  • Soporta C, C ++, Fortran;
  • Para una ejecución determinada de un programa PVM, los usuarios pueden seleccionar el grupo de máquinas;
  • Es un modelo de transmisión de mensajes,
  • Computación basada en procesos;
  • Soporta arquitectura heterogénea.

Programación en paralelo de datos

El enfoque principal del modelo de programación en paralelo de datos es realizar operaciones en un conjunto de datos simultáneamente. El conjunto de datos está organizado en alguna estructura como una matriz, hipercubo, etc. Los procesadores realizan operaciones colectivamente en la misma estructura de datos. Cada tarea se realiza en una partición diferente de la misma estructura de datos.

Es restrictivo, ya que no todos los algoritmos pueden especificarse en términos de paralelismo de datos. Ésta es la razón por la que el paralelismo de datos no es universal.

Los lenguajes paralelos de datos ayudan a especificar la descomposición de datos y la asignación a los procesadores. También incluye declaraciones de distribución de datos que permiten al programador tener control sobre los datos (por ejemplo, qué datos irán a qué procesador) para reducir la cantidad de comunicación dentro de los procesadores.