Introdução ao Processamento

Paralelo e Distribuído
Marcelo Veiga Neves
[Link]@[Link]
 Roteiro
• Histórico e evolução das arquiteturas usadas por estes sistemas
• Revisão das classes de arquiteturas paralelas e distribuídas
• Semelhanças, diferenças e o escopo de aplicação de sistemas
concorrentes, paralelos e distribuídos
• Métricas para avaliação destes sistemas
Evolução das arquiteturas
• Arquitetura tradicional • Unidades de E/S autônomas
• uma única unidade ativa • Direct memory access (DMA)
• problema: latência de E/S • multiprogramação
Evolução das arquiteturas
• Hierarquia de memória • Memórias não voláteis
• acelerar alimentação da CPU • Reduzir latências de E/S
• localidade temporal e espacial • Memória única
• problema fundamental – E/S • Rápida e persistente
Evolução das arquiteturas
• Hierarquia de memória
Evolução das arquiteturas
• Pipelines
• De instrução (superescalar)
• De dados (máquinas vetoriais)
Evolução das arquiteturas
• Hyperthreading (HT)
• Melhor aproveitar os pipelines
superescalares
• Simultaneous multithreading (SMT)
 Evolução das arquiteturas
• Multicore
• Múltiplos núcleos de processamento
• Foco não apenas na frequência
• Motivação: energia
 Evolução das arquiteturas
• Ex: Intel Core i7-3770K
Evolução das arquiteturas
• Manycore
• GPU
• Unidade geral – GP/GPU
• Co-processadores: Intel Phi e Nvidia Titan V
 Evolução das arquiteturas
• Ex: Nvidia Tesla V100 (GPU)
Objetivo desta evolução
• Acelerar processamento dos dados por parte da CPU
• Liberando CPU (delegando tarefas)
• controle do barramento
• tratamento de E/S
• Acelerando alimentação da CPU
• hierarquia de memória
• Sobrepondo ciclos da CPU
• pipeline de instrução
• múltiplas threads
• múltiplos cores

• Próximo passo?
 Replicação da CPU
• Acelerar processamento dos dados construindo arquiteturas com
múltiplas CPUs
• Computadores com múltiplos processadores
• Combinação de múltiplos computadores

• Arquiteturas Paralelas
• Arquiteturas Distribuídas
Arquiteturas paralelas e distribuídas

Evolução das
Clusters of
arquiteturas
Supercomputadores
Vetorial/SMP/NUMA Workstations
Grid

Escala / Poder Computacional

Acoplamento

Complexidade de uso
Classes de arquiteturas paralelas e
distribuídas
• Por que estudar classificações ?
• Identificar o critério da classificação
• por que é importante e quais são as suas implicações
• Analisar todas as possibilidades
• mesmo as classes que não foram implementadas ou as implementações
que não deram certo
• Entender como se deu a evolução da área
• como pode evoluir
Classificação de Flynn
• Classificação genérica (1970)
• Diferencia se o fluxo de instruções (instruction stream) e o fluxo de
dados (data stream) são múltiplos ou não
Classificação segundo o compartilhamento de
memória
• Multiprocessador • Multicomputador
• Compartilha uma memória central • Não compartilha memória
• Arquitetura tradicional com vários • Interligação de várias arquiteturas
processadores tradicionais
• Comunica através da memória • Cada uma possui sua memória
• Variáveis compartilhadas local
• Comunica por troca de mensagens
Espaço de endereçamento
• Área de memória visível ao processador
• Memória compartilhada
• único espaço de endereçamento
• Memória não compartilhada
• múltiplos espaços de endereçamento privados
• Memória distribuída
• localização física da memória
• oposto de memória centralizada
Classificação segundo o tipo de acesso à
memória
• Multiprocessadores: • O problema é como acessar
• UMA a memória e garantir
• NCC-NUMA coerência entre caches
• CC-NUMA
• SC-NUMA
• COMA
Classificação segundo o tipo de acesso à
memória
• UMA
• Uniform Memory Access
• Memória centralizada (mesma distância de todos os processadores)
• Custo único de acesso
• Precisa tratar coerência de cache
Classificação segundo o tipo de acesso à
memória
• NUMA
• Non Uniform Memory Access
• Único espaço de endereçamento
• Memória distribuída (distâncias diferentes)
• Custo não uniforme de acesso à memória
Classificação segundo o tipo de acesso à
memória
• Em relação ao tratamento do problema de coerência de cache
• NCC-NUMA
• non cache-coherent NUMA
• CC-NUMA
• cache-coherent NUMA
• implementada em hardware
• SC-NUMA
• software-coherent NUMA
• implementada em software
• DSM (Distributed Shared Memory)
Classificação segundo o tipo de acesso à
memória
• COMA
• Cache-only Memory Architecture
• Memórias locais são caches (coma caches)
• Gerência de caches na MMU
Classificação segundo o tipo de acesso à
memória
• NORMA
• Non-remote memory access
• Apenas acesso local à memória
• Multicomputadores
Resumo
Plataformas tradicionais para PPD
• PVP - Processadores Vetoriais (SIMD)
• SMP - Multiprocessadores simétricos
• MPP - Multicomputadores massivamente paralelos
• NOW – Redes de estações de trabalho
• COW – Clusters de estações de trabalho
Multiprocessadores simétricos (SMP)
• Symmetric Multiprocessing (SMP)
• Computador com múltiplos processadores idênticos
• Número limitado de processadores (até dezenas)
• Arquitetura de compartilhamento total (shared everything)
• Executa um único sistema operacional
Multiprocessadores simétricos (SMP)
Multicomputadores massivamente paralelos
• Massively Parallel Processing (MPP)
• Múltiplos computadores interconectados por rede de alta velocidade
• Suporta um grande número de processadores (milhares)
• Arquitetura sem compartilhamento (shared-nothing)
• Memória distribuída (cada computador tem sua memória)
• Cada computador executa seu próprio sistema operacional
Multicomputadores massivamente paralelos
Definições de PP e PD
• O que são Sistemas Concorrentes?
• O que são Sistemas Paralelos?
• O que são Sistemas Distribuídos?
• O que é Processamento Paralelo e Distribuído?
Sistemas Concorrentes
• Tanto SP quanto SD são sistemas concorrentes
• Compartilham características comportamentais
• Mas tem objetivos diferentes!
Sistemas Concorrentes
• Concorrência:
• “ability of different parts or units of a program, algorithm, or problem to be
executed out-of-order or at the same time simultaneously, without affecting
the final outcome” (Leslie Lamport)

• Objetivo principal
• Melhor aproveitamento dos recursos e ganho de responsividade
Sistema Concorrente
Sistemas Distribuídos
• Definição:
• “Coleção de computadores independentes entre si que se apresenta ao
usuário como um sistema único e coerente" (Andrew Tanenbaum)

• Objetivo principal:
• Escalabilidade e Tolerância a Falhas
• Compartilhamento de Recursos
Sistemas Distribuídos
Sistemas Paralelos
• Definição:
• "É um conjunto de processadores que é caaz de trabalhar cooperativamente
para resolver um problema computacional" (Ian Foster)

• Objetivo principal:
• Ganho de Desempenho
Sistemas Paralelos
Métricas de Avaliação
• Como avaliar sistemas sistemas concorrentes, paralelos e
distribuídos?
Sistemas Concorrentes
• Responsividade
• Corretude
• Safety: não vai acontecer nada de ruim
• Liveness: eventualmente vai acontecer algo de bom
• Justiça (fairness)
Sistemas Distribuídos
• Tempo de resposta
• Latência (cliente)
• Transações por segundo (serviço)
• Tolerância a falhas
• Segurança
Sistemas Paralelos
• Fator de aceleração (speed-up)
• quantas vezes o programa ficou mais rápido do que a versão sequencial
• Eficiência
• taxa de utilização média dos recursos