Solução Numérica de Descritores Markovianos


...no final do dia...
Frase comumente dita na defesa...

Informações Gerais

Título: "Solução numérica de descritores Markovianos a partir de re-estruturações de termos tensoriais"
Autor: Ricardo M. Czekster
Orientador: Paulo Fernandes
Banca Examinadora:
      Nicolas Maillard (PGCC/UFRGS)
      Dalcídio Moraes Cláudio (FAMAT)
      Fernando Luis Dotti (PPGCC/PUCRS)

Total de páginas: 195
Data da Defesa: 29/03/2010 (1489 dias a partir de 01/03/2006)
Data da Homologação: 18/05/2010 (50 dias a partir da defesa)
Data do Diploma: 28/05/2010 (60 dias a partir da defesa, 10 dias após homologação)

Resumo - Total de palavras: 479

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 (constante 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: 1) na discussão das primitivas de modelagem para composição de sistemas através de formas mais abstratas de descrição, 2) 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 3) 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 constantes 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 e 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.
Palavras-chave: Modelos abstratos de representação; Formalismos estruturados; Soluções numéricas; Descritores Kronecker; Ferramentas computacionais; Cadeias de Markov; Álgebra Tensorial.

Estrutura do Volume

  1. Versão completa da Tese [195p] [1,6mb]
    1. Apresentação da tese (lâminas utilizadas) [1,2mb]
    2. Arquivo com outras informações relevantes (+lâminas) [329kb]
  1. Capítulo 1: Introdução [6p]
    1. Motivação
    2. Objetivo
    3. Contribuição
    4. Organização
  2. Capítulo 2: Descrição de sistemas através de formalismos [22p]
    1. Modelagem de sistemas
    2. Cadeias de Markov
      1. Emergência dos formalismos estruturados
    3. Redes de Petri
      1. Redes de Petri Coloridas
    4. Redes de Autômatos Estocásticos
    5. Álgebras de Processos
      1. PEPA - Performance Evaluation Process Algebra
      2. PEPA nets
    6. Discussão
  3. Capítulo 3: Modelo abstrato de formalismos estruturados [18p]
    1. Introdução
    2. Conceitos preliminares
    3. Correspondência entre formalismos
    4. Estudo de caso: tradução de PEPA nets para descritor
      1. Trabalhos relacionados e observações iniciais
      2. Método de tradução
      3. Exemplo de tradução
    5. Comunicação e interação
    6. Exemplo de modelagem abstrata
    7. Discussão
  4. Capítulo 4: Solução de descritores tensoriais [30p]
    1. Álgebra Tensorial Clássica - ATC
      1. Produto tensorial clássico
      2. Soma tensorial clássica
      3. Propriedades
    2. Álgebra Tensorial Generalizada - ATG
      1. Produto tensorial generalizado
      2. Soma tensorial generalizada
      3. Propriedades
    3. Descritores Markovianos
      1. Descrição de eventos
      2. Exemplo
    4. Multiplicação Vetor-Descritor
      1. Algoritmo Esparso
      2. Algoritmo Shuffle
      3. Algoritmo Split
    5. Permutações dos termos tensoriais
    6. Algoritmo Split com permutações e identidades à direita de sigma
  5. Capítulo 5: Estratégias de re-estruturação [16p]
    1. Análises preliminares
    2. Re-estruturações de descritores Markovianos
      1. Descritor Markoviano constante
      2. Descritor Markoviano generalizado
    3. Análise teórica
      1. Características de termos tensoriais
      2. Matrizes identidade na multiplicação de termos tensoriais
      3. Custo das avaliações dos elementos funcionais e permutações
    4. Discussão
  6. Capítulo 6: GTAexpress - ferramenta para solução de descritores [14p]
    1. Abordagem tensorial de armazenamento
    2. Descritores Markovianos
    3. Etapas para construção de descritores
    4. Arquitetura e detalhes da ferramenta
      1. Formato de entrada proposto
      2. Configurações de entrada, execução e saída
    5. Discussão
  7. Capítulo 7: Resultados numéricos [30p]
    1. Experimentos
    2. Modelos
      1. Modelo Mestre-Escravo
      2. Modelo Redes Wireless ad hoc
      3. Modelo First Available Server, ou FAS
      4. Modelos do formalismo PEPA: Workcell e WebServer
      5. Modelos Jantar dos Filósofos
      6. Modelo Compartilhamento de Recursos
      7. Modelo Alternate Service Patterns, ou ASP
      8. Modelo Non-Uniform Memory Access, ou NUMA
      9. Modelo Open Queueing Network, ou OQN
    3. Estudo de caso: Modelo Redes Wireless ad hoc
      1. Modelo
      2. Descritor Generalizado
      3. Descritor Constante
      4. Complexidade em termos de multiplicações em ponto flutuante
    4. Considerações sobre os resultados
    5. Determinação do ponto de corte para o Algoritmo Split
    6. Discussão
  8. Capítulo 8: Considerações finais e perspectivas [10p]
    1. Resumo
    2. Contribuição
    3. Perspectivas futuras
    4. Epílogo
  9. Referências [10p]
  10. Apêndice A: Experimentos [13p]
  11. Modelos utilizados
  12. Fontes LaTeX [206Kb]




Nenhum comentário:

Postar um comentário