Avaliação de Desempenho de Sistemas
Análise de Resultados de Simulação
Paulo Adeodato
Departamento de Informática
Universidade Federal de Pernambuco
© 2000 Paulo Adeodato
Conteúdo
Introdução
 Técnicas de Verificação do Modelo
 Técnicas de Validação do Modelo
 Remoção de Transientes
 Critério de Parada: Estimativa da Variância

© 2000 Paulo Adeodato
Introdução
Passos no desenvolvimento do modelo:
• Verificação do Modelo:
assegura que o modelo está corretamente implementado
• Validação do Modelo:
assegura que o modelo é representativo do sistema real
• Remoção de Transientes:
elimina observações iniciais (transitórias) para garantir que o
sistema atingiu o regime estável (permanente)
• Critério de Parada:
determina quanto deve durar a simulação
© 2000 Paulo Adeodato
Verificação x Validação do Modelo
Verificação do modelo:
• Depuração (debugging) do programa
• Atividade do programador
Validação do modelo:
• Modelo = Mundo Real ?
• Atividade do modelador
Resultam em quatro possibilidades:
• 1. Não-verificado, Inválido
• 2. Não-verificado, Válido
• 3. Verificado, Inválido
• 4. Verificado, Válido
© 2000 Paulo Adeodato
Técnicas de Verificação do Modelo
Simulações são programas longos e nelas se aplicam
técnicas gerais de programação:
de desenvolvimento, depuração e manutenção de programas
de modularidade em procedimentos e interfaces
de estruturação top-down
Simulações são programas que tratam de processos
estocásticos que dificultam a verificação ampla e algumas
restrições facilitam o processo
restrições a casos determinísticos
restrições às mesmas sementes para os geradores de números
aleatórios
© 2000 Paulo Adeodato
Técnicas de Verificação do Modelo-1
1. Projeto Modular Top Down
2. Medidas Antibugs
3. Varrida Estruturada
4. Modelos Determinísticos
5. Execução de Casos Simplificados
6. Trace
7. Apresentação de Gráficos On-Line
8. Teste de Continuidade
9. Testes Degenerativos
10. Testes de Consistência
11. Independência das Sementes
© 2000 Paulo Adeodato
Técnicas de Verificação do Modelo-2
1. Projeto Modular Top Down
• Dividir para Conquistar: Modularidade
• Módulos = Subrotinas, Subprogramas, Procedimentos.
• Módulos têm interfaces bem definidas.
• Podem ser desenvolvidos, depurados e mantidos independentemente.
• Projeto Top-down  estrutura hierárquica  Módulos e submódulos (decomposição recursiva do problema)
© 2000 Paulo Adeodato
Técnicas de Verificação do Modelo-3
2. Medidas Antibugs: Inclusão de verificações
•  Probabilidades = 1
• Jobs remanescentes = Gerados - Servidos
• Contagens de packets, nós e conexões gerados e destruídos
3. Varrida Estruturada:
• Explique o código a outra pessoa ou grupo de pessoas.
• Funciona pela simples explicação a terceiros
4. Modelos Determinísticos:
• Uso de valores constantes em vez de aleatórios
© 2000 Paulo Adeodato
Técnicas de Verificação do Modelo-4
5. Execução de Casos Simplificados: restringir a simulação a
casos analisáveis na teoria
• Apenas um pacote
• Apenas uma fonte
• Apenas um nó intermediário
6. Trace = Lista de eventos e variáveis ordenada no tempo
• Diversos níveis de detalhes:

Trace de eventos

Trace de procedimentos

Trace de variáveis
• O usuário seleciona o nível de detalhes
• Inclui chave de ligar e desligar
© 2000 Paulo Adeodato
Técnicas de Verificação do Modelo-5
7. Apresentação de Gráficos On-Line
• Torna a simulação interessante
• Ajuda a vender os resultados
• Mais compreensível do que o trace
8. Teste de Continuidade
• Se baseia no fato de que pequena mudança na entrada deve
produzir pequena mudança na saída (diferente de sistemas
dinâmicos com bifurcação)
• Executar para diferentes valores de parâmetros de entrada
© 2000 Paulo Adeodato
Técnicas de Verificação do Modelo-6
Teste de Continuidade (continuação)
Antes
© 2000 Paulo Adeodato
Depois
Outras Técnicas de Verificação do Modelo
9. Testes Degenerativos:
Tente usar configurações e cargas extremas:
uma CPU
nenhum disco
ou qualquer combinação
10. Testes de Consistência:
• Resultados semelhantes para entradas que têm o mesmo efeito:
Quatro usuários a 10OMbps x Dois a 20OMbps.
• Construa uma biblioteca de testes de continuidade, degeneração
e consistência
11. Independência das sementes:
• Resultados semelhantes para sementes diferentes
© 2000 Paulo Adeodato
Técnicas de Validação do Modelo-1

Técnicas de validação: asseguram que as hipóteses do
modelo são razoáveis

As técnicas para um problema podem não se aplicar a
outro problema (dependem do modelo)
© 2000 Paulo Adeodato
Técnicas de Validação do Modelo-2

Aspectos a serem validados:
• 1. Hipóteses
• 2. Valores dos parâmetros de entrada e distribuições
• 3. Valores de saída e conclusões

Técnicas:
• 1. Intuição do especialista
• 2. Medidas de um sistema real
• 3. Resultados teóricos
 3 aspectos x 3 técnicas = 9 testes de validação
© 2000 Paulo Adeodato
Técnicas de Validação do Modelo-3
1. Intuição do especialista
• Forma mais prática e comum
• Especialistas = envolvidos no projeto, arquitetura, implementação,
análise, marketing ou manutenção do sistema

Seleção = função do estágio do ciclo de vida do sistema

Apresentar e discutir hipóteses, entradas e saídas

Validar uma parte de cada vez ao longo do processo

Observar se os especialistas conseguem distinguir as medições reais
dos resultados do modelo.
Exemplo:
© 2000 Paulo Adeodato
Técnicas de Validação do Modelo-4
2. Medidas de um Sistema Real
• Comparar as hipóteses, entradas e saídas com o mundo real
(utilizar as técnicas vistas na aula de comparação entre 2
sistemas)
• Freqüentemente é inviável ou muito caro
• Mesmo uma ou duas medidas contribuem para a validação
(diagrama)
© 2000 Paulo Adeodato
Técnicas de Validação do Modelo-5
3. Resultados Teóricos
• Fazer Análise = Simulação sob hipóteses simplificadas
em:
y = ax2 + bx + c
ou
fazer:
b = c = 0 ou x1 = x2 = 0, não a = 0
y = k (x - x1) (x - x2)
• Usados tanto para validar as análises quanto as simulações
• Cautela: ambos podem ser inválidos (não representam o
comportamento do sistema real)
• Usar teoria em conjunto com a intuição de um especialista ou
medições de um sistema real
• Aplicar a teoria para uma configuração maior
• Um "modelo completamente validado" é um mito.
• Pode-se mostrar que o modelo não é inválido para algumas das
situações comparadas. Tentar cobrir os casos mais importantes.
© 2000 Paulo Adeodato
Remoção de Transientes-1


Geralmente estamos interessados no desempenho do
sistema em regime permanente
Ao iniciar a operação, o sistema passa por um regime
transitório até se estabilizar.
Transientes de um circuito linear de 2a ordem (RLC)
superamortecido
subamortecido
© 2000 Paulo Adeodato
Remoção de Transientes-2

No caso geral, não há uma definição exata do que seja o
regime transitório. Assim, teremos soluções heurísticas:
• 1. Execuções longas
• 2. Inicialização apropriada
• 3. Truncamento
• 4. Descarte dos dados iniciais
• 5. Média móvel de replicações independentes
• 6. Médias de lotes (Batch)
© 2000 Paulo Adeodato
Técnicas de Remoção de Transientes-1
1. Execuções Longas:
• Consiste em realizar simulações longas o suficiente para
assegurarem que as condições iniciais não afetem os resultados
• Desperdiçam recursos
• É difícil assegurar que são longas o bastante
2. Inicialização Apropriada:
• Consiste em iniciar a simulação num estado próximo ao do regime
permanente esperado
• Reduz o comprimento e o efeito do regime transiente.
• Exemplo: Considerar jobs na fila em vez de fila vazia. Partir de
uma análise simples ou de simulação anteriores.
Nas técnicas seguintes se supõe que a variabilidade é menor
no regime permanente que no transitório.
© 2000 Paulo Adeodato
Técnicas de Remoção de Transientes-2
3. Truncamento
• Plote o máx-min (range) de n - l observações para l = 1, 2, ...
• Quando a (l + 1)-ésima observação não for nem um mínimo nem
um máximo  encerrou o regime transiente.
Exemplo:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 10, 9, 10, 11, 10, 9, 10, 11, 10, 9,...
Para l = 9, Range = (9, 11), próxima observação = 10
Algumas vezes pode produzir resultados incorretos (se tiver
máximo ou mínimo no transiente)
© 2000 Paulo Adeodato
Técnicas de Remoção de Transientes-3
4. Descarte dos dados iniciais
•
•
•
•
Descartar algumas observações iniciais
Calcular a média
Nenhuma mudança  Regime permanente
Usar diversas replicações para suavizar a média
•
m replicações cada uma de tamanho n
• xij = j-ésima observação da i-ésima replicação
• Passos:
1. Obtenha a trajetória média, tomando a média entre as replicações:
2. Obtenha a média global
© 2000 Paulo Adeodato
1 m
x j   xij , j  1,2,...n
m i 1
1 n
x   xj
n j 1
Técnicas de Remoção de Transientes-4
Descarte dos dados iniciais (continuação)
faça l = 1 e prossiga para o próximo passo
3. Descarte as primeiras l observações e obtenha uma média global a
partir dos restantes n - l valores:
n
1
xl 
nl
4. Calcule a mudança relativa:
x
j l 1
j
xl  x
mudança relativa
x
5. Repita os passos 3 e 4 variando l de l a (n - l)
6. Plote a média global e a mudança relativa
7. Valor de l no joelho = comprimento do intervalo transiente
© 2000 Paulo Adeodato
Técnicas de Remoção de Transientes-5
Descarte dos dados iniciais (continuação)
© 2000 Paulo Adeodato
Técnicas de Remoção de Transientes-6
5. Média Móvel de Replicações Independentes
(Média dentro de uma janela de tempo móvel)
• 1. Obtenha uma trajetória média tomando a média entre
replicações:
Faca k = 1 e prossiga para o próximo passo.
• 2. Plote uma trajetória da média móvel de 2k + 1 valores
• 3. Repita o passo 2, com k = 2,3, ... até que a curva fique suave.
• 4. O valor de j no joelho corresponde ao comprimento da fase
transiente.
© 2000 Paulo Adeodato
Técnicas de Remoção de Transientes-7
© 2000 Paulo Adeodato
Técnicas de Remoção de Transientes-8
6. Médias de Lotes (Batch)
• Execute uma simulação longa e divida-a em partes (batches ou
lotes ) de igual duração
• Estude a variância das médias dos lotes em função do
comprimento do lote
• Passos:
1. Para cada lote, calcule a média do lote:
1 n
xi   xij , j  1,2,...m
n i 1
© 2000 Paulo Adeodato
Técnicas de Remoção de Transientes-9
Médias de Lotes (Batch) (continuação)
• Passos: (continuação)
• 2. Calcule a média total:
1 m
x   xi
m i 1
• 3. Calcule a variância das médias dos lotes:
1 m
2
Var ( x ) 
(
x

x
)

i
m  1 i 1
• 4. Repita os passos 1 e 3, para n = 3, 4, 5,...
• 5. Faca um gráfico da variância em função do comprimento n do
lote.
• 6. O valor de n no qual a variância definitivamente começa a
decrescer, corresponde ao intervalo transiente.
© 2000 Paulo Adeodato
Técnicas de Remoção de Transientes-10
Médias de Lotes (Batch) (continuação)
Motivação:


Comprimento do lote << transiente  média global = média inicial 
Menor variância
Comprimento do lote >> transiente  média global = média do estado
permanente  Menor variância
Ignore os picos seguidos por uma nova subida.
© 2000 Paulo Adeodato
Critério de Parada: Estimativa da Variância-1

Execute até que o intervalo de confiança seja estreito o
bastante
(a, b)  x  z(1 2)Var( x )

Para observações independentes:
Var ( x)
Var ( x ) 
n

Independência não é aplicável a muitas simulações.
Grande tempo de espera para o i-ésimo job  Grande
tempo de espera para o (i +1)-ésimo job
© 2000 Paulo Adeodato
Critério de Parada: Estimativa da Variância-2

Para observações correlacionadas:
Var ( x)
Variância real 
n

Soluções:
• 1. Replicações Independentes
• 2. Médias de Lotes (batches)
• 3. Método Regenerativo
© 2000 Paulo Adeodato
Técnicas de Estimativa da Variância
1-Replicações Independentes
Supõe que as médias de replicações independentes são
independentes
 Conduza m replicações de tamanho n +n0 cada

• 1. Calcule a média para cada replicação:
• 2. Calcule a média geral para todas as replicações:
© 2000 Paulo Adeodato
Técnicas de Estimativa da Variância-1
Replicações Independentes (Continuação)
• 3. Calcule a variância das médias das replicações:
• 4. O intervalo de confiança para a resposta média é:
Mantenha as replicações longas para evitar desperdícios
Normalmente bastam dez replicações
© 2000 Paulo Adeodato
Técnicas de Estimativa da Variância-2
Médias de Lotes (batches)-1
Também chamado de método das subamostras
 Execute uma simulação por um tempo longo

• Descarte o intervalo transiente inicial e divida as observações
restantes em diversos lotes ou subamostras
1. Calcule a média para cada lote:
2. Calcule a média geral:
© 2000 Paulo Adeodato
Técnicas de Estimativa da Variância-2
Médias de Lotes (batches)-2
3. Calcule a variância das médias dos lotes:
4. O intervalo de confiança para a resposta média é:
Menos desperdício do que replicações independentes
Mantenha os lotes longos para evitar correlações
Verificação: Calcule a autocovariância de médias de lotes
sucessivos:
Dobre n até que a autocovariância seja pequena.
© 2000 Paulo Adeodato
Médias de Lotes (batches)-2
Estudo de Caso: Redes de Interconexão
Redes n-cubo binárias indiretas: Usadas para a interconexão entre processadores e memórias
 Rede de dois estágios com fan-out completo.

• Comprimento do lote
•
1
•
2
•
4
•
8
•
16
•
32
•
64
•
128
•
256
•
512
•
1024
Autocovariância
-0,18792
0,02643
0,11024
0,08979
0,04001
0,01108
0,00010
-0,00378
0,00027
0,00069
0,00078
Variância
1,79989
0,81173
0,42003
0,26437
0,17650
0,10833
0,06066
0,02992
0,01133
0,00503
0,00202
Com comprimento 64, auto-covariância < 1% da variância da amostra
© 2000 Paulo Adeodato
Técnicas de Estimativa da Variância-3
Método Regenerativo-1

O comportamento após o período ocioso não depende da
história passada
 Sistema tem um novo nascimento
 Ponto de regeneração

Ciclo de regeneração: Entre dois pontos sucessivos de
regeneração
© 2000 Paulo Adeodato
Técnicas de Estimativa da Variância-3
Método Regenerativo-2
Usar as médias dos ciclos de regeneração
 Problemas:

• Nem todos os sistemas são regenerativos
• Comprimentos diferentes  Cálculo mais complexo
• Média geral  Média das médias dos ciclos

As médias dos ciclos são dadas por:
© 2000 Paulo Adeodato
Técnicas de Estimativa da Variância-3
Método Regenerativo-3

Média geral:

1. Calcule as somas dos ciclos:

2. Calcule a média geral:
© 2000 Paulo Adeodato
Técnicas de Estimativa da Variância-3
Método Regenerativo-4


3. Calcule a diferença entre as somas esperada e
observada dos ciclos:
4. Calcule a variância das diferenças:
© 2000 Paulo Adeodato
Técnicas de Estimativa da Variância-3
Método Regenerativo-5



5. Calcule o comprimento médio dos ciclos:
6. O intervalo de confiança para a resposta média é dado
por:
7. Não há necessidade de remover observações do
período transiente.
© 2000 Paulo Adeodato
Técnicas de Estimativa da Variância-3
Método Regenerativo-5

Problemas:
• 1. Os comprimentos dos cicios são imprevisíveis.
Não dá para planejar o tempo de simulação antecipadamente.
• 2. Encontrar o ponto de regeneração pode demandar um monte de
verificações após cada evento.
• 3. Muitas das técnicas de redução da variância não podem ser
utilizadas devido ao comprimento variável dos ciclos.
• 4. Os estimadores da média e da variância são polarizados
© 2000 Paulo Adeodato
Simulações Terminais

Temos interesse no desempenho do transiente
Exemplo, Tráfego de redes

Sistemas que são desligados
Não é necessária a remoção de transientes.
Condições finais:
Pode ser necessário excluir dos resultados a parte final da
simulação
Técnicas semelhantes às de remoção de transientes.
© 2000 Paulo Adeodato
Tratamento de Entidades Abandonadas

Tempo médio de serviço:
Tempo total de serviço
Número de jobs que completaram o serviço

Tempo médio de espera:
Soma do tempo de espera
Número de jobs que receberam serviço

Comprimento Médio da Fila:
Comprimento da fila no evento j
Número de eventos n
Comprimento-da-fila(t)dt
© 2000 Paulo Adeodato
Referências Bibliográficas

Raj Jain (1991)
The Art of Computer Systems Performance Analysis:
Techniques for Experimental Design, Measurement and
Modeling
John Wiley & Sons
Capítulo 25
© 2000 Paulo Adeodato
© 2000 Paulo Adeodato
© 2000 Paulo Adeodato
© 2000 Paulo Adeodato
Redução da Variância

Reduza a variância através do controle das cadeias de
números aleatórios
Introduz correlação em observações sucessivas

Problema: O uso sem o devido cuidado pode não dar
certo, levando a aumentar a variância.

Apenas para analistas com conhecimentos sofisticados
de estatística

Não é recomendado para iniciantes
© 2000 Paulo Adeodato
Redução da Variância: Exercício 25.1

Imagine que você foi chamado como um especialista para
rever um estudo de simulação. Quais dos seguintes
resultados de simulação você consideraria como nãointuitivo e gostaria de tê-los validado cuidadosamente:
1. A vazão de um sistema aumenta à medida que a sua carga
aumenta.
2. A vazão de um sistema diminui à medida que a sua carga aumenta.
3. O tempo de resposta aumenta à medida que a carga aumenta.
4. O tempo de resposta de um sistema diminui à medida que a carga
aumenta.
5. A taxa de perda de um sistema diminui à medida que a carga
aumenta.
© 2000 Paulo Adeodato