Solução numérica de descritores markovianos a partir de re-estruturações de termos tensoriais

Abstract

Several formalisms have been defined throughout the years aiming the enhancement of the abstraction level which offer a more sophisticated modeling alternative than traditional Markov Chains. Examples of formalisms that use tensor algebra for descriptor storage are Stochastic Automata Networks, Superposed Generalized Stochastic Petri Nets, and Process Algebras. These descriptions employ modeling primitives among their components by capturing their operational semantics, and allow analysis by returning quantitative performance indexes when subjected to numerical solution. Solution mechanisms use both classic and generalized Tensor Algebra properties to multiply tensor terms of events among the states of the models (i. e., a Markovian descriptor) by a probability vector, using stationary or transient measurements. This operation is called Vector-Descriptor Multiplication (VDM), and can be performed by three different methods: sparsely (memory inefficient, time efficient), using the Shuffle Algorithm (memory efficient, time inefficient, depending on the model) or through the Split Algorithm, a combination between the two former approaches. The main contribution of the Split approach was the proposition of a hybrid method where memory increments (in a reasonable fashion) are used to accelerate the calculations per iteration. On the other hand, the main challenge of the Split Algorithm is the determination of each division point (e. g. the cut parameter), and how the tensor terms must be restructured to reduce computational costs per iteration, allowing quicker convergence for structured models. The present work addresses these problems in three distinct ways: i) by discussing the modeling primitives for system composition through more abstract ways of description, ii) by treating each tensor term of Markovian descriptors in different manners for more optimized VDM solution restructuring the original orders, iii) by executing the Algorithm Split having both constant or functional rates, demonstrating the results for a variety of models. The experiments discussed here demonstrate that the best gain considering time and memory is verified when the matrices of the tensor terms are reordered, treating the identity ones in the structured part and evaluating functional elements just once in the sparse part. When the functions were evaluated only once in all VDM process, a conversion of generalized to classic descriptor took place in execution time, with considerable gain in time for some classes of models. In addition, it was observed that synchronization or communication activities between each module or system partition and the total number of functional parameters play a crucial role in the overall performance. The present thesis is finalized with the identification of the most suitable class of models for the utilization of the Split Algorithm, and the proposition of a restructuration of Markovian that privileges sparsity and identity matrices to balance memory costs and execution time.

Os formalismos estruturados foram definidos ao longo dos anos com o objetivo de aumentar o nível de abstração e oferecer uma alternativa de modelagem mais sofisticada do que a proporcionada pelas tradicionais Cadeias de Markov. Exemplos de formalismos estruturados que utilizam álgebra tensorial para o armazenamento de seus descritores são as Redes de Autômatos Estocásticos, as Redes de Petri Estocásticas Generalizadas Superpostas e as Álgebras de Processo. Tais descrições utilizam primitivas de modelagem entre seus componentes capturando sua semântica operacional e permitindo a sua análise ao retornarem índices quantitativos de desempenho quando são resolvidos numericamente. Os mecanismos atuais de solução usam propriedades da Álgebra Tensorial (clássica ou generalizada) para multiplicar termos tensoriais de eventos entre os estados dos modelos (i. e., um descritor Markoviano) por um vetor de probabilidade, que contém a solução estacionária ou transiente. Esta operação é chamada de Multiplicação Vetor-Descritor (MVD) e é realizada de três maneiras básicas: de forma esparsa (ineficiente em memória, eficiente em tempo), utilizando o Algoritmo Shuffle (eficiente em memória, ineficiente em tempo para algumas classes de modelos) ou através do Algoritmo Split, que é uma combinação das duas primeiras abordagens. A principal contribuição deste último foi a proposição de um método híbrido onde incrementa-se a memória (de forma razoável) para acelerar o cálculo efetuado por iteração. Entretanto, o principal desafio do Algoritmo Split é relativo à determinação de cortes de cada termo tensorial e em como re-estruturá-lo para reduzir o custo computacional por iteração, acelerando a convergência de modelos estruturados. Este trabalho aborda estes problemas, baseando-se em três eixos: i) na discussão das primitivas de modelagem para composição de sistemas através de formas mais abstratas de descrição, ii) nas diferentes formas de tratamento de termos tensoriais de descritores Markovianos para execução mais otimizada da MVD a partir de re-estruturações das ordens originais, e iii) na execução do Algoritmo Split com taxas constantes ou funcionais demonstrando os resultados obtidos para diversas classes de modelos. Para os casos observados, foi demonstrado através de experimentos que o melhor ganho, balanceando-se tempo e memória, é verificado quando as matrizes dos termos tensoriais são reordenadas, tratando as do tipo identidade na parte estruturada e avaliando-se os elementos funcionais uma única vez na parte esparsa. Ao avaliar as funções somente uma vez em todo o processo de MVD, converte-se os descritores generalizados para clássicos em tempo de execução e promove-se ganhos consideráveis em tempo para determinadas classes de modelos. Observou-se também que as atividades de sincronização ou comunicação entre os módulos ou partições envolvidas bem como o total de parâmetros das dependências funcionais realizam um papel crucial no desempenho obtido. A presente tese é finalizada identificando as classes de modelos mais adequadas para a utilização do Algoritmo Split, propondo formas de re-estruturação de descritores Markovianos que privilegiem a esparsidade e a existência de matrizes do tipo identidade para balancear os custos em memória e tempo de execução.