Made available in DSpace on 2015-04-14T14:49:09Z (GMT). No. of bitstreams: 1
415453.pdf: 1512363 bytes, checksum: 42043724fd23719f6c7529ca1c04ff6a (MD5)
Previous issue date: 2009-03-27 / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede2.pucrs.br:tede/5056 |
| Date | 27 March 2009 |
| Creators | Santos, Thais Christina Webber dos |
| Contributors | Fernandes, Paulo Henrique Lemelle |
| Publisher | Pontif?cia Universidade Cat?lica do Rio Grande do Sul, Programa de P?s-Gradua??o em Ci?ncia da Computa??o, PUCRS, BR, Faculdade de Inform?ca |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da PUC_RS, instname:Pontifícia Universidade Católica do Rio Grande do Sul, instacron:PUC_RS |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 1974996533081274470, 500, 600, 1946639708616176246 |
Page generated in 0.3392 seconds