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).

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.

O avanço na tecnologia de hardware está permitindo que máquinas SMP de 2 a 8 processadores estejam disponíveis a um custo cada vez menor, possibilitando que a incorporação de tais máquinas em aglomerados de PC's ou até mesmo a composição de um aglomerado de SMP's sejam alternativas cada vez mais viáveis para computação de alto desempenho. O grande desafio é extrair o potencial que tal conjunto de máquinas oferece. Uma alternativa é usar um paradigma híbrido de programação para aproveitar a arquitetura de memória compartilhada através de multihreadeing e utilizar o modelo de troca de mensagens para comunicação entre os nós. Contudo, essa estratégia impõe uma tarefa árdua e pouco produtiva para o programador da aplicação. Este trabalho apresenta o sistema CPAR- Cluster que oferece uma abstração de memória compartilhada no topo de um aglomerado formado por nós mono e multiprocessadores. O sistema é implementado no nível de biblioteca e não faz uso de recursos especiais tais como hardware especializado ou alteração na camada de sistema operacional. Serão apresentados os modelos, estratégias, questões de implementação e os resultados obtidos através de testes realizados com a ferramenta e que apresentaram comportamento esperado. / The advance in hardware technologies is making small configuration SMP machines (from 2 to 8 processors) available at a low cost. For this reason, the inclusion of an SMP node into a cluster of PCs or even clusters of SMPs are becoming viable alternatives for high performance computing. The challenge is the exploitation of the computational resources that these platforms provide. A Hybrid programming paradigm which uses shared memory architecture through multihreading and also message passing model for inter node communication is an alternative. However, programming in such paradigm is very hard. This thesis presents CPAR- Cluster, a runtime system, that provides shared memory abstraction on top of a cluster composed by mono and multiprocessor nodes. Its implementation is at the library level and doesn't require special resources such as particular hardware or operating system moditfications. Models, strategies, implementation aspects and results will be presented.

O avanço na tecnologia de hardware está permitindo que máquinas SMP de 2 a 8 processadores estejam disponíveis a um custo cada vez menor, possibilitando que a incorporação de tais máquinas em aglomerados de PC's ou até mesmo a composição de um aglomerado de SMP's sejam alternativas cada vez mais viáveis para computação de alto desempenho. O grande desafio é extrair o potencial que tal conjunto de máquinas oferece. Uma alternativa é usar um paradigma híbrido de programação para aproveitar a arquitetura de memória compartilhada através de multihreadeing e utilizar o modelo de troca de mensagens para comunicação entre os nós. Contudo, essa estratégia impõe uma tarefa árdua e pouco produtiva para o programador da aplicação. Este trabalho apresenta o sistema CPAR- Cluster que oferece uma abstração de memória compartilhada no topo de um aglomerado formado por nós mono e multiprocessadores. O sistema é implementado no nível de biblioteca e não faz uso de recursos especiais tais como hardware especializado ou alteração na camada de sistema operacional. Serão apresentados os modelos, estratégias, questões de implementação e os resultados obtidos através de testes realizados com a ferramenta e que apresentaram comportamento esperado. / The advance in hardware technologies is making small configuration SMP machines (from 2 to 8 processors) available at a low cost. For this reason, the inclusion of an SMP node into a cluster of PCs or even clusters of SMPs are becoming viable alternatives for high performance computing. The challenge is the exploitation of the computational resources that these platforms provide. A Hybrid programming paradigm which uses shared memory architecture through multihreading and also message passing model for inter node communication is an alternative. However, programming in such paradigm is very hard. This thesis presents CPAR- Cluster, a runtime system, that provides shared memory abstraction on top of a cluster composed by mono and multiprocessor nodes. Its implementation is at the library level and doesn't require special resources such as particular hardware or operating system moditfications. Models, strategies, implementation aspects and results will be presented.