Upload
others
View
11
Download
0
Embed Size (px)
Citation preview
05/10/11
1
Avaliação de Desempenho Planejamento de Experimentos 2
Aula 2
Marcos José Santana Regina Helena Carlucci Santana
Universidade de São Paulo Instituto de Ciências Matemáticas e de Computação
Departamento de Sistemas de Computação
Etapas a serem consideradas 1. Estudar o sistema e definir os
objetivos 2. Determinar os serviços oferecidos pelo
sistema 3. Selecionar métricas de avaliação 4. Determinar os parâmetros que afetam o
desempenho do sistema 5. Determinar o nível de detalhamento da
análise 6. Determinar a Técnica de Avaliação
apropriada 7. Determinar a carga de trabalho
característica 8. Realizar a avaliação e obter os
resultados 9. Analisar e interpretar os resultados 10. Apresentar os resultados
Planejamento de
Experimento
Análise dos
Resultados
Técnica de Avaliação
Lembrando.....
05/10/11
2
Conteúdo
1. Planejamento de Experimentos – Motivação – Introdução à Avaliação de Desempenho – Etapas de um Experimento – Planejamento do Experimento
• Conceitos Básicos • Carga de trabalho • Modelos para Planejamento de Experimento
2. Análise de Resultados
3. Técnicas para Avaliação de Desempenho
Tipos de Planejamento de Experimentos
• Planejamento Simples
• Planejamento Fatorial completo
• Planejamento Fatorial parcial
05/10/11
3
Tipos de Planejamento de Experimentos
Planejamento Simples
– Iniciar com uma configuração inicial – Fixar todos os fatores e variar um fator por vez – Verificar que fator afeta o desempenho
– Fácil de ser implementado – Não permite verificar a relação entre os fatores – Estatisticamente não eficiente
Tipos de Planejamento de Experimentos
Planejamento Simples
– Para um experimento com K fatores e ni níveis no fator i, tem-se:
– Exemplo do servidor de arquivos
∑=
−+=K
iinn
1
)1(1
05/10/11
4
Fator 1 Microprocessador a ser utilizado 3 níveis: Pentium IV; Athlon XP; Pentium IV com Hyper Thread
Fator 2 Quantidade de Memória 4 níveis: 512 M bytes; 1 G bytes; 2G bytes; 4G bytes
Fator 3 Quantidade de Cache 3 níveis: 256 K bytes; 512 K bytes; 1 M bytes
Fator 4 Número de Discos: 3 níveis: Dois; Três; Quatro
Planejamento de Experimentos Exemplo do Servidor de arquivos – 4 fatores
n= 1+(3-1)+(4-1)+(3-1)+(3-1) = 10
Tipos de Planejamento de Experimentos
Planejamento Simples
– Não recomendado
– Muito utilizado
05/10/11
5
Tipos de Planejamento de Experimentos
Planejamento Simples - Não recomendado – Porque?
– Ex. Aquário
Tipos de Planejamento de Experimentos
Planejamento Simples - Não recomendado – Porque?
– Fatores: 1. Número de garrafas de cerveja: 10, 100, 1000 2. Espessura do vidro: 2mm, 5mm, 10mm 3. Quantidade de gelo: 0,5 kg, 1Kg, 10Kg
– Variável de Resposta: Tempo necessário para diminuir a temperatura de cerveja em 30 graus
05/10/11
6
Tipos de Planejamento de Experimentos
Planejamento Simples - Não recomendado –
– 1o. Experimento, • fixo: Esp = 5mm; no. Garrafas = 10 • gelo = 0,5 Kg -> Saída = 2 minutos • gelo = 1 Kg -> Saída = 2 minutos • gelo = 10Kg -> Saída = 2minutos
– Mas.... 2o. Experimento, • fixo: Esp = 5mm; no. Garrafas = 100 • gelo = 0,5 Kg -> Saída = 30 minutos • gelo = 1 Kg -> Saída = 20 minutos • gelo = 10 Kg -> Saída = 20 minutos
Tipos de Planejamento de Experimentos
Planejamento Simples - Não recomendado – Porque?
– 3o. Experimento, • fixo: Esp = 5mm; no. Garrafas = 1000 • gelo = 0,5 Kg -> Saída = XX minutos • gelo = 1 Kg -> Saída = 3horas • Gelo = 10Kg -> Saída = 1 hora
05/10/11
7
Tipos de Planejamento de Experimentos
Planejamento Totalmente Fatorial – Utiliza todas as combinações considerando
todos os fatores e todos os níveis
– Para um experimento com K fatores e ni níveis no fator i, tem-se:
– Para o exemplo da estação de trabalho tem-se: n = 3 (CPU)*4(memória)*3(cache)*3(no. discos) n= 108
∏=
=K
iinn
1
Tipos de Planejamento de Experimentos
Planejamento Totalmente Fatorial
Vantagens • Todos os fatores são avaliados • Pode-se determinar o efeito de qualquer fator • Interações entre fatores podem ser verificadas
Desvantagens • Grande número de experimentos • Alto custo para avaliação
05/10/11
8
Planejamento Totalmente Fatorial Formas para minimizar custos
1. Reduzir o número de níveis de cada fator • Altamente recomendada • Selecionar dois níveis para cada fator a ser
analisado – número de experimentos reduzido para 2k
• Analisar os resultados e selecionar os fatores primários
• Analisar os fatores primários para um número maior de níveis
Planejamento Totalmente Fatorial Formas para minimizar custos
2. Reduzir o número de fatores • Deve ser implementada com cuidado. Por
exemplo, utilizando forma 1. • Se não for utilizada uma metodologia adequada
podem estar sendo desconsiderados fatores com grande influência para as variáveis de resposta
05/10/11
9
Planejamento Totalmente Fatorial Formas para minimizar custos
3. Utilização do método do Fatorial Parcial • Parte dos experimentos são excluídos • Podem ser eliminadas comparações em que se
sabe, a interação não existe ou é insignificante • Por exemplo, no servidor de arquivos tem-se
108 experimentos. Pode-se dizer que o número de discos não tem relacionamento com a quantidade de cache
• Mais rápido • Obtém-se menos informações
Método Fatorial • Pelo método fatorial pode-se ter k fatores com
ni níveis para cada fator i • Para valores elevados de K e ni o custo da
avaliação pode tornar-se inviável, principalmente lembrando-se que diversas execuções de cada experimento devem ser consideradas.
• Forma recomendada: Selecionar poucos fatores e 2 níveis por fator.
• Para entender a abordagem utilizada para a análise inicia-se com 2 fatores contendo 2 níveis em cada um - 22
05/10/11
10
Projeto Fatorial 22 • Análise através do modelo de regressão • Considere um problema analisando dois fatores
(A e B) • Quatro experimentos são efetuados obtendo-se
os valores y1, y2, y3, y4 • Os quatro experimentos consideram a seguinte
seqüência Experimento A B y
1 -1 -1 y1 2 1 -1 y2 3 -1 1 y3 4 1 1 y4
Projeto Fatorial 22 • Modelo para projeto 22 é dado por:
y = q0+ qAxA + qBxB + qABxAB • Substituindo-se as quatro observações no
modelo, obtêm-se os valores de q0, qA, qB, qAB
q0 = ¼ *(y1 + y2 + y3 + y4) qA = ¼ *(-y1 + y2 - y3 + y4) qB = ¼ *(-y1 - y2 + y3 + y4) qAB = ¼ *(y1 - y2 - y3 + y4)
05/10/11
11
Projeto Fatorial 22 • A partir dos valores de q0, qA, qB, qAB pode-se determinar a soma dos quadrados • A soma dos quadrados dará a variação total das variáveis de resposta e as variações devido a influência do fator A, do fator B e da interação entre A e B • Variância Total de y ou
Soma dos Quadrados Total –
ou
∑=
−=22
1
2)(i
i yySST
222222 222 ABBA qqqSST ++=
Projeto Fatorial 22 1. A soma das entradas em
cada coluna = 0
Experimento A B y 1 -1 -1 y1 2 1 -1 y2 3 -1 1 y3 4 1 1 y4
2. Soma dos quadrados em cada coluna = 4
3. Produto interno de cada duas colunas = 0
05/10/11
12
Projeto Fatorial 22
A Média da Amostra é dada por:
Modelo considerado:
y = q0+ qAxA + qBxB + qABxAB
Projeto Fatorial 22 Variação total - SST:
05/10/11
13
Projeto Fatorial 22 Soma dos Quadrados devido a influência do Fator A Soma dos Quadrados devido a influência do Fator B Soma dos Quadrados devido a interação entre os
Fatores A e B 222 ABqSSAB =
222 BqSSB =
222 AqSSA =Influência do Fator A = SSA / SST
Influência do Fator B = SSB / SST
Influência da interação entre os Fatores A e B = SSAB/SST
Projeto Fatorial 22 Interpretações possíveis a partir desses resultados:
– Média da variável de resposta – q0 – Qual a variação da variável de resposta devido ao
fator A – Qual a variação da variável de resposta devido ao
fator B – Qual a variação devido a interação entre os fatores A
e B – De que fator a variável de resposta é mais
dependente? – Algum dos fatores observados pode ser desprezado? – A interação entre os fatores observados é
considerável?
05/10/11
14
Projeto Fatorial 22 Exemplo: Avaliação de duas redes de comunicação
em uma máquina paralela com: • 16 processadores • Escalonamento aleatório • Não existe problema de acesso a memória –
interleaving de memória infinito • Redes utilizam Chaveamento de circuito – conexão
é estabelecida da fonte ao destino e pacotes são enviados (ex. telefone)
• Requisições não atendidas são bloqueadas
Fatores Considerados
Duas formas de acesso a memória – Fator B
• Aleatório – probabilidade uniforme de referenciar cada posição de memória – Nível = -1
• Matriz – simula uma multiplicação de matrizes – Nível = 1
Duas Redes de Interconexão – Fator A • Omega – Nível = 1 • Crossbar – Nível = -1
05/10/11
15
Tipos de Redes de Interconexão Consideradas
Resultados Obtidos Variáveis de Resposta
– Throughput - T – Ciclos para transmissão - N – Tempo de Resposta – R
Fatores Variáveis de Resposta A (rede) B(Acesso) T N R
-1(C) -1(A) 0,6041 3 1,655 1(O) -1 (A) 0,7922 2 1,262 -1(C) 1(M) 0,4220 5 2,378
1(O) 1 (M) 0,4717 4 2,190
05/10/11
16
Fatores Variáveis de Resposta
I A (rede) B(Acesso) AB T N R
1 -1(C) -1(A) 1 0,6041 3 1,655
1 1(O) -1 (A) -1 0,7922 2 1,262
1 -1(C) 1(M) -1 0,4220 5 2,378
1 1(O) 1 (M) 1 0,4717 4 2,190
Parâmetro Média Estimada Variação % T N R T N R
q0 0,5725 3,5 1,871
qA 0,0595 -0,5 -0,145 17,2 20 10,9
qB -0,1257 1,0 0,413 77,0 80 87,8
qAB -0,0346 0 0,051 5,8 0 1,3
SSA/SST=0.05952 /(0,05952+0,12572+0,03462)
Parâmetro Média Estimada Variação % T N R T N R
q0 0,5725 3,5 1,871
qA 0,0595 -0,5 -0,145 17,2 20 10,9
qB -0,1257 1,0 0,413 77,0 80 87,8
qAB -0,0346 0 0,051 5,8 0 1,3
• Média das variáveis de Resposta – q0 • Influência de cada fator • Fator com maior influência
• Grau de interação entre os fatores
05/10/11
17
Mais Um Exemplo...
Avaliação de Desempenho do Gerenciador de Banco de Dados MySQL
Trabalho desenvolvido por alunos do Curso de Bach em Ciências da Computação
Avaliação do MySQL
• Objetivo: verificar como o número de usuários executando comandos em paralelo e o tamanho do banco de dados influenciam no desempenho do sistema
• 2 Fatores: – Tamanho do Banco: 50.000, 100.000, 200.000 – Quantidade de usuários: 5, 10, 20 e 50
• AMD Athlon 64 com 512 MBs de RAM
05/10/11
18
Avaliação do MySQL
• Procedimento Utilizado:
– Configuração do servidor MySQL – Criação de um Banco de Dados – Programa para inserir nomes na tabela – Programa que realiza n consultas no
banco – Programa que ativa k vezes a consulta
Avaliação do MySQL
Variável de Saída – tempo para executar um conjunto de consultas dividido por n
Para 5, 10 e 20 usuários – n = 20
Para 50 usuários – n = 5
Tem-se k usuários realizando consultas no banco de dados em paralelo
05/10/11
19
Avaliação do MySQL
Alguns Resultados....
Avaliação do MySQL
Alguns Resultados....
05/10/11
20
Avaliação do MySQL
Alguns Resultados....
Avaliação do MySQL Alguns Resultados....
05/10/11
21
Avaliação do MySQL
Alguns Resultados....
Avaliação do MySQL Alguns Resultados....
05/10/11
22
Projeto Fatorial 2k • Utilizado para avaliar experimentos com k
fatores com 2 níveis cada • Análise similar ao 22 Para k = 3
)(2 22222223 ABCBCACABCBA qqqqqqqSST ++++++=
232 AqSSA=232 BqSSB =
232 ABCqSSABC =232 ABqSSAB =
232 CqSSC =
........
Projeto Fatorial 2k Problema com o Projeto Fatorial 2k
Para k = 2 – 4 experimentos Para k = 3 - 8 experimentos Para k = 4 – 16 experimentos ........
Solução – Planejamento Fatorial Parcial - 2k -p
1. Muitos fatores devem ser avaliados 2. Sabe-se que existem fatores que não
interagem 3. Deseja-se determinar quais fatores
realmente influenciam no resultado
05/10/11
23
Planejamento Fatorial Parcial - 2k -p
k – número total de fatores a serem considerados p – número inteiro - quantas dimensões serão
desprezadas Exemplo: p=1 – reduz os experimentos a metade p=2 – um quarto dos experimentos k=7 – 128 experimentos p=4 – 8 experimentos
Neste caso não é possível avaliar as interações
k=7 – 128 experimentos p=5 – 16 experimentos
Algumas interações podem ser avaliadas
Projeto Fatorial 22 1. A soma das entradas em
cada coluna = 0
Experimento A B y 1 -1 -1 y1 2 1 -1 y2 3 -1 1 y3 4 1 1 y4
2. Soma dos quadrados em cada coluna = 4
3. Produto interno de cada duas colunas = 0
05/10/11
24
Planejamento Fatorial Parcial - 2k -p
Exemplo (Jain) 27 -4
Devo satisfazer as mesmas condições que 22
Modelo Similar:
Planejamento Fatorial Parcial - 2k -p
Exemplo (Jain) 27 -4
05/10/11
25
Planejamento Fatorial Parcial - 2k -p
Exemplo (Jain) 27 -4
37,26 4,74 43,40 6,75 0 8,06 0,03
Variação em porcentagem
Planejamento Fatorial Parcial - 2k -p
Pode-se preparar a tabela para considerar qualquer combinação, desde que atendidas as condições
Exemplo (Jain) 24-1
05/10/11
26
Planejamento Fatorial Parcial - 2k -p
Pode-se preparar a tabela para considerar qualquer combinação, desde que atendidas as condições
Exemplo (Jain) 24-1
Coluna D
Influência do fator D + interação entre A, B e C
Planejamento Fatorial Parcial - 2k -p
Pode-se preparar a tabela para considerar qualquer combinação, desde que atendidas as condições
Exemplo 19.2 (Jain) Considere um sistema que possa ser utilizado para:
• Processamento de textos,
• Processamento de dados interativo,
• Processamento de dados em background Fator Descrição nível -1 nível +1 A Preempção não sim
B Time slice pequeno grande
C Filas (prioridade) uma fila duas filas
D Classes para as tarefas duas filas cinco filas E Justiça (pref. p/ tarefa antiga) desligado ligado
Analisar cada caso independentemente
05/10/11
27
Planejamento Fatorial Parcial - 2k -p
Exemplo 19.2 (Jain)
25-1
Planejamento Fatorial Parcial - 2k -p
Exemplo 19.2 (Jain)
05/10/11
28
Planejamento de Experimento • Planejamento de Experimentos designa toda uma área
de estudos da Estatística que desenvolve técnicas de planejamento e análise de experimentos.
• Existe um grande número de técnicas, com vários níveis de sofisticação e uma grande quantidade de ferramentas visando oferecer as condições necessárias para o planejamento de experimentos.
• Essas técnicas cobrem todas as possibilidades, diversos fatores, diferentes quantidades de níveis , tratamento de replicações, etc.
• Importância dentro de Avaliação de Desempenho – saber como utilizar as técnicas/ferramentas e saber analisar os resultados
Erros Comuns em Experimentos • Uso de apenas um fator por vez – essa
opção simplifica a experimentação mas não permite verificar interações
• Execução de muitos experimentos – em um primeiro passo poucos fatores/níveis devem ser considerados. Com as conclusões iniciais, pode-se considerar outros fatores/níveis
05/10/11
29
Conteúdo
1. Planejamento de Experimentos – Motivação – Introdução à Avaliação de Desempenho – Etapas de um Experimento – Planejamento do Experimento
• Conceitos Básicos • Carga de trabalho • Modelos para Planejamento de Experimento
2. Análise de Resultados
3. Técnicas para Avaliação de Desempenho