| Resumo: | The solution of Markovian models with large state spaces is one of the major challenges in performance evaluation. Structured formalisms such as Stochastic Automata Networks (SAN) were proposed to describe multiple components through the use of automata, whose transitions are determined by local or synchronizing events, having constant or functional rates. Due to the inherent modular representation of SAN, it is possible through tensor (Kronecker) algebra to store the model infinitesimal generator in memory, in a compact and efficient manner. The numerical methods that calculate the stationary probabilities distribution are adapted to these structured representations. The basic operation is the vector-descriptor multiplication, which is the product of a probability vector by tensor products composed by sparse matrices. The traditional Shuffle algorithm is characterized by the access and shuffling positions of the vector when multiplied by each matrix of a tensor product term. This approach is considered highly memory-efficient, however, presents a high processing time for the solution of real models. We propose a more flexible and hybrid algorithm for the vector-descriptor product called Split, putting the Shuffle approach in perspective, presenting significant improvements in the execution time for a diverse set of models without impairing the computational resources. Nevertheless, increasing the state space of models, this algorithm also becomes unsuitable to obtain a numerical solution. To mitigate the impact of state space explosion, it is proposed the use of simulations to estimate the stationary probability distribution as close as possible to analytical solutions, executing long-run trajectories. We propose the application of perfect sampling techniques (also called exact simulation) to produce reliable samples through trajectory couplings, in reverse simulation time. This technique is distinguished from traditional simulation by avoiding transient periods and the initial state to be chosen. It is discussed the feasibility of these algorithms applied to SAN, specially focusing on partially ordered state spaces and monotonicity properties allowing the execution of less parallel trajectories for the generation of a sample. The iterative numerical analysis and the simulation of stochastic models are approaches that present advantages and limitations when applied to the solution of structured models such as SAN. The main contribution of this thesis focuses on the reduction of the impact of state space explosion of Markovian models described in SAN, proposing solutions when the computational time of analytical techniques is too long or when the memory requirements for the probability vector exceeds current technologies storage capacity.
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. |
