Export this record: EndNote BibTex

Please use this identifier to cite or link to this item: http://tede2.pucrs.br/tede2/handle/tede/5056
Document type: Tese
Title: Reducing the impact of state space explosion in Stochastic Automata Networks
Author: Santos, Thais Christina Webber dos 
Advisor: Fernandes, Paulo Henrique Lemelle
Abstract (native): A solução de modelos markovianos com grande espaço de estados é um dos maiores desafios da área de avaliação de desempenho de sistemas. Os formalismos estruturados, como as Redes de Autômatos Estocásticos (SAN), foram propostos para descrever múltiplos componentes através de autômatos, cujas transições são regidas por eventos locais ou sincronizantes, com taxas de ocorrência constantes ou funcionais. Devido à capacidade de representação modular de SAN, através do uso de álgebra tensorial (ou de Kronecker), armazena-se o gerador infinitesimal do modelo de forma compacta e eficiente em memória. Os métodos numéricos de solção que calculam a distribuição estacionária das probabilidades são adaptados a estas representações tensoriais. A operação básica é a multiplicação vetor-descritor, que é produto de um vetor de probabilidades por termos tensoriais compostos por matrizes normalmente esparsas. O principal algoritmo chama-se Shuffle e é caracterizado pelo acesso e embaralhamento de posições do vetor quando multiplicado pelas matrizes de cada termo. Este método é considerado extremamente eficaz no armazenamento em memória, entretanto apresenta um tempo de processamento alto para a solução de modelos reais. Propõe-se um algoritmo híbrido e mais flexível para a multiplicação vetor-descritor, chamado Split, que coloca o algoritmo Shuffle em perspectiva, apresentando ganhos significativos no tempo de execução para diversas classes de modelos, sem onerar os recursos computacionais. Entretanto, quando os modelos aumentam em escala, este algoritmo numérico torna-se inadequado devido ao problema da explosão do espaço de estados. Para mitigar o impacto deste problema propõe-se o uso de soluções alternativas de simulação, as quais buscam estimar a distribuição estacionária de probabilidades tão próximas quanto possível das soluções analíticas, baseando-se na execução de longas trajetórias. Utiliza-se a técnica de simulação baseada em amostragem perfeita (também chamada de simulação exata), para fornecer amostras confiáveis da distribuição estacionária através do casamento de trajetórias, em tempo de simulação reverso. Esta difere-se da simulação tradicional por evitar o período transiente e a escolha aleatória de um estado inicial. Mostra-se a viabilidade destes algoritmos aplicados a SAN, principalmente quando se detectam propriedades de monotonicidade nos modelos. Espaços de estados parcialmente ordenados e propriedades de monotonicidade permitem a execução de um número reduzido de trajetórias em paralelo para obtenção de uma amostra. A análise numérica iterativa e a simulação de modelos estocásticos são abordagens que apresentam vantagens e limitações quando aplicadas à solução de modelos estruturados como SAN. A principal contribuição desta tese foca na redução do impacto da explosão do espaço de estados de modelos markovianos descritos em SAN, propondo soluções quando o tempo de computação das técnicas analíticas é muito longo ou quando os requisitos de armazenamento do vetor de probabilidade excedem a capacidade de memória das tecnologias correntes.
Keywords: INFORMÁTICA
MÉTODOS NUMÉRICOS
REDES DE AUTÔMATOS ESTOCÁSTICOS
CNPQ Knowledge Areas: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
Country: BR
Publisher: Pontifícia Universidade Católica do Rio Grande do Sul
Institution Acronym: PUCRS
Department: Faculdade de Informáca
Program: Programa de Pós-Graduação em Ciência da Computação
Citation: SANTOS, Thais Christina Webber dos. Reducing the impact of state space explosion in Stochastic Automata Networks. 2009. 136 f. Tese (Doutorado em Ciência da Computação) - Pontifícia Universidade Católica do Rio Grande do Sul, Porto Alegre, 2009.
Access type: Acesso Aberto
URI: http://tede2.pucrs.br/tede2/handle/tede/5056
Issue Date: 27-Mar-2009
Appears in Collections:Programa de Pós-Graduação em Ciência da Computação

Files in This Item:
File Description SizeFormat 
415453.pdfTexto Completo1.48 MBAdobe PDFThumbnail

Download/Open Preview


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.