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-19T23:34:34Z (GMT). No. of bitstreams: 1 186753.pdf: 850566 bytes, checksum: 4993604aeb19696408ddda37ddd0b258 (MD5) / Pesquisas em Computação Paralela realizadas na Universidade Federal de Santa Catarina, resultaram no desenvolvimento da arquitetura de um multicomputador com rede de interconexão configurável dinamicamente, conhecida como arquitetura Crux. Resultados experimentais, obtidos através de simulações, mostraram fortes evidências de um desempenho superior a arquiteturas paralelas clássicas. A chave desse ganho em desempenho é a escolha de uma rede de interconexão deliberamente simples, pois a simplicidade elimina o "overhead" devido ao conflito de mensagens nos meios de conexão. Vários trabalhos já foram desenvolvidos tendo o Crux como arquitetura-alvo. Em particular, foram desenvolvidos trabalhos de projeto do sistema de interconexão dos elementos de processamento da arquitetura utilizando Links Transputer. No entanto, os Links Transputer apresentaram uma alta complexidade e dificuldade de prototipação. No intuito de encontrar uma solução mais simples para a implementação da rede de interconexão, resolveu-se buscar uma alternativa de menor complexidade, baseada em componentes de fácil aquisição no mercado, tornando a prototipação mais simples e rápida. O presente trabalho apresenta uma alternativa que utiliza interfaces seriais padrão. Embora diminuindo a velocidade de comunicação em relação aos Links Transputer, a alternativa proposta mantém a simplicidade dos meios de conexão. Assim, apesar da diminuição da velocidade de comunicação, espera-se que a degradação do desempenho seja pequena, pois se continua garantindo a ausência de "overhead" devido a conflitos entre mensagens. Este trabalho apresenta o projeto do protótipo de um "crossbar" e apresenta componentes auxiliares de hardware para a rede de interconexão alternativa. São apresentados diagramas esquemáticos do sistema digital que implementa tal "crossbar". O sistema digital foi validado através de simulação temporal e mapeado para lógica programável. A descrição esquemática do sistema digital foi feita em uma ferramenta de projeto auxiliado por computador, o que permite sua futura implementação através de mapeamento automático para um dispositivo lógico programável (e.g. FPGA).

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-21T06:59:19Z (GMT). No. of bitstreams: 1 195053.pdf: 496541 bytes, checksum: 423de153bc835a354f243426ae6dfca0 (MD5)

A Computação Gráfica, área em franco desenvolvimento, têm caminhado em busca da geração, cada vez mais rápida, de imagens mais realísticas. Os algoritmos que permitem a síntese de imagens realísticas demandam alto poder computacional, fazendo com que a geração deste tipo de imagem, de forma rápida, requeira o uso de computadores paralelos. Hoje, a técnica que permite gerar as imagens mais realísticas é o "ray tracing" . Os multicomputadores, por sua vez, são a arquitetura de computadores paralelos mais promissora na busca do desempenho computacional necessário às aplicações modernas. Esta dissertação aborda o problema da implementação do algoritmo de "ray tracing" em multicomputadores. A paralelização desta técnica para uso em computadores paralelos de memória distribuída pode ser feita de muitas formas diferentes, sempre envolvendo um compromisso entre a velocidade de processamento e a memória utilizada. Neste trabalho conceitua-se este problema e introduz-se ferramentas para a avaliação de soluções que levam em consideração a eficiência de processamento e a redundância no uso de memória. Também é apresentada uma nova taxonomia que, além de permitir a classificação de propostas para implementações de "ray tracing" paralelo, orienta a procura de novas soluções para este problema. O desempenho das soluções em cada classe desta taxonomia é avaliado qualitativamente. Por fim, são sugeridas novas alternativas de paralelização do algoritmo de "ray tracing" em multicomputadores. / Computer Graphics is headed today towards the synthesis of more realistic images, in less time. The algorithms used for realistic image synthesis demand high computer power, so that the synthesis of this kind of image, in short periods of time, requires the use of parallel computers. Nowadays, the technique that yields the most realistic images is ray tracing. On its turn, multicomputers are the most promising parallel architecture for reaching the performance needed in modern applications. This dissertation is on the problem of implementing the ray tracing algorithm on multicomputers. The parallelization of this technique on distributed memory parallel computers can take several forms, always involving a compromise between speed and memory. In this work, this problem is conceptualized and tools for evaluation of solutions that account for efficiency and redundancy, are introduced. It is also presented a new taxonomy that can be used for both the classification of parallel ray tracing proposals and for driving the search of new solutions to this problem. The performances of entries in each class of the taxonomy are qualitatively assessed. New alternatives for parallelizing the ray tracing algorithm on multicomputers, are suggested.

A Computação Gráfica, área em franco desenvolvimento, têm caminhado em busca da geração, cada vez mais rápida, de imagens mais realísticas. Os algoritmos que permitem a síntese de imagens realísticas demandam alto poder computacional, fazendo com que a geração deste tipo de imagem, de forma rápida, requeira o uso de computadores paralelos. Hoje, a técnica que permite gerar as imagens mais realísticas é o "ray tracing" . Os multicomputadores, por sua vez, são a arquitetura de computadores paralelos mais promissora na busca do desempenho computacional necessário às aplicações modernas. Esta dissertação aborda o problema da implementação do algoritmo de "ray tracing" em multicomputadores. A paralelização desta técnica para uso em computadores paralelos de memória distribuída pode ser feita de muitas formas diferentes, sempre envolvendo um compromisso entre a velocidade de processamento e a memória utilizada. Neste trabalho conceitua-se este problema e introduz-se ferramentas para a avaliação de soluções que levam em consideração a eficiência de processamento e a redundância no uso de memória. Também é apresentada uma nova taxonomia que, além de permitir a classificação de propostas para implementações de "ray tracing" paralelo, orienta a procura de novas soluções para este problema. O desempenho das soluções em cada classe desta taxonomia é avaliado qualitativamente. Por fim, são sugeridas novas alternativas de paralelização do algoritmo de "ray tracing" em multicomputadores. / Computer Graphics is headed today towards the synthesis of more realistic images, in less time. The algorithms used for realistic image synthesis demand high computer power, so that the synthesis of this kind of image, in short periods of time, requires the use of parallel computers. Nowadays, the technique that yields the most realistic images is ray tracing. On its turn, multicomputers are the most promising parallel architecture for reaching the performance needed in modern applications. This dissertation is on the problem of implementing the ray tracing algorithm on multicomputers. The parallelization of this technique on distributed memory parallel computers can take several forms, always involving a compromise between speed and memory. In this work, this problem is conceptualized and tools for evaluation of solutions that account for efficiency and redundancy, are introduced. It is also presented a new taxonomy that can be used for both the classification of parallel ray tracing proposals and for driving the search of new solutions to this problem. The performances of entries in each class of the taxonomy are qualitatively assessed. New alternatives for parallelizing the ray tracing algorithm on multicomputers, are suggested.

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-21T01:22:24Z (GMT). No. of bitstreams: 1 194221.pdf: 767782 bytes, checksum: 4badd4ca67e1d432a631ec554c5b27de (MD5) / A computação de alto desempenho sempre fascinou os experimentadores de hardware. A busca incessante por performance conduziu diversos projetos de computação cooperativa, e nesse cenário os CLUSTER obtiveram lugar de destaque. Através da análise de testes de desempenho, podemos argumentar que as conexões em rede utilizando-se de ligações PCI em máquinas heterogêneas pode ser uma solução viável e de baixo custo. Porém o padrão USB, com sua flexibilidade e conectividade, poderá substituir as atuais placas de redes Ethernet e Fast-Ethernet baseadas no barramento PCI, em vários outros ambientes CLUSTERS. Nesse trabalho será abordado o assunto CLUSTER no seu ponto mais fraco: as interfaces de conexão. No capítulo 2 é apresentado os modelos conceituais de hardware em sistemas distribuídos e os respectivos modelos baseados na Taxonomia de Flynn. O capitulo 3 explora as principais tecnologia em protocolos de comunicação internet e os de baixa latência, bem como o hardware necessário para a montagem e configuração de ambientes de multicomputadores. O capitulo 4 cita as redes de interconexão e seus tipos. No capitulo 5 é apresentado o Multicomputador CRUX, a sua arquitetura de funcionamento e de hardware. No capitulo 6 é apresentado o barramento USB e todas as suas características técnicas, a forma como a comunicação serial funciona no USB e como o Linux trata os pacotes USB-Ethernet. O capítulo 7 apresenta os resultados de desempenho após os testes com os periféricos USB e os cenários de implementação do Multicomputador CRUX ligado por USB.

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-19T17:03:22Z (GMT). No. of bitstreams: 0Bitstream added on 2014-09-26T01:32:09Z : No. of bitstreams: 1 184877.pdf: 1381527 bytes, checksum: 350586acaff42648acc71066e50acb0b (MD5) / : Esse trabalho tem por objetivo propor um protocolo de rede para o projeto de um multicomputador. O projeto do multicomputador conhecido como Clux está sendo desenvolvido no Departamento de Informática e Estatística da Universidade Federal de Santa Catarina objetivando um ambiente para execução de programas paralelos organizados como redes de processos comunicantes. O protocolo a ser proposto será implementado como um módulo de kernel do Linux para dar suporte ao mesmo no tratamento da comunicação entre os processos da rede. Existirá um nó no multicomputador cujo processo correspondente será responsável pelo controle da comunicação entre os processos dos demais nós. Tanto o controle como a comunicação propriamente dita serão realizados utilizando o protocolo proposto neste trabalho, através de uma rede Ethernet de 100Mbits, conectados por um switch objetivando um desempenho que se equipare o máximo possível de um barramento de dados de um computador normal.

Neste trabalho, apresenta-se uma adaptação dos procedimentos utilizados nos códigos computacionais seqüenciais advindos do MEF, para utilizá-los em multicomputadores. Desenvolve-se uma rotina para a montagem do sistema linear particionado entre os diversos processadores. Resolve-se o sistema de equações lineares geradas mediante a rotina do PIM (Parallel Iterative Method). São feitas adaptações deste pacote para se aproveitar as características comuns do sistema linear gerado pelo MEF: esparsidade e simetria. A técnica de resolução do sistema em paralelo é otimizada com o uso de dois tipos de pré-condicionadores: a decomposição incompleta de Cholesky (IC) generalizado e o POLY(0) ou Jacobi. É feita uma aplicação para a solução de pavimento com o algoritmo-base totalmente paralelizado. Também é avaliada a solução do sistema de equações de uma treliça. Mostram-se resultados de speed-up, de eficiência e de tempo para estes dois modelos estruturais. Além disso, é feito um estudo em processamento seqüencial da performance dos pré-condicionadores genéricos (IC) e do advindo de uma série truncada de Neumann, também generalizada, utilizando-se modelos estruturais de placa e chapa. / This work presents an adaptation of conventional finite element method (FEM) computing procedures to multicomputers. It is presented the procedure which the linear system of equations is split among the processor and its solution. It was improved a public software called PIM (Parallel Iterative Method) is used to solve this system of equations. These improvements explore efficiently the usual features of the FEM systems of equations: sparseness and symmetry. To improve the solution of the system, two different preconditioners are used: a generic Incomplete Cholesky (IC) and the Polynomial preconditioning (POLY(0) or Jacobi). It is carried out a full adaptation of the method to parallel computing with a program developed to analyse floor structures. The improved PIM is also used to solve the system of equations of a tri-dimensional truss. It is presented the speed-up, the efficiency and the time used in the resolution of the systems of equations for the floor and for the truss. It is also presented a study of performance in sequential processing of the generic (IC) and the generic Neumann series preconditioners in the analysis of plates in bending and in plane actions.

Neste trabalho, apresenta-se uma adaptação dos procedimentos utilizados nos códigos computacionais seqüenciais advindos do MEF, para utilizá-los em multicomputadores. Desenvolve-se uma rotina para a montagem do sistema linear particionado entre os diversos processadores. Resolve-se o sistema de equações lineares geradas mediante a rotina do PIM (Parallel Iterative Method). São feitas adaptações deste pacote para se aproveitar as características comuns do sistema linear gerado pelo MEF: esparsidade e simetria. A técnica de resolução do sistema em paralelo é otimizada com o uso de dois tipos de pré-condicionadores: a decomposição incompleta de Cholesky (IC) generalizado e o POLY(0) ou Jacobi. É feita uma aplicação para a solução de pavimento com o algoritmo-base totalmente paralelizado. Também é avaliada a solução do sistema de equações de uma treliça. Mostram-se resultados de speed-up, de eficiência e de tempo para estes dois modelos estruturais. Além disso, é feito um estudo em processamento seqüencial da performance dos pré-condicionadores genéricos (IC) e do advindo de uma série truncada de Neumann, também generalizada, utilizando-se modelos estruturais de placa e chapa. / This work presents an adaptation of conventional finite element method (FEM) computing procedures to multicomputers. It is presented the procedure which the linear system of equations is split among the processor and its solution. It was improved a public software called PIM (Parallel Iterative Method) is used to solve this system of equations. These improvements explore efficiently the usual features of the FEM systems of equations: sparseness and symmetry. To improve the solution of the system, two different preconditioners are used: a generic Incomplete Cholesky (IC) and the Polynomial preconditioning (POLY(0) or Jacobi). It is carried out a full adaptation of the method to parallel computing with a program developed to analyse floor structures. The improved PIM is also used to solve the system of equations of a tri-dimensional truss. It is presented the speed-up, the efficiency and the time used in the resolution of the systems of equations for the floor and for the truss. It is also presented a study of performance in sequential processing of the generic (IC) and the generic Neumann series preconditioners in the analysis of plates in bending and in plane actions.