PDF de programación - Tema 4 - Paralelismo a nivel de datos: arquitectura vectorial, instrucciones SIMD para multimedia, GPUs

Arquitectura de Computadores

TEMA 4

Paralelismo a nivel de datos: arquitectura vectorial,

instrucciones SIMD para multimedia, GPUs

Curso 2015-2016

Contenidos

 Introducción
 Arquitectura vectorial

o Repertorio de instrucciones vectoriales
o Tiempo de ejecución, medidas de rendimiento
o Procesamiento selectivo de elementos
o Ejemplos

 Instrucciones SIMD para procesamiento multimedia
 Unidades para procesamiento gráfico (GPUs)

o Modelo de programación a alto nivel: CUDA
o Instrucciones PTX
o Arquitectura del elemento de proceso

 Paralelismo a nivel bucle: vectorización

o Detección de dependencias

 Bibliografía

o Cap 4 y Apéndice G de [HePa12]

(Nota.- En la elaboración de este material se han utilizado algunos contenidos del
curso CS152 de la UC Berkeley. También se han utilizado figuras de HePa12)

AC — Tema 4

Curso 2015-16

2

Introducción

 SIMD (Single Instruction Multiple Data).

o Una operación (codificada como una sola instrucción de

LM) se ejecuta sobre un conjunto de datos (en
contraposición a SISD).

o Ejemplo:

 En lenguaje matemático: V3 = V2 + V1
 En LAN: for (i = 0; i<N; i++)

V3(i) = V2(i) + V1(i);

 En LM: ADDV V3,V2,V1

 Arquitectura SIMD: puede explotar una cantidad

importante de paralelismo de datos en

o Aplicaciones de ciencia/ingeniería con abundante cálculo

matricial (ámbito tradicional)

o Nuevas aplicaciones: gráficos, visión artificial,

comprensión de voz, ...

AC — Tema 4

Curso 2015-16

3

Introducción

 Predicción de Speedup potencial esperable mediante paralelismos

SIMD, MIMD y la combinación de ambos [HePa12]

(Op/cycle)

(No. of cores)

8

6

4

2

x2

4 años

 Incrementos esperados

en arquitecturas ‘x86
o Núcleos : +2 cada 2 años
o Anchura  Operaciones
de 32/64 bits por ciclo
de reloj: x2 cada 4 años

 Proyección 2020: En

aplicaciones con TLP y
DLP  Speedup ~ x10
(Comp 2021 vs. 2013)

AC — Tema 4

Curso 2015-16

4

Introducción

 Eficiencia energética de SIMD: puede ser ventajosa

frente a MIMD

o Sólo es preciso hacer un “fetch” para operar sobre varios

datos.

o Ahorro de energía atractivo en dispositivos portátiles

 En SIMD el programador sigue “pensando”

básicamente en un flujo secuencial de instrucciones.

 Soporte arquitectónico para explotar paralelismo

SIMD

o Arquitectura vectorial
o Extensiones SIMD (extensiones multimedia)
o Graphics Processor Units (GPUs)

AC — Tema 4

Curso 2015-16

5

Arquitectura vectorial

 Ideas básicas

o Leer conjuntos de datos sobre “registros vectoriales”
o Operar sobre el contenido de estos registros
o Almacenar los resultados finales en memoria

 Usar los registros vectoriales para ocultar la latencia de

memoria

 Características de las operaciones vectoriales

o Secuencias de cálculos independientes  Ausencia de

riesgos

o Alto contenido semántico

 Una instrucción  Muchas operaciones

o Patrón de accesos a memoria conocido
o Explotación eficiente de memoria entrelazada
o Disminución de instrucciones de salto (un bucle completo

puede transformarse en una instrucción)

 Reducción conflictos de control

AC — Tema 4

Curso 2015-16

6

Arquitectura vectorial

 En el principio... Seymour Cray – CDC 6600 (1963)

 No es una arquitectura vectorial, pero...

o Muy segmentada, con palabra de 60 bits
o Mp de 128 Kword con 32 bancos
o

10 Fus (paralelas, no segmentadas)

 PF: sumador, 2 mult, divisor

o Control cableado
o

Planificación dinámica de instrucciones
(scoreboard)
10 procesadores de E/S

o
o Clock 10 MHz

 Muy rápido para la época
 Suma FP en 4 ciclos

o

>400,000 transistores, 750 sq. ft. (~70 m2),
5 tons, 150 KW, refrigeración freon

o Máquina más rápida del mundo durante 5

años (hasta el 7600)

o Vendidas >100 (a $7-10M c.u.)

AC — Tema 4

Curso 2015-16

7

Arquitectura vectorial

 En el principio... Seymour Cray – CDC 6600 (1963)

 Thomas Watson Jr., IBM CEO, August 1963:

“Last week, Control Data ... announced the 6600 system. I
understand that in the laboratory developing the system
there are only 34 people including the janitor. Of these, 14
are engineers and 4 are programmers... Contrasting this
modest effort with our vast development activities, I fail to
understand why we have lost our industry leadership position
by letting someone else offer the world's most powerful
computer.”

 To which Cray replied: “It seems like Mr. Watson

has answered his own question.”

AC — Tema 4

Curso 2015-16

8

Arquitectura vectorial

El Cray-1 (1976)
 Unidad escalar

o Arquitectura Load/Store

Extensión Vectorial

o Registros Vectoriales
o Instrucciones Vectoriales

Implementación

o Control cableado
o UF muy segmentadas
o Memoria entrelazada
o Sin cache de datos
o Sin memoria virtual

AC — Tema 4

Curso 2015-16

9

Arquitectura vectorial

 Visión global del Cray-1

T ciclo banco memoria: 50 ns, T ciclo procesador: 12,5 ns (80 Mhz)

AC — Tema 4

Curso 2015-16

10

Arquitectura vectorial

 Estructura de un procesador vectorial: VMIPS

UFs segmentadas:
• Add 6 etapas
• Mul 7 etapas
• Div 20 etapas

Funcionalmente
equivalente a un pipe: un
dato por ciclo, después de
latencia inicial (12 ciclos).

8 registros vectoriales
1 reg = 64 elementos
1 elemento = 64 bits
16 read, 8 write ports

AC — Tema 4

Curso 2015-16

11

Arquitectura vectorial: repertorio VMIPS (1)

 Operaciones vectoriales aritméticas sobre registros
 Instrucciones especiales de carga/almac de vectores

(LV,SV)

 Modos de direccionamiento especiales para vectores no

contiguos. Ejemplos

o LVWS: Load Vector With Stride. Carga elementos equiespaciados

a una cierta distancia

o LVI: Load Vector using Index. El contenido de un registro

vectorial indica las posiciones de los elementos a cargar.

 Registros especiales de longitud vectorial (VLR) y máscara

(VM)

o Reg VLR: Indica la longitud de los vectores a procesar ( 64)
o Reg VM: Registro de 64 bits. Para las posiciones con VM a cero, la

operación no se ejecuta.

 Ejecución selectiva de operaciones sobre componentes

AC — Tema 4

Curso 2015-16

12

Arquitectura vectorial: repertorio VMIPS (2)

Instruction Operands

Function

ADDVV.D
ADDVS.D

SUBVV.D
SUBVS.D
SUBSV.D

MULVV.D
MULVS.D

DIVVV.D
DIVVS.D
DIVSV.D

LV

SV

LVWS

SVWS

LVI

SVI

V1,V2,V3
V1,V2,F0

V1,V2,V3
V1,V2,F0
V1,F0,V2

V1,V2,V3
V1,V2,F0

V1,V2,V3
V1,V2,F0
V1,F0,V2

V1,R1

R1, V1

Add elements of V2 and V3, then put each result in V1.
Add F0 to each element of V2, then put each result in V1.

Subtract elements of V3 from V2, then put each result in V1.
Subtract F0 from elements of V2, then put each result in V1.
Subtract elements of V2 from F0, then put each result in V1.

Multiply elements V2 and V3, then put each result in V1.
Multiply each element of V2 by F0, then put each result in V1.

Divide elements of V2 by V3, then put each result in V1.
Divide elements of V2 by F0, then put each result in V1.
Divide F0 by elements of V2, then put each result in V1.

Load vector register V1 from memory starting at address R1.

Store vector register V1 into memory starting at address R1.

V1,(R1,R2)

Load V1 from address at R1 with stride in R2 (i.e .. R1 + i x R2).

(R1,R2),V1

Store V1 to address at R1 with stride in R2 (i.e .. R1 + i x R2).

V1,(R1+V2)

Load V1 with vector whose elements are at R1 + V2(i) (i.e., V2 is an index).

(R1+V2) ,V1 Store V1 to vector whose elements are at R1 + V2(i) (i.e., V2 is an index).

AC — Tema 4

Curso 2015-16

13

Arquitectura vectorial: repertorio VMIPS (3)

Instruction Operands

Function

CVI

V1,R1

S--VV.D
S--VS.D

V1, V2
V1, F0

Create an index vector by storing the values 0, 1 x R1, 2 x R1, ... ,63 x R1
into V1.
Compare the elements (EQ, NE, GT, LT, GE, LE) in V1 and V2. If condition
is true, put a 1 in the corresponding bit vector: otherwise put 0. Put
resulting bit vector in vector mask register (VM). The instruction S--VS.D
performs the same compare but using a scalar value as one operand

POP

CVM

MTC1
MFC1

MVTM
MVFM

R1,VM

Count the 1s in vector-mask register VM and store count in R1.

VLR,R1
R1,VLR

VM,F0
F0,VM

Set the vector-mask register to all 1s.

Move contents of R1 to vector-length register VL.
Move the contents of vector-length register VL to R1.

Move contents of F0 to vector-mask register VM.
Move contents of vector-mask register VM to F0.

AC — Tema 4

Curso 2015-16

14

Código escalar vs. Código vectorial

 Y = a*X + Y (vectores de 64 elementos)

o Versión escalar
L.D

F0, a

; load scalar a

DADDIU

R4,Rx,#512

; last address to load

Loop:

L.D

MUL.D

L.D

ADD.D

S.D

DADDIU

DADDIU

DSUBU

BNEZ
o Versión vectorial
L.D

LV

F2, 0(Rx)

F2, F2, F0

F4, 0(Ry)

F4, F4, F2

F4, 0(Ry)

Rx, Rx, #8

Ry, Ry, #8

; Load X[i]

; A x X[i]

; Load Y[i]

; A x X[i] + Y[i]

; Store Y[i]

; increment index X

; increment index Y

R20, R4, Rx

; loop exhausted?

R20, Loop

F0, a

V1, Rx

; load scalar a

; Load vector X

MULVS.D

V2, V1, F0

; Vector-scalar multiply

LV

V3, Ry

; Load vector Y

ADDVV.D

V4, V2, V3

; Vector addition

SV

V4, Ry

; Store result Y

o Instrucciones ejecutadas: ~ 580 vs. 6 !!

AC — Tema 4

Curso 2015-16

15

Tiempo de ejecución

 Dependiente básicamente de tres factores

o Longitud de los vectores operandos
o Riesgos estructurales: las UF necesarias están ocupadas, no

hay puertos del BR disponibles

o Dependencias de datos

 Velocidad de procesamiento

o Las FUs del VMIPS consumen (y producen) un elemento por

ciclo de reloj

o El tiempo de ejecución de una operación vectorial es

aproximadamente igual a la longitud del vector

 Convoy

o Se denomina así a un conjunto de (una o varias) instrucciones

vectoriales que potencialmente pueden ejecutarse juntas
(ausencia de riesgos estructurales). Pueden tener riesgos
LDE.

 Paso (chime)

o Unidad de tiempo para ejecutar un convoy
o m convoyes se ejecutan en m pasos
o Para vectores de longitud n, ejecutar m convoyes requiere

(aprox.) mxn ciclos de relo