Este trabalho descreve a prova de conceito de uma abordagem que utiliza o modelo de computação a fluxo de dados, inerentemente paralelo, associado ao modelo de computação reconfigurável parcial e dinamicamente, visando à obtenção de sistemas computacionais de alto desempenho. Mais especificamente, trata da obtenção de um modelo para o particionamento dos grafos a fluxo de dados dinâmicos e de um protocolo de comunicação entre suas partes, a fim de permitir a sua implementação em arquiteturas dinamicamente reconfiguráveis, em especial em FGPAs Virtex da Xilinx. Enquadra-se no contexto do projeto ChipCFlow, de escopo mais amplo, que pretende obter uma ferramenta para geração automática de descrição de hardware sintetizável, a partir de código em alto nível, escrito em linguagem C, fazendo uso da abordagem a fluxo de dados para extrair o paralelismo implícito nas aplicações originais. O modelo proposto é aplicado em um grafo a fluxo de dados dinâmico, e através de simulações sua viabilidade é discutida / This work describes the concept of an approach that uses data ow computational model, inherently parallel, associated with de reconfigurable computing model, partial and dynamic, in order to obtain high performance computational systems. More specifically, it is about a model to the partitioning and communication between partitioned sectors of a CDFG (Control Data Flow Graph) in order to map these graphs on a partial reconfiguration FPGA fabric, in special Virtex II/II-Pro from Xilinx. It is part of the ChipCFlow project, that has a bigger scope, and that aims to automatically obtain syntetisable hardware descriptions, from high level code written in C and, by using a data flow approach to extract implicit parallelism in original applications. The model obtained is extensively explained and applied to an example of CDFG, where by means of simulations its feasibility is discussed

[pt] As principais estratégias de sintonia fina utilizadas por administradores de bancos de dados relacionais são a construção de estruturas de acesso, como índices, índices parciais e visões materializadas, e técnicas como desnormalização e reescrita de consultas. Estas técnicas e estruturas de acesso, juntas ou separadas, podem melhorar o desempenho das consultas submetidas ao banco de dados. O particionamento de tabelas do banco de dados, técnica tradicionalmente utilizada para distribuição de dados, também possui potencial para sintonia fina, pois permite que a varredura das tabelas seja realizada somente nas partições que satisfazem os predicados das consultas. Mesmo em consultas com predicados de seletividade alta, cujos planos de execução frequentemente utilizam índices, o particionamento pode oferecer um benefício ainda maior. Esta dissertação de mestrado propõe avaliar o particionamento como ação de sintonia fina de bancos de dados relacionais e, para tanto, desenvolve heurísticas para seleção de estratégias de particionamento e avaliação do seu benefício. Uma avaliação da qualidade dos resultados obtidos é realizada através de experimentos com um benchmark padrão para este tipo de pesquisa e mostramos que, em certos casos, é vantajoso particionar dados. / [en] The main fine tuning strategies used by relational database administrators are the construction of access structures, such as indexes, partial indexes and materialized views, and techniques such as denormalization and query rewriting. These techniques and access structures, together or separately, can improve the performance of queries submitted to the database. Database partitioning, a technique traditionally used for data distribution, has also the potential for fine tuning, since it allows the scanning of tables to be performed only on partitions that satisfy query predicates. Even in queries with high selectivity predicates, whose execution plans often use indexes, partitioning can offer even greater benefit. This dissertation proposes to evaluate the partitioning as a fine tuning action of relational databases and, for that, develops heuristics for selection of partitioning strategies and evaluation of its benefit. An evaluation of the quality of the results obtained is carried out through experiments with a standard benchmark for this type of research and we have shown that, in certain cases, it is advantageous to partition data.

Submitted by Valquíria Barbieri (kikibarbi@hotmail.com) on 2018-04-06T21:13:27Z No. of bitstreams: 1 DISS_2014_Rogerio Conceição Lima dos Santos.pdf: 1090088 bytes, checksum: d06d0c75f11cacba50aedbf179785382 (MD5) / Approved for entry into archive by Jordan (jordanbiblio@gmail.com) on 2018-04-23T18:34:10Z (GMT) No. of bitstreams: 1 DISS_2014_Rogerio Conceição Lima dos Santos.pdf: 1090088 bytes, checksum: d06d0c75f11cacba50aedbf179785382 (MD5) / Made available in DSpace on 2018-04-23T18:34:10Z (GMT). No. of bitstreams: 1 DISS_2014_Rogerio Conceição Lima dos Santos.pdf: 1090088 bytes, checksum: d06d0c75f11cacba50aedbf179785382 (MD5) Previous issue date: 2014-12-05 / CAPES / Ecossistemas aquáticos são hierarquicamente organizados que e incorporam em níveis sucessivos diferentes escalas espaciais influenciando as comunidades aquáticas. A compreensão dos atributos ecológicos envolvidos é fundamental para evitar a perda da biodiversidade e subsidiar estratégias de conservação. Os objetivos deste estudo foram identificar quais escalas espaciais estão associadas a maior diversidade beta e quais são os fatores ambientais mais importantes para estruturar a comunidade de Trichoptera nas escalas de riachos e microbacias. As coletas foram espacialmente hierarquizadas em quatro escalas: Unidade de conservação (Escala 4); 12 microbacias (Escala 3); 36 riachos (Escala 2); micro-habitats (Escala 1). Para amostragem utilizamos o coletor Surber (0,250 mm), e a cobertura vegetal foi mensurada através do Índice de Vegetação por Diferença Normalizada (NDVI). As relações entre os componentes da diversidade foram realizadas através da análise de particionamento aditivo, e a influência do ambiente na comunidade através de regressão múltipla multivariada com dimensões da NMDS e eixos da PCA. Foram registrados 4325 larvas de Trichoptera, distribuídos em 36 morfoespécies. As famílias com maior riqueza foram Hydroptilidae (9 spp.) e Leptoceridae (8 spp.). O particionamento aditivo demonstrou que a escala de microbacia estão associadas a maior diversidade beta, tanto para a métrica de riqueza (β3=25%) quanto para diversidade de Shannon (β3=18,25%). A análise de regressão múltipla multivariada entre os eixos da PCA e as dimensões do NMDS, na escala de microbacia, demonstrou que a cobertura vegetal e a condutividade elétrica foram relacionadas com abundância (Eixo 1 - Pillai Trace= 0,58686, F= 5,6820, p= 0,029) e presença e ausência (Eixo 1 - Pillai Trace= 0,58187, F= 5,5665, p= 0,03) de larvas de Trichoptera. A comunidade de Trichoptera nas diferentes escalas espaciais (substratos, riacho, microbacia e unidade de conservação) foi afetada por múltiplos fatores locais e regionais. As maiores variações ocorreram na escala de microbacias, influenciadas pela heterogeneidade de micro-habitats, cobertura vegetal e condutividade elétrica. / Aquatic Ecosystems are hierarchically organized and incorporate into successive levels different spatial scales, which influence the aquatic communities. The understanding of ecological attributes involved is crucial to prevent the loss of biodiversity and to subsidize conservation strategies. The objectives of this study are to identify which spatial scales are associated with higher beta diversity and what are the environmental factors most important for structuring community of Trichoptera in scales of streams and watersheds. The collections were spatially graded in four scales: conservation Unit (Level 4); 12 watersheds (Scale 3); 36 streams (Level 2); micro-habitats (Scale 1). For sampling we use the manifold Surber sampler (0.250 mm), and the canopy was measured through the Vegetation Index by Difference (NDVI). The relations between the components of diversity were carried out through the analysis of additive partitioning, and the influence of the environment in the community through multiple regression multivariate dimensions of NMDS and PCA axs. Were recorded 4325 Trichoptera larvae, distributed in 36 morphospecies. The families with the highest richness were Hydroptilidae (9 spp.) and Leptoceridae (8 spp.). The additive partitioning demonstrated that the watershed scale are associated with higher beta diversity, both for the metric of wealth (β3 = 25%) and Shannon diversity (β3= 18,25%). The multiple regression analysis multivariate analysis between the axs of the PCA and the dimensions of the NMDS, the watershed scale, demonstrated that the vegetation cover and electrical conductivity were related with abundance (Axis 1 - Pillai Trace=0,58686, F = 5,6820, p = 0,029) and presence and absence (Axis 1 - Pillai Trace= 0,58187, F = 5,5665, p = 0,03) Trichoptera larvae. The community of Trichoptera in different spatial scales (substrates, stream, and watershed conservation unit) was affected by multiple local and regional factors. The largest changes occurred in the scale of watersheds, influenced by heterogeneity of micro-habitats, vegetation coverage, and electrical conductivity.

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T07:52:55Z (GMT). No. of bitstreams: 1 Faleiros_ThiagodePaulo_M.pdf: 2870028 bytes, checksum: fc82c1cba0951230720985bb3a712fd0 (MD5) Previous issue date: 2010 / Resumo: Investigamos Problemas de Particionamento de objetos que têm relações de similaridade entre si. Instâncias desses problemas podem ser representados por grafos, em que objetos são vértices e a similaridade entre dois objetos é representada por um valor associado à aresta que liga os objetos. O objetivo do problema é particionar os objetos de tal forma que objetos similares pertençam a um mesmo subconjunto de objetos. Nosso foco é o estudo de algoritmos para clusterização em grafos, onde deve-se determinar clusteres tal que arestas ligando vértices de clusteres diferentes tenham peso baixo e ao mesmo tempo as arestas entre vértices de um mesmo cluster tenha peso alto. Problemas de particionamento e clusterização possuem aplicações em diversas áreas, como mineração de dados, recuperação de informação, biologia computacional, entre outros. No caso geral estes problemas são NP-Difíceis. Nosso interesse é investigar algoritmos eficientes (com complexidade de tempo polinomial) e que gerem boas soluções, como Heurísticas, Metaheurísticas e Algoritmos de Aproximação. Dentre os algoritmos estudados, implementamos os mais promissores e fazemos uma comparação de seus resultados utilizando instâncias geradas computacionalmente. Por fim, propomos um algoritmo que utiliza a metaheurística GRASP para o problema considerado e mostramos que, para as instâncias de testes geradas, nosso algoritmo obtém melhores resultados / Abstract: In this work we investigate Partitioning Problems of objects for which a similarity relations is defined. Instance to these problems can be represented by graphs where vertices are objects, and the similarity between two objects is represented by a value associated with an edge that connects objects. The problem objective is to partition the objects such that similar objects belong to the same subset of objects. We study clustering algorithms for graphs, where clusters must be determined such that edges connecting vertices of different clusters have low weight while the edges between vertices of a same cluster have high weight. Partitioning and clustering problems have applications in many areas, such as data mining, information retrieval, computational biology, and others. Many versions of these problems are NP-Hard. Our interest is to study eficient algorithms (with polynomial time complexity) that generate good solutions, such as Heuristics, Approximation Algorithms and Metaheuristics. We implemented the most promising algorithms and compared their results using instances generated computationally. Finally, we propose a GRASP based algorithm for the partition and clustering problem and show that, for the generated test instances, our algorithm achieves better results / Mestrado / Mestre em Ciência da Computação

Este trabalho descreve a prova de conceito de uma abordagem que utiliza o modelo de computação a fluxo de dados, inerentemente paralelo, associado ao modelo de computação reconfigurável parcial e dinamicamente, visando à obtenção de sistemas computacionais de alto desempenho. Mais especificamente, trata da obtenção de um modelo para o particionamento dos grafos a fluxo de dados dinâmicos e de um protocolo de comunicação entre suas partes, a fim de permitir a sua implementação em arquiteturas dinamicamente reconfiguráveis, em especial em FGPAs Virtex da Xilinx. Enquadra-se no contexto do projeto ChipCFlow, de escopo mais amplo, que pretende obter uma ferramenta para geração automática de descrição de hardware sintetizável, a partir de código em alto nível, escrito em linguagem C, fazendo uso da abordagem a fluxo de dados para extrair o paralelismo implícito nas aplicações originais. O modelo proposto é aplicado em um grafo a fluxo de dados dinâmico, e através de simulações sua viabilidade é discutida / This work describes the concept of an approach that uses data ow computational model, inherently parallel, associated with de reconfigurable computing model, partial and dynamic, in order to obtain high performance computational systems. More specifically, it is about a model to the partitioning and communication between partitioned sectors of a CDFG (Control Data Flow Graph) in order to map these graphs on a partial reconfiguration FPGA fabric, in special Virtex II/II-Pro from Xilinx. It is part of the ChipCFlow project, that has a bigger scope, and that aims to automatically obtain syntetisable hardware descriptions, from high level code written in C and, by using a data flow approach to extract implicit parallelism in original applications. The model obtained is extensively explained and applied to an example of CDFG, where by means of simulations its feasibility is discussed

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T04:31:47Z (GMT). No. of bitstreams: 1 Braga_AndreideAlmeidaSampaio_M.pdf: 1060769 bytes, checksum: 789d9000e49ebe5d5a54a275c6018cb6 (MD5) Previous issue date: 2011 / Resumo: O problema de particionamento de conjuntos (SPP, do inglês set partitioning problem) é considerado um dos problemas de otimização combinatória com mais vasta gama de aplicações. Para solucioná-lo, utilizam-se comumente métodos tradicionais para a resolução de problemas NP - Difíceis. Nesta dissertação, estuda-se o uso da combinação de relaxação Lagrangiana com planos de corte. Relaxação Lagrangiana é uma técnica que tem sido usada com bastante sucesso para atacar vários problemas NP-Difíceis. Os algoritmos relax-and-cut, em especial, onde se adicionam dinamicamente planos de corte a relaxações Lagrangianas, têm ganhado bastante destaque nas últimas décadas. Em [15], Cavalcante et al. aplicam um algoritmo relax-and-cut ao SPP e obtém ótimos resultados. No entanto, tal algoritmo, bem como implementações em geral da citada combinação, são ainda passíveis de refinamentos e extensões. O estudo proposto aqui é realizado por meio das seguintes extensões do referido algoritmo: a implementação de uma partida quente para o multiplicador de uma inequação adicionada; a incorporação do algoritmo a uma enumeração, gerando, assim, um branch-and-cut baseado em relaxação Lagrangiana para o SPP; a implementação do citado branch-and-cut com o emprego de relaxações alternativas e a implementação de uma versão distribuída do algoritmo / Abstract: The set partitioning problem (SPP) is considered one of the combinatorial optimization problems with the widest range of applications. To solve the SPP, one commonly uses traditional methods for NP-Hard problem solving. In this dissertation, we study the use of the combination of Lagrangean relaxation with cutting planes. Lagrangean relaxation is a technique that has been used quite successfully to tackle several NP-Hard problems. In particular, relax-and-cut algorithms, in which cutting planes are added dynamically to Lagrangean relaxations, have gained much importance in the last decades. In [15], Cavalcante et al. applied a relax-and-cut algorithm to the SPP and obtained promising results. However, that algorithm, as well as implementations of the mentioned combination in general, are still subject to refinements and extensions. The study proposed here is carried out through the following extensions of that algorithm: the implementation of a warm start to the multiplier of an added inequality; the incorporation of the algorithm to an enumeration, thus generating a Lagrangean relaxation based branch-and-cut for the SPP; the implementation of that branch-and-cut with the use of alternative relaxations and the implementation of a distributed version of the algorithm / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-04-13T12:35:48Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação_Mestrado_Gabriel_Dannunzio_Gomes_Junior.pdf: 5445671 bytes, checksum: 0fbfa28afa66b0dd5cc8217c1d6c2418 (MD5) / Made available in DSpace on 2016-04-13T12:35:48Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação_Mestrado_Gabriel_Dannunzio_Gomes_Junior.pdf: 5445671 bytes, checksum: 0fbfa28afa66b0dd5cc8217c1d6c2418 (MD5) Previous issue date: 2015-08-26 / Existe uma crescente atenção voltada para o tema erosão costeira, devido principalmente à mudança climática de causas antrópicas, que está induzindo ao lento e gradual aumento do nível dos oceanos de forma irreversível a curto prazo, de acordo com a grande maioria dos cientistas do clima. Outro fator que influencia no aumento do risco de erosão costeira é a ocupação antrópica desordenada da área de pós-praia, que serve como proteção natural, bem como reserva de sedimentos para a área de praia, e que está constantemente sendo modificada pela ação das ondas e da corrente costeira. Este trabalho possui dois focos principais que estão interconectados. O primeiro trata do estudo de um caso de intervenção antrópica numa área de praia altamente suscetível à erosão costeira, numa zona urbana densamente povoada no litoral da zona metropolitana do Recife. Esta intervenção consiste na construção de um quebra-mar, com a intenção de proteger esta área de praia resultou na transferência da problemática da erosão costeira para a praia ao Norte. Numa segunda tentativa de resolver o problema, foi adotada uma terceira configuração que aparentemente teve um impacto positivo na prevenção da erosão costeira. Estudou-se os três cenários de configuração deste quebra-mar, utilizando-se de um pacote de software de simulação de ondas, correntes costeiras e transporte de sedimento, com o objetivo específico de se estudar, testar e encontrar soluções que possam eliminar a erosão costeira. O segundo foco deste trabalho trata-se de estudar o clima de ondas da região, através de medições feitas por um ondógrafo direcional durante um período de três anos. Para esta finalidade, desenvolveu-se uma metodologia de classificação das ondas a partir do espectro direcional, obtido através das medições, de forma a se distinguir com mais clareza as características de cada sistema de ondas que fazia parte deste espectro. Após esta etapa foi feita uma comparação entre o clima de ondas obtido através das medições, com o clima de ondas que faz parte da base de dados que acompanha o pacote de software utilizado na primeira etapa deste trabalho, de forma a validar o uso do software como uma ferramenta confiável no estudo do impacto da erosão. O resultado da comparação foi que o software possui uma base de dados confiável, mas que precisa de alguns ajustes para obter uma melhor descrição do clima de ondas da região. / There is increasing attention on the coastal erosion issue, mainly due to anthropogenic causes, first on the climate change, which led to the slow and gradual sea level rise, and also by the irregular occupation of the post-beach area, which serves as a natural protection and a sediment reserve to the beach area, which is constantly being modified by wave action and coastal currents. This work has two main focuses which are interconnected. The first is the study of a human intervention case in a beach area highly susceptible to coastal erosion in a densely populated urban area on the coast of the metropolitan area of Recife. This intervention , made by installing a breakwater with the intention to protect this beach area, but resulted in the transfer of the coastal erosion problem to the northern beach. In a second attempt to solve this problem, it was adopted a third configuration that apparently had a positive impact on the prevention of the coastal erosion. These three different breakwater configuration scenarios were studied, using a software package that simulates waves, coastal currents and sediment transport, with the specific objectives of studying, testing and finding solutions in order to eliminate the coastal erosion. The second focus of this work is to study the wave climate of the region, through the measurements of a directional wave buoy over a period of three years. For this purpose it was developed a practical wave partitioning method to be applied on the measured directional spectra, in order to more clearly distinguish the characteristics of each wave system that is part of the spectrum. After this step, a comparison was made between the wave climate obtained through the buoy measurements, and the wave climate obtained through the software package, used in the first stage of this work, in order to validate the use of this software as a reliable tool in the study of the coastal erosion impact. The result of this comparison is that the software has a reliable database, but it needs some tweaking to get a better description of the region wave climate.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-06T13:51:44Z No. of bitstreams: 1 THICIANY MATSUDO IWANO - DISSERTAÇÃO PPGMAT 2005..pdf: 3751075 bytes, checksum: 2aaae3fdd115cd9f6f4b653f522d94c8 (MD5) / Made available in DSpace on 2018-07-06T13:51:44Z (GMT). No. of bitstreams: 1 THICIANY MATSUDO IWANO - DISSERTAÇÃO PPGMAT 2005..pdf: 3751075 bytes, checksum: 2aaae3fdd115cd9f6f4b653f522d94c8 (MD5) Previous issue date: 2005-10 / Neste trabalho apresentamos um estudo das principais técnicas de geração de malhas poligonais, a partir de superfícies descritas matematicamente por funções implícitas,isto é, superfícies definidas pelo conjunto S = f−1(0) = {X ∈ R3 | f(X) = 0}, onde f : R3 → R e f é, pelo menos, de classe C2. Mostramos um método para obter as curvaturas gaussiana e média dessas superfícies a partir do vetor ∇f para cada ponto de S. Abordamos questões como a preservação de características geométricas e topológicas do objeto gráfico. Dentre os métodos estudados, ressaltamos o algoritmo Marching Triangles, que gera uma malha a partir de um ponto arbitrário p sobre a superfície S e um referencial local, usando a abordagem do avanço de frentes. Em sua implementação, usamos o raio de curvatura, calculado a partir da curvatura normal máxima absoluta da superfície em cada ponto p pertencente a S, para adaptar o comprimento das arestas da malha triangular à geometria local da superfície S / In this work we present a study about the main techniques of surfaces meshes generation, described by implicit functions, that is, surfaces defined by the set S = f−1(0) = {X ∈ R3 | f(X) = 0}, where f : R3 → R and f is, at least, C2. We discuss aspects involving his preservation of graphic object’s geometry and topology. As special method we cite the Marching Triangles that generates a mesh starting from an arbitrary point p on surface S and a local referencial, using advancing fronts approach. In our implementation, we use the radius of curvature, calculated from surface’s absolute maximum normal curvature in each point p in S and the triangular mesh, to adapt the edges length of the mesh to the local geometry.

O grande volume de dados armazenados em meio digital dificulta a anáalise e extração de informações por um ser humano sem que seja utilizada alguma ferramenta computacional inteligente. A área de Aprendizado de Máquina (AM) estuda e desenvolve algoritmos para o processamento e obtenção automática de conhecimento em dados digitais. Tradicionalmente, os algoritmos de AM modelam os dados analisados com base na abordagem proposicional; entretanto, recentemente com a disponibilidade de conjuntos de dados relacionais novas abordagens têm sido estudadas, como a modelagem utilizando redes complexas. Redes complexas é uma área de pesquisa recente e ativa que têm atraíido a atenção de pesquisadores e tem sido aplicada em diversos domínios. Mais especificamente, o estudo de detecção de comunidades em redes complexas é o tema principal deste trabalho. Detectar comunidades consiste em buscar grupos de vértices densamente conectados entre si em uma rede. Detectar a melhor divisão em comunidades de uma rede é um problema NP-completo, o que requer que o desenvolvimento de soluções viáveis baseiem-se em heurísticas como, por exemplo, medidas de qualidade. Newman prop^os a medida de modularidade Q que tem se mostrado eficiiente na análise de comunidades em redes. Este trabalho apresenta o Algoritmo Multinível de Otimização de Modularidade (AMOM) que é baseado a na otimização da medida de modularidade e integrado na estratégia multinível. A estratégia multinível é composta de três fases: (i) sucessivas compactações da rede inicial com base em contrações de arestas e fus~oes de vértices, (ii) particionamento da rede reduzida utilizando Algoritmo de Otimização de Modularidade (AOM) modificado, e (iii) sucessivas descompactações das redes intermediárias até que se retorne a rede inicial. O principal atrativo da estratégia é viabilizar a utilização de algoritmos custosos no particionamento do grafo compactado, uma vez que neste grafo a quantidade de vértices e arestas é uma fração reduzida em relação ao grafo inicial. O trabalho também propõe dois novos métodos para refinamento dos particionamentos durante a fase de uncoasening. A fiim de avaliar a escalabilidade e eficiiência da metodologia proposta foram realizados experimentos empíricos em redes consideradas benchmark. Os resultados demonstram um significativo ganho de desempenho, mantendo bons resultados qualitativos / Human based analysis of large amount of data is a hard task when no intelligent computer aid is provided. In this context, Machine Learning (ML) algorithms are aimed at automatically processing and obtaining knowledge from data. In general, ML algorithms use a propositional representation of data such as an attribute-value table. However, this model is not suitable for relational information modeling, which can be better accomplished using graphs or networks. In this context, complex networks have been call attention of scientific community recently and many applications in different domains have been developed. In special, one of complex networks research trends is the community detection field which is the main focus of this work. Community detection is the problem of finding dense and disjoint connected groups of vertices in a network. The problem is a well know NP-complete task which requires heuristics approaches, like quality measures, to be addressed. Newman introduced a specific quality measure called modularity that proved to be useful for analysis communities in networks. This work presents a new algorithm, called Multilevel Modularity Optimization Algorithm, based on modularity measure optimization integrated in a multilevel graph partitioning strategy. The multilevel graph partitioning scheme consists of three phases: (i) reduction of the size (coarsen) of original graph by collapsing vertices and edges, (ii) partitioning the coarsened graph, and (iii) uncoarsen it to construct a partition for the original graph. The rationale behind this strategy is to apply a computationally expensive method in a coarsened graph, i.e., with a significantly reduced number of vertices and edges. In addition, it is proposed two new methods that uses modularity and clustering coefficient for partition refinement. Empirical evaluation on benchmarks networks using this approach demonstrate a significant speed up gain compared to the original modularity-based algorithm, keeping a good quality clusters partitioning

Sistemas baseados em processadores de uso geral caracterizam-se pela flexibilidade a mudanças de projeto, porém com desempenho computacional abaixo daqueles baseados em circuitos dedicados otimizados. A implementação de algoritmos em dispositivos reconfiguráveis, conhecidos como Field Programmable Gate Arrays - FPGAs, oferece uma solução de compromisso entre a flexibilidade dos processadores e o desempenho dos circuitos dedicados, pois as FPGAs permitem que seus recursos de hardware sejam configurados por software, com uma granularidade menor que a do processador de uso geral e flexibilidade maior que a dos circuitos dedicados. As versões atuais de FPGAs apresentam um tempo de reconfiguração suficientemente pequeno para viabilizar sua reconfiguração dinâmica, i.e., mesmo com o dispositivo executando um algoritmo, a forma como seus recursos são dispostos pode ser alterada, oferecendo a possibilidade de particionar temporalmente um algoritmo. Novas linhas de FPGAs já são fabricadas com opção de reconfiguração dinâmica parcial, i.e., é possível reconfigurar áreas selecionadas de uma FPGA enquanto o restante continua em operação. No entanto, para que esta nova tecnologia se torne largamente difundida é necessário o desenvolvimento de uma metodologia própria, que ofereça soluções eficazes aos novos desdobramentos do projeto digital. Em particular, uma das principais dificuldades apresentadas por esta abordagem refere-se à maneira de particionar o algoritmo, de forma a minimizar o tempo necessário para completar sua tarefa. Este manuscrito oferece uma metodologia de projeto para dispositivos dinamicamente reconfiguráveis, com ênfase no problema do particionamento temporal de circuitos, tendo como aplicação alvo uma família de algoritmos, utilizados principalmente em Bioinformática, representada pelo classificador binário conhecido como Support Vector Machine. Algumas técnicas de particionamento para FPGA Dinamicamente Reconfigurável, especificamente aplicáveis ao particionamento de FSM, foram desenvolvidas para garantir que um projeto dominado por fluxo de controle seja mapeado numa única FPGA, sem alterar sua funcionalidade. / Systems based on general-purpose processors are characterized by a flexibility to design changes, although with a computational performance below those based on optimized dedicated circuits. The implementation of algorithms in reconfigurable devices, known as Field Programmable Gate Arrays, FPGAs, offers a solution with a trade-off between the processor\'s flexibility and the dedicated circuit\'s performance. With FPGAs it is possible to have their hardware resources configured by software, with a smaller granularity than that of the general-purpose processor and greater flexibility than that of dedicated circuits. Current versions of FPGAs present a reconfiguration time sufficiently small as to make feasible dynamic reconfiguration, i.e., even with the device executing an algorithm, the way its resources are displayed can be modified, offering the possibility of temporal partitioning of an algorithm. New lines of FPGAs are already being manufactured with the option of partial dynamic reconfiguration, i.e. it is possible to reconfigure selected areas of an FPGA anytime, while the remainder area continue in operation. However, in order for this new technology to become widely adopted the development of a proper methodology is necessary, which offers efficient solutions to the new stages of the digital project. In particular, one of the main difficulties presented by this approach is related to the way of partitioning the algorithm, in order to minimize the time necessary to complete its task. This manuscript offers a project methodology for dynamically reconfigurable devices, with an emphasis on the problem of the temporal partitioning of circuits, having as a target application a family of algorithms, used mainly in Bioinformatics, represented by the binary classifier known as Support Machine Vector. Some techniques of functional partitioning for Dynamically Reconfigurable FPGA, specifically applicable to partitioning of FSMs, were developed to guarantee that a control flow dominated design be mapped in only one FPGA, without modifying its functionality.