PDF de programación - TEMA 5 Multiprocesadores y redes de interconexión

Arquitectura de Computadores

TEMA 5

Multiprocesadores y redes de interconexión

Curso 2014-2015

Contenidos

 Introducción
 Arquitecturas paralelas

o Memoria compartida
o Paso de mensajes

 Redes de interconexión
o Descripción estructural
o Topología de Red

 Redes estáticas
 Redes dinámicas

o Técnicas de conmutación
o Control de flujo
o Encaminamiento (routing)

 Bibliografía

o Apéndice F de [HePa12]
o Cap 1 y 10 de [CuSi99]

Nota.- En la elaboración de este material se han utilizado contenidos desarrollados por los profesores Manuel
Prieto, Luis Piñuel e Ignacio Martín. También se han utilizado figuras de [HePa12] y [CuSi99].

AC — Tema 5

Curso 2015-16

2

Introducción

 Una definición clásica de computador paralelo

o Colección de elementos de procesamiento que cooperan y se

comunican para resolver problemas grandes (cálculo,
almacenamiento) “rápidamente”. (Almansi and Gottlieb 1989)

 Objetivo

o Rendimiento / Eficiencia
o Replicación (Tolerancia a fallos)

 Esta definición da lugar a muchas preguntas:

o ¿Qué potencia tienen los elementos de proceso?
o ¿Cuánta memoria?
o ¿El número puede crecer de una manera sencilla: es escalable

el sistema?

o ¿Cómo se comunican y cooperan dichos elementos?
o ¿Cómo se transmiten los datos entre los procesadores?
o ¿Qué tipo de interconexión conecta los distintos

procesadores?

o ¿Qué abstracción (primitivas) proporciona el hardware

/software al programador?

AC — Tema 5

Curso 2015-16

3

Introducción

 Creciente interés por los multiprocesadores

“We are dedicating all of our future product development to multicore
designs. We believe this is a key inflection point for the industry.”

Intel President Paul Otellini,

describing Intel’s future direction at the
Intel Developer Forum in 2005

 Algunos factores determinantes

o Agotamiento de ILP

 Consumo de energía y coste creen más rápido que rendimiento

o Creciente interés en servidores de altas prestaciones

 Cloud computing, Software-as-a-Service (SaaS)
o Aumento de las aplicaciones intensivas en datos

 Geociencia, Biología computacional, ...
 Disponibilidad de enormes cantidades de datos vía Internet

o Mejora del conocimiento sobre cómo usar eficazmente los

multiprocesadores

 Entornos de grandes BD, multitud de accesos simultáneos,

problemas de cálculo científico

o Aprovechamiento de los diseños vía replicación del

procesador

AC — Tema 5

Curso 2015-16

4

•Arquitectura, Tecnología

• Aplicaciones

Aplicaciones

 Demanda: Aplicaciones “Grand-Challange”

o Evolución climática-Predicción meteorológica
o Genómica y Proteómica (Industria

farmacéutica)

o Industrias Aeronáutica y Automovilística
o Industria Militar (Proyecto ASCI

departamento defensa US)
o Industria Entretenimiento
o Procesamiento Transaccional

•Nuevas Aplicaciones

•Más Rendimiento

AC — Tema 5

Curso 2015-16

5

Aplicaciones: Ejemplo

 Evolución climática-Predicción meteorológica.

 Necesidades de memoria y cálculo

o El clima es una función de la longitud , latitud, altura, tiempo
o Para cada uno de estos puntos se debe calcular temperatura,

presión, humedad, y velocidad del viento (3 componentes)

o Conocido clima(i,j,k,t), el simulador debe proporcionar el

valor clima(i,j,k,t+t)

 Predicción 1 Minuto

Celdas de 1km x1km y 10 celdas en altura

 5x109 celdas (0.1 TB)
t de un minuto: 100 flop por celda (estimación muy
optimista)
 100x5x109 operaciones en menos de un minuto: 8 GFlops

 Predicción del tiempo a 7dias en 24 horas  56 Gflops

 Predicción de clima a 50 años en 30 días

 4.8 Tflops

AC — Tema 5

Curso 2015-16

6

Aplicaciones: Ejemplo

 Búsquedas en Internet

Febrero 2003

•Más de 150 millones de búsquedas/día

•Web’s largest index: Más de 3

billones (US) de páginas

Availability: 24x7

•World's largest commercial Linux
cluster: Más de 10,000 servidores

AC — Tema 5

Curso 2015-16

7

Arquitecturas Paralelas

 Modelo de Programación: concepto de máquina que utiliza el

programador

o ¿Cómo se comparte la información? ¿Cómo transferir la
información entre distintas partes de un programa que se
ejecuta en paralelo?

o ¿Cómo se lleva a cabo la coordinación de actividades? ¿Qué

primitivas de sincronización hay para coordinar actividades?
o Típicamente: el modelo de programación esta incorporado a

 Lenguaje de Programación (compilación)
 Librería

Son los encargados de realizar la correspondencia

 Construcciones del lenguaje o llamadas de la librería  Primitivas

disponibles a nivel usuario (Arquitectura de Comunicaciones)

 Algunas operaciones las realiza una combinación Hw/SO

 Memoria compartida vs. paso de mensajes

AC — Tema 5

Curso 2015-16

8

Arquitecturas de Memoria Compartida

 Un espacio de direcciones compartido

o Referente: multiprogramación en monoprocesadores

 Objetivo: Productividad (entornos time-sharing)
 Los procesos pueden configurarse de modo que parte de su

espacio de direcciones sea compartido:

– Comunicaciones: implícitas (operaciones LOAD/STORE)
– Sincronizaciones: SO, Operaciones Atómicas

Espacio de Direcciones

Virtual Compartido

Pn Private

Shared

Espacio de
Direcciones

P2 Private

Físicas

P1 Private

P0 Private

Múltiples procesos
pueden tener una
región de memoria
compartida proyectada
sobre su espacio de
direcciones virtual

Las escrituras de
variables residentes en
esta región son visibles
para el resto de los
procesos.

Store

Load

Pn

P0

Shared

Private

AC — Tema 5

Curso 2015-16

9

Arquitecturas de Memoria Compartida

 Multiprocesador de memoria compartida:

o Extensión natural de un sistema en el que diferentes

procesos pueden compartir memoria  añadir uno o varios
procesadores

o Red de interconexión vs. Nº de procesadores

 Pocos procesadores: red sencilla (p. ej. Bus)
 Muchos procesadores: red más compleja (p. ej. red multietapa)

o Escalabilidad: ¿Cuántos procesadores se pueden conectar sin
que la red se convierta en un cuello de botella que degrade el
rendimiento global?

I/O
devices

Mem

Mem Mem Mem

I/O ctrl

I/O ctrl

Interconnect

Processor

Processor

Processor

AC — Tema 5

Curso 2015-16

10

Arquitecturas de Memoria Compartida

 Diseño para un nº reducido de procesadores

o Symmetric (Shared-Memory) Multiprocessor (SMP)
o Memoria: centralizada con tiempo de acceso uniforme (“UMA”)

Interconexión vía bus común, E/S compartida

o Anchura de banda limitada. Limite en el numero máximo de procesadores
o Caches son cruciales: Coherencia
o Posibilidad de usar otras redes: crossbar, multietapa

o Ejemplos: Sun Enterprise 6000, SGI Challenge, Intel SystemPro, ……

Coherencia

Caches
Privadas

AC — Tema 5

Curso 2015-16

11

Arquitecturas de Memoria Compartida

 Diseño para un número elevado de procesadores

o Memoria: Distribuida con tiempo de acceso no uniforme (“NUMA”)
o Interconexión escalable.
o Anchura de banda crece con el numero de EP
o Ejemplos: Cray T3E

Baja Latencia

Alta fiabilidad

AC — Tema 5

Curso 2015-16

12

Arquitecturas de Paso de Mensajes

 Elemento de Proceso: Computador Completo (microproces, mem, E/S)

o Modelo de Programación

 Acceso directo al espacio de direcciones privado (memoria local)
 Comunicación explícita mediante operaciones I/O (llamadas al SO:

send/recv)

Recv Y,P, tag

Send X,Q, tag

Address Y

La combinación

send-recv establece:

• copia memoria-memoria
• sincronización

Address X

Proces P

Proces Q

 Sobrecarga:

o

Construir la cabecera del mensaje; copiar los datos en el
buffer de la red; enviar el mensaje; copiar los datos en el
buffer receptor; copiar los datos del espacio S.O. al
espacio usuario

 Diagrama de Bloques Semejante a NUMA

o

Diferencia: Las comunicaciones están integradas en el
sistema de E/S en lugar de en el sistema de memoria

 Semejante a los clusters de PCs

AC — Tema 5

Curso 2015-16

13

Redes de interconexión: Introducción

Red de interconexión como

elemento vertebrador de

los sistemas digitales

actuales

SAN / NOW

Clusters

PC / WS

IP Networks

LAN, WAN

Servidores

Supercomputadores

Placas

Chips

Diferentes exigencias

para el diseño de la

red de interconexión

AC — Tema 5

Curso 2015-16

14

Redes de interconexión: Introducción

 Local Area Network (LAN). Ej:

Ethernet (hasta 10 Gbps sobre una
distancia de 40 Km). Tb Clusters de
PCs

 Wide Area Network (WAN). Conexión

a escala global. Ej: ATM

Dominios de aplicación

 Network-on-Chip (NoC, OCN). Ej:

AMBA de ARM, SCCC de Intel, TILE-
GX de Tilera

 System/Storage Area Network (SAN).

Comunicación proc-mem-discos. Ej:
Infiniband (hasta 200 Gbps sobre una
distancia de 300 m)

AC — Tema 5

Curso 2015-16

15

Redes de interconexión: Introducción

 Factores de diseño: El principal factor en

computadores paralelos son las prestaciones de la
red:

o Latencia
o Productividad

 Otros factores de diseño:

o Escalabilidad
o Fiabilidad
o Expansión incremental
o Particionado y seguridad
o Simplicidad y bajo coste
o Distancia de expansión
o Consumo/disipación de energía

AC — Tema 5

Curso 2015-16

16

Descripción estructural: Elementos

RED

Conmutador
(Switch)

Enlace

Interfaz de Red
(Network Adapter)

AC — Tema 5

Curso 2015-16

17

Descripción estructural: Interfaz de Red

Esquema básico de un interfaz de red

Nodo

CPU

Memoria

Bus de Memoria

Bus de E/S

Interfaz SW

Interfaz HW

DMA

AC

Colas envío/recepción

CE

CE

Interfaz de Red

Red de

Interconexión

Programable

AC — Tema 5

Curso 2015-16

18

Descripción estructural: Interfaz de Red

 Mensaje

o Unidad lógica de comunicación
o Es la única unidad vista a nivel de aplicación.

 Paquete

o Unidad de transferencia entre interfaces de red (end-

to-end)

o También es la menor unidad que contiene información

de encaminamiento.

o Mecanismos de abstracción:

 Encapsulado
 Fragmentación

AC — Tema 5

Curso 2015-16

19

Descripción estructural: Enlace

Esquema básico de un enlace punto-a-punto

Gestor de

Buffers

Gestor de

Buffers

Planifica