Reducing the impact of state space explosion in Stochastic Automata Networks
Thais Christina Webber dos Santos · 2009
A solucao de modelos markovianos com grande espaco de estados e um dos maiores desafios da area de avaliacao de desempenho de sistemas. Os formalismos estruturados, como as Redes de Automatos Estocasticos (SAN), foram propostos para descrever multiplos componentes atraves de automatos, cujas transicoes sao regidas por eventos locais ou sincronizantes, com taxas de ocorrencia constantes ou funcionais. Devido a capacidade de representacao modular de SAN, atraves do uso de algebra tensorial (ou de Kronecker), armazena-se o gerador infinitesimal do modelo de forma compacta e eficiente em memoria. Os metodos numericos de solcao que calculam a distribuicao estacionaria das probabilidades sao adaptados a estas representacoes tensoriais. A operacao basica e a multiplicacao vetor-descritor, que e produto de um vetor de probabilidades por termos tensoriais compostos por matrizes normalmente esparsas. O principal algoritmo chama-se Shuffle e e caracterizado pelo acesso e embaralhamento de posicoes do vetor quando multiplicado pelas matrizes de cada termo. Este metodo e considerado extremamente eficaz no armazenamento em memoria, entretanto apresenta um tempo de processamento alto para a solucao de modelos reais. Propoe-se um algoritmo hibrido e mais flexivel para a multiplicacao vetor-descritor, chamado Split, que coloca o algoritmo Shuffle em perspectiva, apresentando ganhos significativos no tempo de execucao para diversas classes de modelos, sem onerar os recursos computacionais. Entretanto, quando os modelos aumentam em escala, este algoritmo numerico torna-se inadequado devido ao problema da explosao do espaco de estados. Para mitigar o impacto deste problema propoe-se o uso de solucoes alternativas de simulacao, as quais buscam estimar a distribuicao estacionaria de probabilidades tao proximas quanto possivel das solucoes analiticas, baseando-se na execucao de longas trajetorias. Utiliza-se a tecnica de simulacao baseada em amostragem perfeita (tambem chamada de simulacao exata), para fornecer amostras confiaveis da distribuicao estacionaria atraves do casamento de trajetorias, em tempo de simulacao reverso. Esta difere-se da simulacao tradicional por evitar o periodo transiente e a escolha aleatoria de um estado inicial. Mostra-se a viabilidade destes algoritmos aplicados a SAN, principalmente quando se detectam propriedades de monotonicidade nos modelos. Espacos de estados parcialmente ordenados e propriedades de monotonicidade permitem a execucao de um numero reduzido de trajetorias em paralelo para obtencao de uma amostra. A analise numerica iterativa e a simulacao de modelos estocasticos sao abordagens que apresentam vantagens e limitacoes quando aplicadas a solucao de modelos estruturados como SAN. A principal contribuicao desta tese foca na reducao do impacto da explosao do espaco de estados de modelos markovianos descritos em SAN, propondo solucoes quando o tempo de computacao das tecnicas analiticas e muito longo ou quando os requisitos de armazenamento do vetor de probabilidade excedem a capacidade de memoria das tecnologias correntes.