Processamento de
Alto Desempenho
Prof. Mateus Raeder
Universidade do Vale do Rio dos Sinos
- São Leopoldo -
Sumário
•
•
•
•
•
•
•
•
•
Introdução ao Processamento de Alto Desempenho
Desafios e considerações
Taxonomia de arquiteturas paralelas
Classificação quanto à memória
Multiprocessadores
Multicomputadores
Máquinas paralelas
Requisitos básicos de PAD
Medidas de desempenho
Processamento de Alto Desempenho – Prof. Mateus Raeder
Introdução ao PAD
• O que é Processamento de Alto Desempenho?
– (quadro 1)
• Primeiros trabalhos utilizando paralelismo
– Década de 40
– Sistema Model V
• Stibitz e Willians (Bell Telephone)
– Formado por 2 processadores
– Já mostrava um bom exemplo de uma arquitetura
paralela
• 2 programas diferentes poderiam ser executados ao mesmo
tempo
Processamento de Alto Desempenho – Prof. Mateus Raeder
Introdução ao PAD
• Máquinas são geralmente criadas utilizando o
modelo de Von Neumann
– Dados e programas são armazenados na memória
– Memória é separada da CPU
– Instruções e dados são trocados entre a memória e a CPU
Processamento de Alto Desempenho – Prof. Mateus Raeder
Introdução ao PAD
• Fluxo de dados limita a velocidade do computador
– Velocidade de conexão entre a memória e o processador
define esta velocidade
• Geralmente, as instruções são executadas em um tempo
menor do que a sua transferência
• Isto é denominado Gargalo de Von Neumann
– (quadro 2)
Processamento de Alto Desempenho – Prof. Mateus Raeder
Introdução ao PAD
• O Gargalo de Von Neumann é um dos principais
precursores do paradigma de Programação
Paralela e Concorrente
• Adição de mais processadores supera o Gargalo
de Von Neumann
– Cada um com sua taxa individual de transferência
Processamento de Alto Desempenho – Prof. Mateus Raeder
Introdução ao PAD
• No mundo real, as coisas acontecem em paralelo
– Natural que computações possam ser realizadas em
paralelo, ou não impedidas de tal
• Programação sequencial
– Inevitável ordenar as ações a serem realizadas
– Impede novos conceitos
• Dificuldade de perceber o paralelismo em alguns
casos
Processamento de Alto Desempenho – Prof. Mateus Raeder
Introdução ao PAD
• Aplicações complexas
– Aplicações de hoje em dia esperam muito mais dos
processadores
– Precisam de poder computacional muito além do
existente
•
•
•
•
•
•
•
Inteligência artificial
Simulações (principalmente Monte Carlo)
Algoritmos de busca e processamento de grafos
Processamento de imagens
Procura por petróleo
Bancos de dados (principalmente em tempo real)
Etc...
Processamento de Alto Desempenho – Prof. Mateus Raeder
Introdução ao PAD
• Aplicações complexas
– Aplicações de hoje em dia esperam muito mais dos
processadores
– Precisam de poder computacional muito além do
existente
•
•
•
•
Previsão do tempo
Simulações físicas com alta carga computacional
Bioinformática
Computação gráfica
Processamento de Alto Desempenho – Prof. Mateus Raeder
Introdução ao PAD
• Hoje em dia, paralelismo traz muito benefício para
a computação
– Principalmente para a área da pesquisa
• Mas, por que exatamente utilizar paralelismo?
– O Processamento Paralelo surge com o intuito de melhorar
o desempenho de tais aplicações
– Proporciona um custo relativamente pequeno para a
aquisição de um ambiente paralelo
Processamento de Alto Desempenho – Prof. Mateus Raeder
Introdução ao PAD
• Supercomputadores são muito caros
– Alguns por mais de US$130,000.000,00
• A obtenção de computadores pessoais é mais
barata
– Agrupar computadores pessoais mais baratos
– Mesmo desempenho (teórico) do que um
supercomputador
– Preço mais baixo
Processamento de Alto Desempenho – Prof. Mateus Raeder
Desafios e considerações
• Idealmente, a modelagem de programas paralelos
deve ser a mais abstrata possível
– Permitindo a execução do programa em diferentes
arquiteturas
– Aumentar o tempo de vida dos programas
• Arquiteturas novas surgindo
• Ocultar aspectos de arquitetura
– (quadro 3)
Processamento de Alto Desempenho – Prof. Mateus Raeder
Desafios e considerações
• O controle da execução em paralelo é bastante
complexo
• O modelo paralelo criado deve:
– Decompor o programa em partes paralelizáveis
– Mapear as tarefas aos processadores
• Decisão de onde alocar cada tarefa
• Influenciada pelo tipo de processadores (homogêneos x
heterogêneos)
– Comunicação entre as tarefas paralelas
– Sincronização das tarefas
Processamento de Alto Desempenho – Prof. Mateus Raeder
Desafios e considerações
• Facilidade de entendimento
– O modelo deve ser o mais entendível possível
– Ocultar ao máximo a complexidade
– De uso simples
• Previsibilidade de desempenho
– É possível prever o desempenho pra diferentes arquiteturas
• Evitar comunicação exagerada
• Balancear a carga de trabalho adequadamente
Processamento de Alto Desempenho – Prof. Mateus Raeder
Taxonomia de Arquiteturas Paralelas
• A classificação de arquiteturas paralelas mais
difundida na área é a de Flynn
– Fluxo de instruções
– Fluxo de dados
• Resulta em 4 classes (quadro 4)
–
–
–
–
SISD (Single Instruction, Single Data)
SIMD (Single Instruction, Multiple Data)
MISD (Multiple Instruction, Silgle Data)
MIMD (Multiple Instruction, Multiple Data)
Processamento de Alto Desempenho – Prof. Mateus Raeder
Taxonomia de Arquiteturas Paralelas
• SISD
–
–
–
–
Fluxo de instruções alimenta a unidade de controle (C)
Ativa a CPU (P)
Atua sobre um único fluxo de dados
Máquinas tradicionais de Von Neumann (pessoais)
• SIMD
– Única instrução (uma unidade de controle)
– Executada de forma síncrona sobre um conjunto de dados
diferentes
– Unidade de controle é alimentada por um fluxo de instruções
– A mesma instrução, é enviada para todas as CPUs
• Mesmo programa sobre diferentes dados (máquinas vetoriais)
Processamento de Alto Desempenho – Prof. Mateus Raeder
Taxonomia de Arquiteturas Paralelas
• MISD
– Várias instruções sobre um único dado
– Classe considerada vazia
• Diferentes instruções acessam e operam a mesma posição de
memória ao mesmo tempo
• Impraticável
• MIMD
– Vários instruções sobre vários dados
– É a arquitetura desejada em computadores paralelos
– Cada processador executa um programa com seus próprios
dados
• De maneira assíncrona
Processamento de Alto Desempenho – Prof. Mateus Raeder
Classificação quanto à Memória
• Classificadas quanto ao compartilhamento da
memória
– Memória compartilhada
– Memória distribuída
Processamento de Alto Desempenho – Prof. Mateus Raeder
Classificação quanto à Memória
• Memória compartilhada
– Um único espaço de endereçamento para todos os
processadores
– Comunicação entre os processadores através de escrita e
leitura da memória
• Memória distribuída
– Múltiplos espaços de endereçamento privados
– Cada processador com o seu espaço de endereçamento
Processamento de Alto Desempenho – Prof. Mateus Raeder
Classificação quanto à Memória
• Multiprocessador x Multicomputador
• Multiprocessador
–
–
–
–
N processadores acessam uma memória compartilhada
Comunicação através de leitura e escrita na memória
Espaço de endereçamento global
Tipos de multiprocessadores:
• UMA (Uniform Memory Access)
• NUMA (Non-Uniform Memory Access)
• COMA (Cache-Only Memory Architecture)
Processamento de Alto Desempenho – Prof. Mateus Raeder
Multiprocessadores
• UMA (quadro 5)
– Memória centralizada (equidistante aos processadores)
– Acesso uniforme, através do barramento (um de cada vez)
• NUMA (quadro 6)
– Pares processador/memória conectados através de um
barramento
• Memória é dividida em blocos
• Cada bloco associado a um processador
• Aparentemente distribuído, mas possui espaço de
endereçamento único
• Quando o acesso é “local”, o tempo é reduzido
Processamento de Alto Desempenho – Prof. Mateus Raeder
Multiprocessadores
• COMA (quadro 7)
– Assemelham-se às arquiteturas NUMA
– Memórias cache para cada processador
• Capacidade de armazenamento bem maior que uma
memória cache normal
– Dados podem migrar de uma memória para a outra
• Diminui o número de cópias redundantes da NUMA
• Maior dificuldade para encontrar o dado
Processamento de Alto Desempenho – Prof. Mateus Raeder
Multicomputadores
• Espaço de endereçamento privado
• Cada processador possui sua memória local
• Os pares processador/memória são interconectados
através de uma rede de interconexão (quadro 8)
• Quando um processo necessita de dados de outro
processo?
– Utiliza troca de mensagens através da rede
– Memórias não-locais não podem ser acessadas diretamente
– Classificação
• NORMA (NOn-Remote Memory Access)
Processamento de Alto Desempenho – Prof. Mateus Raeder
Máquinas Paralelas
• Diversas formas de construir uma máquina paralela
• Algumas classificações de máquinas paralelas
–
–
–
–
–
–
PVP
SMP
DSM
MPP
NOW
COW
Processamento de Alto Desempenho – Prof. Mateus Raeder
Máquinas Paralelas
• PVP (Parallel Vector Processor)
– Processadores especiais para operações vetoriais
• Operações aritméticas, por exemplo
– Aplicações matemáticas e simulações físicas obtêm ganho
significativo de desempenho
• SMP (Symmetric Multi Processing)
– Constituída de processadores comerciais (comuns)
– Conectados através de um barramento de alta velocidade à uma
memória compartilhada
• Mesma velocidade no acesso à memória (Symmetric)
• Utilização do barramento exclusivo
Processamento de Alto Desempenho – Prof. Mateus Raeder
Máquinas Paralelas
• DSM (Distributed Shared Memory)
– Possuem uma memória distribuída fisicamente entre as máquinas
– Porém, com um único espaço de endereçamento
• Todas enxergam as memórias como se fossem uma só
– Conectados por uma rede de acesso mais lento ao meio
• Acesso mais rápido nas posições mais próximas
–
Importância da localização dos dados
• MPP (Massive Parallel Processors)
– PVP utilizam uma quantidade pequena de processadores de alto
desempenho
– MPP utiliza uma grande quantidade (milhares) de processadores de baixo
ou médio desempenho para aumentar o desempenho
• Quantidade ao invés de qualidade
• Cada processador possui uma memória local (troca de mensagens)
Processamento de Alto Desempenho – Prof. Mateus Raeder
Máquinas Paralelas
• NOW (Network Of Workstations)
– Conjunto de estações de trabalho interligadas por uma rede padrão
– Tem custo muito baixo
– Processadores possuem memória privada, restringindo o acesso a sua
memória local
• Troca de mensagens
– Redes padrão não otimizadas para alto desempenho
• Comunicação mais lenta
• Gargalo
– Utilização não visa alto desempenho, mas sim compartilhamento de
recursos
• Diferente do MPP, dificilmente encontra-se NOW para aplicações paralelas
• Uso acadêmico
Processamento de Alto Desempenho – Prof. Mateus Raeder
Máquinas Paralelas
• COW (Cluster Of Workstations)
– Evolução da NOW
– Também composto por estações de trabalho, porém, projetado para
prover alto desempenho
• Estações conectadas por uma rede de alto desempenho
• Facilitando a comunicação entre os processos
– Muitos sistemas COW descartam periféricos como monitor, teclado e
mouse
• Headless workstations (estações de trabalho sem cabeça)
• Toda estrutura para o desenvolvimento paralelo
Processamento de Alto Desempenho – Prof. Mateus Raeder
Requisitos básicos de PAD
• Quando falamos de programação paralela, alguns fatores
básicos devem ser atendidos
– Desempenho
– Portabilidade
– Modularidade
• Primordialmente, buscamos DESEMPENHO
– Alguns minutos de processamento podem fazer diferença
– Aplicações meteorológicas, por exemplo
• Possuem alto custo computacional
• De nada adianta conseguir calcular amanhã a previsão do tempo
para hoje
• Precisão pode ser diminuída
- Aumenta desempenho, mas diminui credibilidade
Processamento de Alto Desempenho – Prof. Mateus Raeder
Requisitos básicos de PAD
• A existência de diversas arquiteturas paralelas exige
PORTABILIDADE
– O programa paralelo deve se adaptar a certa variedade de
máquinas
– Programador não deve se preocupar com soluções específicas
• A MODULARIDADE procura facilitar o desenvolvimento
– Aplicações são complexas
– Divisão em módulos facilita a implementação
• Isola componentes
• Proporciona facilidade na manutenção do programa
Processamento de Alto Desempenho – Prof. Mateus Raeder
Medidas de Desempenho
• Quando utilizamos uma solução paralela, devemos constatar:
– Se obtivemos ganho ou perda de desempenho
– Se existe sub/sobre-utilização de recursos
• Se o balanceamento de carga foi adequado
• Foram criadas métricas de desempenho para quantificar
estas informações
– Fator de aceleração (speedup)
– Eficiência (efficiency)
– Desequilíbrio de carga
Processamento de Alto Desempenho – Prof. Mateus Raeder
Speedup
• É o fator de aceleração da versão paralela em relação à
sequencial
• Quantifica o ganho de desempenho
– Calculando-se o speedup, temos quantas vezes a versão
paralela é mais rápida que a sequencial
– Calculado para cada processo
– Speedup ideal: com x processos, x vezes mais rápido
– Gera uma curva em um gráfico
speedup =
TempoSequencial
TempoParalelo
Se speedup > 1: versão paralela reduziu o tempo
Se speedup < 1: versão paralela aumentou o tempo
Processamento de Alto Desempenho – Prof. Mateus Raeder
Eficiência
• Indica se os recursos estão sendo bem utilizados
• Razão entre o speedup e o número de processos utilizados
eficiência =
speedup
número de processos
• Idealmente, cada unidade deveria ter ficado 100% ativa
– Devido aos custos de comunicação, processamento,
inicialização, esta eficiência ideal não é alcançada
Processamento de Alto Desempenho – Prof. Mateus Raeder
Desequilíbrio de carga
• Distribuição do trabalho entre os recursos
• O trabalho deve ser distribuído de forma a ocupar sempre
todos os processos
– Isto não ocorre quando alguns processos possuem muito mais
carga que outros
– Sub-utiliza uns, sobrecarrega outros
– Perda de desempenho (desperdício de poder computacional)
– Má divisão do trabalho, execução em ambientes heterogêneos,
etc
– Técnicas de balanceamento de carga
Processamento de Alto Desempenho – Prof. Mateus Raeder