Multiprocessadores e Paralelismo nível de Thread

Multiprocessadores e Paralelismo nível de Thread

Roteiro da Aula

• Revisando o problema coerência• Protocolo de coerência para memória baseado

em Snooping• Protocolo de coerência baseado em diretórios

– Como funciona• Implementando protocolo baseado em diretórios

– Tipos de mensagens na rede– Mudanças do estado do bloco de cache e no diretório

• Sincronização de processos– Problema em processadores DSM– Solução para processadores DSM

• Comparação uniprocessadores vs. multiprocessadores

Coerência• Só uma pessoa pode falar no

microfone por vez

• Toda modificação em conta deve ser comunicada entre os funcionários através do alto falante

• Após modificações cópias devem ser inutilizadas

Protocolo Snooping de Coerência de Cache

StateTagData

I/O devicesMem

P1

$

Bus snoop

$

Pn

Cache-memorytransaction

• Controladores de Cache “snoops” todas as transações no barramento– Transações relevantes : envolvem bloco que a cache possui– Realiza ação para garantir coerência

• invalida, atualiza, ou fornece valor– Atualiza estado de compartilhamento do bloco de cache

Protocolo Snooping de Coerência de Cache

StateTagData

I/O devicesMem

P1

$

Bus snoop

$

Pn

Cache-memorytransaction

• Problemas:– Aumento no número de processadores

• Mais acessos à memória• Congestionamento na utilização do barramento

– Aumento no número de faltas devido à invalidação por compartilhamento

7

Memória Distribuída

• Cada nó de processamento inclui cache e memória local

• Comunicação entre nós: Rede de Interconexão

C - Cache

M - Memory

IO - Input/Output

...

P0

M

C

IO

Interconnection Network

P1

M

C

IO

Pn

M

C

IO

8

Memória Distribuída• Pro: Abordagem eficaz para um grande número de

processadores• Pro: reduz tempo de acesso à memória local• Con: Comunicação bem mais complexa

C - Cache

M - Memory

IO - Input/Output

...

P0

M

C

IO


P1

M

C

IO

Pn

M

C

IO

Modelos de Comunicação vs. Modelo de Memória

1. Comunicação através de endereços compartilhados (via loads e stores): multiprocessadores de memória compartilhada

• Memória Centralizada (Symmetric shared memory - SMPs)

• Memória Distribuída

2. Comunicação explícita através de passagem de mensagens entre processadores

• Memória Distribuída

Comunicação por Variável Compartilhada

• As memórias fisicamente separadas são endereçadas como Espaço Compartilhado Logicamente– As memórias locais podem ser acessadas por

qualquer processador

• Estes multiprocessadores são denominados Processadores DSM (distributed shared memory)

Como garantir Coerência?

• Cada bloco de memória tem informação de compartilhamento armazenada em um componente chamado diretório

• O que faz o diretório?• Tem informação de onde estão as cópias e do

estado de cada cópia• Manda informação para as caches em caso de

escritas• Faz a transferência de informações de

memória requisitada entre nós de processamento

Coerência:Diretório

• Acessos às pastas somente através do diretório

• Toda modificação em qualquer cópia deve ser comunicada ao diretório

• Diretório comunica a necessidade de inutilização

• Diretório envia cópia mais atualizada

Protocolo baseado em Diretório


Directory

Local Memory

Cache

CPU 0

Directory

Local Memory

Cache

CPU 1

Directory

Local Memory

Cache

CPU 2


CPU 0 CPU 1 CPU 2

7X

Caches

Memories

Directories X U 0 0 0

Bit Vector

Protocolo baseado em Diretório

CPU 0 lê X


CPU 0 CPU 1 CPU 2

7X

Caches

Memories

Directories X U 0 0 0

Read Miss

CPU 0 lê X


CPU 0 CPU 1 CPU 2

7X

Caches

Memories

Directories X S 1 0 0

CPU 0 lê X


CPU 0 CPU 1 CPU 2

7X

Caches

Memories


7X

CPU 2 lê X


CPU 0 CPU 1 CPU 2

7X

Caches

Memories


7X

Read Miss

CPU 2 lê X


CPU 0 CPU 1 CPU 2

7X

Caches

Memories


7X

CPU 2 lê X


CPU 0 CPU 1 CPU 2

7X

Caches

Memories


7X 7X

CPU 0 escreve 6 em X


CPU 0 CPU 1 CPU 2

7X

Caches

Memories


7X 7X

Write Miss



CPU 0 CPU 1 CPU 2

7X

Caches

Memories


7X 7X

Invalidate



CPU 0 CPU 1 CPU 2

7X

Caches

Memories

Directories X E 1 0 0

6X

CPU 1 lê X


CPU 0 CPU 1 CPU 2

7X

Caches

Memories


6X

Read Miss

CPU 1 lê X


CPU 0 CPU 1 CPU 2

7X

Caches

Memories


6X

Switch to Shared

CPU 1 lê X


CPU 0 CPU 1 CPU 2

6X

Caches

Memories


6X

CPU 1 lê X


CPU 0 CPU 1 CPU 2

6X

Caches

Memories


6X 6X



CPU 0 CPU 1 CPU 2

6X

Caches

Memories


6X 6X

Write Miss



CPU 0 CPU 1 CPU 2

6X

Caches

Memories


6X 6X

Invalidate

CPU 2 escreve 5 em X(Write back)


CPU 0 CPU 1 CPU 2

6X

Caches

Memories


5X



CPU 0 CPU 1 CPU 2

6X

Caches

Memories


5X

Write Miss



CPU 0 CPU 1 CPU 2

6X

Caches

Memories


Take Away

5X



CPU 0 CPU 1 CPU 2

5X

Caches

Memories


5X



CPU 0 CPU 1 CPU 2

5X

Caches

Memories




CPU 0 CPU 1 CPU 2

5X

Caches

Memories


5X



CPU 0 CPU 1 CPU 2

5X

Caches

Memories


4X

Diretório

• k processadores: k bits

• Cada bloco de memória: k presence-bits, 1 dirty-bit

• Cada bloco na cache: 1 valid bit, e 1 dirty (owner) bit

• ••

P P

Cache Cache

Memory Directory

presence bits dirty bit


Operação Básica de Diretório

P1 Pn

CA

$

Scalable Interconnection network

CA

$…MemoryDirectory MemoryDirectory

• ••

Directory


• N processadores: N bits

• Cada bloco de memória: N presence-bits, 1 dirty-bit



• k processadores. • Cada bloco de cache na memória:

k presence-bits, 1 dirty-bit• Cada bloco na cache:

1 valid bit, e 1 dirty (owner) bit

• Falta na Leitura da memória pelo processador i:

• Se dirty-bit está OFF então • leitura da memória;• atualiza p[i] para ON;

• Se dirty-bit está ON então • acessa linha de cache do processador owner (na cache: shared); • atualiza memória; • faz dirty-bit igual a OFF; • faz p[i] igual a ON;

• fornece dado para i

• ••

P P

Cache Cache

Memory Directory




• k processadores. • Cada bloco de cache na memória:

k presence-bits, 1 dirty-bit• Cada bloco na cache:

1 valid bit, e 1 dirty (owner) bit

• Falta devido a Escrita na memória pelo processador i:

• Se dirty-bit igual a OFF então • fornece dado para i; • envia invalidations para todas as caches que tem cópia do bloco; • faz dirty-bit igual a ON; • faz p[i] igual a ON;

• ••

P P

Cache Cache

Memory Directory



Protocolo de Diretório

• Estados dos blocos de memória : Três estados– Shared: ≥ 1 processador tem dado, memória

atualizada– Uncached: nenhum nó (processador e cache) tem o

endereço; não é válido em nenhuma cache.– Exclusive: 1 processador (owner) tem o dado;

memória desatualizada.• Princípios básicos:

– Escrita em dado non-exclusive => write miss

– Processador fica esperando até que todos invalidates tenham sido enviados e confirmados

Protocolo de Diretório

• Não tem barramento para broadcast:– Todas as mensagens devem ter o recebimento

confirmado• Cada mensagem pode envolver até 3

processadores – Local node onde a requisição origina– Home node onde reside o endereço de memória – Remote node tem uma cópia do bloco de cache em

estado exclusive ou shared• Composição da mensagem:

– P = processor number, A = address

Estados dos Blocos de Cache

• Para cada bloco de cache em um sistema baseado em diretório:– Estados idênticos ao snoopy:

• Invalid• Shared• Exclusive

– Transições causadas por:• read misses• write misses• Invalidates• busca de dado (fetch)

Estados dos Blocos de Cache

• Controlador envia mensagens de read miss e write miss para o diretório do processador que tem o dado na memória local

CPU Read hit

Estados da Cache (Write Back) CPU• Estados da cache

para requisições da CPU para cada bloco de cache

• Blocos que não estão na cache não são válidos

InvalidShared

(read/only)

Exclusive(read/write)

CPU Read

CPU Write

Send read miss msg

Send Write Miss msg

CPU Writ

e m

iss

Send W

rite

Mis

s m

sg

CPU Write Miss Write back cache block

Send write miss msg

CPU read hitCPU write hit

Cache BlockState

CPU read

mis

s

Writ

e ba

ck b

lock,

send

read

miss

msg

CPU Writ

e hit

Sen

d inva

lidat

e m

sg

Estados da Cache (Write Back) Diretório

• Estados da cache para requisições do Directory para cada cache block

Invalid

Shared(read/only)


Write BackBlock; (abortmemory access)

Fetch invalidate for this block

Read miss for this block

Invalidate msg


Fetch

, dat

a writ

e ba

ck

Send read miss

Estados da Cache (Write Back) CPU

Estados da cache para requisições da CPU para cada cache block e para requisições do directiory para cada cache block

InvalidShared

(read/only)


CPU Read

CPU Write

CPU Read hit

Send Write Miss

CPU read

mis

s

Writ

e ba

ck b

lock

, Sen

d re

ad m

iss

CPU WriteSend Write Miss

CPU Read missSend read miss

CPU Write MissWrite back cache blockPlace write miss on bus

CPU read hitCPU write hit

Cache BlockState

Write miss for this block


Write miss for this block

Read m

iss

for t

his

bloc

k


Fetch

, dat

a writ

e ba

ck

Estados do DiretórioEstados do Directory requisição para cada memory block

Estado Uncached se estiver não tiver cópias na cache

UncachedShared

(read only)


Read miss:Sharers = {P}send Data Value Reply

Data Write Back:Sharers = {}

(Write back block)

Write Miss:Sharers = {P}; send Data Value Replymsg

Write Miss: send Invalidate to Sharers;then Sharers = {P};send Data Value Reply msg

Read miss:Sharers += {P}; send Fetch to remote cache;send Data Value Reply msg (Write back block)

Read miss: Sharers += {P};send Data Value Reply

Write Miss:Sharers = {P}; send Fetch/Invalidate to remote cache;send Data Value Replymsg

Exemplo

• 2 processadores: 2 bits

• Cada bloco de memória: 2 presence-bits, 1 dirty-bit


• ••

P P

Cache Cache

Memory Directory



1 2

Bus

Exemplo

Estados Cache: Invalid, Shared, Exclusiv

Estados Diretório (memória): Uncached, Shared, Exclusiv

• ••

P P

Cache Cache

Memory Directory



1 2

Bus

Exemplo

Mensagens do controlador de cache (requisitante do bloco) para o diretório:

• Read Miss• Write Miss

• ••

P P

Cache Cache

Memory Directory



1 2

Bus

Exemplo

• Data reply• Invalidate• Fetch

• Fetch/Invalidate

• ••

P P

Cache Cache

Memory Directory



1 2

Bus

Mensagens do diretório para os controladores de cache:

Exemplo

Mensagens do controlador de cache (owner do bloco) para o diretório:

• Data write back

• ••

P P

Cache Cache

Memory Directory



1 2

Bus

Exemplo

P1 P2 Bus Directory Memorystep StateAddr ValueStateAddrValueActionProc. Addr ValueAddr State{Procs}Value

P1: Write 10 to A1

P1: Read A1P2: Read A1

P2: Write 40 to A2

P2: Write 20 to A1

A1 and A2 map to the same cache block

Processor 1 Processor 2 Interconnect MemoryDirectory

• ••

P P

Cache Cache

Memory Directory



1 2

Bus

Exemplo


P1: Write 10 to A1 WrMs P1 A1 A1 Ex {P1}Excl. A1 10 DaRp P1 A1 0

P1: Read A1P2: Read A1

P2: Write 40 to A2

P2: Write 20 to A1



• ••

P P

Cache Cache

Memory Directory



1 2

Bus

Exemplo



P1: Read A1 Excl. A1 10P2: Read A1

P2: Write 40 to A2

P2: Write 20 to A1



• ••

P P

Cache Cache

Memory Directory



1 2

Bus

Exemplo


A1

• ••

P P

Cache Cache

Memory Directory



1 2

Bus

P2: Write 20 to A1



P1: Read A1 Excl. A1 10P2: Read A1 Shar. A1 RdMs P2 A1

Shar. A1 10 Ftch P1 A1 10 10Shar. A1 10 DaRp P2 A1 10 A1 Shar.{P1,P2} 10

1010

P2: Write 40 to A2 10


A1

Write BackWrite Back

A1

Exemplo

P2: Write 20 to A1





Shar. A1 10 Ftch P1 A1 10 10Shar. A1 10 DaRp P2 A1 10 A1 Shar.{P1,P2} 10Excl. A1 20 WrMs P2 A1 10

Inv. Inval. P1 A1 A1 Excl. {P2} 10P2: Write 40 to A2 10


A1A1

• ••

P P

Cache Cache

Memory Directory



1 2

Bus

Exemplo

P2: Write 20 to A1





Shar. A1 10 Ftch P1 A1 10 10Shar. A1 10 DaRp P2 A1 10 A1 Shar.{P1,P2} 10Excl. A1 20 WrMs P2 A1 10

Inv. Inval. P1 A1 A1 Excl. {P2} 10P2: Write 40 to A2 WrMs P2 A2 A2 Excl. {P2} 0

WrBk P2 A1 20 A1 Unca. {} 20Excl. A2 40 DaRp P2 A2 0 A2 Excl. {P2} 0


A1A1

• ••

P P

Cache Cache

Memory Directory



1 2

Bus

Desafios da Coerência baseada em Diretórios

• Devemos assumir operações atômicas:– Difícil implementação em redes

• Problema na sincronização de processos– Necessidade de leitura e escrita em variável

compartilhada de forma indivisível– operações atômicas

Sincronização

• Por que sincronizar? Necessidade de saber quando é seguro para diferentes processos usar um dado compartihado.

• Garantindo a Sincronização :– Instrução que acessa variável compartilhada não

pode ser interrompida entre a leitura e escrita na memória (operação atômica)

Problema da Sincronização

• Processos necessitam de receber enviar dados de/para outros processos

• Exemplo básico: produtor/consumidor– Processo A produz dados, Processo

B consome dados produzidos– Ex: A decodifica pacotes de vídeo, B

mostra pacotes decodificados na tela

• Como a comunicação é feita?– Memória Compartilhada– Passagem de Mensagem

processA() { // Decode packet // Communicate packet to B }}

void processB() { // Get packet from A // Display packet}

Encoded video packets

Decoded video packets

To display

Problema da Sincronização• Exemplo: Produtor/Consumidor com erro

– Compartilham buffer[N], count– ProcessA produz dados e armazena no buffer

• Se buffer está cheio deve esperar– processB consome dados do buffer

• Se buffer estiver vazio deve esperar– Erro quando os processos tentam atualizar o

contador (linhas 10 e 19) e a seguinte sequencia ocorre

– Considere que “count” é 3.• A carrega count (count = 3) no registrador

R1 (R1 = 3)• A incrementa R1 (R1 = 4)• B carrega (count = 3) no registrador R2 (R2

= 3)• B decrementa R2 (R2 = 2)• A armazena R1 na memória na variável

(count = 4)• B armazena R2 na memória na variável

count (count = 2)– count tem um valor incorreto

01: data_type buffer[N];02: int count = 0;03: void processA() {04: int i;05: while( 1 ) {06: produce(&data);07: while( count == N );/*loop*/08: buffer[i] = data;09: i = (i + 1) % N;10: count = count + 1;11: }12: }13: void processB() {14: int i;15: while( 1 ) {16: while( count == 0 );/*loop*/17: data = buffer[i];18: i = (i + 1) % N;19: count = count - 1;20: consume(&data);21: }22: }23: void main() {24: create_process(processA); 25: create_process(processB);26: }

Memória Compartilhada: Exclusão Mútua

• Algumas partes do código que não podem ser executadas de forma concorrente–Região Crítica

• Região do código onde as variáveis compartilhadas são lidas ou escritas

Memória Compartilhada: Exclusão Mútua

• Quando um processo começa a executar código da região crítica, todos os outros processos deveriam esperar até que o processo termine a execução da região crítica– Mutex

• Um objeto compartilhado usado para bloquear ou desbloquear a entrada na região crítica

• Desabilita o acesso de leitura/escrita no endereço que ele guarda

• Vários processos podem tentar dar lock simultaneamente mas apenas UM consegue sucesso

• Os demais processos ficam bloqueados até que a operação de unlock seja realizada pelo processo na região crítica

• Os processos competirão novamente para entrar na região crítica

Solução para o Produtor/Consumidor

• Uso da variável count_mutex do tipo mutex• Sequencia de execução

– A/B executam operação de lock em count_mutex

– Ou A ou B terão sucesso• Vamos considerar que B conseguiu o lock• A é bloqueado

– B lê count (count = 3) no registrador R2 (R2 = 3)– B decrementa R2 (R2 = 2)– B escreve R2 back na memória (count = 2)– B executa operação de unlock

• A volta para o estado de execução– A carrega (count = 2) no registrador R1 (R1 = 2)– A incrementa R1 (R1 = 3)– A escreve count na memória (count = 3)

• Count tem o valor correto: 3

01: data_type buffer[N];02: int count = 0;03: mutex count_mutex;04: void processA() {05: int i;06: while( 1 ) {07: produce(&data);08: while( count == N );/*loop*/09: buffer[i] = data;10: i = (i + 1) % N;11: count_mutex.lock();12: count = count + 1;13: count_mutex.unlock();14: }15: }16: void processB() {17: int i;18: while( 1 ) {19: while( count == 0 );/*loop*/20: data = buffer[i];21: i = (i + 1) % N;22: count_mutex.lock();23: count = count - 1;24: count_mutex.unlock();25: consume(&data);26: }27: }28: void main() {29: create_process(processA); 30: create_process(processB);31: }

• Atomic exchange: troca os valores entre um registrador e um endereço de memória.– 0 variável de sincronização está livre– 1 variável de sincronização está locked e não

disponível• Seta registrador para 1 & troca valor do registrador

com endereço de memória– Novo valor no registrador determina o sucesso em ter

acesso ao lock • 0 se teve sucesso (chegou primeiro)• 1 se outro processo chegou primeiro

– O segredo é que a operação de exchange seja indivisível

Como garantir que a operação seja executada de forma indivisível em

DSMs com diretórios?

Como implementar variável lock?.

Estratégia para leitura e atualização de memória de forma atômica

• Dificuldade em ter leitura e escrita na memória de forma indivisível por apenas 1 instrução

• Processadores possuem 2 instruções• Load linked (or load locked) + store

conditional–Load linked retorna o valor inicial–Store conditional retorna 1 se foi sucesso

(nenhum outro store acessou o endereço de memória desde o último load) e 0 caso contrário.

Estratégia para leitura e atualização de memória de forma atômica

• Load linked (or load locked) + store conditional– Load linked retorna o valor inicial– Store conditional retorna 1 se foi sucesso (nenhum outro store acessou

o endereço de memória desde o último load) e 0 caso contrário.

• Exemplo swap atômico com LL & SC:try: mov R3,R4 ; mov exchange value

ll R2,0(R1) ; load linkedsc R3,0(R1) ; store conditionalbeqz R3,try ; branch store fails (R3 = 0)mov R4,R2 ; put load value in R4

Exemplo T1

• Oito cores: cada um suporta até 4 threads.

• Cada core consiste num pipeline de 6 estágios

• Tl usa fine-grained multithreading,

• Os cores acessam 4 caches de 2 níveis

• Existe coerência entre caches L1 e um diretório com cada cache L2

• LI data cache é write through,

Exemplo T1

Comparação T1 e Superescalares



Conclusões

• Protocolo de coerência para memória baseado em Snooping• Problemas• Protocolo de coerência baseado em diretórios

– Idéia Básica– Como funciona

• Implementando protocolo baseado em diretórios– Tipos de mensagens na rede– Mudanças do estado do bloco de cache– Mudanças de estado no diretório

• Problemas na Sincronização de processos– Suporte para sincronização em uniprocessadores – Problema em processadores DSM– Solução para processadores DSM

• Exemplo Processador T1 da Sun• Comparação monoprocessadores vs. multiprocessadores

Documents

Multiprocessadores e Paralelismo nível de Thread