PDF de programación - Programación de arquitecturas paralelas

Programación de arquitecturas

paralelas

José M. Cámara
([email protected])

v. 1.0



Guión

Niveles de aproximación.
Nivel de sistema operativo.
• Sistemas Operativos de red.
• Sistemas Operativos multiprocesador.
• Sistemas Operativos distribuidos.
o Sistemas de paso de mensajes.

Nivel de aplicación.
• Programación concurrente.

o Sincronización en variable compartida.
o Sincronización en paso de mensajes.
o Gestión de procesos concurrentes.
o Motivación para la programación

concurrente.



Nivel de gestión.
• Planificación.
• PBS.

Conceptos relevantes
Programa: código a ejecutar por el
procesador (nivel de máquina).

Usuario: persona que hace uso de la
máquina (programador, administrador,…)

Nivel de sistema operativo

Sistemas operativos para multiprocesadores con
memoria compartida (SMP):
• Software fuertemente acoplado
• sobre Hardware fuertemente acoplado

Sistema operativo de red (actualmente todos):

• Software débilmente acoplado
• sobre Hardware débilmente acoplado

Sistema operativo distribuido (SOD):

• Software fuertemente acoplado
• sobre Hardware débilmente acoplado

La tradicional multiplicidad de sistemas disponibles (normalmente versiones
propietarias de UNIX), ha venido a converger en un limitado número de
sistemas UNIX (LINUX casi siempre) y la irrupción de Windows.

Sistemas operativos de red.

Permiten realizar

operaciones en máquinas

remotas a través del
adaptador de red.

En la actualidad, todos los

sistemas operativos

ofrecen esta funcionalidad,

por lo que no vamos a

profundizar en su estudio.

Se trata de una

funcionalidad que permite
la computación paralela,
pero de una manera muy

poco eficiente.

Sistemas operativos multiprocesador I

Al igual que los sistemas

operativos de red,
proporcionan una
funcionalidad que
actualmente está

disponible por defecto.

Permiten la gestión de un

entorno de

multiprogramación sobre

un hardware

multiprocesador.

Respecto a la gestión
monoprocesador, la

diferencia está en que hay
un recurso, el procesador,
que se ha multiplicado.

El planificador debe dar

servicio a la cola de

procesos, haciendo uso
eficiente de los diferentes
procesadores disponibles.

Su diseño les permite

gobernar tanto entornos
multiprocesador como
multinúcleo o ambos.

Sistemas operativos multiprocesador II

Dos conceptos
relevantes:

Proceso: unidad de protección y asignación de recursos.

Hilo: unidad de planificación.

Multiprocesadores simétricos: todos los nodos tienen la
misma funcionalidad y pueden ejecutar igualmente el SO.

Un proceso puede albergar varios hilos, cada uno de ellos con su propia pila,
estado de ejecución y contexto del procesador.
Los hilos a planificar
pertenecen a las
aplicaciones de usuario
y al propio sistema
operativo. A este
respecto tenemos:
Un problema a atajar es la posible aparición de condiciones de carrera en el
acceso a la cola de procesos por parte de un planificador ejecutado
concurrentemente en varios procesadores. Para evitarlo, el SO se ejecutaría en
exclusión mutua.

Multiprocesadores asimétricos (maestro – esclavo): un nodo
ejecuta SO y otros solamente aplicaciones -> Si el nº de
esclavos es alto, el maestro se colapsa.

Sistemas operativos multiprocesador III -

Planificación

En los multiprocesadores la
planificación de procesos
(hilos) se convierte en una
tarea doble:

Decidir qué proceso recibe tiempo de CPU.

Decidir qué CPU alberga el proceso.

Tiempo compartido: todos los hilos se encolan y son
planificados de forma independiente.

Existen diferentes
modelos:

Espacio compartido: los hilos relacionados (pertenecientes a un
mismo proceso o tarea) se planifican en conjunto, empiezan
cuando hay disponible un número suficiente de CPUs y no son
interrumpidos).

En pandilla (gang): los hilos pueden ser interrumpidos, pero los
que están relacionados son interrumpidos y recuperados a la
vez.

Sistemas operativos multiprocesador IV -

Ejemplo

LINUX incorpora soporte para multiprocesadores desde la versión 2.6 de su núcleo. En
ella implementa el planificador O(1).
La planificación de procesos se realiza en tiempo compartido, para lo cual mantiene
una cola de procesos activos y una cola de procesos expirados por CPU.
Los procesos que han consumido su “slot” de tiempo asignado pasan a la cola de
expirados.
Para un determinado nivel de prioridad, cuando todas sus tareas se encuentran
expiradas, ésta cola pasa a ser activa.
Cada cola soporta 140 niveles de prioridad, siendo los 100 más altos para tareas de
tiempo real. En cada nivel, la cola de procesos es FIFO.
Cada 200ms se monitoriza la carga de los procesadores y se rebalancea.

La existencia de una cola por CPU permite mejorar la eficiencia de cache. La
recuperación de una tarea previamente procesada, disminuye los fallos de cache.

Sistemas operativos distribuidos

Logran que un hardware formado por computadores independiente, funcione a ojos del
usuario como una sola máquina (máquina virtual).

• Los SO actuales no proporcionan esta funcionalidad.

Existen diversas formas de implementar el sistema:

• Arquitectura cliente servidor: implementadas por ejemplo en sistemas de información en los que clientes locales

acceden a servidores remotos mediante un lenguaje de consultas.

• Llamadas a procedimiento remoto: las aplicaciones invocan procedimientos que se ejecutan en máquinas remotas.
• Sistemas de paso de mensajes: procesos ejecutados en máquinas diferentes se comunican entre sí mediante

mensajes y colaboran para realizar una tarea. Se trata de la opción por defecto en sistemas de computación paralela.
Para lograrlo va a ser necesaria una capa adicional de software denominada middleware que
proporciona la funcionalidad de máquina virtual, que está basada en dos conceptos:

• Migración de procesos: debe ser capaz de mover procesos de una máquina a otra en tiempo de ejecución para, entre

otras cosas, lograr un balanceo dinámico de carga.

• Tolerancia a fallos: debe responder sin fallos a situaciones de incorporación o desaparición de componentes de la

máquina.

Sistemas de paso de mensajes

Fiable: garantiza la entrega del mensaje y dispone de mecanismos de notificación al emisor.

Alternativas del
sistema de paso
de mensajes:

No fiable: entrega en mensaje a la red y lo olvida. Es menos seguro pero menos costoso en términos de
sobrecarga de la red.

Bloqueante: interrumpe al proceso peticionario hasta que se haya completado la operación requerida
(envío o recepción). Considera que se ha completado la operación cuando la información se encuentra
en un buffer local, no cuando ha llegado a destino en caso de envío.
No bloqueante: continúa el procesamiento independientemente del estado del mensaje. El envío o
recepción se procesa en background. Permite acelerar el procesamiento pero puede producir
condiciones de carrera.
Síncrono: interrumpe al emisor hasta que el receptor ha recogido el mensaje.

Asíncrono: solamente interrumpe al emisor en función de si el sistema es bloqueante o no.

La implementación del middleware puede tomar una decisión en cuanto a fiabilidad, bloqueo y sincronización,
pero también puede proporcionar varias alternativas.

El middleware se puede implementar bajo dos
estrategias diferenciadas:

Extensión del sistema operativo que le proporciona la
funcionalidad de sistema distribuido

Capa intermedia independiente del SO que proporciona un API a
las aplicaciones de usuario (MPI).

Ambas opciones pueden ser complementarias: la primera de ellas suele responder mejor al modelo de máquina virtual,
mientras que la segunda facilita el desarrollo de aplicaciones paralelas mientras que implementa los servicios mínimos
para proporcionar soporte de máquina virtual.

Dos paradigmas
en cuanto al
desarrollo de
aplicaciones
paralelas:

Modelos de
paralelismo
explícito:

Nivel de aplicación

Paralelismo implícito: el usuario no se implica en el aprovechamiento de las posibilidades del
hardware. Confía en que las capas inferiores (compilador, sistema operativo) lo hagan por él.

Paralelismo explícito: el usuario desarrolla sus aplicaciones bajo alguna de las alternativas que
permiten la explotación de un hardware paralelo.

Lenguajes tradicionales con librerías paralelas (MPI). Solución simple en cuanto a esfuerzo
inicial, pero con alta implicación por parte del usuario. Un programador inexperto puede
provocar una pérdida de rendimiento.

Extensiones a lenguajes tradicionales. Requieren de un nuevo compilador y un esfuerzo de
aprendizaje algo mayor.

Directivas de compilación: el paralelismo se explicita a nivel de directivas que, si se obvian, no
impiden que el programa se compile como secuencia.

Una vez más, existen soluciones que combinan varias alternativas. Por otro lado, el
esfuerzo de aprendizaje puede depender de su ámbito de aplicación (CUDA).

Programación concurrente

Concepto: se produce cuando el programador se encarga de forma explícita de la creación, destrucción y
sincronización hilos, procesos o tareas.

Cada una de esas entidades se va a ejecutar en un procesador virtual.

Si el procesador virtual es también real, hablaremos de programación paralela.

Independientemente del entorno en
que se desarrolle, el entorno de
programación debe proporcionar
una serie de servicios:

Expresión de la ejecución concurrente mediante el concepto de proceso
(hilo o tarea según los casos).

Comunicación entre procesos.

Sincronización entre procesos.

Independientes: no necesitan comunicación ni sincronización.

Los procesos pueden ser:

Cooperativos: se comunican y sincronizan para realizar una labor común.

Competitivos: son independientes pero compiten por recursos comunes
para lo cual van a requerir comunicación y/o sincronización.

La comunicación puede ser:

Variable compartida.

Paso de mensa