1

SSC114 Arquitetura de ComputadoresArquiteturas ParalelasArquiteturas MIMD

Memória CompartilhadaAulas 11 e 12

08/10/10 (Turma 1 e 2)

Profa. Sarita

2

Arquiteturas MIMD

As arquiteturas MIMD dividem-se em dois grandes grupos: Memória Compartilhada

Cada processador pode endereçar toda a memória do sistema

Memória Distribuída Cada processador endereça somente a própria memória

local

3

Arquiteturas MIMD com memória compartilhada Vantagens

A comunicação entre os processos é bastante eficiente, pois os dados não precisam se movimentar fisicamente

A programação não difere muita da programação para um único processador, não necessitando particionar código nem dados

4

Arquiteturas MIMD com memória compartilhada Desvantagens

Primitivas de sincronização são necessárias para acesso às regiões compartilhadas Em algumas linguagens isso fica a cargo do

programador Linguagens mais novas escondem alguns detalhes do

programador Esse tipo de arquitetura não é muito escalável,

devido ao limite da memória

5

Arquiteturas MIMD com memória distribuída Vantanges

Altamente escalável, permitindo a construção de MPPs (computadores massivamente paralelos)

A forma de comunicação (através de troca de mensagens) resolve tanto os problemas de comunicação como sincronização

6

Arquiteturas MIMD com memória distribuída Desvantagens

A programação exige que os problemas possuam uma natureza paralela

É necessária a distribuição da carga entre os processadores, seja de maneira automática ou manual

7

Computador com as seguintes características: dois ou mais processadores com capacidade semelhante processadores compartilham a mesma memória e I/O processadores conectados por um barramento ou outra conexão

interna tempo de acesso à memória é aproximadamente o mesmo para

todos os processadores Também denominado por arquitetura UMA (Uniform Memory Access)

processadores compartilham acesso a I/O podem usar o mesmo canal ou possuírem caminhos independentes para

cada dispositivo processadores podem fazer as mesmas funções (são simétricos) sistema operacional integrado controla a arquitetura

fornece interação entre processadores, jobs, tarefas, threads, arquivos e níveis de elementos de dados

SMP – Symmetric MultiProcessors

8

SMP - Vantagens

Desempenho, caso algum trabalho possa ser feito em paralelo

Disponibilidade de recursos todos os processadores podem fazer as mesmas funções,

falhas de um processador não param a máquina Aumento incremental

usuário pode aumentar o desempenho adicionando novos processadores, mas sempre limitado pela memória

Diferentes faixas de equipamentos (scaling) fornecedores oferecem diferentes produtos, baseados no

número de processadores

9

Diagrama de um bloco multiprocessador com memória compartilhada

10

SMP - Organização

Barramento de tempo compartilhado ou comum

Memória multiportas (ou multiportos) Unidade de Controle Central

11

SMP – Barramento Compartilhado Forma mais simples Estrutura e interface similares às arquiteturas

monoprocessadas endereçamento – distingue módulos no barramento arbitragem – qualquer módulo pode ser o mestre

temporariamente time sharing – se um módulo tem o barramento, outros

dispositivos esperam Diferença em relação aos monoprocessados:

múltiplos processadores além de múltiplos dispositivos de I/O

12

SMP – Barramento Compartilhado

13

SMP – Barramento Compartilhado Vantagens

simplicidade flexibilidade confiabilidade

Desvantagens: desempenho limitado pelo clock do barramento cada processador deveria ter cache local

reduz número de acessos ao barramento gera problemas com a coerência da cache

14

SMP – Memória Multiportas

Acesso direto e independente dos módulos de memória pelos processadores

Lógica necessária para solucionar conflitos Pouca ou nenhuma modificação nos

processadores ou módulos de memória

15

SMP – Memória Multiportas

Mais complexa precisa de um login extra no sistema de memória

Desempenho melhor cada processador tem o seu próprio caminho aos módulos

de memória Pode configurar porções da memória como

“privada” para um ou mais processadores aumenta a segurança

Política write through para atualização da cache

16

SMP – Considerações sobre o SO Encapsula detalhes, fornece visão de uma

arquitetura monoprocessada Trabalha com:

processos concorrentes escalonamento sincronização gerência de memória confiabilidade e tolerância a falhas

17

Exemplo – IBM S/390 mainframe

18

Memória Compartilhada Distribuída Implementação de uma memória que é

logicamente compartilhada mas implementada com o uso de um conjunto de memórias locais

Pode ser de três classes: NUMA (Non-uniform Memory Access) CC-NUMA (Cache Coherent Non-Uniform

Memory Access) COMA (Cache-Only Memory Access)

19

NUMA (Non-Uninform Memory Access) NUMA - quando o acesso à memória NÃO é

uniforme todos os processadores têm acesso a toda

memória normalmente usando load & store

tempo de acesso à memória difere em função da região

diferentes processadores têm acesso às regiões da memória em diferentes velocidades, o que faz necessário um certo cuidado na hora de programar

20

NUMA (Non-Uninform Memory Access)

21

COMA (Cache Coherent Non-Uniform Memory Access) Assemelham-se a uma arquitetura NUMA, onde cada nó de

processamento possui uma parte da memória global.

O particionamento dos dados entre as memórias de cada nó não é estático -> as memórias funcionam como caches de nível 3.

O problema de partição de dados e balanceamento dinâmico de carga é realizado automaticamente.

Conforme o algoritmo de coerência utilizado, os dados migram automaticamente para as caches locais dos processadores onde é mais necessária.

22

COMA (Cache Coherent Non-Uniform Memory Access)

23

CC-NUMA (Cache Coherent Non-Uniform Memory Access) Solução de compromisso entre as

arquiteturas NUMA e COMA. Cada nó processador possui uma cache local

para reduzir o tráfego na rede de interconexão.

O balanceamento de carga é realizado dinamicamente pelos protocolos de coerência das caches.

24

CC-NUMA (Cache Coherent Non-Uniform Memory Access)

25

CC-NUMA – Uma possível organização

26

SSC114 Arquitetura de Computadores

Arquiteturas ParalelasProtocolos de Coerência de Cache

Aulas 11 e 1208/10/10 (Turmas 1 e 2)

Profa. Sarita

27

Memórias CachePolíticas de Atualização As memórias caches possuem dois modos básicos

para trabalhar em relação à atualização dos dados na memória principal durante uma escrita: Write-through: Os dados são atualizados tanto na memória

cache como na memória principal. Write-back: Os dados são atualizados apenas na memória

cache, e copiados para a memória principal, apenas quando da substituição do bloco/linha modificado na cache.

28

Problema de Coerência de Cache Os sistemas multiprocessados com memória

compartilhada apresentam os seguintes problemas: Conteção de memória: o módulo de memória pode

manipular somente uma requisição de memória por vez Contenção de comunicação: contenção dos links de

comunicação, mesmo que deseje-se acessar módulos diferentes da memória

Tempo de latência: tempo de comunicação utilizando as redes de interconexão tende a aumentar quando o número de processadores aumenta e a interconexão se torna mais complexa

29

Tempo de acesso à memória

Fonte: Organização e Projeto de Computadores (Patterson & Hennesy), 2003

30

Problema de Coerência de Cache Para solucionar os problemas citados, utiliza-

se memórias cache, objetivando reduzir o número de acessos à memória principal

Problema: várias cópias de um mesmo bloco compartilhado por diversos processos ao mesmo tempo As várias cópias devem estar consistentes Problema denominado “Problema de coerência

de cache” ou “Problema de consistência de cache”

31

Exemplo de algoritmos com compartilhamento de variáveis Problema do Produtor/Consumidor

Variáveis compartilhadas: buffer, in, out e count

32

Políticas de coerência de cache Write-invalidate: política que mantém a

consistência da seguinte maneira: Requisições de leitura são tratadas localmente

caso já exista uma cópia local do bloco Todas as outas cópias são invalidadas caso o

bloco seja atualizado Uma próxima atualização pelo mesmo processador

pode ser feita localmente, já que as outras cópias estão invalidadas

Múltiplos leitores, um escritor

33

Políticas de coerência de cache Write-invalidate

34

Políticas de coerência de cache Write-update: política que mantém a

consistência da seguinte maneira: Ao invés de invalidar as cópias, esta política

atualiza todas as outras cópias Múltiplos leitores e escritores

35

Políticas de coerência de cache Write-update

36

Exemplo 1Produtor/consumidor Considere um processo produtor P e um

processo consumidor C Cada processo está executando em uma

máquina diferente O processo P executa k entradas na região crítica

(inserções) seguidas O processo C executa k entradas na região crítica

(remoções) seguidas

37

Exemplo 1Produtor/consumidor Comparação do custo de comunicação para

acesso à variável count para k execuções consecutivas na região crítica

38

Exemplo 2

Considere a seguinte seqüencia de instruções

Conte o número de transações do barramento utilizando os protocolos write-update e write-invalidate (com write-back) e que o tamanho do bloco é igual a uma palavra (4 bytes)

Etapa Processador Atividade da memória Endereço de memória

1 P1 Leitura 100

2 P2 Escrita 104

3 P1 Leitura 100

4 P2 Leitura 104

5 P1 Leitura 104

6 P2 Leitura 100

39

Protocolos para manter a consistência Independente da política utilizada (write-invalidate

ou write-update), as mensagens para manter a consistência dos dados devem ser enviadas para pelo menos as que possuem uma cópia do dado

Para redes onde o custo de se fazer um broadcast não é muito alto, utiliza-se um protocolo denominado Snoopy Cache Protocol

Para redes de interconexão mais complexas utiliza-se um protocolo denominado Directory Protocol

40

Snoopy Cache Protocol ou snooping O snooping distribui a responsabilidade da

coerência entre os controles de cache, os quais reconhecem que a linha é compartilhada

Esse monitoramento pode invalidar (política write-invalidate) ou atualizar (política write-update) a cópia do bloco na memória cache local que esteja sendo alterado por uma operação de escrita no barramento

41

Snoopy Cache Protocol ou snooping

Fonte: Organização e Projeto de Computadores (Patterson & Hennesy), 2003

42

Directory Protocol

Utilizado quando os processadores não são conectados por barramento

Existe um controlador central, o qual faz parte do controlador da memória principal, que coleta e mantém informações sobre as cópias dos dados nas caches

Quando uma linha da cache é refenciada, a base de dados é verificada para saber onde é “limpa” (shared) ou “suja” (modified)

43

Directory Protocol

Antes de um processador atualizar os dados compartilhados, este deve requisitar ao controlador acesso exclusivo à linha desejada

Para obter o acesso exclusivo, o controlador envia uma mensagem a todos os processadores com uma cópia cacheada dessa linha, forçando cada processador a invalidar sua cópia

44

Directory Protocol

O controlador tem que receber uma mensagem de cada processador antes de dar o acesso exclusivo

Quando um processador tenta ler uma linha que está com acesso exclusivo a outro processador, é enviada uma notificação de falha de acesso para o controlador

O controlador requisita que o processador que tem acesso exclusivo faça a atualização da linha na memória principal e passa o acesso exclusivo ao processador que requisitou a linha e compartilha para leitura para o processador que detinha o acesso exclusivo

45

Directory Protocol

Problema: é centralizado, criando um gargalo central e sobrecarregando a comunicação entre os vários controladores de cache e o controlador central

São eficientes em sistemas de larga escala, os quais envolvem múltiplos barramentos ou interconexões mais complexas

46

Protocolo MSI

Este protocolo é utilizado com as políticas write-invalidate e write-back

Os exemplos das transições a seguir consideram a utilização de snooping

Baseia-se em uma máquina de estados finitos com 3 estados: Shared (Compartilhado - somente leitura): esse bloco na

cache é “limpo” (não escrito) e pode ser compartilhado Modified (Modificado – leitura/escrita): esse bloco na

cache é “sujo” (escrito) e pode não ser compartilhado Invalid (Inválido): esse bloco de cache não possui dados

válidos

47

Protocolo MSI

Transições ocorrem em três situações: Falha de leitura

Se estiver nos estados M ou S, o dado local é utilizado Se estiver no estado I, deve-se verificar se o bloco não está em outras

caches Se estiver em outras caches no estado M, esta deve escrever o bloco de

volta na memória principal e mudar seu estado para I Falha de escrita

Se houver outra cópia no estado S, adquire o barramento, envia sinal de invalidação, copia o bloco da MP, atualiza e modifica o estado para M

Se estiver no estado M, idem para falha de leitura Acerto de escrita

Se estiver no estado M, nada acontece Se estiver no estado S, adquire o barramento e envia uma mensagem de

invalidação para bloquear outras cópias Acertos de leitura não alteram o estado da cache

48

Protocolo MSI

Fonte: Organização e Projeto de Computadores (Patterson & Hennesy), 2003

49

Protocolo MSI

Fonte: Organização e Projeto de Computadores (Patterson & Hennesy), 2003

50

Protocolo MESI

Divide o estado Shared (compartilhado) em dois outros estados: Shared (compartilhado): existem múltiplas cópias

do bloco Exclusive (exclusivo): existe apenas uma cópia

Existe apenas uma cópia do bloco e um acerto de escrita não precisa invalidar

Protocolo utilizado pelo Pentium 4

51

Protocolo MESI

Resumo dos 4 estados

M (Modified) E (Exclusive) S (Shared) I (Invalid)

A linha é válida? Sim Sim Sim Não

A cópia da MP é... Desatualizada Válida Válida -

Existe cópia em outra cache?

Não Não Talvez Talvez

Uma escrita nessa linha...

Não precisa do barramento

Não precisa do barramento

Precisa do barramento e

atualiza a cache

Acessa direto o barramento

Fonte: Computer Organization and Architecture (William Stallings), 2003

52

Protocolo MESI

Fonte: Computer Organization and Architecture (William Stallings), 2003

53Fonte: Structured Computer Organization (Andrew S. Tananbaum), 2006

54

Protocolo MOESI

Acrescenta o estado Owner, no qual a cache que possui o bloco neste estado, fornece o dado em caso de falha de leitura no barramento, uma vez que a memória não possui o dado atualizado

Pode existir cópias do dado em outras caches

55

Exercício

Conte o número de transações no barramento para a seqüência de instruções, explicitando as transições na máquina de estado finito de um protocolo MESI

Considere que os processadores utilizam as políticas write-invalidate, write-back, tamanho de bloco de uma word e que os blocos não estão na memória cache (estado inicial Invalid)

56

Exercício

Etapa Processador Atividade da memória Endereço de memória

1 P1 Leitura 100

2 P1 Escrita 100

3 P3 Leitura 104

4 P2 Escrita 100

5 P3 Escrita 104

6 P3 Escrita 100

7 P1 Leitura 100