pipeline Exemplo de - gec.di.uminho.ptgec.di.uminho.pt/Discip/MInf/cpd0910/SCD/RSC_2.pdf · AJProença,Sistemas de Computação e Desempenho, MInf, UMinho, 2009/10 Algumas limitações

AJProença,Sistemas de Computação e Desempenho, MInf, UMinho, 2009/10

1

Sistemasde Computaçãoe Desempenho

Mestr

ado e

m Info

rmática

2009/10

A.J.Proença

Tem

a

Revis

itando o

s S

iste

mas d

e C

om

puta

ção (2)


2

Chapter 1 —

Computer Abstractions and Technology —

2

Understanding Perform

ance

•Algorithm

–Determines number of operations executed

•Programming language, compiler, architecture

–Determine number of machine instructions executed

per operation

•Processor and memory system

–Determine how fast instructions are executed

•I/O system (including OS)

–Determines how fast I/O operations are executed


3

Análise do desempenho em Sistemas de Computação:

oportunidades para optimizar na arquitectura

Optim

ização d

o d

esem

penho (no

CP

U)

–com introdução de p

ara

lelism

o

•ao nível do processo (sistemas concorrentes/paralelos/distribuídos)

–sófio de execução (multi-threading/ -core / -chip ...)

–processo (memória partilhada/distribuída)

•ao nível da instrução (InstructionLevelParallelism)

–sónos dados (processadores vectoriais)

–paralelismo desfasado (pipeline)

–paralelismo "real" (VLIW, superescalar)

•no acesso àmemória

–paralelismo desfasado (interleaving)

–paralelismo "real" (maior largura do bus)

–paralelismo “redundante”(hierarquia de memória)

»análise d

e p

rocessadore

s d

a Inte

l


4

Paralelismo no processador

Exemplo 1

Exem

plo

de pipeline


5

Paralelismo no processador

Exemplo 2

Exem

plo

de s

upere

scala

ridade (nív

el 2)


6

A introdução de cache

na arquitectura Intel P6

Nota: "Intel P6" éa designação comum da microarquitecturade

PentiumPro, Pentium II e Pentium III,

que serviu depois de base àCore e Nehalem


7

Chapter 1 —

Computer Abstractions and Technology —

7

Inside an AMD Processor

•AMD Barcelona: 4 processor cores


8

Inside an Intel Processor

•Intel Nehalem : 4 processor cores


9

A arquitectura interna

dos processadores Intel P6 (1)

Unidades

Funcionais

Integer/

Branch

FP

Add

FP

Mult/Div

Load

Store

Instruction

Cache

Data

Cache

Fetch

Control

Instruction

Decode

Addre

ss

Instr

s.

Opera

ções

Pre

vis

ão

OK

?

Data

Data

Addr.

Addr.

General

Integer

Operation Results

Retirement

Unit

Register

File

Execution Unit

Instruction Control Unit


10

Algumas potencialidades

do Intel P6 (1)

de

4-n

íveis

de

pipeline...

para

vári

os

nív

eis

de

pipeline...


11

A arquitectura interna

dos processadores Pentium 4


12


13

Percurso crítico no pipeline de instruções:

o P6 e o Pentium 4

P6

Pentium

4


14

Níveis de pipeline

em 3 gerações de Pentium


15

O pipeline no Pentium 4:

níveis 1-5


16


níveis 6-12


17


níveis 13-17


18


níveis 18-20


19

CPU features before 2006

FIG

UR

E 4

.73 R

ecord

of In

tel and S

un M

icro

pro

cessors

in term

s o

f pip

eline c

om

ple

xity, num

ber of core

s, and

pow

er. The Pentium 4 pipeline stages do not include the commit stages. If we included them, the Pentium 4 pipelines

would be even deeper. Copyright ©2009 Elsevier, Inc. All rights reserved.


20

A brief history of x86 vector capabilities


21

Como estão a evoluir as memórias?

“The main challenge for the CPU designer

today is the average memory latency the CPU

sees. A Pentium 4 3.6 GHz with DDR-400

runs (...) faster than the base clock of the

RAM (200 MHz). (...) The result is that wait

times of 200 to 300 cycles are not uncommon

on the Pentium 4. The goal of CPU cache is to

avoid accessing RAM, but (...)”

Statement in 2004…


22

Evolução das caches nos x86,

pré2006


23

•Execução

para

lela

de v

árias

instr

uções

–2 integer(1 podeser branch)

–1 FP Add

–1 FP Multiply ouDivide

–1 load

–1 store

•Algumasinstruçõesrequerem> 1 ciclo, maspodemser encadeadas

Instr

ução

Latê

ncia

Cic

los/E

mis

são

–Load / Store

31

–Integer Multiply

41

–Integer Divide

36

36

–Double/Single FP Multiply

52

–Double/Single FP Add

31

–Double/Single FP Divide

38

38

U.

Func.

Integer/

Branch

FP

Add

FP

Mult/Div

Load

Store

Data

Cache

Data

Data

Addr.

Addr.

General

Integer

Operation Results

Execution U

nit

Algumas potencialidades

do Intel P6 (2)


24

•Traduzinstruçõesem

Operações

–Operações: designaçãodaIntel parainstruçõestipo-RISC

–instruçãotípicarequer1–3 operações

•Convertereferênciasa Registosem

Tags

–Tags: identificadorabstractoqueligao resultadode umaoperaçãocom

operandos-fontede operaçõesfuturas

Instruction

Cache

Fetch

Control

Instruction

Decode

Addre

ss

Instr

s.

Opera

tions

Retirement

Unit

Register

File

A unidade de controlo de instruções

do Intel P6

Instruction Control Unit

Papel da IC

U:

•LêinstruçõesdaInstCache

–baseadono IP +

previsãode saltos

–antecipadinamicamente(por

h/w) se salta/não_saltae

(possível) endereçode salto


25

Algumas limitações do pipeline:

dependências de dados e saltos condicionais

Ver exem

plo

nos s

lides s

eguin

tes...

incl

%edx

cmpl

%esi,%edx

jl

.L24


26

•Pro

cedim

ento

–calcula a soma de todos os elementos do vector

–guarda o resultado numa localização destino

–estruturae operaçõesdo vector definidosvia ADT

void combine4(vec_ptr v, int*dest)

{inti;

intlength = vec_length(v);

int*data = get_vec_start(v);

intsum = 0;

for (i = 0; i < length; i++)

sum += data[i];

*dest= sum;

}

Análise detalhada do exemplo:

form

a genérica e abstracta de combine

void abstract_combine4(vec_ptr v, data_t

*dest)

{inti;

intlength = vec_length(v);

data_t*data = get_vec_start(v);

data_tt = IDENT;

for (i = 0; i < length; i++)

t = t OPdata[i];

*dest= t;

}


27

•V

ers

ão

de combine4

–tipode dados: inteiro; operação: multiplicação

•Tra

dução

da

1ªitera

ção

.L24:

# Loop:

imull(%eax,%edx,4),%ecx

# t *= data[i]

incl

%edx

# i++

cmpl

%esi,%edx

# i:length

jl

.L24

# if < goto

Loop

.L24:

imull(%eax,%edx,4),%ecx

incl

%edx

cmpl

%esi,%edx

jl

.L24

load

(%eax,%edx.0,4)� ��

t.1

imullt.1, %ecx.0

� ��%ecx.1

incl

%edx.0

� ��%edx.1

cmpl

%esi, %edx.1 � ��

cc.1

jl

-taken cc.1

Conversão de instruções com registos

para operações com tags


28

•O

pera

ções

–a posiçãovertical dáumaindicação

do tempo emqueéexecutada

•umaoperaçãonãopodeiniciar-se

semosseusoperandos

–a alturatraduza latência

•O

pera

ndos

–osarcos apenassãorepresentados

paraosoperandosquesãousados

no contextodaexecution unit

cc.1

t.1

load

%ecx.1

incl

cmpl

jl

%edx.0

%edx.1

%ecx.0

imull

Tim

e

Análise visual da execução de instruções no P6:

1 iteração do ciclo de produtos em combine

load

(%eax,%edx.0,4

� ��t.1

imullt.1, %ecx.0

� ��%ecx.1

incl

%edx.0

� ��%edx.1

cmpl

%esi, %edx.1

� ��cc.1

jl

-taken cc.1


29

cc.1

t.1

load

%ecx.1

incl

cmpl

jl

%edx.0

%edx.1

%ecx.0

imullc

c.1

cc.2

%ecx.0

%edx.3

t.1

imull

%ecx.1

incl

cmpl

jl

%edx.0

i=0

load

t.2

imull

%ecx.2

incl

cmpl

jl

%edx.1

i=1

load

cc.3

t.3

imull

%ecx.3

incl

cmpl

jl

%edx.2

i=2

load

Cycle

1 2 3 4 5 6 7 8 9

10

11

12

13

14

15

cc.1

cc.2

Iteration 3

Iteration 2

Iteration 1

cc.1

cc.2

%ecx.0

%edx.3

t.1

imull

%ecx.1

incl

cmpl

jl

%edx.0

i=0

load t.1

imull

%ecx.1

incl

cmpl

jl

%edx.0

i=0

load

t.2

imull

%ecx.2

incl

cmpl

jl

%edx.1

i=1

load t.2

imull

%ecx.2

incl

cmpl

jl

%edx.1

i=1

load

cc.3

t.3

imull

%ecx.3

incl

cmpl

jl

%edx.2

i=2

load

Cycle

1 2 3 4 5 6 7 8 9

10

11

12

13

14

15

Cycle

1 2 3 4 5 6 7 8 9

10

11

12

13

14

15

cc.1

cc.2

Iteration 3

Iteration 2

Iteration 1

•A

nálise

com

recurs

os

ilim

itados

–execuçãoparalelae

encadeadade

operaçõesnaEU

–execuçãoout-of-

ordere especulativa

•D

esem

penho

–factor limitativo:

latênciadamultipl.

de inteiros

–CPE: 4.0


3 iterações do ciclo de produtos em combine


30

•A

nálise

com

recurs

os

ilim

itados

•D

esem

penho

–podecomeçarumanova iteraçãoemcadaciclode clock

–valor teóricode CPE: 1.0

–requera execuçãode 4 operaçõesc/ inteirosemparalelo

%edx.0 t.1

%ecx.i +1

incl

cmpl

jl

addl

%ecx.1

i=0

load

cc.1

%edx.0 t.1

%ecx.i +1

incl

cmpl

jl

addl

%ecx.1

i=0

load

cc.1

%edx.1 t.2

%ecx.i +1

incl

cmpl

jl

addl

%ecx.2

i=1

load

cc.2

%edx.1 t.2

%ecx.i +1

incl

cmpl

jl

addl

%ecx.2

i=1

load

cc.2

%edx.2 t.3

%ecx.i +1

incl

cmpl

jl

addl

%ecx.3

i=2

load

cc.3

%edx.2 t.3

%ecx.i +1

incl

cmpl

jl

addl

%ecx.3

i=2

load

cc.3

%edx.3 t.4

%ecx.i +1

incl

cmpl

jl

addl

%ecx.4

i=3

load

cc.4

%edx.3 t.4

%ecx.i +1

incl

cmpl

jl

addl

%ecx.4

i=3

load

cc.4

%ecx.0

%edx.4

Cycle

1 2 3 4 5 6 7

Cycle

1 2 3 4 5 6 7

Iteration 1

Iteration 2

Iteration 3

Iteration 4

4 o

ps inte

iro


4 iterações do ciclo de somas em combine


31

Iteration 4

Iteration 5

Iteration 6

Iteration 7

Iteration 8

%ecx.3

%edx.8

%edx.3 t.4

%ecx.i +1

incl

cmpl

jl

addl

%ecx.4

i=3

load

cc.4

%edx.3 t.4

%ecx.i +1

incl

cmpl

jl

addl

%ecx.4

i=3

load

cc.4

%edx.4 t.5

%ecx.i +1

incl

cmpl

jl

addl

%ecx.5

i=4

load

cc.5

%edx.4 t.5

%ecx.i +1

incl

cmpl

jl

addl

%ecx.5

i=4

load

cc.5

cc.6

%edx.7 t.8

%ecx.i +1

incl

cmpl

jl

addl

%ecx.8

i=7

load

cc.8

%edx.7 t.8

%ecx.i +1

incl

cmpl

jl

addl

%ecx.8

i=7

load

cc.8

%edx.5 t.6

incl

cmpl

jl

addl

%ecx.6

load

i=5

%edx.5 t.6

incl

cmpl

jl

addl

%ecx.6

load

i=5

6 7 8 9

10

11

12

Cycle

13

14

15

16

176 7 8 9

10

11

12

Cycle

13

14

15

16

17

18

cc.6

%edx.6 t.7

cmpl

jl

addl

%ecx.7

load

cc.7

i=6

incl

%edx.6 t.7

cmpl

jl

addl

%ecx.7

load

cc.7

i=6

incl

–apenas2 unidfuncionaisde inteiros

–algumasoperaçõestêmde ser

atrasadas, mesmoexistindooperandos

–prioridade: ordemde exec do programa

•D

esem

penho

–CPE expectável: 2.0

As iterações do ciclo de somas:

análise com recursos limitados


32

Optim

ização

4:

–juntarvárias(3)

iteraçõesnum

simples ciclo

–amortizaoverhead

dos ciclosem

váriasiterações

–terminaextras no

fim

–C

PE

: 1.3

3


{intlength = vec_length(v);

intlimit = length-2;


intsum = 0;

inti;

/* junta 3 elem'sno mesmociclo*/

for (i = 0; i < limit; i+=3) {

sum += data[i] + data[i+1]

+ data[i+2];

} /* completaosrestanteselem's

*/

for (; i < length; i++) {

sum += data[i];

} *dest= sum;

}

Técnicasde optimizaçãodependentesdamáquina:

loop unroll (1)


33

–loadspodem

encadear, umavezque

nãohádependências

–apenasum conjuntode

instruçõesde controlo

de ciclo

load (%eax,%edx.0,4) � ��

t.1a

iaddlt.1a, %ecx.0c � ��

%ecx.1a

load 4(%eax,%edx.0,4) � ��

t.1b

iaddlt.1b, %ecx.1a � ��

%ecx.1b

load 8(%eax,%edx.0,4) � ��

t.1c

iaddlt.1c, %ecx.1b � ��

%ecx.1c

iaddl$3,%edx.0 � ��

%edx.1

cmpl%esi, %edx.1 � ��

cc.1

jl-taken cc.1

Tim

e

%edx.0

%edx.1

%ecx.0c

cc.1

t.1a

%ecx.i+1

addl

cmpl

jl

addl

%ecx.1c

addl

addl

t.1b

t.1c

%ecx.1a

%ecx.1b

load

load

load


loop unroll (2)


34

i=6

cc.3

t.3a

%ecx.i +1

addl

cmpl

jl

addl

%ecx.3c

addl

addl

t.3b

t.3c

%ecx.3a

%ecx.3b

load

load

load

%ecx.2c

i=9

cc.4

t.4a

%ecx.i +1

addl

cmpl

jl

addl

%ecx.4c

addl

addl

t.4b

t.4c

%ecx.4a

%ecx.4b

load

load

load

cc.4

t.4a

%ecx.i +1

addl

cmpl

jl

addl

%ecx.4c

addl

addl

t.4b

t.4c

%ecx.4a

%ecx.4b

load

load

load

%edx.3

%edx.2

%edx.4

5 6 7 8 9

10

11

Cycle

12

13

14

155 6 7 8 9

10

11

Cycle

12

13

14

15

Iteration 3

Iteration 4

•Desempenhoestimado

–podecompletariteraçãoem3 ciclos

–deveriadarCPE de 1.0

•Desempenhomedido

–CPE: 1.33

–1 iteraçãoemcada4 ciclos


loop unroll (3)


35

–apenasmelhoranassomas de inteiros

•restantescasoshárestriçõescom a latênciadaunidade

–efeitonãoélinear com o graude unroll

•háefeitossubtisquedeterminama atribuiçãoexacta das

operações

Graude Unroll

12

34

816

Inteiro

Soma

2.00

1.50

1.33

1.50

1.25

1.06

Inteiro

Produto

4.00

fpSoma

3.00

fpProduto

5.00


loop unroll (4)

Valor do C

PEpara várias situações de loopunroll:

*+


36

•a computação…

((((((((((((1 * x0) * x1) *

x2) * x3) * x4) * x5) * x6) *

x7) * x8) * x9) * x10) * x11)

*

*

11xx00

xx11

*xx22

*xx33

*xx44

*xx55

*xx66

*xx77

*xx88

*xx99

*xx10

10

*xx11

11

…o desempenho

–N elementos, D ciclos/operação

–N*D ciclos


computaçãosequencialversus…

Com

puta

ção s

equencia

l versus

...


37

•a computação…

((((((1 * x0) * x2) * x4) *

* x6) * x8) * x10) *

((((((1 * x1) * x3) * x5) *

* x7) * x9) * x11)

*

*

11xx11

xx33

*xx55

*xx77

*xx99

*xx11

11

*

*

*

11xx00

xx22

*xx44

*xx66

*xx88

*xx10

10

…o desempenho

–N elementos, D ciclos/op

–(N/2+1)*D ciclos

–melhoriade ~2x


…versus computaçãoparalela

Com

puta

ção s

equencia

l ... versus

para

lela

!


38

Optim

ização

5:

–acumularem2

produtosdiferentes

•pode ser feito em

paralelo, se OP fôr

associativa!

–juntar no fim

–Desempenho

–C

PE

: 2.0

–melhoriade 2x

Com

puta

ção s

equencia

l ... versus

para

lela

!


loop unroll com paralelismo(1)


{intlength = vec_length(v);

intlimit = length-1;


intx0 = 1;

intx1 = 1;

inti;

/* junta 2 elem's

de cadavez*/

for (i = 0; i < limit; i+=2) {

x0 *= data[i];

x1 *= data[i+1];

} /* completaosrestanteselem's

*/

for (; i < length; i++) {

x0 *= data[i];

} *dest= x0 * x1;

}


39

–osdoisprodutosno interior

do ciclonãodependemum

do outro…

–e épossívelencadeá-los

–iterationsplitting, na literatura

load (%eax,%edx.0,4) � ��

t.1a

imullt.1a, %ecx.0 � ��

%ecx.1

load 4(%eax,%edx.0,4) � ��

t.1b

imullt.1b, %ebx.0 � ��

%ebx.1

iaddl$2,%edx.0 � ��

%edx.1

cmpl%esi, %edx.1 � ��

cc.1

jl-taken cc.1

Tim

e

%edx.1

%ecx.0

%ebx.0

cc.1

t.1a

imull

%ecx.1

addl

cmpl

jl

%edx.0

imull

%ebx.1

t.1b

load

load




40%edx.3

%ecx.0

%ebx.0

i=0

i=2

cc.1

t.1a

imull

%ecx.1

addl

cmpl

jl

%edx.0

imull

%ebx.1

t.1b

load

load

cc.1

t.1a

imull

%ecx.1

addl

cmpl

jl

%edx.0

imull

%ebx.1

t.1b

load

load

cc.2

t.2a

imull

%ecx.2

addl

cmpl

jl

%edx.1

imull

%ebx.2

t.2b

load

load

cc.2

t.2a

imull

%ecx.2

addl

cmpl

jl

%edx.1

imull

%ebx.2

t.2b

load

load

i=4

cc.3

t.3a

imull

%ecx.3

addl

cmpl

jl

%edx.2

imull

%ebx.3

t.3b

load

load

14

Cycle

1 2 3 4 5 6 7 8 9

10

11

12

13

14

15

16

Cycle

1 2 3 4 5 6 7 8 9

10

11

12

13

14

15

16

Iteration 1

Iteration 2

Iteration 3

Desempenhoestimado

–mantém-se o multiplicador

ocupadocom 2 op’s em

simultâneo

–C

PE

: 2.0




41

Inte

iro

Real (precisão simples)

Méto

do

+

* +

* Abstract -g

42.0

6

41.8

6

41.4

4

160.0

0

Abstract -O

2

31.2

5

33.2

5

31.2

5

143.0

0

Move vec_length

20.6

6

21.2

5

21.1

5

135.0

0

Acesso a

os d

ados

6.0

0

9.0

0

8.0

0

117.0

0

Acum

. em

tem

p

2.0

0

4.0

0

3.0

0

5.0

0

Unroll 4x

1.5

0

4.0

0

3.0

0

5.0

0

Unroll 16x

1.0

6

4.0

0

3.0

0

5.0

0

Unroll 2

x, para

l. 2

x

1.5

0

2.0

0

2.0

0

2.5

0

Unroll 4

x, para

l. 4

x

1.5

0

2.0

0

1.5

0

2.5

0

Unroll 8

x, para

l. 4

x

1.2

5

1.2

5

1.5

0

2.0

0

Optim

ização T

eóri

ca

1.0

0

1.0

0

1.0

0

2.0

0

Pior : Melhor

39.7

33.5

27.6

80.0

Técnicasde optimizaçãode código:

análisecomparativade combine


42

•Precisade muitosregistos!

–paraguardarsomas/produtos

–apenas6 registos(p/ inteiros) disponíveisno IA32

•tbusadoscomoapontadores, controlode ciclos, …

–8 registosde fp

–quandoosregistossãoinsuficientes, temp's vãoparaa stack

•eliminaganhosde desempenho

(verassemblyemprodutointeirocom unroll8x e paralelismo8x)

–re-nomeaçãode registosnãochega

•nãoépossívelreferenciarmaisoperandosqueaquelesqueo

instruction setpermite

•…principal inconvenientedo instruction setdo IA32

•Operaçõesa paralelizar têmde ser associativas

–a soma e multiplde fpnum computadornãoéassociativa!

•(3.14+1e20)-1e20 nemsempreéiguala 3.14+(1e20-1e20)…

Optimizaçãode código:

limitaçõesdo paralelismoaoníveldainstrução


43

•combine

–produto de inteiros

–unroll8x e paralelismo8x

–7 variáveislocais

partilham1 registo(%edi)

•observarosacessosà

stack

•melhoria desempenho é

comprometida...

•registerspillingna

literatura

.L165: imull(%eax),%ecx

movl-4(%ebp),%edi

imull4(%eax),%edi

movl%edi,-4(%ebp)

movl-8(%ebp),%edi

imull8(%eax),%edi

movl%edi,-8(%ebp)

movl-12(%ebp),%edi

imull12(%eax),%edi

movl%edi,-12(%ebp)

movl-16(%ebp),%edi

imull16(%eax),%edi

movl%edi,-16(%ebp)

…addl$32,%eax

addl$8,%edx

cmpl-32(%ebp),%edx

jl.L165

Limitaçõesdo paralelismo:

a insuficiênciade registos


44

Trabalhoparacasa

•Identificartodasas geraçõesde processadoresAMD e

Intel desdeo Hammer e Prescott atéaoIstanbul e

Nehalem-EX, e caracterizá-lasemtabela:

–níveisde pipeline, threads simultâneas, graude

superescalaridade, suportevectorial, # cores,

tipos/velocidadesde ligaçãoc/ exterior,…

–níveis, dimensãoe tipode organizaçãode caches,

largurade bandano acessoàRAM, …

•Identificaras geraçõesde CPUs nosclusters HPC/DI

•Fazerum levantamentodas técnicasde mediçãode

desempenhodo par processador-memória

Documents

pipeline Exemplo de - gec.di.uminho.ptgec.di.uminho.pt/Discip/MInf/cpd0910/SCD/RSC_2.pdf · AJProença,Sistemas de Computação e Desempenho, MInf, UMinho, 2009/10 Algumas limitações