PDF de programación - Paralelismo en monoprocesadores - Multithreading

Paralelismo en

monoprocesadores

Multithreading

Ejecución de múltiples hebras

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

Introducción

• Puesto que los programas usualmente ejecutan mas de un thread,
un paso mas de desarrollo de procesadores es la incorporación de
capacidad para ejecutar varias hebras

• Desarrollo motivado por aumentar la utilización de los recursos de
cálculo sobre todo cuando el thread actual por algún evento de E/S
de mucha latencia

• Se pueden mantener los recursos del procesador ocupados aún cuando

un thread se frene ante un fallo de caché o una falla de predicción de
salto

• Aproximaciones:

• CMP (Chip Multi Processor)
• FGMT (Fine Grained Multi Threading)
• CGMT (Coarse Grained Multi Threading)
• SMT (Simultaneous Multi Threading)

Aproximaciones multithreading

Aproximación MT

Recursos compartidos

mecanismo de

entre threads

cambio de contexto

Ninguna

Todos

Cambio de contexto

explícito del SO

FGMT

CGMT

SMT

CMP

Todos excepto banco de

Cambio de contexto en cada

registros y lógica de control

ciclo de reloj

Todos excepto buffers de

fecthing, banco de registros

y lógica de control

Todos excepto buffers de
fecthing, pila de hardware,
banco de registros, lógica
de control, ROB y restore

queue

Cambio de contexto ante

frenado del pipeline

No hay cambio de contexto.

Todos los contextos están
activos simultáneamente

Caché secundaria y sistema

No hay cambio de contexto.

de interconexión con el

exterior

Todos los contextos están
activos simultáneamente

Aproximaciones multithreading

Particionado estático
Particionado estático
de recursos de ejecución
de recursos de ejecución

Particionado dinámico
Particionado dinámico
de recursos de ejecución
de recursos de ejecución

Partición
Partición
espacial
espacial

Partición
Partición
temporal
temporal

Por ciclo
Por ciclo
de reloj
de reloj

Por unidad
Por unidad
funcional
funcional

CMP

FGMT

CGMT

SMT

Aproximaciones multithreading

CMP: Chip Multiprocessing
(SMP: Symetric multiprocessing)

SMT: Simultaneous multithreading

(HT: Hiper Threading de Intel)

2 o mas cores en el mismo chip

un único core en el chip

CORE 1

L2/L3

CORE 2

Chip

MT core

L3/RAM

L2/L3

L3/RAM

Paralelismo a nivel de hebra
(Thread Level Paralelism - TLP)
• El paralelismo a nivel de instrucciones (ILP) se basa en operaciones

“independientes” que pueden resolverse cuando se ejecuta un
programa

• Por otro lado, un procesador superescalar ejecuta “al mismo tiempo”

varios programas (procesos, threads, etc) pero multiplexados en el
tiempo

• Las instrucciones de diferentes threads son paralelizables

• Objetivo: Explotar este paralelismo a nivel de hebra (thread level)

mediante ejecución concurrente, para mejorar el rendimiento del
procesador

• La mejora anterior NO mejora los tiempos de ejecución de cada thread

• La idea básica: Cuando se ejecuta un solo thread quedan recursos sin

ejecutar en el procesador. Entonces se pueden utilizar ejecutando mas
threads

Ejecución de threads

Un solo thread

thread
thread

I/OI/O

thread
thread

I/OI/O

thread
thread

I/OI/O

thread
thread

• Habiendo un solo thread el procesador queda inactivo durante los eventos de I/O
• La perdida de rendimiento puede ser de millones de ciclos de reloj

Múltiples threads

thread 1 thread 2
thread 1

thread 2 thread 1
thread 1

thread 2 thread 1
thread 2

thread 1 thread 2

thread 2 thread 1
thread 1

• Cuando un thread entra en espera por I/O se debe liberar el procesador para

permitir a otro thread el uso de los recursos

• El proceso de cambio entre threads se realiza mediante un cambio de contexto

Cambio de contexto tradicional

Contexto: Estado del procesador asociado a un proceso particular

• Contador de programa
• Registros
• Datos de memoria
• Registros de estado y control, punteros de paginas y segmentos
• Registros de sombra
• ¿Contenidos de caché, entradas de BTB y TLB?

Cambio de contexto tradicional

1.
2.
3.

4.

Una interrupción (precisa) del timer detiene un programa en ejecución
El SO almacena el contexto del thread parado
El SO recupera el contecto de un thread detenido con anterioridad (a
excepción del PC)
El SO utiliza un “retorno de excepción - IRET” para saltar al “PC” reiniciando
el thread.

El thread nunca se entera que fue detenido, dezplazado, recuperado y

reiniciado en el procesador

Cambio de contexto rápido

Un procesador queda inactivo (idle) cuando un thread entra

en espera por un fallo de caché

• Normalmente un fallo de caché necesita del orden de 16 a 32 ciclos
• Normalmente un fallo de caché necesita del orden de 16 a 32 ciclos

• Un cambio completo de contexto puede llevar del orden de cientos de
• Un cambio completo de contexto puede llevar del orden de cientos de

de penalización de fallo y
de penalización de fallo y

ciclos, entonces…
ciclos, entonces…

No siempre conviene un cambio de contexto por el SO
No siempre conviene un cambio de contexto por el SO

Solución: cambio de contexto por hardware

• Replicar registros de contexto (PC, GPRs, flags, pointers, etc) eliminando

el copiado a y desde memoria RAM

• Varios contextos pueden compartir recursos comunes (caché, BTB, TLB)

incluyendo un campo “process ID” en sus entradas… Se elimina la
necesidad de cambio de contexto (Se eliminan fallos forzosos por cambio de contexto)

• El cambio de contexto por HW consume pocos ciclos de reloj:
• PID se carga con el siguiente identificador de proceso
• Seleccionar el conjunto de registros de contexto a activar

Optimización del cambio de contexto
rápido
¿Es posible el cambio de contexto cuando un thread se detiene

por dependencias RAW?

Cambio de contexto a nivel de unidades funcionales
Cambio de contexto a nivel de unidades funcionales

Div – 16 cycles
Div – 16 cycles

Mul – 12 cycles
Mul – 12 cycles

fetching
fetching

decoding
decoding

dispatch
dispatch

Add – 2 cyc

Add – 2 cyc

ROBROB

FXFX

Load/Store - ? cyc
Load/Store - ? cyc

Justificación:

• El grado de un superescalar es usualmente mayor que el ILP logrado
• En la actualidad, procesadores de grado 8 alcanzan ILP de 2 ó 3

¿Por qué no usar las unidades funcionales ociosas en otro thread?

Implementación para varios threads

• Se puede suponer varios pipelines que repliquen la parte “in order” de

un superescalar.

• Cada pipeline tiene su propio PC y su banco de registros
• Mayor lógica de administración de los recursos compartidos (UF)

fetch 1
fetch 1

decode 1
decode 1

dispatch 1
dispatch 1

Div – 16 cycles
Div – 16 cycles

Mul – 12 cycles
Mul – 12 cycles

fetch 2
fetch 2

decode 2
decode 2

dispatch 2
dispatch 2

Add – 2 cyc

Add – 2 cyc

fetch n
fetch n

decode n
decode n

dispatch n
dispatch n

FXFX

Load/Store - ? cyc
Load/Store - ? cyc

ROB 1
ROB 1

ROB 2
ROB 2

ROB n
ROB n

• El rendimiento de cada thread es peor que en un superescalar debido a

degradaciones asociadas al aumento de complejidad

• Mayor utilización de los elementos compartidos

Fine Grained Multi-Threading (FGMT)
• Un procesador de granularidad fina provee dos o más contextos en un

mismo chip

• Los contextos son intercambiados en un tiempo fijo y breve, usualmente

cada ciclo de reloj

• Precursores: Cray CDC 6600 (1960) y Denelcor HEP (1970)

• Justificación: Intercalar instrucciones de diferentes threads a fin de

• Enmascarar latencias de memoria
• Evitar detectar y resolver dependencias RAW entre instrucciones

• La Tera MTA (Tera Computer Company, 1998) maximiza el uso del

pipeline de acceso a memoria intercalando peticiones de diversos threads
en esa etapa
Tera MTA posee 128 registros de contexto que permiten la ejecución de
128 threads, con lo que enmascara totalmente las latencias de memoria
a tal punto que no se necesita usar caché

• Principal desventaja de esta máquina: El compilador debe esforzarse para

encontrar varios (hasta 128) threads independientes, sino se degrada el
rendimiento

Fine Grained Multi-Threading (FGMT)

Desventajas:

• El rendimiento de un thread en particular decae fuertemente respecto

de su ejecución en un procesador superescalar clásico

• Las ganancias en uso del procesador generadas por las latencias de I/O

del thread no son suficientes para compensar las demoras impuestas
por la ejecución de los otros contextos (otros threads)

Ejemplo:

En un entorno con varios threads intentando acceder a una zona de
memoria compartida, las variables compartidas permanecen mucho
tiempo bloqueadas por threads inactivos

Coarse Grained Multi-Threading
(CGMT)

Características generales:

Aproximación intermedia de multi-threading que tiene los beneficios
de FGMT pero sin la severa restricción de tiempo de contexto de esta

Primer procesador comercial: Power PC (NorthStar y Pulsar) de IBM
en 1996 y 1998

El cambio de contexto entre threads se realiza sólo cuando el thread
actual se frena por algún evento de gran latencia (pe: fallo de caché)

En lugar de frenar el pipeline, sus etapas se cargan con instrucciones
ejecutables de otro thread

Coarse Grained Multi-Threading
(CGMT)
Problemas de la aproximación:

• Penalización de cambio de contexto: En FGMT el cambio de contexto se hace

en cada ciclo, por lo tanto la etapa de fetching carga en cada nuevo ciclo la
instrucción siguiente del thread siguiente. NO hay frenado por llenado del pipe

En CGMT el cambio de contexto es asincrónico (depende de un evento externo
como un fallo de caché) por lo que, cuando ocurre (en la etapa de ejecución) las
etapas anteriores del pipeline deberian llenarse con instrucciones del nuevo
thread. HAY frenado por llenado del pipe

instr i+3
thread 1

instr n
thread 2

instr i+1
thread 1

fallo
X X X

instr i+2
thread 1

instr i

thread 1

instr i

thread 1

instr i+2
thread 1

instr i+3
thread 1

fetch

decode

reserv

execute

• Potencial inhanición: En el caso de que un thread no produzca fallos de caché,

nunca libera el procesado