PDF de programación - Sistemas de Procesadores paralelos

Sistemas de Procesadores

Paralelos

(Multiprocesadores y Multicomputadoras)

PARTE I

Profesor: Mag. Marcelo Tosini
Cátedra: Arquitectura de Computadoras y técnicas Digitales
Carrera: Ingeniería de Sistemas
Ciclo: 4º año

1

Generalidades

Introducción

Sistemas de cómputo compuestos por varios (decenas… miles) de procesadores
Sistemas de cómputo compuestos por varios (decenas… miles) de procesadores

Tres elementos principales:
Tres elementos principales:

• Procesadores
• Procesadores
• Memoria
• Memoria
• Interconexión
• Interconexión

Microprocesadores

Multicomputadoras

• Fuertemente acoplados
• Fuertemente acoplados

•Comunicación a través de
•Comunicación a través de
memoria central
memoria central

• Velocidad acotada por el
• Velocidad acotada por el
ancho de banda (bits/seg.)
ancho de banda (bits/seg.)

• Conexionado a través de
• Conexionado a través de
una red o con memorias
una red o con memorias
multipuerta
multipuerta

• Débilmente acoplados
• Débilmente acoplados

•Comunicación a través de
•Comunicación a través de
redes de comunicación
redes de comunicación

• Existe un protocolo de
• Existe un protocolo de
pasaje de mensajes
pasaje de mensajes

• Cada procesador posee su
• Cada procesador posee su
propia memoria RAM y sus
propia memoria RAM y sus
puertos de I/O
puertos de I/O

3

Multiprocesadores

UMA (Uniform Memory Access)
La memoria física es uniformemente compartida por todos los procesadores. Todos los
procesadores tienen el mismo tiempo de acceso a todas las palabras de la memoria. Cada
procesador tiene su propia caché privada y también se comparten los periféricos

NUMA (Non Uniform Memory Access)
El acceso a memoria no es uniforme para diferentes procesadores. Existen memorias locales
asociadas a cada procesador y estos pueden acceder a datos de su memoria local de una
manera más rápida que a las memorias de otros procesadores

COMA (Cache Only Memory Access)
Caso especial de los sistemas NUMA. No
ha tenido mucha transcendencia, al igual
que los SIMD.
Las memorias distribuidas son memorias
caché, por este motivo es un sistema
muy restringido en cuanto a la
capacidad de memoria global. No hay
jerarquía de memoria en cada módulo
procesador. Todas las caché forman un
mismo espacio global de direcciones.

Multi

procesadores

UMA

COMA

NUMA

SMP: Symetric
MultiProcessor

DSM: Distributed
Shared Memory

Distintas maneras de organizar la memoria común

4

Multicomputadores

• Se pueden ver como un computador paralelo en el cual cada procesador tiene su propia
• Se pueden ver como un computador paralelo en el cual cada procesador tiene su propia

• En estos sistemas la memoria se encuentra distribuida y no compartida como en los
• En estos sistemas la memoria se encuentra distribuida y no compartida como en los

memoria local.
memoria local.

sistemas multiprocesador.
sistemas multiprocesador.

• Los computadores se comunican a través de paso de mensajes
• Los computadores se comunican a través de paso de mensajes
• Sólo tienen acceso directo a su memoria local y no al las memorias del resto de
• Sólo tienen acceso directo a su memoria local y no al las memorias del resto de

• El diagrama de bloques de un multicomputador es similar a los sistemas UMA
• El diagrama de bloques de un multicomputador es similar a los sistemas UMA

procesadores.
procesadores.

• MPP: Masively Parallel Processors

• COW: Cluster of Workstations

Multi

computadoras

• NOW: Network of Workstations

MPP

COW

NOW

5

Sistema de memoria compartida

PE1PE1

PE2PE2

PEnPEn

Red de

interconexión

PEPE

caché
caché
local
local

Mapeo
Mapeo
memoria
memoria

Memoria
Memoria

Red de interconexión
Red de interconexión

Sistema de memoria compartida

Elemento de proceso con memoria local

UMA

6

Sistema de pasaje de mensajes

memoria
memoria
local
local

E/SE/S

PEPE

STMSTM

Conexión entre los módulos
y la red de interconexión
a través del sistema de
transferencia de
mensajes (STM)

Esquema de un módulo de procesamiento

bus de transferencia de mensajes
bus de transferencia de mensajes

7

Conectividad de ambas alternativas

Memoria común
(Load / Store)

[La RED comunica

procesadores y memorias]

Se realiza por hardware

Paso de mensajes
(Send / Receive)
[La RED comunica

procesadores entre si]
Se realiza por software

µP1µP1

µP2µP2

µP3µP3

µPnµPn

µP1µP1

µP2µP2

µP3µP3

µPnµPn

RedRed

M1M1

M2M2

MkMk

RedRed

Multiprocesadores

Multicomputadoras

8

Redes de

Interconexión

Clasificación de las redes de
interconexión

1

De medio compartido
De medio compartido
• Redes de área local
• Redes de área local

• Ethernet
• Ethernet
• Token bus
• Token bus
• Token ring
• Token ring
• Bus de sistema
• Bus de sistema

3

Indirectas (dinámicas basadas en switches)
Indirectas (dinámicas basadas en switches)

• Topologías regulares
• Topologías regulares

• Crossbar
• Crossbar
• De interconexión multietapa (MIN)
• De interconexión multietapa (MIN)

• Redes con bloqueos
• Redes con bloqueos

2

Directas (estáticas basadas en routers)
Directas (estáticas basadas en routers)
• Topologías estrictamente ortogonales
• Topologías estrictamente ortogonales

• Malla
• Malla

• 2D
• 2D
• 3D
• 3D
• Toroides
• Toroides

• Toro 1D unidireccional
• Toro 1D unidireccional
• Toro 2D unidireccional
• Toro 2D unidireccional
• Toro 2D bidireccional
• Toro 2D bidireccional

• Hipercubo
• Hipercubo

• Otras topologías específicas:
• Otras topologías específicas:

• Árboles, grafos en estrella, etc
• Árboles, grafos en estrella, etc

• MIN unidireccional
• MIN unidireccional
• MIN bidireccional
• MIN bidireccional

Red Omega
Red Omega

• Redes sin bloqueos
• Redes sin bloqueos

• Red Closs
• Red Closs

• Hipercubo
• Hipercubo

• Topologías irregulares
• Topologías irregulares

4

Híbridas
Híbridas

• Buses de sistema múltiples
• Buses de sistema múltiples
• Redes jerárquicas
• Redes jerárquicas
• Otras topologías Hipergrafo
• Otras topologías Hipergrafo

• Hiperbuses
• Hiperbuses
• Hipermallas
• Hipermallas

10

1

Redes de medio compartido
• El medio de comunicación es compartido por todos los elementos de
• El medio de comunicación es compartido por todos los elementos de

proceso
proceso

• Sólo un dispositivo puede usar la red en un momento dado
• Sólo un dispositivo puede usar la red en un momento dado
• La red actúa como un elemento pasivo ya que no genera mensajes
• La red actúa como un elemento pasivo ya que no genera mensajes
• La comunicación es tipo broadcast por lo que debe haber sistemas de
• La comunicación es tipo broadcast por lo que debe haber sistemas de

arbitraje para solucionar colisiones
arbitraje para solucionar colisiones

Redes de área local
Redes de área local

Permiten comunicar equipos distanciados varios metros entre si
Permiten comunicar equipos distanciados varios metros entre si

Buses
Buses

Comunican equipos (procesadores) dentro de un rack
Comunican equipos (procesadores) dentro de un rack

11

1

Bus de sistema

•• Estructura mas simple para comunicar procesadores basados en bu
Estructura mas simple para comunicar procesadores basados en buss
•• Conecta procesadores y memorias en topolog
Conecta procesadores y memorias en topologíía UMA
a UMA
•• SegSegúún la arquitectura puede ser:
n la arquitectura puede ser:
•• Un bus
Un bus bidireccional
bidireccional
•• Dos buses unidireccionales
Dos buses unidireccionales

Bus
Bus
driver
driver

Proc1
Proc1

Proc2
Proc2

Proc3
Proc3

Mem1Mem1

Mem2Mem2

I/OI/O

Bus
Bus
driver
driver

Proc1
Proc1

Proc2
Proc2

Proc3
Proc3

Mem1Mem1

I/OI/O

Un bus bidireccional

Dos buses unidireccionales

12

1

Redes de área local
• Bus de Contención (CSMA/CD)
• Bus de Contención (CSMA/CD)
Acceso al bus compartido mediante competencia entre los dispositivos y
Acceso al bus compartido mediante competencia entre los dispositivos y
resolución de colisiones. Mas popular: CSMA/CD
resolución de colisiones. Mas popular: CSMA/CD
Desventaja: No determinista. No se puede garantizar el tiempo de espera
Desventaja: No determinista. No se puede garantizar el tiempo de espera
de un dispositivo hasta ganar el acceso al bus
de un dispositivo hasta ganar el acceso al bus
Velocidades de 10 Mbps a 100 Mbps
Velocidades de 10 Mbps a 100 Mbps
• Token Bus
• Token Bus
Dispositivos conectados en modo broadcast al medio (bus)
Dispositivos conectados en modo broadcast al medio (bus)
Uso de un token circulante entre los dispositivos en orden para habilitar
Uso de un token circulante entre los dispositivos en orden para habilitar
el uso del bus
el uso del bus
Velocidades de 2.4 Mbps
Velocidades de 2.4 Mbps
• Token Ring
• Token Ring
Dispositivos conectados en anillo físico
Dispositivos conectados en anillo físico
Uso de un token circulante entre los dispositivos
Uso de un token circulante entre los dispositivos
Velocidades de hasta 16 Mbps sobre cable y hasta 100 Mbps con FDDI (Fiber distributed
Velocidades de hasta 16 Mbps sobre cable y hasta 100 Mbps con FDDI (Fiber distributed
Data Interface)
Data Interface)

13

Redes Directas (punto a punto)

• Conexiones punto a punto entre distintos

procesadores de la red

• Consiste en un conjunto de nodos
• Cada nodo se conecta a un subconjunto

de otros nodos de la red

• Se pueden formar varios patrones regulares

o irregulares

I/OI/O

Procesador
Procesador

Memoria
Memoria
local
local

Router
Router

canales

de entrada

canales
de salida

Arquitectura de un nodo

• Cada nodo posee un procesador, memoria local

y dispositivos de entrada/salida

• Los nodos pueden tener distintas capacidades

funcionales: vectoriales, gráficos, etc

• El nodo se conecta a la red a través de un router
• El router maneja la comunicación mediante el uso

• Cada router tiene conexión directa con el router

de mensajes

de sus vecinos

• Los nodos no están necesariamente conectados

físicamente a todos los demás nodos de la red

• La topología de conexiones debe asegurar que todos

los nodos se puedan acceder desde cualquier nodo

2

14