Orientador: Marco Aurelio Amaral Henriques / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-23T23:38:03Z (GMT). No. of bitstreams: 1 HuertaYero_EduardoJavier_M.pdf: 6263685 bytes, checksum: da85b66c077cab0f74c134bb27cb51f3 (MD5) Previous issue date: 1998 / Resumo: A velocidade das redes e o poder de processamento dos computadores conectados a elas têm aumentado muito nos últimos anos. Os computadores ligados à Internet, vistos em conjunto, oferecem um poder computacional muito maior que o oferecido pela mais avançada máquina paralela. Estes dados indicam à possibilidade de se usar esse enorme poder computacional disponível na Internet como um computador massivamente paralelo. Este trabalho apresenta o JOIN, um sistema que tem como objetivo implementar um Computador Massivamente Paralelo Virtual, que pode ser visto como um grande conjunto de computadores independentes conectados por uma rede tipo Internet. Diferente de outras abordagens, o JOIN se baseia na ampla disponibilidade da linguagem Java e de interfaces simples de acesso à Internet para atingir seus objetivos e prevê formas de recompensar os donos dos computadores participantes no processamento paralelo. Estas características tornam o sistema proposto capaz de agrupar um grande número de computadores, permitindo a exploração do potencial de computação disponível na Internet / Abstract: The processing power of computers and the network bandwidth have rapidly increased in the last several years. The computers connected to Internet, seen as a whole, offer a computing power much larger than the most advanced parallel machine. These facts open the possibility of exploiting this enormous processing power as a massively parallel computer. The objective of this work is to introduce JOIN, a system that aims at implementing a Massively Parallel Virtual Computer (MPVC). An MPVC can be seen as a large set of independent heterogeneous computers connected by a network like Internet. Different from other approaches, JOIN is based on the wide availability of the Java language and easy to use interfaces to access Internet, and includes the possibility to compensate the owner of the computers participating in the system for their services. These characteristics make the proposed system capable of grouping a large number of computers and thus exploiting the potential computing power available in the Internet / Mestrado / Mestre em Engenharia Elétrica

Made available in DSpace on 2013-08-07T18:43:07Z (GMT). No. of bitstreams: 1 000415011-Texto+Completo-0.pdf: 9818822 bytes, checksum: 000259a328a840b445d92337ab6707ce (MD5) Previous issue date: 2009 / This thesis presents a free, fast, reliable and accurate solver for point and interval dense linear systems. The idea was to implement a solver for dense linear systems using a verified method, interval arithmetic and directed roundings based on MPI communication primitives associated to optimized libraries, aiming to provide both self-verification and speed-up at the same time. A first parallel implementation was developed using the C-XSC library. However, the CXSC parallel method did not achieve the expected overall performance since the solver was not 100% parallelized due to its implementation properties (special variables and optimal scalar product). C-XSC did not seem to be the most efficient tool for time critical applications, consequently we proposed and implemented a new sequential verified solver for dense linear systems for point and interval input data using both infimum-supremum and midpoint-radius arithmetic based on highly optimized libraries (BLAS/ LAPACK). Performance tests showed that the midpointradius algorithm needs approximately the same time to solve a linear system with point or interval input data, while the infimum-supremum algorithm needs much more time for interval data. Considering that, midpoint-radius arithmetic was the natural choice for the next step of this work: the parallel implementation. We then developed a new parallel verified solver for point and interval dense linear systems using midpoint-radius arithmetic, directed roundings and optimized libraries (PBLAS/ ScaLAPACK). The performance results showed that it was possible to achieve very good speed-ups in a wide range of processor numbers for large matrix dimensions for both point and interval input data. In order to overcome the memory limitation imposed by the generation of the whole matrix in one processor, we decided to generate sub-matrices of the input matrix individually on each available node, allowing a better use of the global memory. These modifications made it possible to solve dense systems with up to 100 000 dimension. In addition to that, in order to investigate the portability of the proposed solution, during this thesis, tests were performed using 3 different clusters in Germany (ALiCEnext, XC1 and IC1) with distinct configurations presenting significant results, indicating that the parallel solver scales well even for very large dense systems over many processors. Further investigations were done in two directions: study of the use of dedicated threads to speed up the solver of dense linear systems on shared memory, specially dual-core processors and the use of the ideas presented in this thesis to speed-up the C-XSC library. / Esta tese apresenta uma ferramenta de resolução de sistemas lineares densos pontuais e intervalares. As principais características desta ferramenta são rapidez, confiabilidade e precisão. Esta ferramenta é baseada em um método de resolução de sistemas densos verificado usando arredondamentos direcionados e aritmética intervalar associados a bibliotecas otimizadas e primitivas MPI para prover resultados confiáveis e alto desempenho. A primeira versão paralela foi desenvolvida usando a biblioteca C-XSC. Esta versão não alcançou o desempenho global esperado uma vez que não foi paralelizada totalmente devido a particularidades do C-XSC (variáveis especiais e produto escalar ótimo). Como o C-XSC não se mostrou eficiente para aplicações de grande porte, foi proposta e implementada uma nova versão seqüencial para sistemas lineares densos usando tanto a aritmética de ínfimo e supremo como a aritmética de ponto médio e raio, baseada nas bibliotecas BLAS e LAPACK. Testes de desempenho mostraram que o algoritmo que implementa a aritmética de ponto médio e raio possui um desempenho melhor do que o algoritmo que implementa a aritmética de ínfimo e supremo. Considerando este resultado, a aritmética de ponto médio e raio foi escolhida para a próxima etapa: a implementação paralela. Uma versão paralela para solução de sistemas lineares pontuais e intervalares densos foi então desenvolvida utilizando a aritmética de ponto médio e raio, arredondamentos direcionados e as bibliotecas otimizadas PBLAS e ScaLAPACK. Os resultados mostraram que foi possível alcançar um bom desempenho utilizando um número de processadores variado e proporcionando considerável aceleração na obtenção dos resultados para diferentes tamanhos de matrizes (pontuais e intervalares).A fim de superar as limitações impostas pelo uso da memória na geração de toda a matriz em um só processador, uma nova versão foi implementada. Esta versão gera as sub-matrizes da matriz principal em cada processador, permitindo uma melhor utilização da memória global disponibilizada pelo Cluster. Estas alterações tornaram possível resolver sistemas densos de dimensão 100 000. Para investigar a portabilidade da solução proposta, os testes foram realizados em 3 Clusters diferentes na Alemanha (ALiCEnext, XC1 e IC1). Cada um destes Clusters possui configurações distintas e apresentaram resultados significativos, indicando que a versão paralela possui uma boa escalabilidade para sistemas lineares muito grandes usando um número variado de processadores. Outros estudos foram realizados em duas direções. O primeiro diz respeito ao uso de threads dedicadas para aumentar o desempenho da solução de sistemas lineares usando memória compartilhada (em especial para processadores dual-core). Também foi estudada a utilização dessas idéias para aumentar o desempenho da solução usando C-XSC.

Fenômenos naturais, tecnológicos e industriais podem, em geral, ser modelados de modo acurado através de equações diferenciais parciais, definidas sobre domínios contínuos que necessitam ser discretizados para serem resolvidos. Dependendo do esquema de discretização utilizado, pode-se gerar sistemas de equações lineares. Esses sistemas são, de modo geral, esparsos e de grande porte, onde as incógnitas podem ser da ordem de milhares, ou até mesmo de milhões. Levando em consideração essas características, o emprego de métodos iterativos é o mais apropriado para a resolução dos sistemas gerados, devido principalmente a sua potencialidade quanto à otimização de armazenamento e eficiência computacional. Uma forma de incrementar o desempenho dos métodos iterativos é empregar uma técnica multigrid. Multigrid são uma classe de métodos que resolvem eficientemente um grande conjunto de equações algébricas através da aceleração da convergência de métodos iterativos. Considerando que a resolução de sistemas de equações de problemas realísticos pode requerer grande capacidade de processamento e de armazenamento, torna-se imprescindível o uso de ambientes computacionais de alto desempenho. Uma das abordagens encontradas na literatura técnica para a resolução de sistemas de equações em paralelo é aquela que emprega métodos de decomposição de domínio (MDDs). Os MDDs são baseados no particionamento do domínio computacional em subdomínios, de modo que a solução global do problema é obtida pela combinação apropriada das soluções obtidas em cada um dos subdomínios Assim, neste trabalho são disponibilizados diferentes métodos de resolução paralela baseado em decomposição de domínio, utilizando técnicas multigrid para a aceleração da solução de sistemas de equações lineares. Para cada método, são apresentados dois estudos de caso visando a validação das implementações. Os estudos de caso abordados são o problema da difusão de calor e o modelo de hidrodinâmica do modelo UnHIDRA. Os métodos implementados mostraram-se altamente paralelizáveis, apresentando bons ganhos de desempenho. Os métodos multigrid mostraram-se eficiente na aceleração dos métodos iterativos, já que métodos que utilizaram esta técnica apresentaram desempenho superior aos métodos que não utilizaram nenhum método de aceleração.

Este trabalho descreve o projeto lógico de três meios alternativos de interconexão entre processadores e módulos de memória para um sistema multimicroprocessador: barramento multiplexado, múltiplos barramentos dedicados/memórias multiporta e matriz de barramentos cruzados. Com vistas ao projeto, são analisadas as características operacionais de multiprocessadores e identificadas algumas de suas funções de controle. O problema de interconexão em sistemas compostos de múltiplas unidades de processamento é abordado hierarquicamente. São mostradas as formas de se realizar a estrutura de interconexão, dando-se maior atenção aos barramentos digitais são apresentados os protocolos de arbitração e protocolos de comunicação mais utilizados neste tipo de estrutura. / This work describes the logical project of three alternative ways of interconnecting processors and memory modules in a multimicro processor system: multi p lexed bus, multi ple dedicated buses/multi-port memories, and cross-bar matrix. Aiming the project, the o perational features of multiprocessors are analysed and some control functions identified. The interconnection problem in multiple processing units systems is hierarchichally approached, em phasizing digital buses. The arbitration protocols and communication Protocols mostly used in this kind of structure are shown.

Este trabalho descreve a área de processamento matricial, mostrando os principais compromissos existentes na obtenção de arquiteturas paralelas a partir de algoritmos, para que haja um ganho real na avaliação destes. São feitas, ainda, considerações sobre ferramentas de programação para arquiteturas paralelas. Os principais compromissos que influenciam as arquiteturas SIMD, objeto de estudo deste trabalho, são abordados analisando-se uma áera de aplicação de arquiteturas SIMD: tratamento de imagens. Como uma caso prático de estudo e exemplo destes compromissos, é proposta uma arquitetura SIMD para um processador matricial empregando um chip matricial disponível comercialmente - o GAPP (Geometric Arithmetic Parallel Processor). É proposto, ainda, um ambiente para o desenvolvimento de programas nesta arquitetura. Este ambiente é baseado na utilização da lingaugem GAL (GAPP Algorithm Language), criada especificamente para elaboração de programas para o GAPP. / This work describes the array processing area, discussing the main tradeoffs in the design of parallel architecture from algorithms. The algorithm to architecture transformation is called a mapping problem. Some considerations about progamming tools for parallel architectures are also made. The relationship between algorithms and architectures is covered by studying a specific case for SIMD architectures: digital image processing. A SIMD architecture proposal, using a commercially available chip array - GAPP (Geometric Arithmetic Parallel Processor) is made. This architecture is used on a practical case to study and analyze those tradeoffs. An environment for program development for this architecture is also proposed. This environment is based on the use of GAL language (GAPP Algorithm Language), which was created specificaly for GAPP program development.

Dissertação (mestrado) - Universidade Federal de Santa Cataina, Centro Tecnologico / Made available in DSpace on 2016-01-08T22:01:54Z (GMT). No. of bitstreams: 1 109889.pdf: 12632049 bytes, checksum: f035acfabf47de46b318a51a2b6cc436 (MD5) Previous issue date: 1997 / Apresenta-se neste trabalho o desenvolvimento e implementação de uma ferramenta para modelagem e simulação de sistemas computacionais, cujo objetivo é facilitar e reduzir o tempo entre o projeto e sua implementação. Mais especificamente, a ferramenta destina-se a modelagem de sistemas que comportam uma arquitetura de processamento paralelo em configuração com linhas de interrupção e barramento de serviço. Ela reúne uma linguagem de simulação, possui uma interface amigável com alta flexibilidade e atende às características específicas daqueles sistemas. Estudos de sistemas complexos, como os que envolvem o projeto de arquitetura de computadores, necessitam de ferramentas para simulação e análise de desempenho das inúmeras propostas que se apresentam. A ferramenta aqui proposta fornece assistência ao projetista permitindo a análise do sistema em todas as etapas de modelagem e avaliação de performance do projeto, desde a coleta de dados até a apresentação e análise dos resultados. É oportuno o desenvolvimento deste tipo de pesquisa, uma vez que, a grande maioria das ferramentas existentes no mercado, não conseguem reunir as características que o usuário procura para encaminhar soluções aos inúmeros problemas que surgem ao longo do projeto. O trabalho foi desenvolvido a partir de conhecimentos nas áreas de arquitetura paralela, simulação e modelagem de sistemas juntamente com o projeto Nó// (leia-se nó paralelo) desenvolvido na Universidade Federal de Santa Catarina.

Este trabalho descreve o projeto lógico de três meios alternativos de interconexão entre processadores e módulos de memória para um sistema multimicroprocessador: barramento multiplexado, múltiplos barramentos dedicados/memórias multiporta e matriz de barramentos cruzados. Com vistas ao projeto, são analisadas as características operacionais de multiprocessadores e identificadas algumas de suas funções de controle. O problema de interconexão em sistemas compostos de múltiplas unidades de processamento é abordado hierarquicamente. São mostradas as formas de se realizar a estrutura de interconexão, dando-se maior atenção aos barramentos digitais são apresentados os protocolos de arbitração e protocolos de comunicação mais utilizados neste tipo de estrutura. / This work describes the logical project of three alternative ways of interconnecting processors and memory modules in a multimicro processor system: multi p lexed bus, multi ple dedicated buses/multi-port memories, and cross-bar matrix. Aiming the project, the o perational features of multiprocessors are analysed and some control functions identified. The interconnection problem in multiple processing units systems is hierarchichally approached, em phasizing digital buses. The arbitration protocols and communication Protocols mostly used in this kind of structure are shown.

Fenômenos naturais, tecnológicos e industriais podem, em geral, ser modelados de modo acurado através de equações diferenciais parciais, definidas sobre domínios contínuos que necessitam ser discretizados para serem resolvidos. Dependendo do esquema de discretização utilizado, pode-se gerar sistemas de equações lineares. Esses sistemas são, de modo geral, esparsos e de grande porte, onde as incógnitas podem ser da ordem de milhares, ou até mesmo de milhões. Levando em consideração essas características, o emprego de métodos iterativos é o mais apropriado para a resolução dos sistemas gerados, devido principalmente a sua potencialidade quanto à otimização de armazenamento e eficiência computacional. Uma forma de incrementar o desempenho dos métodos iterativos é empregar uma técnica multigrid. Multigrid são uma classe de métodos que resolvem eficientemente um grande conjunto de equações algébricas através da aceleração da convergência de métodos iterativos. Considerando que a resolução de sistemas de equações de problemas realísticos pode requerer grande capacidade de processamento e de armazenamento, torna-se imprescindível o uso de ambientes computacionais de alto desempenho. Uma das abordagens encontradas na literatura técnica para a resolução de sistemas de equações em paralelo é aquela que emprega métodos de decomposição de domínio (MDDs). Os MDDs são baseados no particionamento do domínio computacional em subdomínios, de modo que a solução global do problema é obtida pela combinação apropriada das soluções obtidas em cada um dos subdomínios Assim, neste trabalho são disponibilizados diferentes métodos de resolução paralela baseado em decomposição de domínio, utilizando técnicas multigrid para a aceleração da solução de sistemas de equações lineares. Para cada método, são apresentados dois estudos de caso visando a validação das implementações. Os estudos de caso abordados são o problema da difusão de calor e o modelo de hidrodinâmica do modelo UnHIDRA. Os métodos implementados mostraram-se altamente paralelizáveis, apresentando bons ganhos de desempenho. Os métodos multigrid mostraram-se eficiente na aceleração dos métodos iterativos, já que métodos que utilizaram esta técnica apresentaram desempenho superior aos métodos que não utilizaram nenhum método de aceleração.

Orientador: José Márcio Machado / Banca: Liria Matsumoto Sato / Banca: Renata Spolon Lobato / Resumo: A biologia, como uma ciência bastante desenvolvida, foi dividida em diversas areas, dentre elas, a genética. Esta area passou a crescer em importância nos ultimos cinquenta anos devido aos in umeros benefícios que ela pode trazer, principalmente, aos seres humanos. Como a gen etica passou a apresentar problemas com grande complexidade de resolução estratégias computacionais foram agregadas a ela, surgindo assim a bioinform atica. A bioinformática desenvolveu-se de forma bastante signi cativa nos ultimos anos e esse desenvolvimento vem se acentuando a cada dia, devido ao aumento da complexidade dos problemas genômicos propostos pelos biólogos. Assim, os cientistas da computação têm se empenhado no desenvolvimento de novas técnicas computacionais para os biólogos, principalmente no que diz respeito as estrat egias para alinhamentos m ultiplos de sequências. Quando as sequências estão alinhadas, os biólogos podem realizar mais inferências sobre elas, principalmente no reconhecimento de padrões que e uma outra area interessante da bioinformática. Atrav es do reconhecimento de padrãoes, os bi ologos podem identicar pontos de alta signi cância (hot spots) entre as sequências e, consequentemente, pesquisar curas para doençass, melhoramentos genéticos na agricultura, entre outras possibilidades. Este trabalho traz o desenvolvimento e a comparação entre duas técnicas computacionais para o alinhamento m ultiplo de sequências. Uma e baseada na técnica de alinhamento múltiplo de sequências progressivas pura e a outra, e uma técnica de alinhamento múltiplo de sequências otimizada a partir da heurística de colônia de formigas. Ambas as técnicas adotam em algumas de suas fases estratégias de paralelismo, focando na redu c~ao do tempo de execução dos algoritmos. Os testes de desempenho e qualidade dos alinhamentos que foram conduzidos com as duas estrat egias... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: Biology as an enough developed science was divided in some areas, and genetics is one of them. This area has improved its relevance in last fty years due to the several bene ts that it can mainly bring to the humans. As genetics starts to show problems with hard resolution complexity, computational strategies were aggregated to it, leading to the start of the bioinformatics. The bioinformatics has been developed in a signi cant way in the last years and this development is accentuating everyday due to the increase of the complexity of the genomic problems proposed by biologists. Thus, the computer scientists have committed in the development of new computational techniques to the biologists, mainly related to the strategies to multiple sequence alignments. When the sequences are aligned, the biologists can do more inferences about them mainly in the pattern recognition that is another interesting area of the bioinformatics. Through the pattern recognition, the biologists can nd hot spots among the sequences and consequently contribute for the cure of diseases, genetics improvements in the agriculture and many other possibilities. This work brings the development and the comparison between two computational techniques for the multiple sequence alignments. One is based on the pure progressive multiple sequence alignment technique and the other one is an optimized multiple sequence alignment technique based on the ant colony heuristics. Both techniques take on some of its stages of parallel strategies, focusing on reducing the execution time of algorithms. Performance and quality tests of the alignments were conducted with both strategies and showed that the optimized approach presents better results when it is compared with the pure progressive approach. Biology as an enough developed science was divided in some areas, and genetics is one of them. This area has improved... (Complete abstract click electronic access below) / Mestre

Resumo: Este trabalho aborda a implementação paralela da técnica Branch-and-Bound em problemas de otimização combinatoria, especificamente busca em grafos. E utilizado na implementação o modelo de programação paralela por troca de mensagens com o uso da biblioteca Parallel Virtual Machine (PVM) sobre o sistema operacional Linux em uma arquitetura multicomputador. E analisado o comportamento da técnica Branch-and-Bound, em particular a relação entre (a) três critérios de busca, (b) a utilização dos recursos de memória e (c) granularidade de, processamento e comunicação entre processos. E proposto um esquema de implementação com processos mestre-escravos semi-distribuído, onde o processo mestre é responsável pela distribuição de tarefas e os processos escravos pela disseminação de resultados parciais no sistema. Resultados experimentais dessa implementação são exibidos e analisados, assim como algumas características relevantes ao desempenho global encontradas no uso da biblioteca PVM para esta arquitetura. De um modo geral obtivemos em média para os problemas investigados uma eficiência da execução paralela da ordem de 98% em comparação à execução serial.