ARQUITETURA DE COMPUTADORES II
Medidas de Desempenho
Prof. César Augusto M. Marcon
2 / 23
Índice
1. Introdução
2. Medidas de Desempenho
3 / 23
Introdução
• Aumento de desempenho dos PCs não atende diversas aplicações
– Previsão do tempo
– Prospecção de petróleo (análise de local para perfuração de poços de
petróleo)
– Simulações físicas (aerodinâmica; energia nuclear)
– Matemática computacional (análise de algoritmos para criptografia)
– Bioinformática (simulação computacional da dinâmica molecular de
proteínas)
• Problemas
– Falta de processamento
– Falta de memória
• Alternativas dos usuários destas aplicações
–
–
–
–
Modelos mais abstratos
Heurísticas
Aceleradores (HW especial)
Executar aplicação em máquinas mais poderosas (arquiteturas especiais ou
arquiteturas paralelas)
4 / 23
Arquiteturas Especiais
• Melhoram desempenho, replicando número de unidades
ativas (normalmente processadores)
• Principal objetivo
– Reduzir o tempo total de execução
• Outros objetivos
– Tolerância a falhas
• Reduz a probabilidade de falhas em cálculos  cada unidade ativa
calcula o mesmo problema  no final ocorre uma votação
– Modelagem
• Reduz a complexidade da modelagem e implementação da aplicação,
utilizando uma linguagem que expresse paralelismo
– Aproveitamento de recursos
• Aproveita melhor os recursos disponíveis, executando uma aplicação
com múltiplos processos
5 / 23
Processamento Paralelo
• Dificuldades inerentes ao paralelismo
– Dificuldade de alimentar vários processadores com dados
• Gera custo de comunicação entre processadores
– Programas mais complexos devido ao particionamento em unidades
ativas
• O particionamento do programa não é realizado pelo SO
– Dificuldade em extrair o paralelismo da aplicação
• Programa que não foi preparado com paralelismo não executa
mais rápido, apenas por estar em máquina paralela
• Exemplos de programas paralelos
– Aplicação com várias threads
– Aplicação usando RMI (Remote Method Invocation)
– Aplicação com vários processos que se comunicam por sockets
6 / 23
Níveis de Exploração de Paralelismo
• Exploração de paralelismo está presente nos diversos
níveis de um sistema
7 / 23
Granularidade de Paralelismo
• Definição
– Grau de agrupamento de funcionalidades em unidades ativas
• Grão grosso
– Particionamento em unidades de trabalho grandes
– Alto custo de processamento. Processador é a parte mais complexa
do sistema
– Baixo custo de comunicação. Infra-estrutura de comunicação de
menor complexidade
• Grão fino
– Particionamento em unidades de trabalho pequenas
– Baixo custo de processamento. Processador é a parte menos
complexa do sistema
– Alto custo de comunicação. Infra-estrutura de comunicação de alta
complexidade
• Grão médio
– Caso intermediário entre os dois anteriores
8 / 23
Processamento Paralelo x Distribuído
• Ambas áreas têm os mesmos complicadores
– Custo de comunicação
– Distribuição dos dados
– Dependências
• Motivações diferentes
– Motivação do processamento paralelo é o ganho de
desempenho
• Unidades ativas estão normalmente na mesma máquina 
custos de comunicação menores (baixa latência)
– Motivação do processamento distribuído é a modelagem
e o aproveitamento de recursos
• Unidades ativas estão normalmente afastadas  custos de
comunicação maiores (alta latência)
9 / 23
Processamento Paralelo x Distribuído
• Aumento de unidades ativas não aumenta
necessariamente o desempenho
– Quantidade de trabalho e arquitetura alvo limitam o
número de unidades ativas usadas eficientemente
– Muitas unidades ativas para uma quantidade limitada de
trabalho prejudica o desempenho do sistema
• O tempo pode aumentar!!
– Complicadores
•
•
•
•
Dependências de dados
Distribuição dos dados
Sincronização
Áreas críticas
10 / 23
Exemplo
• Construção de um muro
–
–
–
–
–
1 pedreiro faz este muro em 3 horas
2 pedreiros fazem em 2 horas
3 pedreiros fazem em 1 hora e meia
4 pedreiros fazem em 2 horas (aumentou o tempo !!!)
8 pedreiros fazem em 3 horas e meia (tempo pior que a
versão sem paralelismo !!!)
– Avaliação dos dados obtidos e porque ocorreu o
aumento de tempo?
– Incidência de muitos complicadores  ganho de
desempenho não é proporcional ao acréscimo de
unidades ativas
• Duplicação do número de pedreiros de 1 para dois não reduz o
tempo de execução pela metade
11 / 23
Exemplo
• Complicadores encontrados e a analogia com a
computação paralela
– O muro só pode ser feito de baixo para cima
• Dependência de dados
– Os tijolos têm que ser distribuídos entre os pedreiros
• Distribuição dos dados
– Um pedreiro não pode levantar o muro do seu lado muito
na frente dos outros pedreiros. Ritmo de subida do muro
é dado pelo pedreiro mais lento
• Sincronização
– Se só existir um carrinho com cimento este será
disputado por todos os pedreiros
• Áreas críticas
12 / 23
Índice
1. Introdução
2. Medidas de Desempenho
13 / 23
Medidas Básicas de Desempenho
• Definição
– Índices que indicam o desempenho de diferentes aspectos de um
sistema paralelo
• Medidas
– Desempenho da aplicação
• Aqui considera-se o efeito conjunto do processamento, armazenamento
e comunicação
– Desempenho da rede de interconexão
• Aqui considera-se o efeito apenas da comunicação
14 / 23
Desempenho da Aplicação
Speed-Up (Fator de Aceleração)
• Indica quantas vezes o programa paralelo é mais rápido que a
versão seqüencial para executar uma dada tarefa
• É calculado pela razão entre o melhor tempo seqüencial e o melhor
tempo da versão paralela
SpeedUp(p)
ou
SU(p) = TS / TP(p)
– Onde:
• TS é o tempo de execução da aplicação na versão seqüencial
• TP é o tempo de execução na versão paralela
• p é o número de unidades ativas (processadores) utilizadas
• Se SU > 1 a versão paralela reduziu o tempo de execução (ficou mais
rápido que a seqüencial)
• Se SU < 1 a versão paralela aumentou o tempo de execução (ficou mais
lenta que a seqüencial)
15 / 23
Desempenho da Aplicação
Speed-Up
• Cada aplicação tem sua curva que depende do trabalho e da
incidência de complicadores
• Todo o algoritmo de uma aplicação tem um número de unidades
ativas ideal para a obtenção do melhor desempenho em uma dada
arquitetura alvo
– Não sendo verdade que quanto mais unidades ativas melhor
16 / 23
Desempenho da Aplicação
Eficiência
• Indica a taxa de utilização média das unidades ativas
• Mostra se os recursos foram bem aproveitados
• É calculado pela razão entre o Speed-Up e o número de unidades
ativas utilizadas
Eficiência(p)
ou
E(p) = SU(p) / p
• Normalmente, as unidades ativas ficam parte de seu tempo
esperando por resultados de vizinhos
– Reduz sua taxa de utilização e conseqüentemente a eficiência
17 / 23
Desempenho da Aplicação
Eficiência
• Eficiência ideal
– Cada unidade ativa com 100% do tempo ativa (linha azul)
• A melhor taxa de utilização média não significa o menor
tempo de execução
– Exemplo: o menor tempo de execução ocorreu com 11 unidades
ativas e a melhor taxa de utilização média com 5 unidades ativas
18 / 23
Desempenho da Rede de Interconexão
Latência
• Tempo necessário para enviar mensagem através da
rede de interconexão
• Inclui tempo de empacotar e desempacotar dados mais
tempo de envio propriamente dito
• A latência aumenta a medida que a quantidade de dados
a serem enviados aumenta
– O aumento não é linear
• A componente do tempo referente ao custo de empacotamento e
desempacotamento não varia tanto em relação ao tamanho da
mensagem como a componente de custo de envio pela rede
19 / 23
Desempenho da Rede de Interconexão
Vazão
• Expressa a capacidade da rede de “bombear” dados
entre dois pontos
• Unidade
– Quantidade de dados por unidade de tempo
– Ex: 10 MBytes/segundo (10MB/s)
• A vazão (V) é afetada pela “largura” (L) do canal de
comunicação (bits) e pela freqüência (F) da transmissão
dos dados (MHz)
VLF
20 / 23
Desempenho da Rede de Interconexão
• Exemplos:
– Latência de 1 mensagem de 1 byte entre máquinas rodando GNU/Linux
ligadas por Fast-Ethernet é de aproximadamente 150 µs
– A melhor vazão, obtida com uma mensagem de aproximadamente 64 KB, é
em torno de 10 MB/s. Próximo do limite teórico (12,5 MB = 100 Mbits/s)
21 / 23
Exercícios
1. Mostre três exemplos onde a simplificação de um modelo computacional pode
diminuir o tempo de execução da aplicação
2. Comente o efeito da simplificação em cada exemplo
3. Defina processamento paralelo
4. Comente os objetivos de arquiteturas paralelas
5. O que normalmente acontece com o consumo de energia quando comparamos
uma implementação seqüencial com uma paralela?
6. Comente a afirmação: - ”Comparando duas máquinas com o mesmo
desempenho, é possível notar que o consumo de energia da máquina
paralela é menor que a máquina sem paralelismo, devido a freqüência de
operação”
7. Existe alguma forma de paralelismo que não objetiva aumentar o desempenho
da máquina? Fale sobre esta
8. Comente a afirmação: - ”A replicação de unidades de entrada e saída é um
paralelismo em nível de aplicação”
22 / 23
Exercícios
9. Desenhe o comportamento do speed-Up real e do speed-Up ideal para uma
aplicação paralela. Por que existe diferença entre estas linhas? Por que esta
diferença com o aumento do número de processadores?
10. Considere que o Sistema A foi implementado com 4 processadores PXY
paralelos e o Sistema B foi implementado com apenas 1 processado PXY.
Teoricamente, quantas vezes um programa projetado para operar sobre o
Sistema B seria mais rápido se operasse sobre o Sistema A?
11. Desenhe o speed-up e a eficiência para um sistema, cujo tempo de execução de
uma aplicação se comporta conforme a fórmula abaixo. Com quantos
processadores obteremos a máxima eficiência? Por quê? Discuta os resultados.
Considere a variação de 1 a 7 processadores:
T(n) = TP / n + TC x (n-1) + TO x (n-1)2
Com:
T(n) – tempo de execução da aplicação com n processadores
n – número de processadores
TP – tempo de processamento (considerar 100 ns)
TC – tempo de comunicação (considerar 10 ns)
TO – tempo devido a colisões (considerar 1 ns)
12. Faça o mesmo do exercício anterior para a fórmula abaixo
T(n) = TP / n + TC x (n-1)
23 / 23
Exercícios
13. Analise o exemplo de construção de um muro descrito a seguir e faça uma
comparação com os seguintes problemas da computação paralela: (a)
dependência de dados, (b) distribuição de dados, (c) sincronização e (d) áreas
críticas
Um pedreiro faz o muro em 3 horas,
Dois pedreiros fazem em 2 horas,
Três pedreiros em 1 hora e meia,
Quatro pedreiros em 2 horas (aumentou o tempo !!!)
14. Construa dois exemplos semelhantes a construção de um muro, mostrando a
analogia com os sistemas paralelos
15. Quais são os complicadores para que os sistemas distribuídos não consigam
obter altas taxas de processamento?
ARQUITETURA DE COMPUTADORES II
Extras
Prof. César Augusto M. Marcon
25 / 23
Desempenho da Aplicação
Speed-Up – Entendendo Melhor
• Arquiteturas, onde tarefas podem ser distribuídas de forma
eqüitativa entre processadores, TP(p) pode ser aproximado por:
TP(p)  TS / p + TCONTROLE + TCOMUNICAÇÃO
– Onde:
• TS / p é o tempo de execução seqüencial dividido nos p processadores
• TCONTROLE é o tempo gasto para controlar a operação com as máquinas paralelas
• TCOMUNICAÇÃO é o tempo gasto para troca de dados e controle entre as máquinas
paralelas
• As parcelas TCONTROLE e TCOMUNICAÇÃO é que geram a redução do
speed-up a partir de um certo número de processadores
– Estas parcelas são fortemente dependentes da arquitetura alvo
• Avaliar o Speed up considerando que o tempo de execução é
composto pelos tempos de processamento, comunicação e
armazenamento, muitas vezes requer modelos muito complexos,
que dependem fortemente da arquitetura alvo
26 / 23
Desempenho da Aplicação
Speed-Up – Exemplo de Modelo
• Implementar um modelo aproximado para estimar o speed-up,
considerando as arquiteturas seqüencial e paralela apresentadas
abaixo
P1
Mem
P
Mem
TS = n  L + C + P + c + N  E
P2
Pc
Pn
Onde:
– n é o número de dados lidos
– L é o tempo de leitura de um dado
– C é o tempo de comunicação para leitura (o caminho de leitura não é
necessariamente o caminho de escrita)
– P é o tempo de processamento em um processador
– c é o tempo de comunicação para escrita
– N é o número de dados para escrever
– E é o tempo de escrita de um dado
27 / 23
Desempenho da Aplicação
Speed-Up – Exemplo de Modelo
TCONTROLE + TCOMUNICAÇÃO = (p  m  C’ + p  M  c’) + PPc
Onde:
– m é o número de dados transmitido de cada P para o Pc;
– C’ é o tempo de comunicação de cada P para o Pc;
– M é o número de dados transmitido do Pc para cada P;
– c’ é o tempo de comunicação para escrita;
– PPc é o tempo de comunicação do Pc para cada P
Como:
TS / p = (n  L + C + P + c + N  E) / p
E:
TP(p)  TS / p + TCONTROLE + TCOMUNICAÇÃO
Então:
TP(p)  (n  L + C + P + c + N  E) / p + (p  m  C’ + p  M  c’) + PPc
28 / 23
Desempenho da Aplicação
Speed-Up – Exemplo de Modelo
• Considerações para simplificar o modelo:
– Supondo que os tempos de comunicação para transmissão de dados
sejam iguais entre quaisquer elementos do sistema, então:
C = c = C’ = c’
– Supondo que os tempos de escrita e leitura nas memórias sejam iguais,
então:
L=E
– Supondo que o número de dados transmitido entre controle e
processadores seja igual, independente de direção, então:
m=M
– Supondo, também, que o número de bytes de leitura e escrita seja igual,
então:
n=N
• Neste caso, poderemos reescrever TP(p) como:
TP(p) = (2  N  L + 2  C + P) / p + (2  p  M  C) + PPc
29 / 23
Desempenho da Aplicação
Speed-Up – Exemplo de Modelo
• Como SU(p) = TS / TP(p), então:
2NL+2C+P
SU(p) =
(2  N  L + 2  C + P) / p + (2  p  M  C) + PPc
• Ou:
2  N  L  p + 2  C  p + P p
SU(p) =
2  N  L + 2  C + P + 2  p2  M  C + PPc  p
•
Novas considerações:
–
Onde estão as memórias e os processadores?
• On-chip?
• Em chips distantes?
–
Qual a infra-estrutura de comunicação?
• Conexão dedicada?
• Barramento?
• Redes especiais?
•
Como estes elementos afetam o desempenho do sistema?
30 / 23
Desempenho da Aplicação
Speed-Up – Exemplo de Modelo
• Supondo comunicação toda intrachip e ordens de grandeza menor que
o processamento, então:
C << P  C  0
• Daí:
SU(p) =
p  (2  N  L + P)
2  N  L + P + PPc  p
•
Nota-se que, mesmo com diversas simplificações do modelo, a
dependência no volume de dados e velocidade de escrita e leitura são
determinantes para o cálculo do SpeedUp  impedindo que o mesmo
seja determinado apenas pela capacidade de processamento do sistema
31 / 23
•
Desempenho da Aplicação
Speed-Up – Exemplo de Modelo
Considerações finais:
– Aplicações podem ser CPU-bounded ou IO-bounded. No primeiro caso n * L << P,
enquanto que no segundo caso P << n * L, o que permite novas simplificações no
modelo usado
SU(p) =
pP
p2NL
SU(p) =
2  N  L + PPc  p
P + PPc  p
•
O Speed-up ideal pode ser obtido se o peso do processamento de controle é
insignificante frente ao tempo de execução de uma tarefa (PPc << P  PPc  0):
SU(p) =
p  (2  N  L + P)
(2  N  L + P)
=p