12/07/2015

1

Arquitetura e Organização de

Computadores 2

Paralelismo em Nível de Dados

Arquiteturas Vetoriais, Extensões SIMD e GPUs

Taxonomia de Flynn - fluxo-de-instruções X fluxo-de-dados

2

SISD – Single Instruction, Single Data

Máquinas clássicas não paralelas da arquitetura von Neumann.

SIMD – Single Instruction, Multiple Data

Um único fluxo de instrução e múltiplos fluxos de dados, execução síncrona de instrução para todos os dados.

MISD – Multiple Instruction, Single Data

Seria o caso de um pipeline de processadores aonde os dados vão sendo processados e passados para o processador seguinte.

Existência duvidosa processadores sistólicos?

MIMD – Multiple Instruction, Multiple Data

é o caso dos multiprocessadores, onde várias instruções podem ser executadas ao mesmo tempo em unidades de processamento diferentes controladas por unidades de controle independentes (uma para cada unidade de processamento).

12/07/2015

2

Sumário:

3

Explorando o Paralelismo em Nível de Dados:

Introdução – Paralelismo em SIMD

Arquiteturas Vetoriais

Multimedia SIMD instruction set extensions

MMX (Multimedia Extensions), SSEx (Streaming SIMD Extensions) e AVX

(AdvancedVector Extensions)

Graphics Processor Units - GPUs

Taxonomia do Paralelismo

4

Horizontal Vertical

ILP Superscalar Pipelined

DLP SIMD / SIMT Vector / temporal SIMT

TLP Multicore SMTInterleaved / switch-on-event

multithreading

ILP (instruction Level Parallelism) - DLP (Data Level Parallelism) - TLP (Thread Level Parallelism)

12/07/2015

3

Introdução

5

Arquiteturas SIMD podem explorar o paralelismo em nível de dados em:

Computação científica orientada-a-matrizes

Aplicações multimídia orientados a vídeo e áudio.

Arquiteturas SIMD possui maior eficiência energética do que MIMD.

Necessita somente buscar (fetch) uma instrução por operação em dados.

A eficiência energética torna a arquitetura SIMD atraente para dispositivos móveis pessoais (PMD).

Arquiteturas SIMD possibilitam ao programador continuar a pensar sequencialmente e, ainda assim, atinge um ganho de velocidade ao realizar operações de dados paralelas.

Figure 4.1 Potential speedup via parallelism from MIMD, SIMD, and both MIMD and SIMD over time for x86

computers. This figure assumes that two cores per chip for MIMD will be added every two years and the number of

operations for SIMD will double every four years.

6

12/07/2015

4

Arquiteturas Vetoriais

7

Alguns processadores incluem unidades dedicadas à execução de operações sobre vetores de forma mais eficiente.

Uma operação típica sobre vetores realiza uma adição de dois vetores de 64 elementos, em ponto flutuante. A operação é equivalente a uma iteração sobre os elementos do vetor, efetuando uma multiplicação por iteração.

Vantagens das operações vetoriais1. o cálculo de um resultado é independente do anterior, possibilitando a

utilização de pipeline com bastante estágios, sem gerar anomalias de dados.

2. uma só instrução especifica um grande número de operações, equivalente à execução de um ciclo, o que reduz a quantidade de buscas de instruções

3. os acessos à memória para carregar os elementos do vetor em registradores podem tirar partido da optimização da latência da memória, amortizando o custo elevado dos acessos à memória.

4. Os hazards de controle são reduzidas porque os ciclos são transformados numa só instrução.

Arquitetura Vetorial VMIPS

Baseado em Cray-1

Registradores Vetoriais Cada registrador vetorial mantém 64 elementos de 64 bits/elemento.

O arquivo de registradores possui 16 portas de leitura e 8 portas de escrita.

Unidades Funcionais Vetoriais Totalmente pipelined

Hazards de dados e controle são detectados.

Unidade Load-StoreVetorial Totalmente pipelined

Uma palavra por ciclo de clock após a latência incial.

Conjunto de registradores escalares 32 registradores de propósito geral

32 registradores de ponto flutuante (FP)

8

12/07/2015

5

Figure 4.2 The basic structure of a vector architecture, VMIPS. This processor has a scalar architecture just like MIPS. There are also

eight 64-element vector registers, and all the functional units are vector functional units. This chapter defines special vector

instructions for both arithmetic and memory accesses. The figure shows vector units for logical and integer operations so that

VMIPS looks like a standard vector processor that usually includes these units; however, we will not be discussing these units. The

vector and scalar registers have a significant number of read and write ports to allow multiple simultaneous vector operations. A

set of crossbar switches (thick gray lines) connects these ports to the inputs and outputs of the vector functional units.

9

VMIPS ISA ADDVV.D, ADDVS.D SUBVV.D, SUBVS.D, SUBSV.D MULVV.D, MULVS.D DIVVV.D, DIVSV.D, DIVVS.D LV, SV LVWS, SVWS (With Stride) V1 <- M[R1+i*R2] LVI V1, (R1+V2)

V1[i] = M[R1 + V2[i]] SVI V1, (R1+V2) CVI V1,R1

V1[i] = i*R1 SxxVV.D

Xx EQ, NE, GE, GT, LE, LT Set the flags in mask register VM

SxxVS.D

10

12/07/2015

6

VMIPS ISA

Como os processadores vetoriais funcionam? Um processador vetorial pode ser melhor entendido

examinando-se um loop vetorial no VMIPS.

Exemplos:

LV V1, X(r1): load vector

for (I=0;I<MVL;I++) ld.d v1[I], X+I(r1);

SV V1, X(r1): store vector

for (I=0;I<MVL;I++) st.d v1[I], X+I(r1);

addvv.d v1,v2,v3: add two vectors

for (I=0;I<MVL;I++) add.d v1[I],v2[I],v3[I];

addvs v1,f2,v3: add vector to scalar

for (I=0;I<MVL;I++) add.d v1[I],f2,v3[I];

11

Exemplo SAXPY ou DAXPY:

12

Y = a X + Y

Y, X - vetores de 64 elementos

a - valor escalar

Unidade de processamento vetorial e 8 registradores vetoriais que

guardam 64 elementos FP de 64 bits

MIPS MIPS vetorial

LD F0, aADDI R4, Rx, 512 # último elem.L1: LD F2, 0(Rx) # lê X(i)MULTDF2, F0, F2 # a X(i)LD F4, 0(Ry) # lê Y(i)ADDD F4, F2, F4 # a.X(i)+Y(i)SD F4, 0(Ry) # guarda Y(i)ADDI Rx, Rx, 8 # inc. índ. XADDI Ry, Ry, 8 # inc. índ. YSUB R20, R4, Rx # calc. limiteBEQZ R20, L1

LD F0, aLV V1, 0(Rx) # lê vetor XMULTSV V2, F0, V1 # a XLV V2, 0(Ry) # lê vetor YADDV V4, V2, V3 # addSV V4, 0(Ry) # guarda Y

12/07/2015

7

Tempo de execução vetorial

O tempo de execução depende de três fatores: O tamanho dos componentes vetorial

Os conflitos estruturais

As dependências de dados

As unidades funcionais VMIPS processam um elemento por ciclo de clock O tempo de execução é aproximadamente o tamanho do

vetor

Comboio (Convey) Conjunto de instruções vetoriais que podem potencialmente

executarem juntas

13

Chimes

Sequencias com dependências RAW (read-after-write) podem ser colocadas no mesmo comboio através do mecanismo de encadeamento (chaining )

Chaining O encadeamento permite que uma operação vetorial comece assim

que os elementos individuais do operando-fonte desse vetor fiquem disponíveis: os resultados da primeira unidade funcional na cadeia são adiantados

para a segunda unidade funcional.

Chime Unidade de tempo necessária para executar um comboio.

Uma sequencia vetorial que consome m comboios é executada em mchimes.

Para um vetor de tamanho n, requer m x n ciclos de clock.

14

12/07/2015

8

Vector Chaining

15

Vector Chaining

16

12/07/2015

9

Exemplo

Mostre como a sequência de código a seguir é disposta em comboios, considerando uma única cópia de cada unidade funcional vetorial.LV V1,Rx ;load vector X

MULVS.D V2,V1,F0 ;vector-scalar multiply

LV V3,Ry ;load vector Y

ADDVV.D V4,V2,V3 ;add two vectors

SV Ry,V4 ;store the sum

De quantos chimes essa sequência vetorial precisa? Ciclos por FLOP?

Comboios (convoys):

1 LV MULVS.D

2 LV ADDVV.D

3 SV

3 chimes, 2 FP ops per result, cycles per FLOP = 1.5

For 64 element vectors, requires 64 x 3 = 192 clock cycles

17

Desafios A fonte mais importante de overhead, ignorada pelo modelo de chime, é o de

tempo e início do vetor.

O tempo de início advém da latência de pipeline da operação vetorial e é determinado pela profundidade do pipeline.

VMIPS usa as mesma profundidade de pipeline do Cray-1:

Floating-point add => 6 clock cycles

Floating-point multiply => 7 clock cycles

Floating-point divide => 20 clock cycles

Vector load => 12 clock cycles

Otimizações que melhoram o desempenho: > 1 element per clock cycle

Non-64 wide vectors

IF statements in vector code

Memory system optimizations to support vector processors

Multiple dimensional matrices

Sparse matrices

Programming a vector computer

18

12/07/2015

10

Múltiplas Pistas - Multiple Lanes O n-ésimo elemento do registrador vetorial A participa das operaçãoes

(hardwired) com o n-ésimo elemento do registrador vetorial B

A unidade funcional vetorial pode ser estruturada com múltiplas pistas (lanes)

paralelas.

19

Como tratar os casos em que o tamanho dos vetores

é diferente do tamanho dos registradores?

O tamanho de determinada operação vetorial normalmente é desconhecido durante a

compilação.

A solução para esse problema é disponibilizar um registrador que controle o tamanho de

qualquer operação vetorial (Vector Length Register - VLR)

O valor de VLR não pode ser maior do que o tamanho máximo dos registradores vetoriais

(MVL).

Empregar a técnica strip mining para vetores maiores do que MVL:

low = 0;

VL = (n % MVL); /*find odd-size piece using modulo op % */

for (j = 0; j <= (n/MVL); j=j+1) { /*outer loop*/

for (i = low; i < (low+VL); i=i+1) /*runs for length VL*/

Y[i] = a * X[i] + Y[i] ; /*main operation*/

low = low + VL; /*start of next vector*/

VL = MVL; /*reset the length to maximum vector length*/

}

20

12/07/2015

11

Registradores de máscara vetorial

Lidando com declarações IF el loops vetoriais:

for (i = 0; i < 64; i=i+1)

if (X[i] != 0)

X[i] = X[i] – Y[i];

A extensão que normalmente é utilizada é o controle de máscara vetorial.

Utiliza um registrador de máscara (mask register) para “desabilitar” elementos:

LV V1,Rx ;load vector X into V1

LV V2,Ry ;load vector Y

L.D F0,#0 ;load FP zero into F0

SNEVS.D V1,F0 ;sets VM(i) to 1 if V1(i)!=F0

SUBVV.D V1,V1,V2 ;subtract under vector mask

SV Rx,V1 ;store the result in X

A taxa de GFLOPS cai quando máscaras são utilizadas!

21

Bancos de Memória

O Sistema de memória deve ser projetado para suportar

grande largura de banda (high bandwidth) para as operações de

carregamento-armazenamento vetorial (vector loads and stores)

Espalhar o acesso através de múltiplos bancos

Control bank addresses independently

Load or store non sequential words

Support multiple vector processors sharing the same memory

Exemplo:

32 processors, each generating 4 loads and 2 stores/cycle

Processor cycle time is 2.167 ns, SRAM cycle time is 15 ns

How many memory banks needed?

22

12/07/2015

12

Manipulando arrays multidimensionais:

Stride

Considere:

for (i = 0; i < 100; i=i+1)

for (j = 0; j < 100; j=j+1) {

A[i][j] = 0.0;

for (k = 0; k < 100; k=k+1)

A[i][j] = A[i][j] + B[i][k] * D[k][j];

}

Must vectorize multiplication of rows of B with columns of D

Use non-unit stride

Bank conflict (stall) occurs when the same bank is hit faster than bank busy

time:

#banks / LCM(stride,#banks) < bank busy time

23

Lidando com matrizes dispersas:

Scatter-Gather

Considere:

for (i = 0; i < n; i=i+1)

A[K[i]] = A[K[i]] + C[M[i]];

Utilizar vetor de índice (index vector):

LV Vk, Rk ;load K

LVI Va, (Ra+Vk) ;load A[K[]]

LV Vm, Rm ;load M

LVI Vc, (Rc+Vm) ;load C[M[]]

ADDVV.D Va, Va, Vc ;add them

SVI (Ra+Vk), Va ;store A[K[]]

24

12/07/2015

13

Programando Arquiteturas Vetoriais

Compilers can provide feedback to programmers

Programmers can provide hints to compiler

25

Bibliografia

26

David Patterson e John Hennessy,

Arquitetura e Organização de

Computadores – uma abordagem

quantitativa, 5ª Edição, ed. Campus.