A simulação paralela de eventos é uma área da computação que congrega grande volume de pesquisas, pela importância em facilitar o estudo de novas soluções nas mais diferentes áreas da ciência e tecnologia, sem a necessidade da construção de onerosos protótipos. Diversos protocolos de simulação paralela podem ser encontrados, divididos em dois grandes grupos de acordo com o algoritmo empregado para a execução em ordem dos eventos: os conservadores e os otimistas; contudo, ambos os grupos utilizam trocas de mensagens para a sincronização e comunicação. Neste trabalho, foi desenvolvido um novo protocolo de simulação paralela, fazendo uso de memória compartilhada, o qual foi implementado e testado sobre um ambiente de estações de trabalho, realizando, assim, simulação paralela com uso de memória compartilhada distribuída. O protocolo foi desenvolvido tendo como base de funcionamento os protocolos conservadores; utilizou diversas características dos mesmos, mas introduziu várias mudanças em seu funcionamento. Sua execução assemelha-se às dos protocolos de execução síncrona, utilizando conceitos como o lookahead e janelas de tempo para execução de eventos. A principal mudança que o novo protocolo sofreu foi proporcionada pelo acesso remoto à memória de um LP por outro, produzindo diversas outras nas funções relativas à sincronização dos processos, como o avanço local da simulação e o agendamento de novos eventos oriundos de outro LP. Um ganho adicional obtido foi a fácil resolução do deadlock, um dos grandes problemas dos protocolos conservadores de simulação paralela. A construção de uma interface de comunicação eficiente com uso de memória compartilhada é o principal enfoque do protocolo, sendo, ao final da execução de uma simulação, disponibilizado o tempo de simulação e o tempo de processamento ocioso (quantia utilizada em comunicação e sincronização). Além de uma implementação facilitada, propiciada pelo uso de memória compartilhada ao invés de trocas de mensagens, o protocolo oferece a possibilidade de melhor ocupar o tempo ocioso dos processadores, originado por esperas cada vez que um LP chega a uma barreira de sincronização. Em nenhum momento as modificações efetuadas infringiram o princípio operacional dos protocolos conservadores, que é não possibilitar a ocorrência de erros de causalidade local. O novo protocolo de simulação foi implementado e testado sobre um ambiente multicomputador de memória distribuída, e seus resultados foram comparados com dois outros simuladores, os quais adotaram as mesmas estratégias, com idênticas ferramentas e testados em um mesmo ambiente de execução. Um simulador implementado não utilizou paralelismo, tendo seus resultados sido utilizados como base para medir o speedup e a eficiência do novo protocolo. O outro simulador implementado utilizou um protocolo conservador tradicional, descrito na literatura, realizando as funções de comunicação e sincronização através de trocas de mensagens; serviu para uma comparação direta do desempenho do novo protocolo proposto, cujos resultados foram comparados e analisados.

A simulação paralela de eventos é uma área da computação que congrega grande volume de pesquisas, pela importância em facilitar o estudo de novas soluções nas mais diferentes áreas da ciência e tecnologia, sem a necessidade da construção de onerosos protótipos. Diversos protocolos de simulação paralela podem ser encontrados, divididos em dois grandes grupos de acordo com o algoritmo empregado para a execução em ordem dos eventos: os conservadores e os otimistas; contudo, ambos os grupos utilizam trocas de mensagens para a sincronização e comunicação. Neste trabalho, foi desenvolvido um novo protocolo de simulação paralela, fazendo uso de memória compartilhada, o qual foi implementado e testado sobre um ambiente de estações de trabalho, realizando, assim, simulação paralela com uso de memória compartilhada distribuída. O protocolo foi desenvolvido tendo como base de funcionamento os protocolos conservadores; utilizou diversas características dos mesmos, mas introduziu várias mudanças em seu funcionamento. Sua execução assemelha-se às dos protocolos de execução síncrona, utilizando conceitos como o lookahead e janelas de tempo para execução de eventos. A principal mudança que o novo protocolo sofreu foi proporcionada pelo acesso remoto à memória de um LP por outro, produzindo diversas outras nas funções relativas à sincronização dos processos, como o avanço local da simulação e o agendamento de novos eventos oriundos de outro LP. Um ganho adicional obtido foi a fácil resolução do deadlock, um dos grandes problemas dos protocolos conservadores de simulação paralela. A construção de uma interface de comunicação eficiente com uso de memória compartilhada é o principal enfoque do protocolo, sendo, ao final da execução de uma simulação, disponibilizado o tempo de simulação e o tempo de processamento ocioso (quantia utilizada em comunicação e sincronização). Além de uma implementação facilitada, propiciada pelo uso de memória compartilhada ao invés de trocas de mensagens, o protocolo oferece a possibilidade de melhor ocupar o tempo ocioso dos processadores, originado por esperas cada vez que um LP chega a uma barreira de sincronização. Em nenhum momento as modificações efetuadas infringiram o princípio operacional dos protocolos conservadores, que é não possibilitar a ocorrência de erros de causalidade local. O novo protocolo de simulação foi implementado e testado sobre um ambiente multicomputador de memória distribuída, e seus resultados foram comparados com dois outros simuladores, os quais adotaram as mesmas estratégias, com idênticas ferramentas e testados em um mesmo ambiente de execução. Um simulador implementado não utilizou paralelismo, tendo seus resultados sido utilizados como base para medir o speedup e a eficiência do novo protocolo. O outro simulador implementado utilizou um protocolo conservador tradicional, descrito na literatura, realizando as funções de comunicação e sincronização através de trocas de mensagens; serviu para uma comparação direta do desempenho do novo protocolo proposto, cujos resultados foram comparados e analisados.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2014 / Made available in DSpace on 2015-02-05T21:02:33Z (GMT). No. of bitstreams: 1 330255.pdf: 3149547 bytes, checksum: 67161f66dc891b9dd0fe6599ef298d40 (MD5) Previous issue date: 2014 / O multiprocessamento em chip sob a crescente demanda por desempenho leva a um número crescente de núcleos de processamento, que interagem através de uma complexa hierarquia de memória compartilhada, a qual deve obedecer a requisitos de coerência e consistência, capturados na interface hardware-software na forma de um modelo de memória. Dada uma execução de um programa paralelo, verificar se a hierarquia obedece aqueles requisitos é um problema intratável quando a observabilidade do sistema restringe-se a um trace de memória para cada processador, tal como ocorre em um checker dinâmico pós-silício. Esses checkers (baseados em inferências sobre traces) requerem o uso de backtracking para excluir falsos negativos. Por outro lado, checkers pré-silício podem se beneficiar da observabilidade ilimitada de representações de projeto para induzir um problema de verificação que pode ser resolvido em tempo polinomial (sem o uso de backtracking) e com plenas garantias de verificação (sem falsos negativos nem falsos positivos). Esta dissertação faz uma avaliação experimental comparativa de checkers dinâmicos baseados em diferentes mecanismos (inferências, emparelhamento em grafo bipartido, scoreboard única e múltiplas scoreboards). Os checkers são comparados para exatamente o mesmo conjunto de casos de teste: 200 programas paralelos não sincronizados, gerados de forma pseudo-aleatória, obtidos variando a frequência de ocorrência de instruções (4 mixes), o número de endereços compartilhados (entre 2 e 32) e o número total de operações de memória (entre 250 e 64K). A partir de uma mesma representação pré-validada do sistema, foram construídas oito representações derivadas, cada uma contendo um erro de projeto distinto. Para reproduzir condições compatíveis com as tendências arquiteturais, os checkers foram comparados ao verificar um modelo com máxima relaxação de ordem de programa (bastante similar ao usado, por exemplo, nas arquiteturas Alpha e ARMv7) para sistemas contendo de 2 a 32 núcleos de processamento. Não é do conhecimento do autor a existência na literatura de uma avaliação experimental tão ampla. Os resultados mostram a inviabilidade do uso de checkers baseados em inferências em tempo de projeto: têm o mais alto esforço computacional e a maior taxa de crescimento com o aumento do número de processadores. A avaliação indica que a forma mais eficiente de construir um checker pré-silício corresponde a uma observabilidade de três pontos de monitoramento por processador, ao uso de verificação on-the-fly (ao invés de análise post-mortem) e à utilização de múltiplos mecanismos para verificar separadamente e em paralelo os subespaços de verificação definidos pelo escopo individual de cada processador, enquanto os subespaços entre processadores são verificados globalmente. Como um desdobramento da avaliação experimental, a dissertação identifica uma deficiência comum a todos os checkers analisados: sua inadequação para verificar modelos de memória com fraca atomicidade de escrita, exatamente aqueles apontados como tendência e já presentes em arquiteturas recentes (e.g. ARMv8). Diante disso, a dissertação propõe algoritmos generalizados capazes de verificar tais modelos.<br> / Abstract: Chip multiprocessing under the growing demand for performance leads to agrowing number of processing cores, which interact through a complex shared memory hierarchy that must satisfy coherence and consistency requirements captured as a memory model in the hardware-software interface. Given an execution of a parallel program, verifying if the hierarchy complies to those requirements is an intractable problem when the system observability is limited to a memory trace per processor, as in dynamic post-silicon checkers.Those checkers (based on inferences over traces) require the use of backtracking to avoid false negatives. On the other hand, pre-silicon checkers may benefit from the unlimited observability of design representations to induce a verification problem that may be solved in polynomial time (without the use of backtracking) with full verification guarantees (i.e. neither false negatives nor false positives). This dissertation provides an experimental evaluation of dynamic checkers based on different mechanisms (inferences, bipartite graph matching, single scoreboard and multiple scoreboards). The checkers are compared under exactly the same set of test cases: 200 non-synchronized parallel programs, generated pseudo-randomly, obtained by varying the frequency of instructions (4 mixes), the number of shared addresses (between 2 and 32) and the total number of memory operations (between 250 and 64K). From the same pre-validated system representation, eight distinct representations were built, each one containing a single and unique design error. To reproduce conditions compatible with architectural trends, the checkers were compared while verifying a memory model with maximal relaxation of program order (similar, for example, to those used in Alpha and ARMv7 architectures) and systems containing 2 to 32 processing cores. To the author's best knowledge, no broader experimental evaluation is available in the literature. The results show that the use of inference-based checkers at design time is impractical: they have the highest computational effort and the highest rate of growth with the number of cores. The evaluation shows that the most efficient way of building a pre-silicon checker corresponds to three observable points per core, the use of on-the-fly analysis (instead of post-mortem) and the usage of multiple engines to check the verification subspaces defined by the scope of each processor independently and in parallel, while checking globally the inter-processor subspaces. As a spin-off from the experimental evaluation, the dissertation identifies a deficiency common to all analyzed checkers: their unsuitability to handle memory models with weak write atomicity, which are precisely those pointed out as the trend and are present in architectures already in the market (e.g. ARMv8). In face of this, the dissertation proposes generic algorithms capable of verifying such models.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2017. / Made available in DSpace on 2017-06-27T04:21:32Z (GMT). No. of bitstreams: 1 345872.pdf: 1423815 bytes, checksum: d7ab5e6898d999346ceec9e69c88bedd (MD5) Previous issue date: 2017 / Introdução A verificação funcional do projeto de um sistema com multiprocessamento em chip (CMP) vem se tornando cada vez mais desafiadora por causa da crescente complexidade para suportar a abstração de memória compartilhada coerente, a qual provavelmente manterá seu papel crucial para multiprocessamento em chip, mesmo na escala de centenas de processadores. A verificação funcional baseia-se principalmente na geração de programas de teste aleatórios.Trabalhos Correlatos e Gerador Proposto Embora frameworks de verificação funcional que se baseiam na solução de problemas de satisfação de restrições possuam a vantagem de oferecer uma abordagem unificada para gerar estímulos aleatórios capazes de verificar todo o sistema, eles não são projetados para explorar não-determinismo, que é um importante mecanismo para expôr erros de memória compartilhada. Esta dissertação reporta novas técnicas que se baseiam em lições aprendidas de ambos? os frameworks de verificação de propósitos gerais e as abordagens especializadas em verificar o modelo de memória. Elas exploram restrições sobre endereços e cadeias canônicas de dependência para melhorar a geração de testes aleatórios enquanto mantêm o papel crucial do não-determinismo como um mecanismo-chave para a exposição de erros. Geração de Sequências Ao invés de selecionar instruções aleatoriamente, como faz uma técnica convencional, o gerador proposto seleciona instruções de acordo com cadeias de dependências pré-definidas que são comprovadamente significativas para preservar o modelo de memória sob verificação. Esta dissertação explora cadeias canônicas, definidas por Gharachorloo, para evitar a indução de instruções que, sendo desnecessárias para preservar o modelo de memória sob verificação, resultem na geração de testes ineficazes. Assinalamento de Endereços Em vez de selecionar aleatoriamente padrões binários para servir de endereços efetivos de memória, como faz um gerador convencional, o gerador proposto aceita restrições à formação desses endereços de forma a forçar o alinhamento de objetos em memória, evitar falso compartilhamento entre variáveis e especificar o grau de competição de endereços por uma mesma linha de cache. Avaliação Experimental Um novo gerador, construído com as técnicas propostas, foi comparado com um gerador convencional de testes aleatórios. Ambos foram avaliados em arquiteturas de 8, 16, e 32 núcleos, ao sintetizar 1200 programas de testes distintos para verificar 5 projetos derivados, cada um contendo um diferente tipo de erro (6000 casos de uso por arquitetura). Os testes sintetizados exploraram uma ampla variedade de parâmetros de geração (5 tamanhos de programas, 4 quantidades de posições compartilhadas de memória, 4 mixes de instruções, e 15 sementes aleatórias). Os resultados experimentais mostram que, em comparação com um convencional, o novo gerador tende a expor erros para um maior número de configurações dos parâmetros: ele aumentou em 38% o potencial de expor erros de projeto. Pela análise dos resultados da verificação sobre todo o espectro de parâmetros, descobriu-se que os geradores requerem um número bastante distinto de posições de memória para alcançar sua melhor exposição. Os geradores foram comparados quando cada um explorou a quantidade de posições de memória correspondente à sua melhor exposição. Nestas condições, quando destinados a projetos com 32 núcleos através da exploração de todo o espectro de tamanhos de testes, o novo gerador expôs um tipo de erro tão frequentemente quanto a técnica convencional, dois tipos com 11% mais frequência, um tipo duas vezes, e um tipo 4 vezes mais frequentemente. Com os testes mais longos (64000 operações) ambos os geradores foram capazes de expor todos os tipos de erros, mas o novo gerador precisou de 1,5 a 15 vezes menor esforço para expor cada erro, exceto por um (para o qual uma degradação de 19% foi observada). Conclusões e Perspectivas Com base na avaliação realizada, conclui-se que, quando se escolhe um número suficientemente grande de variáveis compartilhadas como parâmetro, o gerador proposto requer programas de teste mais curtos para expor erros de projeto e, portanto, resulta em menor esforço, quando comparado a um gerador convencional.<br> / Abstract : Albeit general functional processor verification frameworks relying on the solution of constraint satisfaction problems have the advantage of offering a unified approach for generating random stimuli to verify the whole system, they are not designed to exploit non-determinism, which is an important mechanism to expose shared-memory errors. This dissertation reports new techniques that build upon the lessons learned from both - the general verification frameworks and the approaches specifically targeting memory-model verification. They exploit address biasing constraints and canonical dependence chains to improve random test generation while keeping the crucial role of non-determinism as a key mechanism to error exposure. A new generator, built with the proposed techniques, was compared to a conventional random test generator. Both were evaluated for 8, 16, and 32-core architectures, when synthesizing 1200 distinct test programs for verifying 5 derivative designs containing each a different type of error (6000 use cases per architecture). The synthesized tests explored a wide variety of generation parameters (5 program sizes, 4 shared-location counts, 4 instruction mixes, and 15 random seeds). The experimental results show that, as compared to a conventional one, the new generator tends to expose errors for a larger number of parameter settings: it increased by 38% the potential for exposing design errors. By analyzing the verification out-comes over the full parameter ranges, we found out that the generators require quite distinct numbers of shared locations to reach best exposure. We compared them when each generator exploited the location count leading to its best exposure. In such conditions, when targeting32-core designs by exploring the whole range of test lengths, the new generator exposed one type of error as often as the conventional technique, two types 11% more often, one type twice as often, and one type4 times as often. With the longest tests (64000 operations) both generators were able to expose all types of errors, but the new generator required from 1.5 to 15 times less effort to expose each error, except for one (for which a degradation of 19% was observed).

A simulação paralela de eventos é uma área da computação que congrega grande volume de pesquisas, pela importância em facilitar o estudo de novas soluções nas mais diferentes áreas da ciência e tecnologia, sem a necessidade da construção de onerosos protótipos. Diversos protocolos de simulação paralela podem ser encontrados, divididos em dois grandes grupos de acordo com o algoritmo empregado para a execução em ordem dos eventos: os conservadores e os otimistas; contudo, ambos os grupos utilizam trocas de mensagens para a sincronização e comunicação. Neste trabalho, foi desenvolvido um novo protocolo de simulação paralela, fazendo uso de memória compartilhada, o qual foi implementado e testado sobre um ambiente de estações de trabalho, realizando, assim, simulação paralela com uso de memória compartilhada distribuída. O protocolo foi desenvolvido tendo como base de funcionamento os protocolos conservadores; utilizou diversas características dos mesmos, mas introduziu várias mudanças em seu funcionamento. Sua execução assemelha-se às dos protocolos de execução síncrona, utilizando conceitos como o lookahead e janelas de tempo para execução de eventos. A principal mudança que o novo protocolo sofreu foi proporcionada pelo acesso remoto à memória de um LP por outro, produzindo diversas outras nas funções relativas à sincronização dos processos, como o avanço local da simulação e o agendamento de novos eventos oriundos de outro LP. Um ganho adicional obtido foi a fácil resolução do deadlock, um dos grandes problemas dos protocolos conservadores de simulação paralela. A construção de uma interface de comunicação eficiente com uso de memória compartilhada é o principal enfoque do protocolo, sendo, ao final da execução de uma simulação, disponibilizado o tempo de simulação e o tempo de processamento ocioso (quantia utilizada em comunicação e sincronização). Além de uma implementação facilitada, propiciada pelo uso de memória compartilhada ao invés de trocas de mensagens, o protocolo oferece a possibilidade de melhor ocupar o tempo ocioso dos processadores, originado por esperas cada vez que um LP chega a uma barreira de sincronização. Em nenhum momento as modificações efetuadas infringiram o princípio operacional dos protocolos conservadores, que é não possibilitar a ocorrência de erros de causalidade local. O novo protocolo de simulação foi implementado e testado sobre um ambiente multicomputador de memória distribuída, e seus resultados foram comparados com dois outros simuladores, os quais adotaram as mesmas estratégias, com idênticas ferramentas e testados em um mesmo ambiente de execução. Um simulador implementado não utilizou paralelismo, tendo seus resultados sido utilizados como base para medir o speedup e a eficiência do novo protocolo. O outro simulador implementado utilizou um protocolo conservador tradicional, descrito na literatura, realizando as funções de comunicação e sincronização através de trocas de mensagens; serviu para uma comparação direta do desempenho do novo protocolo proposto, cujos resultados foram comparados e analisados.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2010 / Made available in DSpace on 2012-10-25T07:50:16Z (GMT). No. of bitstreams: 1 278429.pdf: 1820106 bytes, checksum: 30e9982fc870d4660599ea9fe15250db (MD5) / Diversas pesquisas para desenvolvimento de soluções práticas de suporte a aplicações distribuídas tolerantes a faltas bizantinas têm sido realizadas nos últimos anos. Embora seja um conceito apresentado há cerca de trinta anos, somente na última década foram apresentadas soluções para tolerância a faltas bizantinas com foco na viabilidade prática de implementação. Dado o aumento da conectividade em todos tipos de sistemas computacionais, estudos recentes apresentam propostas que visam garantir que o sistema se mantenha correto mesmo na ocorrência de uma intrusão, isto é, de um ataque que obteve sucesso ao explorar uma vulnerabilidade. O principal desafio dos trabalhos na área de tolerância a faltas bizantinas/intrusões reside em propor arquiteturas e protocolos cuja implementação possa ser concretizada em termos práticos. Os fatores proibitivos de propostas anteriores dizem respeito ao custo de implantação e execução dessas propostas e também à complexidade do código necessário para a implementação dos protocolos. Alguns trabalhos têm considerado o uso de tecnologias de virtualização para a construção de ambientes de computação confiável, tomando proveito de recursos específicos de ambientes virtualizados em prol de protocolos de suporte mais simples.Nesse contexto, o presente trabalho apresenta SMIT, uma arquitetura para tolerância a intrusões baseada em tecnologias de virtualização e na utilização de memória compartilhada entre máquinas virtuais. Tal área de memória é utilizada para a simplificação dos protocolos de execução de requisições de clientes nas réplicas de serviço, concretizando o consenso sobre a ordem de execução de operações em tais réplicas em um menor número de passos de comunicação do que propostas anteriores. Devido à utilização da memória compartilhada, também foi possível reduzir o número mínimo de réplicas requeridas para garantia da correção do modelo sob a presença de f réplicas faltosas. Tal redução se deu de 3f + 1 para 2f + 1. Para demonstrar a viabilidade prática da proposta, foram realizados experimentos práticos sobre um protótipo implementado da arquitetura.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-26T07:02:27Z (GMT). No. of bitstreams: 1 300498.pdf: 2938637 bytes, checksum: 7398afa3a077fac745bb7fa071d4f174 (MD5) / O multiprocessamento em chip (CMP) mudou o panorama arquitetural dos servidores e computadores pessoais e agora está mudando o modo como os dispositivos pessoais móveis são projetados. CMP requer acesso a variáveis compartilhadas em hierarquias multiníveis sofisticadas onde caches privadas e compartilhadas coexistem. Ele se baseia no suporte em hardware para implicitamente gerenciar o relaxamento da ordem de programa e a atomicidade de escrita de modo a fornecer, na interface software-hardware, uma semântica de memória compartilhada bem definida, que é capturada pelos axiomas de um modelo de consistência de memória (MCM). Este trabalho aborda o problema de verificar se uma representação executável do subsistema de memória implementa um MCM especificado. Técnicas convencionais de verificação codificam os axiomas como arestas de um único grafo orientado, inferem arestas extras a partir de traces de memória e indicam um erro quando um ciclo é detectado. Usando uma abordagem diferente, esta dissertação propõe uma nova técnica que decompõe o problema de verificação em múltiplas instâncias de um problema (estendido) de emparelhamento de vértices em grafos bipartidos. Como a decomposição foi judiciosamente projetada para induzir instâncias independentes, o problema-alvo pode ser resolvido por um algoritmo paralelo de verificação. Também é proposto um gerador de sequências de instruções aleatórias distribuídas em múltiplas threads para estimular o sistema de memória sob verificação. Por ser independente do MCM sob verificação, o gerador proposto pode ser utilizado pela maioria dos verificadores. A técnica proposta, que é comprovadamente completa para diversos MCMs, superou um verificador convencional para um conjunto de 2400 casos de uso gerados aleatoriamente. Em média, o verificador proposto encontrou um maior percentual de faltas (90%) comparado ao convencional (69%) e foi, em média, 272 vezes mais rápido. / Chip multiprocessing (CMP) changed the architectural landscape of servers and personal computers and is now changing the way personal mobile devices are designed. CMP requires access to shared variables in sophisticated multilevel hierarchies where private and shared caches coexist. It relies on hardware support to implicitly manage relaxed program order and write atomicity so as to provide, at the hardware-software interface, a well-defined sharedmemory semantics, which is captured by the axioms of a memory consistency model (MCM). This dissertation addresses the problem of checking if an executable representation of the memory system complies with a specified consistency model. Conventional verification techniques encode the axioms as edges of a single directed graph, infer extra edges from memory traces, and indicate an error when a cycle is detected. Unlike them, this dissertation proposes a novel technique that decomposes the verification problem into multiple instances of an extended bipartite graph matching problem. Since the decomposition was judiciously designed to induce independent instances, the target problem can be solved by a parallel verification algorithm. To stimulate the memory system under verification, the dissertation also proposes a generator of multi-threading random-instruction sequences. It complies with an arbitrary MCM and can be used by most checkers. Our technique, which is proven to be complete for several MCMs, outperformed a conventional checker for a suite of 2400 randomly-generated use cases. On average, it found a higher percentage of faults (90%) as compared to that checker (69%) and did it, on average, 272 times faster.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2015. / Made available in DSpace on 2015-11-10T03:08:42Z (GMT). No. of bitstreams: 1 335943.pdf: 2286813 bytes, checksum: f696d21066655f662d160f31a95f850f (MD5) Previous issue date: 2015 / Memória Transacional em Software (STM) é um modelo utilizado para tratar acesso concorrente a dados compartilhados, onde programadores não precisam lidar explicitamente com mecanismos de controle de concorrência, como locks. O programador, apenas delineia qual parte do código necessita ser tratado como concorrente e sua execução seguirá o modelo transacional, respeitando as propriedades: atomicidade, consistência e isolação. É proposto nessa dissertação um modelo denominado Mesobi: Memória Transacional em Software Tolerante a Faltas Bizantinas onde transações somente leitura não abortam. Existem algumas abordagens na literatura que utilizam Memória Transacional em Software, das quais grande parte tolera faltas de parada mas pouco se fala sobre faltas maliciosas. Somente o trabalho de Zhang 2012 faz tolerância a faltas Bizantinas no contexto de STM; sua proposta utiliza dois clusters para alcançar tolerância a faltas Bizantinas.No modelo de Zhang, transações somente leitura podem ser abortadas, não é suportada a execução de transações interativas e não é possível executar transações de forma otimista. O Mesobi permite alcançar tolerância a faltas Bizantinas utilizando (3f+1) réplicas, sendo que, f é o número de faltas toleradas. O modelo consiste em inicialmente tentar executar as transações de forma otimista sem a necessidade de executar o protocolo Bizantino. Transações conflitantes localmente não são iniciadas de imediato com isso evita-se trabalho improdutivo. É possível e viável a execução de transações pré-declaradas e interativas no mesmo ambiente, sendo que, transações interativas têm pior desempenho devido a sua maior troca de mensagens.<br> / Abstract : Software Transactional Memory (STM) is a model to deal concurrent accesses on shared data. With STM developers do not need to cope with explicit concurrency control mechanisms like locks. Instead developers can write parallel portions of code as transactions, which are garanteed to execute atomically and in isolation regardless of eventual data races. In this dissertation we propose a model named Mesobi: Memória Transacional em Software Tolerante a Faltas Bizantinas in which read-only transactions do not abort. There are some approaches in literature that use STM, but most of them treat crash faults, but few deal with arbitrary faults. The work presented by Zhang 2012 mentions Byzantine Fault Tolerance (BFT) in STM context, but two clusters are necessary, one for consensus and another to execute transactions. Zhang's model abort read-only transactions, does not use optimistic execution neither interactive transactions processing. It achieves BFT using (3f+1) replicas where f represents the number of tolerated faults. The model executes in an optimistic fashion the transactions without the BFT protocol. Conflicting local transactions are not executed immediately thereby saving wasted work. Execution and consistency tests showed that execution of interactive and pre-declared transactions on same environment are possible and practical. Interactive transactions have worse performance than pre-declared due to need of more message exchanges.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia de Automação e Sistemas, Florianópolis, 2012 / Made available in DSpace on 2013-06-25T23:52:31Z (GMT). No. of bitstreams: 1 314311.pdf: 675294 bytes, checksum: 4f4a5c9fb7d567a0d9359a1006d7e819 (MD5) / As redes par a par (peer-to-peer, P2P) formam uma arquitetura de sistemas distribuídos que apresenta características de escalabilidade, abertura e dinamismo. Essas redes P2P foram inicialmente popularizadas por aplicações de compartilhamento de arquivos, porém hoje suas características as tornaram a base para construção de aplicações que necessitam de larga escala. Apesar das vantagens das redes P2P, sua grande abertura e dinamismo trazem algumas dificuldades para a construção de certos tipos de aplicações. Entre os principais desafios estão a dificuldade em manter a consistência das informações com a possibilidade de entrada e saída de nós durante a execução e a necessidade de tolerar a participação de nós maliciosos que tem por objetivo corromper o sistema e impedir seu funcionamento. Esses desafios fizeram com que a maioria das aplicações sobre P2P sejam aplicações de armazenamento de informações que sofrem pouca ou nenhuma alteração durante a execução e que são autoverificáveis, isto é, é possível identificar modificações maliciosas ou acidentais pela análise do próprio conteúdo. Dentro desse contexto, a proposta desta dissertação é a especificação de uma infraestrutura para a construção de aplicações arbitrárias, por meio de uma abstração de memória distribuída compartilhada, que tolere a participação de um número de nós maliciosos. A ideia central consiste em aplicar técnicas de Replicação Máquina de Estados (RME) sobre a rede P2P. No entanto, RME apresenta problemas de escala pois o número de mensagens trocadas para coordenar as réplicas é de ordem quadrática. Assim sendo, a proposta é dividir a rede P2P em conjuntos de nós com tamanho limitado, denominados de segmentos, de forma a garantir o desempenho dos protocolos RME. Segmentos são dinâmicos, ou seja, podem aumentar ou diminuir à medida que nós entram e saem do sistema, porém a infraestrutura garante, por meio da união ou divisão de segmentos, que o tamanho permanece dentro dos limites estabelecidos. O sistema foi elaborado como uma pilha de camadas com funcionalidades descritas na forma de operações e propriedades. As operações da segmentação foram implementadas por algoritmos em pseudocódigo, cujo funcionamento correto foi demonstrado em provas de lemas e teoremas. Uma análise crítica dos algoritmos esclareceu limitações e levantou os custos dos mesmos. A fim de demonstrar a expressividade da infraestrutura proposta, um espaço de tuplas foi construído utilizando as operações implementadas.<br> / Abstract : Peer-to-peer (P2P) networks form a distributed system architecture that feature good scalability, openness and dynamism. Such networks were first made popular by file-sharing applications, although nowadays these features bacame the basis for the construction of applications that require scalability. Even though P2P networks have some advantages, their openness and dynamism give raise to some difficulties in the construction of certain types of application. Among the most important challenges are the trouble to maintain consistency in face of constant nodes joining and leaving the system, and the need to tolerate the participation of malicious nodes whose purpose is to disrupt the system and to prevent its functioning. These challenges forced that most applications on P2P are storage applications where data is seldom changed and is self-verifying, i.e. it is possible to detect either malicious or accidental modifications by checking the data itself. Within this context, our proposal in this dissertation is the specification of an infrastruture for the construction of arbitrary applications, by means of a shared memory abstraction, that tolerates the participation of a certain number of malicious nodes. The central idea consists of leveraging State Machine Replication (SMR) techniques on top of P2P networks. The problem is SMR has scalability issues as the number of messages exchanged ikn replica coordination is quadratic. Given that, aor proposal is to split the P2P network in sets of limited size, called segments, in a way to ensure the SMR protocolos perform well. Segments are dynamic, i.e. they can grow or shrink as nodes join or leave the system, but the infrastruture guarantees, either by merging or splitting segments, that their size keeps within established limits. The system was designed as a stack of layers whose functionality is defined by a set of operations and its properties. The operations of the segmentation layer were implemented by distributed algorithms written in pseudocode. The correct operation of these algorithms was shown by theorem proofs. Furthermore, a critical analysis of these algorithms clarified limitations and assessed their costs. In order to demonstrate the expressiveness of the proposed infrastructure, a tuple space was built using the implemented operations.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2006. / Submitted by Fernanda Weschenfelder (nandaweschenfelder@gmail.com) on 2009-11-03T16:07:34Z No. of bitstreams: 1 Dissertacao_Lorena Brasil Cirilo Passos_20061207_CIC.pdf: 1280461 bytes, checksum: 5d78db2dd313197338c3e8ca3e9e811f (MD5) / Approved for entry into archive by Gomes Neide(nagomes2005@gmail.com) on 2010-02-08T18:32:57Z (GMT) No. of bitstreams: 1 Dissertacao_Lorena Brasil Cirilo Passos_20061207_CIC.pdf: 1280461 bytes, checksum: 5d78db2dd313197338c3e8ca3e9e811f (MD5) / Made available in DSpace on 2010-02-08T18:32:57Z (GMT). No. of bitstreams: 1 Dissertacao_Lorena Brasil Cirilo Passos_20061207_CIC.pdf: 1280461 bytes, checksum: 5d78db2dd313197338c3e8ca3e9e811f (MD5) Previous issue date: 2006-12-07 / Nesta dissertação, é apresentada a avaliação de desempenho de uma implementação paralela de um algoritmo seqüencial do integrador simplético para simular a evolução temporal de sistemas auto-gravitantes. Este algoritmo foi paralelizado e posteriormente implementado na linguagem C, utilizando-se dois paradigmas de programação paralela: a troca de mensagens empregando-se a biblioteca MPICH 1.2.6 e a memória compartilhada distribuída com o middleware JIAJIA. Um cluster homogêneo de PCs foi o ambiente em que os testes de execução dos programas foram realizados. Um ambiente heterogêneo também foi utilizado para a realização de medidas de desempenho com um balanceamento empírico de carga, uma vez que a montagem deste tipo de sistema paralelo é prática freqüente entre usuários que necessitam de um maior poder computacional. Para quantificar o desempenho da execução paralela das duas implementações distintas, foram realizados as medições dos tempos de execução e os cálculos dos speedups obtidos. Para mensurar o tempo de execução, foi inserida em cada um dos códigos-fonte a instrução assembly rdtsc que fornece ciclos de clock contabilizados em um registrador de hardware. Para o caso da implementação MPI, também foram realizadas medições de tempo de execução por meio da porta paralela utilizando-se a ferramenta PM2P. _______________________________________________________________________________ ABSTRACT / In this work it is presented the performance evaluation of a parallel implementation for the sympletic integrator to simulate the temporal evolution of a self-gravitating system. The algorithm of the sympletic integrator was parallelized and the source code was written in the C programming language. Two parallel programming paradigms were employed: message passing, using the MPICH 1.2.6 library specification, and distributed shared memory, using the JIAJIA middleware. A homogeneous cluster of PCs was used to run the program tests. Due to the fact that users that need greater computational power tend to build heterogeneous computational environments, we also used a heterogeneous parallel system to take the performance measures using an empirical load balancing. To quantify the parallel execution performance of the programs, execution time measures were taken and the speedups achieved were calculated. To measure the execution time, it was inserted into the source codes the assembly instruction rdtsc, which counts the clock cycles in hardware register. For the MPI implementation version, execution time measures made by the parallel port were also taken using a tool called PM2P.