Orientador: Rogerio Drummond Burnier Pessoa de Mello Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-23T12:49:47Z (GMT). No. of bitstreams: 1 Oliveira_AredisSebastiaode_M.pdf: 3427641 bytes, checksum: 37bbd69debac907793af9a3c65ed42a3 (MD5) Previous issue date: 1997 / Resumo: Este trabalho apresenta o projeto e a implementação de um Make Distribuído (MakeD) baseado na conhecida ferramenta make. A aplicação cliente/selVidor MakeD permite usar uma rede de computadores como um re~urso computacional único para minimizar o tempo gasto no processo de make durante o desenvolvimento de projetos de médio e grande porte. Num ambiente de desenvolvimento típico uma estação cliente apresenta um padrão de uso de CPU com curtos períodos de intensa utilização e longos períodos de inatividade ou baixa utilização. Dessa forma, utilizar os clientes como servidores de CPU e usar a ferramenta MakeD para distribuir as tarefas de compilações entre eles melhora o uso da capacidade de processamento disponível na rede, contribuindo para balancear a utilização dos recursos. A implementação do MakeD combina o mecanismo de RPC com recursos de multithreading para explorar a distribuição de tarefas na rede e a multi-tarefa em cada sistema. Os resultados de testes comparativos entre MakeD, GNU Make e outro make distribuído (Dmake) demonstram a eficiência dos métodos empregados. O trabalho também discute alguns aspectos de transformação de aplicações centralizadas em distribuídas e propõe um selVidor de make distribuído multi-usuário como extensão para o MakeD / Abstract: This work presents the design and implementation of a Distributed Make (MakeD) utility. The MakeD c1ient/server application allows using a network as a single computing resource to reduce compilation time in the development of medium and large projects. In a typical development environment, client workstations presents relatively short periods of high CPU load followed by long periods of low or zero utilization. MakeD uses ordinary c1ients as CPU servers in order to distribute tasks, thus making a network's id1e processor capacity available and balancing resource use. MakeD uses RPC and multithreading to achieve distributed processing in the network and multitasking within each node. The results of comparative tests show performance gains relative to GNU Make and a similar distributed make (Dmake). This work also discusses some aspects of transforming centralized applications into distributed ones and proposes a multi-user distributed Make Server as a future evolution / Mestrado / Mestre em Ciência da Computação

Orientador: João Carlos Setubal / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-20T10:42:14Z (GMT). No. of bitstreams: 1 Menezes_RonaldoParentede_M.pdf: 3928510 bytes, checksum: ea2fba03acca3afbcc6c42b92cf68f1c (MD5) Previous issue date: 1995 / Resumo: Modelos de Computação são uma ferramenta muito importante para um bom desenvolvimento de algoritmos. Em geral, eles visam facilitar o trabalho de projetistas abstraindo diversos fatores existentes nas máquinas reais. Em computação paralela, a necessidade de um modelo é extrema devido a grande variedade de arquiteturas. O surgimento de um modelo de computação paralela poderia impulsionar ainda mais o crescimento da área que já é bastante acentuado, devido a limitações físicas existentes em computadores seqüenciais. Nesta dissertação fazemos um estudo de modelos de computação paralela sob o ponto de vista de projeto de algoritmos e com enfoque na computação paralela derivada da arquitetura de von Neumann. Para tanto, começamos por estudar um conjunto de máquinas paralelas para que suas diferenças fiquem claras. Escolhemos as máquinas paralelas mais conhecidas, ou mais difundidas, como: CM-2, Sequent Symmetry, MasPar MP-l, CM-5, entre outras. Após este estudo de máquinas, partimos diretamente para os modelos de computação paralela. Escolhemos três como base. Tais modelos apresentam características bem distintas quanto a simplicidade e realismo. Os modelos estudados são PRAM, BSP [Val90] e LogP [CKP+93]. Muitos defendem que continuemos usando o modelo PRAM , pois este, apesar de ser muito abstrato, facilita bastante o trabalho dos projetistas. A proposta do modelo BSP é um pouco mais ousada pois Valiant tenta, com seu modelo, influenciar as áreas de hardware e software da mesma forma que a arquitetura von Neumann fez com a computação seqüencial. Já a proposta do modelo LogP é bastante imediatista, visto que tenta resolver o problema atual de dificuldade de projeto de algoritmos. Para que pudéssemos avaliar um modelo sob o ponto de vista de projeto de algoritmos, fizemos um estudo de casos com os problemas de Transformada de Fourier e Eliminação de Gauss. Com este estudo de casos pudemos avaliar quão fácil ou difícil é projetar algoritmos em cada um dos modelos. / Abstract: Models of Computation are one of most important tools in algorithm design With these models, the work of an algorithm designer becomes easier, because these models leave out many characteristics of real machines. In parallel computing there is a great need for a general model, because we have many different parallel machines. The advent of a parallel computing model could make the area grow more than it is already growing. In this dissertation we study some parallel computing models. First we take a look at a representative set of parallel machines, in order to learn the differences between each architecture. Our set of machines contains some of the most important commercial machines such as: CM-2, Sequent Symmetry, MasPar MP-l and CM-5. After this, we study the models themselves. The models chosen were: PRAM, BSP [Va190] and LogP [CKP+93]. Many researchers argue that the PRAM is the best model for algorithm design although it is not realistic. The proposal of the BSP mo dei is bold, since it also seeks to influence parallel architecture design The proposal of LogP model although similar to the BSP, does not require parallel machines to have synchronization mechanisms. This makes LogP the most realistic but also the most difficult model to use. We evaluate these models based on the problems of Fourier Transform and Gaussian Elimination. After this study we made an evaluation of the three models. / Mestrado / Mestre em Ciência da Computação

A programação paralela é sem dúvida mais complexa do que a programação seqüencial. O controle de múltiplos processos e de suas interações são as principais razões para tal complexidade. Apesar da existência de algumas ferramentas que atendem à fase de desenvolvimento de programas paralelos, a complexidade é normalmente passada para as ferramentas paralelas, isto é, as ferramentas não são de fácil utilização. Assim, existe uma necessidade de ambientes e ferramentas realmente fáceis de usar no âmbito da programação paralela. Embora existam algumas ferramentas interessantes, inclusive algumas comerciais, seu uso permanece insuficiente, em parte devido à complexidade na utilização de algumas delas, em parte devido ao seu uso específico em determinadas plataformas. Portanto, existe ainda um grande campo de estudo no que diz respeito a melhorias de projeto sobre ferramentas existentes e desenvolvimento de ferramentas com um maior número de recursos. Provavelmente, a ferramenta paralela mais necessária aos programadores é o depurador paralelo. Por sua vez, ferramentas de depuração paralela estão entre as mais complexas de se desenvolver e talvez isso explique o motivo pelo qual poucas têm sido efetivamente utilizadas. Este trabalho descreve uma contribuição no campo da depuração paralela através da análise de interfaces de depuração paralela e da proposta de um modelo. A partir deste modelo, uma interface de depuração paralela – PADI (PArallel Debugger Interface) foi desenvolvida e seu principal objetivo é o de oferecer uma interface intuitiva e de fácil utilização. O modelo proposto e conseqüentemente a ferramenta PADI tratam da depuração paralela simbólica on-line. A depuração on-line trata do oferecimento de acesso aos símbolos do programa, como variáveis e registradores. A depuração on-line diferencia-se da off-line pelo tipo de interação com a execução do programa. A depuração on-line oferece interação direta com a aplicação, enquanto que a off-line interage com um arquivo de monitoração gravado durante a execução da aplicação paralela. A depuração on-line é similar à depuração seqüencial tradicional e, conseqüentemente, é de mais fácil utilização por parte da maioria dos programadores.

A programação paralela é sem dúvida mais complexa do que a programação seqüencial. O controle de múltiplos processos e de suas interações são as principais razões para tal complexidade. Apesar da existência de algumas ferramentas que atendem à fase de desenvolvimento de programas paralelos, a complexidade é normalmente passada para as ferramentas paralelas, isto é, as ferramentas não são de fácil utilização. Assim, existe uma necessidade de ambientes e ferramentas realmente fáceis de usar no âmbito da programação paralela. Embora existam algumas ferramentas interessantes, inclusive algumas comerciais, seu uso permanece insuficiente, em parte devido à complexidade na utilização de algumas delas, em parte devido ao seu uso específico em determinadas plataformas. Portanto, existe ainda um grande campo de estudo no que diz respeito a melhorias de projeto sobre ferramentas existentes e desenvolvimento de ferramentas com um maior número de recursos. Provavelmente, a ferramenta paralela mais necessária aos programadores é o depurador paralelo. Por sua vez, ferramentas de depuração paralela estão entre as mais complexas de se desenvolver e talvez isso explique o motivo pelo qual poucas têm sido efetivamente utilizadas. Este trabalho descreve uma contribuição no campo da depuração paralela através da análise de interfaces de depuração paralela e da proposta de um modelo. A partir deste modelo, uma interface de depuração paralela – PADI (PArallel Debugger Interface) foi desenvolvida e seu principal objetivo é o de oferecer uma interface intuitiva e de fácil utilização. O modelo proposto e conseqüentemente a ferramenta PADI tratam da depuração paralela simbólica on-line. A depuração on-line trata do oferecimento de acesso aos símbolos do programa, como variáveis e registradores. A depuração on-line diferencia-se da off-line pelo tipo de interação com a execução do programa. A depuração on-line oferece interação direta com a aplicação, enquanto que a off-line interage com um arquivo de monitoração gravado durante a execução da aplicação paralela. A depuração on-line é similar à depuração seqüencial tradicional e, conseqüentemente, é de mais fácil utilização por parte da maioria dos programadores.

A programação paralela é sem dúvida mais complexa do que a programação seqüencial. O controle de múltiplos processos e de suas interações são as principais razões para tal complexidade. Apesar da existência de algumas ferramentas que atendem à fase de desenvolvimento de programas paralelos, a complexidade é normalmente passada para as ferramentas paralelas, isto é, as ferramentas não são de fácil utilização. Assim, existe uma necessidade de ambientes e ferramentas realmente fáceis de usar no âmbito da programação paralela. Embora existam algumas ferramentas interessantes, inclusive algumas comerciais, seu uso permanece insuficiente, em parte devido à complexidade na utilização de algumas delas, em parte devido ao seu uso específico em determinadas plataformas. Portanto, existe ainda um grande campo de estudo no que diz respeito a melhorias de projeto sobre ferramentas existentes e desenvolvimento de ferramentas com um maior número de recursos. Provavelmente, a ferramenta paralela mais necessária aos programadores é o depurador paralelo. Por sua vez, ferramentas de depuração paralela estão entre as mais complexas de se desenvolver e talvez isso explique o motivo pelo qual poucas têm sido efetivamente utilizadas. Este trabalho descreve uma contribuição no campo da depuração paralela através da análise de interfaces de depuração paralela e da proposta de um modelo. A partir deste modelo, uma interface de depuração paralela – PADI (PArallel Debugger Interface) foi desenvolvida e seu principal objetivo é o de oferecer uma interface intuitiva e de fácil utilização. O modelo proposto e conseqüentemente a ferramenta PADI tratam da depuração paralela simbólica on-line. A depuração on-line trata do oferecimento de acesso aos símbolos do programa, como variáveis e registradores. A depuração on-line diferencia-se da off-line pelo tipo de interação com a execução do programa. A depuração on-line oferece interação direta com a aplicação, enquanto que a off-line interage com um arquivo de monitoração gravado durante a execução da aplicação paralela. A depuração on-line é similar à depuração seqüencial tradicional e, conseqüentemente, é de mais fácil utilização por parte da maioria dos programadores.

Este trabalho contribui na busca de soluções para o problema de auxílio à programação paralela, apresentando uma abordagem orientada a objetos, como base para a construção de uma ferramenta que dá apoio ao desenvolvimento de programas paralelos. Diversas ferramentas com propostas análogas sac revisadas e suas características principais são destacadas, visando a busca de um modelo adequado para a ferramenta a ser proposta. A ferramenta desenvolvida, implementada e validada neste trabalho (FAPP - Ferramenta de Auxílio à Programação Paralela) baseia-se na tecnologia de orientação a objetos. A teoria dos grafos, modelada segundo a orientação a objetos, serve de base para a criação de modelos tanto para arquiteturas paralelas (hardware) como para programas paralelos (software). Os modelos criados para o hardware e software, permitem ao programador criar o ambiente para a programação, definindo a sua arquitetura paralela, os processos componentes de seu programa e o mapeamento lógico desses processos nos processadores. A ferramenta FAPP gera automaticamente o esqueleto para a aplicação paralela. Todo o desenvolvimento efetuado e validado através de uma implementação básica da ferramenta e são apresentadas às diretrizes para futuras extensões, visando outros ambientes de hardware e software, bem como melhoramentos objetivando futuros trabalhos / This work contributes to the solution of the parallel programming supporting problem, by proposing an object-oriented approach as the basis for building a tool to help the development of parallel programs. Several tools with similar goals are revised and their main features are highlighted aiming the search of an adequate model for the supporting tool to be developed. The tool developed, implemented and validated in this work (FAPP - Parallel Programming Supporting Tool) is based on the object orientation technology. The graph theory was modeled according to the object-orientation and used as the basis for the creation of models for both parallel architectures (hardware) and parallel programs (software). This allows the programmer to create the programming environment by defining his parallel architecture, the program processes and the logical mapping of the processes on the processors. The FAPP tool automatically generates the skeleton for the parallel application. The work is validated by means of a basic implementation of the tool. The guidelines for future extensions aiming other hardware and software environments as well as for future works are presented

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Mecânica, Florianópolis, 2015. / Made available in DSpace on 2016-04-19T04:03:44Z (GMT). No. of bitstreams: 1 337626.pdf: 16916870 bytes, checksum: a0cb8bc1bf93f21cc1a78cd631272e49 (MD5) Previous issue date: 2015 / A simulação numérica é uma ferramenta de extrema importância à indústria do petróleo e gás. Entretanto, para que os resultados advindos da simulação sejam fidedignos, é fundamental o emprego de modelos físicos fiéis e de uma boa caracterização geométrica do reservatório. Isso tende a introduzir elevada carga computacional e, consequentemente, a obtenção da solução do modelo numérico correspondente pode demandar um excessivo tempo de simulação. É evidente que a redução desse tempo interessa profundamente à engenharia de reservatórios. Dentre as técnicas de melhoria de performance, uma das mais promissoras é a aplicação da computação paralela. Nessa técnica, a carga computacional é dividida entre diversos processadores. Idealmente, a carga computacional é dividida de maneira igualitária e, assim, se N é o número de processadores, o tempo computacional é N vezes menor. No presente estudo, a computação paralela foi aplicada a dois simuladores numéricos: UTCHEM e EFVLib. UTCHEM é um simulador químico-composicional desenvolvido pela The University of Texas at Austin. A EFVLib, por sua vez, é uma biblioteca desenvolvida pelo laboratório SINMEC  laboratório ligado ao Departamento de Engenharia Mecânica da Universidade Federal de Santa Catarina  cujo intuito é prover suporte à aplicação do Método dos Volumes Finitos Baseado em Elementos. Em ambos os casos a metodologia de paralalelização é baseada na decomposição de domínio.<br> / Abstract : Numerical simulation is an extremely relevant tool to the oil and gas industry. It makes feasible the procedure of predicting the production scenery in a given reservoir and design more advantageous exploit strategies fromits results. However, in order to obtain reliability fromthe numerical results, it is essential to employ reliable numerical models and an accurate geometrical characterization of the reservoir. This leads to a high computational load and consequently the achievement of the solution of the corresponding numerical method may require an exceedingly large simulation time. Seemingly, reducing this time is an accomplishment of great interest to the reservoir engineering. Among the techniques of boosting performance, parallel computing is one of the most promising ones. In this technique, the computational load is split throughout the set of processors. In the most ideal situation, this computational load is split in an egalitarian way, in such a way that if N is the number of processors then the computational time is N times smaller. In this study, parallel computing was applied to two distinct numerical simulators: UTCHEM and EFVLib. UTCHEM is a compositional reservoir simulator developed at TheUniversity of Texas atAustin. EFVLib, by its turn, is a computational library developed at SINMEC  a laboratory at theMechanical Enginering Department of The Federal University of Santa Catarina  with the aim of supporting the Element-based Finite Volume Method employment. The parallelization process were based on the domain decomposition on the both cases formerly described.

Resumo

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2006. / Submitted by samara castro (sammy_roberta7@hotmail.com) on 2009-11-04T15:46:48Z No. of bitstreams: 1 2006_Marcelo Nardelli Pinto Santana.pdf: 1928461 bytes, checksum: e393ea85d58701c1e89e8ed754ce0caf (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2009-11-15T19:38:34Z (GMT) No. of bitstreams: 1 2006_Marcelo Nardelli Pinto Santana.pdf: 1928461 bytes, checksum: e393ea85d58701c1e89e8ed754ce0caf (MD5) / Made available in DSpace on 2009-11-15T19:38:34Z (GMT). No. of bitstreams: 1 2006_Marcelo Nardelli Pinto Santana.pdf: 1928461 bytes, checksum: e393ea85d58701c1e89e8ed754ce0caf (MD5) Previous issue date: 2006 / Sistemas distribuídos têm sido cada vez mais utilizados na resolução de problemas que demandam grande quantidade de tempo de processamento, por permitirem a utilização simultânea de vários recursos computacionais. Diversas máquinas com arquiteturas distribuídas foram propostas ao longo dos anos. Entre essas arquiteturas, estão os clusters de computadores, que são sistemas distribuídos formados por estações de trabalho interligadas e que podem atingir um bom desempenho a um custo relativamente baixo. Entretanto, para que a utilização de tais sistemas seja proveitosa, é necessário que a utilização dos recursos disponíveis seja feita de maneira a permitir a otimização de algum critério. A alocação de tarefas em um sistema distribuído visa determinar como serão utilizados os processadores do sistema de modo a otimizar um critério, que grande parte das vezes é o tempo de execução de uma aplicação. Diversas abordagens já foram propostas para o problema de alocação de tarefas, que é um problema NP-Completo, incluindo algoritmos heurísticos e estratégias específicas para determinadas aplicações. Uma aplicação para qual existem diversas implementações em sistemas distribuídos é a comparação de seqüências biológicas, uma operação básica da biologia computacional que visa determinar o grau de similaridade entre seqüências. Os algoritmos ótimos existentes possuem complexidade de tempo e espaço de O(n2), sendo baseados na técnica de programação dinâmica e apresentando dependências de dados do tipo wavefront. O alto custo desses algoritmos justifica a utilização de sistemas distribuídos na resolução do problema, sendo que a maioria das implementações distribuídas busca utilizar todos os processadores disponíveis no sistema distribuído, de modo a minimizar a tempo de execução. A presente dissertação propõe um framework de alocação de tarefas de aplicações de comparação de seqüências biológicas baseadas em programação dinâmica, além de quatro estratégias de alocação de tarefas. O framework e as estratégias de alocação foram implementados em um cluster de 10 máquinas. Os resultados mostram que, para seqüências relativamente pequenas, a utilização de todos os processadores disponíveis não é a opção mais vantajosa. Por isso mesmo, a utilização de políticas de alocação que levem em consideração o tamanho das seqüências e as características das máquinas disponíveis pode permitir a redução no tempo de execução da aplicação. ____________________________________________________________________________________________ ABSTRACT / Distributed systems have been widely used in the resolution of problems that demand a large amount of processing time, because they allow the simultaneous utilization of many computational resources. Many machines with a distributed architecture have been proposed during the years. Among these are computer clusters, which are distributed systems composed of interconnected workstations and that may achieve a good performance at a relatively low cost. However, in order to take advantage of distributed systems, the available resources must be used in such a way that some criteria can be optimized. Task allocation in distributed systems aims at determine how the processors available in the system are going to be used, so that a criteria, which in many cases is the execution time of an application, is optimized. Many approaches have been proposed to the task allocation problem, which is NP-Complete, including heuristic algorithms and application specific strategies. There are many proposed distributed implementations of the biological sequence comparison application, which is a basic operation in computational biology that determines the similarity degree between sequences. The optimal algorithms available have time and space complexities in O(n2) , are based in the dynamic programming technique and present data dependencies that follow the wavefront pattern. The high costs of these algorithms justifies the utilization of distributed systems. Most of the known distributed implementations try to use all available processors in the system, so that the execution time can be minimized. The present document proposes a framework for task allocation for biological sequence comparison applications based on dynamic programming, as well as four task allocation strategies. The framework and the strategies have been implemented in a 10 machine cluster. The results show that, when the sequences are relatively small, using all available processors is not the best decision. For this reason, the utilization of task allocation policies that take into account the sequences size and the machines characteristics may cause the execution time of the application to be reduced.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2011. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2012-02-27T16:19:33Z No. of bitstreams: 1 2011_EdansFlaviusOliveiraSandes.pdf: 1562566 bytes, checksum: 676058b28872648ff52973f27bc2f19c (MD5) / Approved for entry into archive by Patrícia Nunes da Silva(patricia@bce.unb.br) on 2012-02-27T20:57:53Z (GMT) No. of bitstreams: 1 2011_EdansFlaviusOliveiraSandes.pdf: 1562566 bytes, checksum: 676058b28872648ff52973f27bc2f19c (MD5) / Made available in DSpace on 2012-02-27T20:57:53Z (GMT). No. of bitstreams: 1 2011_EdansFlaviusOliveiraSandes.pdf: 1562566 bytes, checksum: 676058b28872648ff52973f27bc2f19c (MD5) / A comparação de sequências biológicas é uma operação muito importante na Bioinformática. Embora existam métodos exatos para comparação de sequências, estes métodos usualmente são preteridos por causa da complexidade quadrática de tempo e espaço. De forma a acelerar estes métodos, muitos algoritmos em GPU foram propostos na literatura. Entretanto, todas estas propostas restringem o tamanho da sequência de busca de forma que a comparação de sequências genômicas muito longas não é possível. Neste trabalho, nós propomos e avaliamos o CUDAlign, um algoritmo em GPU capaz de comparar sequências biológicas longas com o método exato de Smith-Waterman com o modelo affine gap. O CUDAlign foi implementado em CUDA e testado em duas placas de vídeo, separadamente. Para sequências reais com tamanho entre 1 MBP (milhões de pares de bases) e 47 MBP, um desempenho aproximadamente constante em GCUPS (Bilhões de células atualizadas por segundo) foi obtida, mostrando o potencial de escalabilidade da nossa abordagem. Além disso, o CUDAlign foi capaz de comparar o cromossomo 21 humano e o cromossomo 22 do chimpanzé. Esta operação levou aproximadamente 18 horas na GeForce GTX 285, resultando em um desempenho de 23.87 GCUPS, valor muito próximo do desempenho máximo previsto (23.93 GCUPS). Até onde sabemos, esta foi a primeira vez que cromossomos grandes como esses foram comparados com um método exato. ______________________________________________________________________________ ABSTRACT / Biological sequence comparison is a very important operation in Bioinformatics. Even though there do exist exact methods to compare biological sequences, these methods are not often employed due to their quadratic time and space complexity. In order to accelerate these methods, many GPU algorithms were proposed in the literature. Nevertheless, all of them restrict the size of the query sequence in such a way that Megabase genome comparison is prevented. In this work, we propose and evaluate CUDAlign, a GPU algorithm that is able to compare Megabase biological sequences with an exact Smith-Waterman affine gap variant. CUDAlign was implemented in CUDA and tested in two GPU boards, separately. For real sequences whose size range from 1 MBP (Megabase Pairs) to 47 MBP, a close to uniform GCUPS (Giga Cells Updates per Second) was obtained, showing the potential scalability of our approach. Also, CUDAlign was able to compare the human chromosome 21 and the chimpanzee chromosome 22. This operation took approximately 18 hours on GeForce GTX 285, resulting in a performance of 23.87 GCUPS, very close to the maximum predicted performance (23.93 GCUPS). As far as we know, this is the first time such huge chromosomes are compared with an exact method.