• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 22
  • Tagged with
  • 22
  • 22
  • 22
  • 19
  • 12
  • 12
  • 9
  • 9
  • 7
  • 6
  • 5
  • 5
  • 4
  • 3
  • 3
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
11

Otimizações para a multiplicação vetor-descritor através do algoritmo Slice

Presotto, Ricardo De Gasperi January 2007 (has links)
Made available in DSpace on 2013-08-07T18:43:41Z (GMT). No. of bitstreams: 1 000397350-Texto+Completo-0.pdf: 1116955 bytes, checksum: 56e8c94cf13d61a08aec37811131b9a1 (MD5) Previous issue date: 2007 / Studies on performance evaluation have progressed in the last years, specially with Stochastic Automata Networks (SAN) and with the implementation of the Shuffle algorithm, which implements an efficient method for vector-descriptor multiplication, needed to solve SAN models. Recently, a new vector-descriptor method was proposed, the Slice method, presenting new concepts to be more efficient than the tradicional Shuffle method. ln this work the Slice method was studied in detail and a new implementation was developed including some new optimizations. ln addition, the Slice algorithm was modified in order to solve functional SAN models, since the previous version was unable to deal with functions. To demonstrate the performance of the Slice method and its optimizations experiments were made using two different SAN models. The results were analyzed and compared with Shuffle results. Thus, it was possible to verify that the Slice method is more efficient than the tradicional Shuffle method in most cases. / Os estudos na área de Avaliação de desempenho de Sistemas têm evoluído nos últimos anos, em especial com a definição do formalismo de Redes de Autômatos Estocásticos (SAN) e com a implementação do algoritmo Shuffle, o qual implementa um método eficiente para a execução da multiplicação vetor-descritor, necessária para a resolução de modelos SAN. Mais recentemente, foi proposto um novo método para a multiplicação vetor-descritor, o método slice, que introduzindo novos conceitos, prometia na teoria ser mais eficiente que o tradicional método Shuffle. Pois neste estudo, este recém definido e até então pouco explorado método, foi estudado em detalhes e realizada uma implementação incluindo algumas otimizações no seu algoritmo original. Ainda, durante este estudo, foram realizadas algumas modificações do algoritmo do método Slice com mesmo intuito de resolver modelos SAN funcionais, uma vez que as versões anteriores não eram capaz de tratar funções. Para demonstrar a eficiência do método Slice e das otimizações propostas, diversos experimentos foram conduzidos utilizando dois modelos SAN. Os resultados de tempo e custo computacional foram analisados e discutidos durante este estudo, comparando-os inclusive com resultados do tradicional método Shuffle. Desta forma, verificou-se o quanto o método Slice pode ser útil na resolução de sistemas, uma vez que os resultados práticos mostram que o método Slice é mais eficiente que a solução tradicional (Shuffle) na maioria dos casos.
12

Técnicas de modelagem para a análise de desempenho de processos de negócio / Modeling techniques for business process performance analysis

Braghetto, Kelly Rosa 21 September 2011 (has links)
As recentes pesquisas na área de Gestão de Processos de Negócio (GPN) vêm contribuindo para aumentar a eficiência nas organizações. A GPN pode ser compreendida como o conjunto de métodos, técnicas e ferramentas computacionais desenvolvidas para amparar os processos de negócios. Tipicamente, a GPN é fundamentada por modelos de processos. Esses modelos, além de permitirem a automação da configuração e execução, aumentam a capacidade de análise dos processos de negócio. Apesar de auxiliar os especialistas de negócio nas diferentes fases envolvidas no ciclo de vida de um processo de negócio (projeto, configuração, implantação/execução e a análise), os modelos definidos em linguagens específicas de domínio, como a BPMN (Business Process Model and Notation), não são os mais apropriados para amparar a fase de análise. De formal geral, esses modelos não possuem uma semântica operacional formalmente definida (o que limita o seu uso para a verificação e validação dos processos) e nem mecanismos para quantificar o comportamento modelado (o que impossibilita a análise de desempenho). Neste trabalho de doutorado, nós desenvolvemos um arcabouço que ampara e automatiza os principais passos envolvidos na análise de desempenho de processos de negócio via modelagem analítica. Nós estudamos a viabilidade da aplicação de três formalismos Markovianos na modelagem de processos de negócio: as Redes de Petri Estocásticas, as Álgebras de Processo Estocásticas e as Redes de Autômatos Estocásticos (SAN, do inglês Stochastic Automata Networks). Escolhemos SAN como formalismo base para o método proposto neste trabalho. Nosso arcabouço é constituído por: (i) uma notação para enriquecer modelos de processos de negócio descritos em BPMN com informações sobre o seu gerenciamento de recursos, e (ii) um algoritmo que faz a conversão automática desses modelos não-formais de processos para modelos estocásticos em SAN. Com isso, somos capazes de capturar o impacto causado pela contenção de recursos no desempenho de um processo de negócio. A partir de um modelo em SAN gerado com o nosso arcabouço, podemos predizer variados índices de desempenho que são boas aproximações para o desempenho esperado do processo de negócio no mundo real. / Recent results in the research field of Business Process Management (BPM) are contributing to improve efficiency in organizations. BPM can be seen as a set of methods, techniques and tools developed to support business processes in their different requirements. Usually, the BPM techniques are based on a process model. In addition to enabling automated process configuration and execution, these models also increase the analizability of business processes. Despite being able to support business specialists in different phases of the life cycle of a business process (design, configuration, execution, and analysis), the models created in domain-specific languages, such as BPMN (Business Process Model and Notation), are not the most appropriated ones to support the analysis phase. Generally, these models have neither a formally defined operational semantics (which hinders their use for verification and validation), nor mechanisms to quantify the modeled behavior (which hinders their use for performance analysis). In this PhD research, we developed a framework to support and to automatize the main steps involved in the analytical modeling of business processes aiming performance evaluation. We studied the viability of applying three Markovian formalisms in business process modeling: Stochastic Petri Nets, Stochastic Process Algebras and Stochastic Automata Networks (SAN). We have chosen SAN to support the method proposed in this work. Our framework is composed of: (i) a notation to enrich BPMN business process models with information concerning the associated resource management and (ii) an algorithm that automatically converts these non-formal business process models in SAN stochastic models. With this, we are able to capture the impact caused by resource contention in the performance of a business process. From a model generated through our framework, we are able to extract varied performance indices that are good approximations for the expected process performance in the real world.
13

Precisão de simulações para solução de modelos estocásticos

Taschetto, Dione January 2010 (has links)
Made available in DSpace on 2013-08-07T18:42:37Z (GMT). No. of bitstreams: 1 000427631-Texto+Completo-0.pdf: 914785 bytes, checksum: 815e75c48669f5e8db50b93c7cf37623 (MD5) Previous issue date: 2010 / The use of Markovian formalisms make possible the use and the computational solution of several systems enabling the prediction and evaluation of their behavior standards. The Stochastic Automata Networks (SAN) formalism provides a compact and modular description for Markovian models. Moreover, SAN is suitable to derive performance indices for systems analysis and interpretation using iterative numerical solutions based on a descriptor and a state space sized probability vector. Depending on the size of the model this operation is computationally onerous and sometimes impracticable. An alternative method to compute indices from a model is simulation, mainly because it simply requires the definition of a pseudorandom generator and transition functions for states that enable the creation of a trajectory. The sampling process can be different for each technique, establishing some rules to collect samples for further statistical analysis. Simulation techniques often demand lots of samples in order to calculate statistically relevant performance indices. This work provides comparisons with accuracy of results from some Markovian models which were obtained from the execution of different simulation techniques. It also proposes a different way to simulate Markovian models by using a Bootstrap-based statistical method to minimize the effect of sample choices. The effectiveness of the proposed method, called Bootstrap simulation, is compared to the numerical solution results for a set of examples described using SAN modeling formalism. / Através de formalismos Markovianos é possível modelar diversos sistemas e resolvê-los através de soluções computacionais específicas possibilitando prever ou avaliar seus padrões de comportamento. O formalismo de Redes de Autômatos Estocásticos (SAN) permite descrever modelos Markovianos de forma compacta e modular. Além disso, é utilizado para obter íındices de desempenho de sistemas através de soluções numéricas iterativas que se baseiam em um descritor e um vetor cujo tamanho é igual ao espaço de estados do modelo. Dependendo do tamanho do modelo esta operaçao torna-se computacionalmente onerosa e muitas vezes impraticável. Um método alternativo para calcular índices a partir de um modelo é a simulação, principalmente porque ela simplesmente exige a definição de um gerador de números pseudo-aleatórios e funções de transição entre estados que permitem a criação de uma trajetória. O processo de amostragem pode ser diferente para cada técnica estabelecendo algumas regras para coleta de amostras para posterior análise estatística. As técnicas de simulação, normalmente requerem muitas amostras para calcular índices de desempenho estatisticamente relevantes. Este trabalho proporciona comparações da precisão dos resultados de alguns modelos Markovianos obtidos a partir da execução de diferentes técnicas de simulação. Além disso, propõe uma maneira distinta de simular modelos Markovianos usando um método baseado em estatística Bootstrap para minimizar o efeito de escolha das amostras. A eficácia do método proposto, denominado Bootstrap simulation, é comparado com resultados da solução numérica para um conjunto de exemplos descritos por meio do formalismo de modelagem SAN.
14

Diminuição da intrusão do teste de software em programas paralelos

Amaral, Leonardo Albernaz January 2006 (has links)
Made available in DSpace on 2013-08-07T18:42:48Z (GMT). No. of bitstreams: 1 000387398-Texto+Completo-0.pdf: 1888290 bytes, checksum: 75c45ec3baed89ae6d44149b3c5e8b3a (MD5) Previous issue date: 2006 / This work introduces a strategy aiming the reduction of the intrusion (probe-effect mitigation) resulting from software testing activities in message passing parallel programs. In order to accomplish this goal, a test environment has been developed, based on functional software testing techniques and debugging approaches. The environment, which makes use of Java as the programming language and MPI as the library for message exchange, is based on the use of Stochastic Automata Network (SAN) for the application behavioural model representation. Test cases are created from this behavioural model to stimulate parallel programs, seeking for inter-process communication errors. These faults are identified by monitoring and analysis modules, using on-line approaches, that observe the application’s execution looking for inconsistencies between reached and expected states in the model. In order to define a less intrusive test strategy, emphasis has been given not only to the definition and generation of test cases, but also to the approaches employed in the test engine for the monitoring and analysis stages. It is expected that this strategy would help in the validation of the testing process approaches, and also in the identification of eventual problems. / Nesse trabalho é apresentada uma estratégia para diminuir a intrusão do teste de software em programas paralelos baseados em troca de mensagens. Para isso, um ambiente de teste foi desenvolvido utilizando técnicas de teste de software funcional e abordagens de depuração. O ambiente, que utiliza Java como linguagem de programação e MPI como biblioteca para troca de mensagens, baseia-se na idéia de utilizar Rede de Autômatos Estocásticos (SAN) para a representação do modelo comportamental da aplicação e, com isso, criar casos de teste que exercitem a aplicação paralela na busca por falhas de comunicação entre os processos. Essas falhas são identificadas pelos módulos de monitoração e análise on-line, que observam a execução da aplicação, verificando inconsistências entre os estados atingidos e os estados esperados do modelo. Para a diminuição da intrusão foi dada ênfase tanto para a definição e geração de casos de teste, quanto para as abordagens utilizadas no engine de teste nas etapas de monitoração e análise. Busca-se com essa estratégia, validar as abordagens utilizadas no processo de teste e identificar eventuais problemas.
15

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

Czekster, Ricardo Melo January 2010 (has links)
Made available in DSpace on 2013-08-07T18:43:08Z (GMT). No. of bitstreams: 1 000423499-Texto+Completo-0.pdf: 2268638 bytes, checksum: a9a287a49644290eaf88a8b8d38f9f10 (MD5) Previous issue date: 2010 / 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.
16

Algoritmo para conversão automática de modelos SAN GTA para modelos SAN CTA

Gil, Paulo Guilherme January 2013 (has links)
Made available in DSpace on 2013-08-07T18:43:22Z (GMT). No. of bitstreams: 1 000447661-Texto+Completo-0.pdf: 550622 bytes, checksum: 5a831618aedabce5554e131c45fcd8d9 (MD5) Previous issue date: 2013 / This work presents a formalism for modeling systems called Stochastic Automata Networks (SAN), SAN formalism aims to increase the abstraction’s level and provides a sophisticated alternative model to the tadicional formalism of Markov Chains (MC). SAN uses both Classical (CTA) and Generalized Tensor Algebra (GTA) to simplify the matrix of transitions between states of the model. Despite all models described with GTA having at least one equivalent model described using CTA, and that the solution of certain models based on CTA could be faster than the equivalent GTA based model, this dissertation proposes an algorithm for translating a model described in GTA into the equivalent model described in CTA. It is expected that some models described using functions (using GTA) could be solved more quickly or taking less memory through the solution of its CTA-converted model. / Este trabalho apresenta o formalismo para modelagem de sistemas chamado Redes de Autômatos Estocásticos (SAN). O formalismo SAN tem o objetivo de aumentar o nível de abstração e oferece uma alternativa de modelagem mais sofisticada do que a proporcionada pelas tradicionais Cadeias de Markov (MC). Este formalismo utiliza a álgebra tensorial clássica (CTA) e geralizada (GTA) para simplificar a matriz das transições entre os estados do modelo. Embora todos os modelos SAN descritos utilizando GTA possuam pelo menos um modelo equivalente descrito utilizando CTA, e que a solução de certos modelos utilizando CTA possa ser mais rápido que o modelo equivalente que utiliza GTA, este trabalho propõe um algoritmo para traduzir um modelo descrito em GTA para o modelo equivalente descrito em CTA. Espera-se com isto permitir que um modelo descrito utilizando funções (usando GTA) possa ser resolvido mais rapidamente ou ocupando menos memória através da solução de seu modelo convertido para CTA.
17

Utilização de diagramas de decisão multi-valorada para representação do espaço de estados atingível em redes de autômatos estocásticos

Scolari, Ana Paula Salengui January 2008 (has links)
Made available in DSpace on 2013-08-07T18:43:24Z (GMT). No. of bitstreams: 1 000400013-Texto+Completo-0.pdf: 1799901 bytes, checksum: 8f9035ff6f9f2bcba55f62be7f4e0d52 (MD5) Previous issue date: 2008 / Modeling formalisms are languages capable of describing a system behavior in a non ambiguous way, allowing its quantitative evaluation. The structured formalisms can represent large and complex models in a systematic manner. However, the modeling of systems with such characteristics is still a problem, since the space state explosion is often a known issue. Usually, structured formalisms with discrete state space present a large number of unreachable states. This work presents an algorithm able to generate and storing the reachable space state of a Stochastic Automata Network (SAN) using Multi-valued Decision Diagram (MDD). This new technique aims to mainly verify that the applicability of MDD for SAN is a valuable approach. / Formalismos de modelagem são linguagens capazes de descrever sistemas de forma não ambígüa, permitindo a sua avaliação quantitativa. Os formalismos conhecidos como estruturados permitem a representação sistemática de modelos grandes e complexos. Entretanto, na prática, a modelagem de sistemas de tal porte pode apresentar o problema de explosão do espaço de estados. Em geral, a modelagem de sistemas através de formalismos estruturados, com espaço de estados discreto, resulta em um grande número de estados inatingíveis. A geração e armazenamento dos estados não atingíveis é um ônus não desejado ao processo de modelagem. Este trabalho apresenta um algoritmo capaz de gerar e armazenar somente o espaço de estados atingível (RSS) para o formalismo de Redes de Autômatos Estocásticos (SAN) utilizando Diagramas de Decisão Multi-Valorada (MDD). A idéia principal é apresentar uma primeira versão desse algoritmo, a m de comprovar a sua viabilidade para o formalismo SAN.
18

Técnica para obtenção de redes de autômatos estocásticos baseada em especificações de software em UML

Neuwald, Felipe Barp January 2008 (has links)
Made available in DSpace on 2013-08-07T18:43:26Z (GMT). No. of bitstreams: 1 000406275-Texto+Completo-0.pdf: 5088741 bytes, checksum: 77356f5ee18c1f01b23fcf0d1843be33 (MD5) Previous issue date: 2008 / Performance evaluation of an object oriented software nowadays can be done, basically, by three different kinds of methods: Stress Testing, Simulations or Analytic Methods, like Stochastic Automata Networks or Queuing Networks. Stress Testing is an efficient method, but could only be performed on final phases of a software development process when the final product is almost finished. Simulations can be performed in initial phases of a software development process, but usually at a high cost, because it depends on a creation of a simulator. The Analytic Methods could be performed at the earlier phases of the software development process too, but they require a creation of a performance evaluation model. ln the object oriented software development a model is created, which contains detailed information about the system. This information could be used to generate a performance evaluation model, since many of the information containing on each other are common. Following that idea researches were made generating methods for conversion of UML diagram into performance evaluation methods, for example, to Queuing Network. However, does not exist a method or technique that converts UML to formalisms like SAN, which has a higher representative power then Queuing Networks. This work will present a technique for converting UML diagrams into Stochastic Automata Networks focusing on the representation of the logical architecture of object oriented softwares. / A avaliação de desempenho de um software orientado a objetos, hoje, pode ser feita basicamente de três maneiras: com testes de desempenho, simulações ou utilizando métodos analíticos como redes de Autômatos estocásticos e redes de filas de espera. Os testes de desempenho são eficientes e, porem podem ser aplicados apenas nas fases finais do desenvolvimento de software, quando o produto esta praticamente pronto, as simulações podem ser realizadas nas etapas iniciais do processo de desenvolvimento de software porém, geralmente, são custosas, pois dependem da criação de um simulador. Os métodos analíticos podem ser aplicados nas fases iniciais do desenvolvimento, mas exigem a criação de um modelo de avaliação de desempenho. No desenvolvimento de software orientados a objetos já se constrói um modelo, o qual possui informações detalhadas sobre o sistema. Estas informações podem ser utilizadas para gerar um modelo de avaliação de desempenho que represente o software já que muitas das informações contidas no modelo do software são comuns ao modelo de avaliação de desempenho. Utilizando esta idéia foram criados alguns métodos de conversão de UML para formalismos de avaliação de desempenho como redes de filas de espera. Porem, ainda inexiste métodos ou técnicas que convertem UML para formalismos como SAN, que é mais abrangente que, por exemplo, redes de espera. Este trabalho demonstra uma técnica de conversão de UML para SAN, onde explora-se a representação da arquitetura lógica de software orientados a objetos.
19

Abordagens paralelas para Model Checking de redes de autômatos estocásticos

Oleksinski, Lucas Giaretta January 2013 (has links)
Made available in DSpace on 2013-10-11T13:35:22Z (GMT). No. of bitstreams: 1 000451032-Texto+Completo-0.pdf: 3224202 bytes, checksum: 0ed1399ff0656c16c4c22f4f6e16cb87 (MD5) Previous issue date: 2013 / The use of critical and complex systems at automation of daily tasks increases the people’s dependence, generating unease about the safety of such systems. In the last years several techniques have been developed to facilitate activities related to design validation in the early stages of the development cycle. Model Checking is an automatic formal technique that allows verification of finite-state concurrent systems under properties described in temporal logics by employing verification algorithms that exhaustively assess the correctness of the system under consideration. Indeed, this technique is costly with respect to storage and processing, justifying the development of parallel and distributed algorithms for powerful computing clusters. This dissertation reports the study and development of verification algorithms for models described in Stochastic Automata Networks and properties written in Computation Tree Logic temporal logic for environments that address memory spaces in a distributed way. / O emprego de sistemas complexos e críticos para automação de tarefas do cotidiano faz crescer a dependência das pessoas, gerando desconforto em relação à segurança de tais sistemas. Nos últimos anos algumas técnicas têm sido desenvolvidas visando facilitar as atividades relacionadas à validação de projetos nos estágios iniciais do ciclo de desenvolvimento. Verificação de modelos é uma técnica formal automática que permite a verificação de sistemas concorrentes de estados finitos sob propriedades descritas em lógicas temporais através do emprego de algoritmos que avaliam exaustivamente o sistema sob consideração. Entretanto, esta técnica é custosa no que tange ao armazenamento em memória e processamento, justificando o desenvolvimento de algoritmos paralelos e distribuídos para poderosos agregados computacionais. Esta dissertação relata o estudo e desenvolvimento de algoritmos de verificação de modelos descritos em Redes de Autômatos Estocásticos e propriedades descritas na lógica temporal Computation Tree Logic para ambientes que endereçam espaços de memória de maneira distribuída.
20

Uso de redes de autômatos estocásticos – SAN na modelagem e avaliação do protocolo DSR em redes wireless ad hoc

Nascimento, Everton Ricardo do January 2009 (has links)
Made available in DSpace on 2013-08-07T18:43:38Z (GMT). No. of bitstreams: 1 000425006-Texto+Completo-0.pdf: 2030732 bytes, checksum: af723abcff811e622f9a8f3c907145a0 (MD5) Previous issue date: 2009 / The performance evaluation of routing protocols for Ad hoc networks is usually made through simulation techniques and tools. The use of Stochastic Automata Networks is a new alternative to evaluate such protocols, since this formalism can handle very large spaces of states, which it was one of the major problems of other analytical formalisms. The routing protocols for Ad hoc networks are a key factor in the success of the data transmissions task between the nodes, so the DSR - Dynamic Source Routing, protocol was evaluated at this work. DSR protocol main characteristics are the techniques of discovery and maintenance of routes, in order to assure the smaller - or better - route inside a network. The first contribution of this work is the straight evaluation of route discovery process, as well as the possibility of transmission failures and the need of route maintenance. These results are directly connected with the workload of the network, which is directly related to route utilization results. The second contribution is the analysis of networks with a DSR protocol with promiscuous listening in order to evaluate if the use of such characteristic helps the networks behavior. Are also presented evaluation results of metrics like throughput with different packets sizes and nodes pause time during the transmission inside a network that uses the DSR protocol to information routing. Additionally, this work demonstrate the efficiency of the Stochastic Automata Networks formalism to obtain these metrics as an alternative to evaluate this type of environment while similar results were obtained in literature. / A avaliação de desempenho dos protocolos de roteamento de redes Ad hoc é realizada, em sua maioria, através do uso de técnicas e ferramentas de simulação. Através do uso das Redes de Autômatos Estocásticos, surge uma nova alternativa para realizar esta avaliação, já que este formalismo provê grande quantidade de espaços de estados, que era um dos grandes problemas de outros formalismos analíticos. Os protocolos de roteamento para redes sem fio Ad hoc são um fator determinante no sucesso da tarefa de transmissão de dados entre os nodos. Sendo assim, foi avaliado neste trabalho o protocolo DSR - Dynamic Source Routing, que tem como características principais as técnicas de descoberta e manutenção de rota, a fim de garantir a menor - ou melhor - rota dentro de uma rede. A primeira contribuição presente neste trabalho trata diretamente da avaliação deste processo de descoberta de rota, bem como da possibilidade de falhas de transmissão ocorrerem e o processo de manutenção de rota se fazer necessário. Estes resultados estão diretamente ligados aos resultados obtidos avaliando-se o workload dos nodos da rede, que reflete diretamente na utilização das rotas.A segunda contribuição é a análise do comportamento de redes quando estas utilizam uma particularidade do protocolo DSR que é a escuta promíscua (promiscuous listening). Busca-se avaliar se o uso de tal característica auxilia no funcionamento da rede. São apresentados também resultados de avaliação de métricas como vazão com diferentes tamanhos de pacotes e tempos de pausa dos nodos durante a transmissão dentro de uma rede que utiliza o protocolo DSR para o roteamento das informações. Adicionalmente busca-se demonstrar a eficiência das Redes de Autômatos Estocásticos na obtenção destas métricas e assim apresentar este formalismo como uma alternativa para avaliação deste tipo de ambiente, dada a similaridade dos resultados obtidos, se comparados àqueles apresentados na literatura.

Page generated in 0.1038 seconds