Upload
phamanh
View
215
Download
0
Embed Size (px)
Citation preview
Avaliação de Desempenho deSistemas Paralelos
Leonardo Brenner Paulo Fernandes Afonso Sales
[email protected] [email protected] [email protected]
Avaliacao de Desempenho de Sistemas Paralelos – p.1/52
Tópicos
Introdução
Conceitos Básicos
Taxonomia de Métodos
Formalismos
Redes de Autômatos Estocásticos
Técnica Básica de Descrição
Obtenção de Resultados
PEPS2003
Exemplos de Modelagem
Exemplos Genéricos
Exemplos Específicos para Alto DesempenhoAvaliacao de Desempenho de Sistemas Paralelos – p.2/52
Introdução
Conceitos Básicos
Objetivos
Características
Taxonomia dos Métodos
Monitoração
Simulação
Métodos analíticos
Avaliacao de Desempenho de Sistemas Paralelos – p.3/52
Avaliação deDesempenho
Objetivo: Projeto Racional
dimensionamento coerente
melhor distribuição de recursos
busca gargalos e falhas
Características da Avaliação
avaliação quantitativa de sistemas (soluçãonumérica)
estimativas probabilísticas (processosestocásticos)
espaço de estados discreto (finito ou enumerável)
escala de tempo contínua ou discretaAvaliacao de Desempenho de Sistemas Paralelos – p.4/52
Monitoração
Consiste na observação de determinadas característicasde um sistema real (físico)
Vantagens
evita erros de abstração (não há modelagem)
credibilidade (o sistema já está funcionando)
Desvantagens
necessidade de implementação física (custoeconômico)
dependência do conjunto de amostras (tempo deobservação)
Avaliacao de Desempenho de Sistemas Paralelos – p.5/52
Simulação
Consite em reproduzir computacionalmente ocomportamento de partes específicas de um sistema
Vantagens
não requer implementação física (baixo custo)
credibilidade relativa (seqüências defuncionamento)
Desvantagens
dependência do conjunto de amostras (tempo desimulação)
Avaliacao de Desempenho de Sistemas Paralelos – p.6/52
Métodos Analíticos
Descrevem o funcionamento do sistema através demodelos teóricos (matemáticos)
Vantagens
não depende do conjunto de amostras (tempo desolução)
facilita a reflexão profunda durante o projeto
Desvantagens
dificuldade na descrição (matemática) dosmodelos (formalismos)
tamanho (número de estados) dos modelosAvaliacao de Desempenho de Sistemas Paralelos – p.7/52
Métodos AnalíticosCadeias de Markov
formalismo básico
descrição monolítica (não modular)
simplicidade e extensa literatura
Redes de Petri Estocásticas (SPN)
formalismo bastante difundido
descrição compacta (estados implícitos)
descrição “quase”-modular
Redes de Autômatos Estocásticos (SAN)
formalismo estruturado (modular)
métodos numéricos de solução eficientes
descrição intuitiva (autômatos)Avaliacao de Desempenho de Sistemas Paralelos – p.8/52
Cadeias de Markov
Representação de todos os estados possíveis etransições entre eles
mudança de estados (transições) segundo umprocesso estocástico
escala de tempo discreta (probabilidade detransição) ou contínua (freqüência de transição)
ergodicidade (ausência de estados absorventes ouinatingíveis)
ausência de memória (exceto estado atual)
proposta no fim do século XIX
solução através de sistema de equações linearesAvaliacao de Desempenho de Sistemas Paralelos – p.9/52
Cadeias de Markov
�
����
��
��
��
������
�� ������ ��
�
Figura 1: Cadeia de Markov - exemplo elementar
Avaliacao de Desempenho de Sistemas Paralelos – p.10/52
Cadeias de Markovsolução
estacionária - supondo um conjunto de estadosiniciais e tempo infinito
transiente - supondo um conjunto de estadosiniciais e um tempo finito e conhecido
resultado
bruto - vetor com a probabilidade de cada estado
integração de estados com determinadascaracterísticas
integração com ponderações (recompensas)
Avaliacao de Desempenho de Sistemas Paralelos – p.11/52
Cadeias de Markov
Matematicamente, as Cadeias de Markov sãorepresentadas através de uma matriz
�com as taxas de
transição (Gerador Infinitesimal) na escala de tempocontínua e por uma matriz
de probabilidades na
escala de tempo discreta.A solução estacionária � é obtida pela resolução dosistema de equações lineares:
� � � �
Avaliacao de Desempenho de Sistemas Paralelos – p.12/52
Redes de AutômatosEstocásticos
idéia básica
autômatos
eventos
taxas e probabilidaes funcionais
representação formal
Avaliacao de Desempenho de Sistemas Paralelos – p.13/52
Redes de AutômatosEstocásticos (SAN)
representação modular - cada módulo representadopor um autômato
um módulo tem um comportamento "quaseindependente"(eventos e funções)
primitivas de sincronismo e paralelismo (eventossincronizantes ou locais)
Avaliacao de Desempenho de Sistemas Paralelos – p.14/52
Redes de AutômatosEstocásticos (Autômatos)
conjunto de estados e transições
mudança de estados através de transições
transições disparadas por eventos
uma transição pode ter vários eventos associados
Avaliacao de Desempenho de Sistemas Paralelos – p.15/52
Redes de AutômatosEstocásticos
� �� ���
��
� �� ���
��
��
� �� � � � �! �� �
" �� �
" � �
Figura 2: Modelo SAN com 2 autômatos
Avaliacao de Desempenho de Sistemas Paralelos – p.16/52
Redes de AutômatosEstocásticos (eventos)
o acontecimento de um evento dispara umatransição
existem dois tipos de eventos
locais - alteram o estado local de apenas umautômato
sincronizantes - alteram o estado local de váriosautômatos ao mesmo tempo
Cade evento tem uma taxa de disparo associada, esta
taxa pode ser constante ou funcional.
Avaliacao de Desempenho de Sistemas Paralelos – p.17/52
Redes de AutômatosEstocásticos
# $% &' () * + () *
,-,.
# $ + &' ( . *
% (. * + ( . *, . $0/ . & ,1
, . $0/ ) &,2
,)Figura 3: Modelo SAN com 2 autômatos e um
evento sincronizante
Avaliacao de Desempenho de Sistemas Paralelos – p.18/52
Redes de AutômatosEstocásticos (funções)
a taxa de um evento tem uma função associada
a função é avaliada conforme o estado dos demaisautômatos do modelo
Os eventos sincronizantes propiciam a interação entre
autômatos por envolver vários autômatos em um único
evento, enquanto as taxas e probabilidades funcionais
avaliam os estados dos demais autômatos do modelo.
Avaliacao de Desempenho de Sistemas Paralelos – p.19/52
Redes de AutômatosEstocásticos
3 45 678
79 7:7;7: 4=< 8 67: 4< 9 67>
? @A BC @A B
? @D B
C @D BE @A B
3 4F 6
Figura 4: Modelo SAN com 2 autômatos, 1 evento
sincronizante e probabilidades funcionais
Avaliacao de Desempenho de Sistemas Paralelos – p.20/52
Redes de AutômatosEstocásticos funções
taxas e probabilidades funcionais
função de atingibilidade
funções de resultado
Avaliacao de Desempenho de Sistemas Paralelos – p.21/52
Taxas e ProbabilidadesFuncionais
associadas a eventos
taxas e probabilidades de disparo variam de acordocom o estado global do modelo
demais autômatos são parâmetros da função
GIH �JKLK
KLKNMO H se autômato
P H Q
está no estado
� P H QSR
�
se autômato
P H Q
está no estado
T P H QSR
OVU se autômato
P H Q
está no estado
W P H QX
Avaliacao de Desempenho de Sistemas Paralelos – p.22/52
Função de Atingilidade
determina o conjunto de estados atingíveis domodelo
estados que representam a realidade do modelo
determina o vetor de probabilidades inicial
retorna
T
para estados atingíveis e
�
caso contrário
YZ [\ ] [ ^_ ` _a b �c
de Hfa gh P dQji k l
Avaliacao de Desempenho de Sistemas Paralelos – p.23/52
Funções de Integração
extração de índices “legíveis” do modelo
soma das probabilidades de um conjunto de estadospara os quais a função é verdadeira
m � fa g P H Qi � � �
Avaliacao de Desempenho de Sistemas Paralelos – p.24/52
Redes de AutômatosEstocásticos
Formalmente, cada autômato
Pn Q
é representado porum conjunto de matrizes
o
matrizes representam os eventos locais
W p o
matrizes representam os eventossincronizantes
Avaliacao de Desempenho de Sistemas Paralelos – p.25/52
PEPS2003
sobre a ferramenta;
arquivo de entrada;
comandos básicos.
Avaliacao de Desempenho de Sistemas Paralelos – p.26/52
Sobre a ferramenta PEPS
A ferramenta de software PEPS (Performance Evaluationof Parallel Systems) é uma ferramenta acadêmica paradescrição e resolução de modelos SAN. A ferramentaimplementa várias facilidades como:
descrição de modelos em alto nível
métodos de solução iterativa
funções de integração
Avaliacao de Desempenho de Sistemas Paralelos – p.27/52
Formato do arquivo deentrada
O arquivo de entrada da ferramenta PEPS é um arquivotextual estruturado em blocos:
identificadores
eventos
função de atingibilidade
descrição da rede
resultados
Avaliacao de Desempenho de Sistemas Paralelos – p.28/52
Identificadores
O bloco de identificadores, primeiro bloco do arquivo deentrada, é precedido da palavra “identifiers” edefine um conjunto funções e domínios utilizados nosblocos seguintesidentifiersq_ r T s � qZ tu s ;
. . . q rwv x T s � y _ X X z {;
. . .
Avaliacao de Desempenho de Sistemas Paralelos – p.29/52
Eventos
O bloco de eventos define o conjunto de evento queserão associados as transições nos autômatos. Estebloco define, além do nome do evento, o tipo de cadaevento e a taxa associada a este. O bloco de eventos éprecedico da palavra “events” e utiliza-se as palavras“loc” e “syn” para definir o tipo do eventos como localou sincronizante, respectivamenteevents
loc evento [dominio] (<identificador>);syn evento1 [dominio1] (<identificador1>);. . .
Avaliacao de Desempenho de Sistemas Paralelos – p.30/52
Função de Atingibilidade
A função de atingibilidade define o conjunto de estadosglobais que corresponde a realidade do modelo. Estebloco é representado da seguinte forma:partial reachability = <exp>;
A palavra reservada partial define que a expressão uti-
lizada para definir o conjunto de estados atingíveis, não
indica todos os estados, apenas uma parte deles
Avaliacao de Desempenho de Sistemas Paralelos – p.31/52
Descrição da Rede
Principal bloco do arquivo, define a escala de tempo, osautômatos e as transições. Obedece a seguinteestruturanetwork
q| v xZ s g qa _ u v siaut
q [ ma T s { y Y Z u ` _ \ [ f { }stt
q fa a T s { y Y Z u ` _ \ [ f { } {g Y Z \ v xu Z | f [i }
to(
q fa a W s)qZ} Z |a v s ~ g qu Y v ^ si�
X X XAvaliacao de Desempenho de Sistemas Paralelos – p.32/52
Resultados
Neste bloco, precedido da palavra “results”, o usuáriodefine os índices desempenho que deseja extrair domodelo. Estes índices são extraídos através funções deintegração e segue a seguinte estrutura:results
função = <exp>;. . .
Avaliacao de Desempenho de Sistemas Paralelos – p.33/52
Comandos Básicos
Menu principal da ferramenta PEPS+--------------------------------------------------------+
| This is PEPS 2003 - the SAN tool |
| released on: May 21 2003 -- compiled on: Sep 1 2003 |
+--------------------------------------------------------+
1) Compile a SAN model 5) Load/Show/Remove data structures
2) Solve a compiled SAN model 6) Inspect data structures
3) Probability vector facilities 7) Sparse matrix facilities
4) Preferences 8) About this version
0) Exit PEPS (Option 0 always exits the current menu)
Avaliacao de Desempenho de Sistemas Paralelos – p.34/52
Compilando um modelo
Opção
T
(Compile a SAN model) no menu principal
******* Compiling a SAN Model *******
1) Standard Compilation
2) Compilation with Algebraic Aggregation
3) Compilation with Aggregation of Replicas
Avaliacao de Desempenho de Sistemas Paralelos – p.35/52
Resolvendo um modelo
Opção
W
(Solve a compiled SAN model) no menuprincipal
******* Solving a SAN model *******
No Preconditioning: Diagonal Preconditioning:
1) Power Method 4) Power Method
2) Arnoldi Method 5) Arnoldi Method
3) GMRES Method 6) GMRES Method
Avaliacao de Desempenho de Sistemas Paralelos – p.36/52
Exemplos
compartilhamento de recursos;
rede de filas de espera;
fontes on/off;
cluster com protocolo de comunicação UDP;
cluster com conexão em anel;
cluster com conexão torus.
Avaliacao de Desempenho de Sistemas Paralelos – p.37/52
Compartilhamento deRecursos
o
clientes disputando recursos
recursos indistintos
duas alternativas de modelagem
número de estados parao � W �
e
� �
modelo com funções - 1.048.576 estados
modelo com eventos sincronizante - 4.194.304estados
Avaliacao de Desempenho de Sistemas Paralelos – p.38/52
Compartilhamento deRecursos
... ��� ���� �� �
��� �� �� �
� ��� ���� �� �
�� � �� �� �
Evento Taxa Evento Taxa���� ���� ��� ��
���� ���� ��� ��
���� ���� ��� ��
... ... ... ...� �� � �� ��� ��
���� ¡£¢ ¤ ¥ � �� �¦ ¦ � �� �¨§ ©«ª ¬ ¯® °²±
Avaliacao de Desempenho de Sistemas Paralelos – p.39/52
Compartilhamento deRecursos
... ...
......
...
......
...
...
...
³´µ³´¶ ³·¶ ³·µ
³´µ³´¶³´µ³´¶
³´µ³´¶
³·¶ ³·µ³·¶ ³·µ
³·¶ ³·µ
³ ´µ ³·µ ³´ ¶ ³·¶
¸ ¹º »¼¹º »
¸ ¹½ »¼¹½ »
¾ ¿ÀÁ  ú ¿ÀÁ  Ã
Ä
-
º ¿ ÀÁ Â ÃÄ¿ÀÁ Â Ã
Å ÆÇ È Å ÆÉ È Å Æ ÉÊ Ç È
Evento Taxa Evento TaxaËÌ Ç ÍÎÇ ËÏ Ç ÐÇ
ËÌÑ ÍÑ ËÏÑ ÐÑ
ËÌÒ ÍÒ ËÏÒ ÐÒ
... ... ... ...ËÌ É ÍÓÉ ËÏ É ÐÉ
Avaliacao de Desempenho de Sistemas Paralelos – p.40/52
Rede de Filas de Espera
1
3
2
loss
ÔÕÔÖ
Número total de estados - 48 estados
Avaliacao de Desempenho de Sistemas Paralelos – p.41/52
Rede de Filas de Espera
Evento Taxa×ÙØ ÚÙØÛÝÜ ÞàßáÛÝâ ãâ
äÝØ Ü ãØ åØäæØ â ãØ åÜ
çéèçéè
çéèßá ê èá
ê èáê èá
ßëßë ê èë
ì íî ï ì íð ï
ßáßáê èá ê èë
ê èá ê èëê èá ê èë
ì íñ ïò óô õ
ñ óô õî óô õ
ð óô õ
ò óö õñ óö õ
î óö õð óö õ
ò ó÷ õñ ó÷ õ
î ó÷ õê èë
ê èë
øúù ö û ü ý«þ ÿ� î�� � � ÿ ì íî ï� � �� î
Avaliacao de Desempenho de Sistemas Paralelos – p.42/52
Fontes On/Off
fontes independentes
taxa constante de envio de dados por fonte
taxa variável de recebimento de dados na fila
número de estados paraT �
fontes e fila de tamanhoT � �
103.424 estados
Avaliacao de Desempenho de Sistemas Paralelos – p.43/52
Fontes On/Off
� � �
� �� �� �� �� � � � � � � �
���� �� �� �
���� �� � �
� �� �� �� �
���� �
� � � � � � � � � � � � � � � �
� �� � �� �� � �(K-1)
�� � �
K
�� � �
Avaliacao de Desempenho de Sistemas Paralelos – p.44/52
Protocolo deComunicação UDP
meio de comunicação único
somente uma transmissão por vez
várias recepções simultâneas
se alguém estiver recebendo, alguém precisa estartransmitindo
número de estados para
T �
nós
1.048.576 estados
Avaliacao de Desempenho de Sistemas Paralelos – p.45/52
Protocolo deComunicação UDP
. . .
. . .! "# $% &' (
) &' (
* &' (+ &' (
,-./ '-0 ' 1243 5
60 ' 12 ' 5 78 9'
./ 8. '7 8 9'
! ": $% &; (
) &; (
* &; (+ &; (
, -./ ;-0 ; 1243 57 8 9;
./ 8. ;7 8 9;
60 ; 12 ' 5
Avaliacao de Desempenho de Sistemas Paralelos – p.46/52
Conexão em anelunidirecional
duas alternativas de modelagem
número de estados para
<nós
um autômato por nó - 3.125 estados
dois autômatos por nó - 59.049 estados
Avaliacao de Desempenho de Sistemas Paralelos – p.47/52
Conexão em anel
= >?@A
B CD E
? >A
? >A ?@ F
?@A
? > F
GIH JK LGM N J K L
OQP J K L RP J K L
O P RP J K L
?@ F= @
? > F
Avaliacao de Desempenho de Sistemas Paralelos – p.48/52
Conexão em anel
S TU VWYXW[Z
S T\ V]^_
`Qa b^ c^de f b^ c
dQg b^ c dQg b Z cde f bZ c
ha bZ c^
] Z_
W^]^ i
W[j] Z i
Avaliacao de Desempenho de Sistemas Paralelos – p.49/52
Conexão em torusunidirecional
dois autômatos por nó
número de estados para
<nós
1.048.576 estados
Avaliacao de Desempenho de Sistemas Paralelos – p.50/52
Conexão em torus
k lm no�porq
stu uvswu uvswu uv
k lx nstu uv
yz {| }qyz {| }|
~� � {| }~� {| } ~� {q }
~� � {q }�z {q }|
�z {q }q
stu u �swu u �stu u �swu u �
or| or�
st |uvstu |vst |uvstu |vsw |u �stu | �
stu | �sw |u �
Avaliacao de Desempenho de Sistemas Paralelos – p.51/52