Orientador: Ivan Luiz Marques Ricarte / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-23T14:35:54Z (GMT). No. of bitstreams: 1 Dantas_AnnaCatharinadaCosta_M.pdf: 9497760 bytes, checksum: 097a379f20e9653f453d5fe6e9bcd664 (MD5) Previous issue date: 1997 / Resumo: A classificação ou ordenação de dados tem assumido grandes proporções no âmbito do processamento de informações, tanto devido a sua importância na análise de desempenho quanto pelo fato de ser utilizado como processo intermediário em diversas aplicações. Os primeiros estudos sobre ordenação se deram a partir dos algoritmos seqüenciais. Entretanto, o tamanho crescente das aplicações tratadas vem impondo maior demanda de tempo de execução e memória, provocando uma necessidade de evolução. Para tentar minimizar os efeitos de complexidade dos algoritmos seqüenciais de ordenação, diversos algoritmos paralelos vêm sendo propostos. A combinação entre a tecnologia disponibilizada pelo processamento paralelo e a eficiência dos algoritmos de ordenação produz algoritmos paralelos de ordenação com alto poder de computação. Esse trabalho avalia alguns dos algoritmos paralelos de ordenação interna disponíveis na literatura, aplicáveis ou adaptados a multicomputadores MIMD de memória distribuída, interconectados por redes locais. Alguns benchmarks com diferentes características de distribuição de probabilidade foram implementados para validar os resultados apresentados, obtidos a partir da execução paralela suportada por bibliotecas de comunicação por troca de mensagens / Abstract: Data sorting has assumed large proportions in the field of information processing, even because of its importance in performance analysis and also because of its use as an intermediate process for several applications. The first researches about sorting have been undertaken trough serial algorithms. However, the increasing size of treated applications has imposed demand on execution time and memory, leading to evolution necessities. In order to minimize complexity effects of serial sorting algorithms, many parallel algorithms have been proposed. The combination between technology made available by parallel processing and efficiency of sorting algorithms produces parallel sorting algorithms with high computation power. This work evaluates some parallel internal sorting algorithms available in actual literature, applicable to or adapted for distributed memory MIMD multicomputers, interconnected by local works. Some benchmarks with different features of probability distribution have been complemented to validate presented results. Such results have been obtained from parallel execution supported by libraries that provide communication by message-passing / Mestrado / Mestre em Engenharia Elétrica

Orientador: Andre Luiz Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T12:31:34Z (GMT). No. of bitstreams: 1 VieiraJunior_JoseCarlosdeMelo_M.pdf: 5365638 bytes, checksum: f688423ce4052a2673b051df020a4828 (MD5) Previous issue date: 1999 / Resumo: Este trabalho propõe um método paralelo para o cálculo do fluxo de potência trifásico em redes assimétricas de distribuição de energia elétrica, baseado no método Zbus Gauss. A modelagem dos diversos componentes da rede é desenvolvida utilizando-se quantidades de fase e a forma I = YV, na qual as fases abc são desacopladas por meio de injeções compensadoras de corrente. Esse desacoplamento por fase permite o uso de computação paralela para resolver o problema, pois as equações referentes a cada fase podem ser solucionadas separadamente. A modelagem inclui representação de linhas assimétricas, transformadores trifásicos com perdas, capacitores, cogeradores e cargas desbalanceadas. Para testar seu desempenho, o método foi implementado em máquinas seriais, no computador paralelo nCUBE2 e numa rede de estações de trabalho com PVM, tendo sido comparado ao método Zbus Gauss convencional utilizando vários sistemas de distribuição reais. Observou-se um ganho de até 2,82 com três processadores em relação ao método convencional serial. O programa desenvolvido pode ser útil na operação e planejamento de redes trifásicas de distribuição permitindo analisá-las sob diversos aspectos: perdas nas linhas e transformadores, configurações radial e reticulada, desbalanceamento das cargas, variação do arregamento, influência das conexões dos enrolamentos dos transformadores e efeitos da presença de cogeradores e capacitores / Abstract: This work proposes a parallel three-phase power flow method for asymmetrical distribution systems, based on the Zbus Gauss method. Ali the elements of the distribution systems are modeled using per phase quantities and the I = YV formo Moreover, the component models are phase decoupled by using compensation current injections, making the method suitable for parallel computing, since the equations of each phase can be solved independently. The modeling includes asymmetricallines, three-phase lossy transformers, capacitors, cogenerators and unbalanced loads. In order to evaluate its performance, the method was implemented in serial machines, in the parallel computer nCUBE2, in a workstation network with PVM, and the results were compared with that showed by the serial Zbus Gauss method using several real distribution networks. It was observed a speedup of 2.82 using three processors in comparison with the serial Zbus Gauss method. The developed program can be applied to three-phase distribution systems operation and planning analysis, allowing some important characteristics to be studied: transformers and lines losses, radial and meshed configurations, unbalanced loads, loading variation, effects of transformers winding connections and effects of cogenerators and shunt capacitors / Mestrado / Mestre em Engenharia Elétrica

Orientador : Edmundo Roberto Mauro Madeira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-18T10:06:41Z (GMT). No. of bitstreams: 1 Silva_FlavioMoraisdeAssis_M.pdf: 5100707 bytes, checksum: ed89630d5b32e158cf8326ca6ef2fcd6 (MD5) Previous issue date: 1993 / Resumo: Esta dissertação consiste de Uma definição mais precisa de funcionalidades para os componentes da camada de Aplicação do RM-OSI/ISO (Reference Model - Open Systems Interconection / International Organization for Standardization). Esta definição de funcionalidades tem a finalidade de esclarecer os relacionamentos que há entre os componentes desta camada e de servir de uma base conceitual, a partir da qual estruturas para implementações possam ser derivadas. As funcionalidades apresentadas constituem um refinamento da estrutura definida pela ISO para esta camada. Também é apresentada a estrutura geral de implementação dos protocolos para um sistema didático de comunicação, chamado SISDI-0SI (Sistema didático para o Modelo OSI), que segue as padronizações do RM-OSI/ISO. Para este sistema descreve-se, em particular, como as estruturas de dados geradas por um compilador para alinguagem ASN.l são usadas na implementação destes protocolos. A dissertação consiste ainda da descrição de uma implementação do protocolo CCH (Commitment, Concurrency and Recovery), da camada de Aplicação do RM-0SI/ISO. Esta implementação foi feita utilizando-se a linguagem ESTELLE, que é uma Técnica de Descrição Formal definida pela ISSO, e faz parte do SISDI-OSI. A estrutura desta implementação foi feita de acordo com a definição de funcionalidades proposta / Abstract: This thesis consists of a more accurate definition of functionalities for the components of the Application Layer of the RM-OSI/ISO (Reference Model - Open Systems Interconnection / International Organization for Standardization). This definition of functionalities intends to clarify the relationships that exist among the components of this layer and to serve as a basis of concepts, from which structures for implementations could be derived. The presented functionalities are a refinement of the structure defined by ISO for this layer. It also presents the general structure for the implementation of the protocols of a didactic communication system, called SISDI-OSI (Didactic System for OSI Model), which conforms to the standards from RM-OSI/ISO. For this system it is described, particularly, how the data structures generated by a compiler for the ASN language are used in the implementation of these protocols. This thesis also describes an implementation of the CCR (Commitment, Concurrency and Recovery) protocol, from the Application Layer of RM-OSI/ISO. This implementation was done using the language ESTELLE, that is a Formal Description Technique defined by ISO, and takes part in SISDI-OSI. The structure of this implementation was done according to the proposed functionalities / Mestrado / Mestre em Ciência da Computação

Orientador: Alcir Jose Monticelli / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-18T11:35:52Z (GMT). No. of bitstreams: 1 SaavedraMendez_OsvaldoRonald_D.pdf: 5883958 bytes, checksum: ee32d0100a9ddf00c916cb7e52645b1a (MD5) Previous issue date: 1993 / Resumo: Este trabalho apresenta um algoritmo concorrente para a solução do fluxo de potência ótimo com restrições de segurança em computadores paralelos. O método assíncrono sugerido é baseado em construções e estruturas típicas da programação concorrente, como é o caso do modelo produtor-consumidor utilizado no gerenciamento da troca de mensagens e na partilha de dados entre as tarefas e subtarefas nas quais o problema original é decomposto. Este modelo permite um gerenciamento simples e eficiente da execução das tarefas assíncronas, o que normalmente resulta em bom balanceamento de carga entre os processadores. Este estilo de programação acomoda uma ampla variedade de problemas relacionados com o fluxo de potência ótimo com restrições de segurança, ao mesmo tempo que facilita a implementação em ambientes físicos distintos (arquiteturas baseadas em memória compartilhada e distribuída). O novo método é implementado com sucesso em uma máquina paralela, tipo memória compartilhada e barramento comum, e em um computador de memória distribuída com arquitetura hipercúbica, de 64 processadores / Abstract: Not informed. / Doutorado / Doutor em Engenharia Elétrica

Orientador: Paulo Morelato França, Michel Gendreau / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-18T19:58:07Z (GMT). No. of bitstreams: 1 Muller_FelipeMartins_D.pdf: 8020755 bytes, checksum: 031f8c626f59dd5d71d81ea4412194fb (MD5) Previous issue date: 1993 / Resumo: Não informado / Abstract: This thesis deals with the problem of scheduling n jobs on m identical parallel machines with the objective of minimizingthe total execution time (makespan).Two cases are considered: in the first one the jobs are independent and the processing times are positive integers; in the second case we have sequence dependent times. For the first case we propose a 3-PHASE heuristic: initial assignment, job reassignment and job interchange. The 3-PHASE algorithm is compared with three other heuristics chosen from the literature by its good known average performance. The new heuristic is also compared with an exact method in order to evaluate the quality of the solutions obtained by the heuristic. Extensive computational tests were performed for randomly generated problems and they exhibited that the 3-PHASE heuristic yields average solution values at least as good as (with only one exception) those obtained with any of the three alternative heuristics used for comparison. The 3-PHASE algorithm found the optimal solution in around 70% of the problems for wich the optimal solution were known. In the second case we also propose a three phase heuristic: initial assignment, tabu phase and post-optimization phase. This algorithm rruUcesuse of tabu search techniques and general insertion procedure called GENIUS, originally designed for the Traveling Salesman Problem and properly adapted for the scheduling problem. A nearest neighbour procedures was also adapted for the scheduling problem and was used in comparisons with the proposed method. An exact method was developed for the problem in question. Tests were performed in randomly generated problems in a structured fashion and in a non-structured fashion. Results for both cases are presented and commented. / Doutorado / Doutor em Engenharia Elétrica

Orientador: Arthur João Catto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-19T02:28:34Z (GMT). No. of bitstreams: 1 Kamienski_CarlosAlberto_M.pdf: 3019895 bytes, checksum: e04af56f49a002f0ae6e47cf4a270778 (MD5) Previous issue date: 1994 / Resumo: Esta tese apresenta um estudo detalhado sobre o armazenamento de resultados (dados utilizados no processamento) em uma arquitetura de fluxo de dados. Ele segue uma forte tendência atual no sentido de unir as melhores características dos modelos Von Neumann e de fluxo de dados em uma arquitetura híbrida. Propõe-se a arquitetura da MX, uma máquina de fluxo de dados que incorpora mecanismos de gerenciamento explícito de memória (memória compartilhada dividida em módulos entrelaçados) e execução seqüencial de instruções. Mostra-se que esta arquitetura constitui uma plataforma adequada para a realização de testes de desempenho no sistema de memória / Abstract: This thesis presents a detailed study on result (data used in processing) storage in a data flow architecture. It follows a strong current tendency towards hibrid architectures which incorporate the best characteristics of the von Neu­mann and data flow computational models. The MX architecture is proposed, a data flow machine which incorporates mechanisms for the explicit management of a shared memory partioned in interleaved modules and for sequential instruction execution. It is shown that such an architecture constitutes an adequate platform for performance testing of the memory system / Mestrado / Mestre em Ciência da Computação

Orientador: Edmundo Roberto Mauro Madeira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-19T14:09:35Z (GMT). No. of bitstreams: 1 LimaJunior_LuizAugustodePaula_M.pdf: 1712349 bytes, checksum: ca48275513dcaa64928c6b4aaf2c09ed (MD5) Previous issue date: 1994 / Resumo: Este trabalho descreve uma proposta de TRADER que é o objeto computacional que recebe ofertas de serviços de outros objetos (chamados "servidores") colocando-as numa base de dados. Assim que um outro objeto qualquer (um "cliente") necessitar de um serviço computacional ele pode perguntar ao trader que então o informa a respeito da "localização" de algum servidor que oferece este serviço. Através de binding dinâmico, o cliente pode acessar o serviço na interface do servidor. Estes conceitos são introduzidos no Capítulo 1, juntamente com o modelo de referência para Processamento Distribuído Aberto da ISO (RMODP) que fornece a estrutura básica para a formulação dos modelos que serão propostos. No Capítulo 2 apresenta-se o trader em detalhes a partir dos cinco pontos de vista definidos pelo RM-ODP. A união de traders estabelecendo Federações é discutida no Capítulo 3 apresentando-se vantagens e os detalhes e mecanismos para tal organização, novamente a partir dos cinco pontos de vista do RM-ODP. No Capítulo 4 são apresentados modelos e mecanismos para a construção de federação de traders. Neste capítulo é proposto um modelo teórico para a implementação de um trader incluindo toda a funcionalidade necessária para a criação de federações e utilização das operações federadas. Ainda no capítulo 4 são discutidos os detalhes da implementação do protótipo de trader construído no trabalho como parte da plataforma MULTIWARE em desenvolvimento na UNICAMP. Também os principais algoritmos e estruturas de dados são comentados e é feita uma análise comparativa com trabalhos relacionados. Por fim, no Capítulo 5, são levantadas as principais dificuldades encontradas durante o desenvolvimento do projeto, as principais contribuições do presente trabalho e possíveis futuras extensões / Abstract: This work describes a proposal of a TRADER which is the computational object that receives service offers from other objects (called "servers") storing them in a data base. When another object (a "client") needs a computational service, it can ask the trader about the service, and then the trader may return the "address" of a server which offers that service. Through dynamic binding the client can access the service at the server's interface. Ali of these concepts are introduced in the Chapter 1 besides the ISO Reference Model for Open Distributed Processing (RM-ODP). In Chapter 2 the trader is described in detail using the five view-points defined in the RM-ODP. The grouping of traders creating Federations is discussed in Chapter 3, presenting the advantages and the details of this organization, again using the five view-points of the RM-ODP. In Chapter 4 mechanisms and models for the construction of federated traders are presented. A theoretic model for the implementation of a trader including all the functionality neccessary for federation and federated operations is also proposed in this chapter. Furthermore, the details of the implementation of the prototype of a trader are discussed. The prototype was built as a part of the MULTIWARE platform which is in development at UNICAMP. The main algorithms and data structures are also commented in Chapter 4. At the end of the chapter, a comparative analysis of related works is made. At last, in Chapter 5, the maim difficulties found during the development of the project are raised and the main contributions of this current work and possible future extensions are commented / Mestrado / Mestre em Ciência da Computação

A Bioinformática tem se desenvolvido de forma intensa nos últimos anos. A necessidade de se processar os grandes conjuntos de sequências, sejam de nucleotídeos ou de aminoácidos, tem estimulado o desenvolvimento de diversas técnicas algorítmicas, de modo a tratar este problema de maneira factível. Os algoritmos de alinhamento de alinhamento múltiplo de sequências assumiram um papel primordial, tornando a execução de alinhamentos de conjuntos com mais de duas sequencias uma tarefa viável computacionalmente. No entanto, com o aumento vertiginoso tanto da quantidade de sequencias em um determinado conjunto, quanto do comprimento dessas sequencias, a utilização desses algoritmos de alinhamento múltiplo, sem o acoplamento de novas estratégias, tornou-se algo impraticável. Consequentemente, a computação de alto desempenho despontou como um dos recursos a serem utilizados, através da paralelização de diversas estratégias para sua execução em grandes sistemas computacionais. Além disso, com a contínua expansão dos conjuntos de sequências, outras estratégias de otimização passaram a ser agregadas aos algoritmos de alinhamento múltiplo paralelos. Com isso, o desenvolvimento de ferramentas para alinhamento múltiplo de sequencias baseadas em abordagens híbridas destaca-se, atualmente, como a solução com melhor aceitação. Assim, no presente trabalho, pode-se verificar o desenvolvimento de uma estratégia híbrida para os algoritmos de alinhamento múltiplo progressivos, cuja utilização e amplamente difundida, em Bioinformática. Nesta abordagem, conjugou-se a paralelização e o particionamento dos conjuntos de sequências, na fase de construção da matriz de pontuação, e a otimização das fases de construção da árvore filogenética e de alinhamento múltiplo, através dos algoritmos de colônia de formigas e simulated annealling paralelo, respectivamente. / Bioinformatics has been developed in a fast way in the last years. The need for processing large sequences sets, either nucleotides or aminoacids, has stimulated the development of many algorithmic techniques, to solve this problem in a feasible way. Multiple sequence alignment algorithms have played an important role, because with the reduced computational complexity provided by them, it is possible to perform alignments with more than two sequences. However, with the fast growing of the amount and length of sequences in a set, the use of multiple alignment algorithms without new optimization strategies became almost impossible. Therefore, high performance computing has emerged as one of the features being used, through the parallelization of many strategies for execution in large computational systems. Moreover, with the continued expansion of sequences sets, other optimization strategies have been coupled with parallel multiple sequence alignments. Thus, the development of multiple sequences alignment tools based on hybrid strategies has been considered the solution with the best results. In this work, we present the development of a hybrid strategy to progressive multiple sequence alignment, where its using is widespread in Bioinformatics. In this approach, we have aggregated the parallelization and the partitioning of sequences sets in the score matrix calculation stage, and the optimization of the stages of the phylogenetic tree reconstruction and multiple alignment through ant colony and parallel simulated annealing algorithms, respectively.

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.

Applications such as electronic commerce, computer networks, social networks, and biology (protein interaction), to name a few, have led to the production of graph-like data in planetary scale { possibly with millions of nodes and billions of edges. These applications pose challenging problems when the task is to use their data to support decision making processes by means of non-obvious and potentially useful patterns. In order to process such data for pattern discover, researchers and practitioners have used distributed processing resources organized in computational clusters. However, building and managing such clusters can be complex, bringing technical and financial issues that can be prohibitive in a variety of scenarios. Alternatively, it is desirable to process large scale graphs using only one computational node. To do so, we developed processes and algorithms according to three different approaches, building up towards an analytical set capable of revealing patterns, comprehension, and to help with the decision making process over planetary-scale graphs. / Aplicações como comércio eletrônico, redes de computadores, redes sociais e biologia (interação proteica), entre outras, levaram a produção de dados que podem ser representados como grafos à escala planetária { podendo possuir milhões de nós e bilhões de arestas. Tais aplicações apresentam problemas desafiadores quando a tarefa consiste em usar as informações contidas nos grafos para auxiliar processos de tomada de decisão através da descoberta de padrões não triviais e potencialmente utéis. Para processar esses grafos em busca de padrões, tanto pesquisadores como a indústria tem usado recursos de processamento distribuído organizado em clusters computacionais. Entretanto, a construção e manutenção desses clusters pode ser complexa, trazendo tanto problemas técnicos como financeiros que podem ser proibitivos em diversos casos. Por isso, torna-se desejável a capacidade de se processar grafos em larga escala usando somente um nó computacional. Para isso, foram desenvolvidos processos e algoritmos seguindo três abordagens diferentes, visando a definição de um arcabouço de análise capaz de revelar padrões, compreensão e auxiliar na tomada de decisão sobre grafos em escala planetária.