MC714 - Instituto de Computaçãobit/ensino/mc714_2s13/aulas/aula02.pdf · Caracterização – sistemas distribuídos • Usuário só descobre que está usando um sistema distribuído

Prof. Luiz Fernando Bittencourt IC - UNICAMP

MC714 Sistemas Distribuídos 2° semestre, 2013


Introdução - sistemas distribuídos •  1. Coleção de entidades independentes que colaboram

para resolver um problema que não poderia ser resolvido individualmente (Kshemkalyani e Singhal).

•  2. Sistema onde componentes de hardware ou software localizados em computadores em rede comunicam-se e coordenam suas ações através somente de troca de mensagens (Couloris, Dollimore e Kindberg).

•  3. Um conjunto de computadores independentes que se apresenta a seus usuários como um sistema único e coerente (Tanenbaum e Van Steen).


Caracterização – sistemas distribuídos • Usuário só descobre que está usando um sistema

distribuído quando alguma falha impede de usar alguma aplicação (Lamport).

• Coleção de computadores que não compartilham memória ou relógio físico comum, que se comunicam por mensagens sobre uma rede de comunicação, e cada computador possui sua própria memória e executa seu próprio sistema operacional. Tipicamente são semi-autônomos e fracamente acoplados enquanto cooperam para resolver um problema coletivamente (Tanenbaum / Van Steen).


Características • Sem relógio físico comum

•  Introduz a noção de distribuição, dando origem à assincronia inerente entre processadores.

• Sem memória compartilhada • Requer troca de mensagens para comunicação. • Deve-se notar que pode fornecer abstração de um

espaço de endereçamento comum através da abstração de memória compartilhada distribuída.


Componentes - hardware • Cada computador tem uma unidade de memória e de

processamento • São conectados por uma rede de comunicação •  Fig 1


Componentes - Software • Aplicação distribuída • Middleware • Sistema operacional • Pilha de protocolos de rede •  Fig 2


Arquitetura / Middleware • Execução distribuída é a execução de processos no

sistema distribuído para alcançar um objetivo comum. • Arquitetura em camadas para quebrar complexidade (Fig

2). • Middleware é o software distribuído que coordena o

sistema distribuído enquanto fornece transparência de heterogeneidade.


Motivação / requisitos • Existem aplicações onde a computação é intrinsecamente

distribuída •  Ex: transferência bancária

• Compartilhamento de recursos •  Hardware, software/bibliotecas, dados, licenças •  Impossível replicar tudo em todo lugar – impraticável ou ineficiente •  Impossível colocar tudo em um lugar só – gargalos e confiabilidade

• Acesso a recursos geograficamente distribuídos •  Dados sensíveis ou muito grandes •  Acesso a dados e supercomputadores a partir de dispositivos

móveis


Motivação / requisitos • Aumentar confiabilidade

• Replicação de dados e de software • Disponibilidade: recurso deve estar disponível “sempre” •  Integridade: estado/valor de um recurso deve ser

correto, sob acessos concorrentes de múltiplos processadores, de acordo com a semântica esperada pela aplicação

•  Tolerância a falhas: habilidade de recuperação de falhas no sistema


Motivação / requisitos • Melhorar taxa desempenho/custo

•  Compartilhamento de recursos e dados remotos •  Aumentar vazão (nem sempre é esse o objetivo...) •  Pode oferecer melhor desempenho/custo que máquinas paralelas

especiais

• Oferecer escalabilidade – evitar gargalos •  Adicionar mais processadores não impõe gargalo direto para a

rede.

• Modularidade / facilidade de expansão •  Adicionar (ou substituir) processadores heterogêneos sem

degradar desempenho.

• Outras?


Sistemas paralelos


Sistemas paralelos • Existem sistemas que possuem algumas, mas não todas, as características de um sistema distribuído

• Como classificá-los? • São sistemas distribuídos ou sistemas multiprocessados?


Arquiteturas de memória • Dois aspectos: localização e política de acesso. • Uma memória para todos os processadores: memória compartilhada.

• Se memória não é compartilhada: acesso via meios explícitos de comunicação, como troca de mensagens.


Arquiteturas de memória • Memória centralizada:

• Memória comum acessada por todos os processadores. • Memória distribuída:

•  Fisicamente distribuída com os processadores. • Memória compartilhada

•  Espaço de endereçamento global •  Tempo de acesso diferente, em geral

• Multiprocessadores de memória distribuída •  Troca de mensagens •  Acesso através do processador •  Hierárquica: alguns (2-4) processadores compartilham memória,

formando um nó de computação. Múltiplos nós são conectados em um nível mais alto – IBM Blue Gene L

• Fig 3


Arquiteturas de memória - diferenças • Memória centralizada

•  Extensão intuitiva da arquitetura de um único processador. •  Contenção na comunicação com memória central limita

escalabilidade. •  Sistemas baseados em barramento geralmente possuem poucos

processadores (<=8).

• Memória distribuída •  Com troca de mensagem permite projeto mais simples, mas

programação torna-se mais complicada. •  Maior escalabilidade – massively parallel processors (MPP) são

sistemas de memória distribuída que usam troca de mensagens e podem conter centenas de milhares de processadores.

•  Multiprocessadores de memória distribuída integram as duas abordagens, fornecendo escalabilidade e maior facilidade de programação.


Sistemas paralelos - classificação • Sistemas multiprocessados. • Multicomputadores. • Processadores vetoriais


Sistemas multiprocessados • Sistemas paralelos onde os múltiplos processadores tem

acesso direto a uma memória compartilhada, a qual forma um espaço de endereçamento único.

• Geralmente sem um relógio comum. • Geralmente constituem uma Uniform Memory Access

(UMA), onde a latência de acesso à memória é a mesma para todo processador.

• Comunicação entre processos: leitura/escrita da memória compartilhada.

• Processadores geralmente do mesmo tipo em um mesmo container.

•  Fig 4


Sistemas multiprocessados •  Interconexão: bus ou multistage switch • Representação: grafo não direcionado

•  Vértice = processador + memória local + switch •  Aresta = enlace de comunicação entre processadores •  Grau – número de mensagens que podem ser manipuladas

simultaneamente por um processador. •  Diâmetro – menor número de nós necessário para comunicação

entre dois nós mais distantes na rede. •  Largura de bisseção – número de enlaces mínimo que divide a

rede na metade. Indica quantas mensagens podem ser trocadas simultaneamente entre duas metades da rede.

•  Fig 15


Sistemas multiprocessados • Duas redes de interconexão populares são a omega e a

butterfly. • São redes multi-estágio formadas por comutadores 2x2.

•  Permitem dados de qualquer das duas entradas serem direcionados para qualquer das duas saídas.

•  Colisões ocorrem quando mais de um dado é direcionado ao mesmo tempo para a mesma saída.


Sistemas multiprocessados • Omega

•  Omega: n processadores, n unidades de memória •  (n/2) log2n switches 2x2, log2n níveis •  Função de interconexão

•  Função de roteamento

•  Para nível s da rede, se o s+1-ésimo bit mais significativo de j é 0, vai pro fio de cima, se for 1 vai pro fio de baixo.

•  Fig 5

j =

�2i, 0 ≤ i ≤ n

2 − 1

2i+ 1− n, n2 ≤ i ≤ n− 1


Sistemas multiprocessados • Butterfly

•  Função de interconexão •  Depende de n e de s •  Seja M=n/2 switches em cada nível, e <x,s> um switch x no nível

s •  Existe uma aresta de <x,s> para <y, s+1> se:

•  x=y •  x XOR y tem exatamente um bit 1, que está no s+1-ésimo bit mais

significativo

•  Função de roteamento •  Num nível s, se s+1-ésimo bit mais significativo de j é 0, vai para

o fio de cima, senão vai para o fio de baixo. •  Fig 6


Multicomputadores • Sistema paralelo onde múltiplos processadores não têm

acesso direto a memória compartilhada. • Memória pode ou não formar um espaço de

endereçamento comum. • Geralmente não têm relógio comum. • Próximos fisicamente. •  Fortemente acoplados (hardware e software

homogêneos). •  Fig 7


Multicomputadores • Espaço de endereçamento comum ou troca de

mensagens. • Espaço de endereçamento comum: geralmente

corresponde a arquitetura NUMA (non-uniform memory access).

•  ccNuma – Cache Coherent NUMA


Multicomputadores - topologias •  Topologias regulares e simétricas

•  Mesh, anel, torus, cubo, hipercubo •  Propriedades matemáticas interessantes para roteamento •  Fig 8


Torus • Wrap-around 2D-mesh (Torus) • Mesh contém processadores. • Comprimento máximo do caminho entre quaisquer 2

processadores: k

k × k k2


Hipercubo • Hipercubo com k dimensões tem unidades de

processamento/memória. • Cada unidade é um nó no hipercubo e tem um rótulo

único de k bits. • Grau de cada nó: log2(n). • Cada uma das k dimensões é associada com uma

posição nos rótulos. • Rótulos de quaisquer 2 nós adjacentes são iguais exceto

pelo bit da posição correspondente à dimensão na qual os nós diferem. •  Processadores rotulados de forma que o caminho mínimo entre

quaisquer 2 nós é a distância de Hamming de seus rótulos (limitante superior = k).

2k


Hipercubo • Um hipercubo de d dimensões pode ser particionado em

2 hipercubos de d-1 dimensões. •  Fixe uma posição qualquer do rótulo. Processadores com 0 nessa

posição são um hipercubo de dimensão d-1, e processadores com 1 são outro hipercubo.

• Roteamento salto-a-salto. •  A cada passo, a mensagem pode ser enviada para qualquer

dimensão correspondente à posição na qual o endereço do nó corrente difere do endereço do destino.

•  Múltiplas rotas entre qualquer par de nós: tolerância a falhas e controle de congestionamento.


Array processors (vector processors) • Processadores fisicamente próximos, fortemente

acoplados. • Relógio comum. • Podem não compartilhar memória e podem comunicar-se

por troca de mensagens. • Processamento e troca de dados sincronizados. • Ex.: DSP e processamento de imagens.


Caracterização de sistemas paralelos • Distinção/caracterização é importante para projeto de

algoritmos. • Considerar latências

•  Muito acesso aos mesmos dados, muito acesso a dados locais e pouco acesso a dados distribuídos, etc.


Caracterização de sistemas paralelos • Uso primário de sistemas paralelos: maior vazão através

da divisão da carga entre os processadores. •  Tarefas que podem ser melhor aceleradas são as que

podem ser particionadas em subtarefas com pouca comunicação. •  Ex.:Muitas operações sobre vetores e matrizes, comuns em

aplicações científicas.

• Máquinas paralelas foram objeto de pesquisa teórica e de sistemas em 1980, entretanto não se provaram economicamente viáveis na época. •  Poucas aplicações populares tiravam vantagem de paralelismo. •  Aumento da capacidade de processamento de PCs.


Taxonomia • Processamento (Flynn):

•  SISD, MISD, SIMD, MIMD

• Programação •  Memória compartilhada •  Troca de mensagens •  PRAM – Parallel Random Access Machine •  LogP vs. PRAM


Taxonomia – Flynn • Quatro “modos” de processamento classificando:

•  Como é o processamento de instruções •  Quais são os dados de entrada de cada processador •  Single Instruction, Single Data – SISD •  Single Instruction, Multiple Data – SIMD •  Multiple Instruction, Single Data – MISD •  Multiple Instruction, Multiple Data – MIMD


SISD • Single instruction stream, single data stream • Modo “convencional” no paradigma de Von Neumann • Uma CPU • Uma unidade de memória • Conectados por bus •  Fig 9


SIMD • Single instruction stream, multiple data stream. • Processamento: múltiplos processadores homogêneos. • Mesma instrução. •  Itens de dados distintos. • Processamento de arrays e matrizes. • Co-processamento (MMX, SSE). •  Fig 10


MISD • Multiple instruction stream, single data stream. • Operações diferentes • Mesmo dado •  Fig 11


MIMD • Multiple instruction stream, multiple data stream. •  Instruções diferentes. • Dados diferentes. • Modo de operação de sistemas distribuídos e paralelos

em geral. • Sem relógio comum. •  Fig 12

Documents

MC714 - Instituto de Computaçãobit/ensino/mc714_2s13/aulas/aula02.pdf · Caracterização – sistemas distribuídos • Usuário só descobre que está usando um sistema distribuído