REZENDE, Cenez Araújo de. Um arcabouço baseado em componentes para computação paralela de larga escala sobre grafos. 2017. 170 f. Tese (Doutorado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2017. / Submitted by Jonatas Martins (jonatasmartins@lia.ufc.br) on 2017-09-26T11:26:26Z No. of bitstreams: 1 2017_tese_carezende.pdf: 3113868 bytes, checksum: 730860f5d4afc3f76981695e2d925c7c (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-09-26T12:43:31Z (GMT) No. of bitstreams: 1 2017_tese_carezende.pdf: 3113868 bytes, checksum: 730860f5d4afc3f76981695e2d925c7c (MD5) / Made available in DSpace on 2017-09-26T12:43:31Z (GMT). No. of bitstreams: 1 2017_tese_carezende.pdf: 3113868 bytes, checksum: 730860f5d4afc3f76981695e2d925c7c (MD5) Previous issue date: 2017 / Faced with the increasing growth of data production to be processed by computer systems, a result of the current technological context and emerging applications of both industrial and scientific interest, researchers and companies have been looking for solutions to leverage large-scale data processing and analysis capacity. In addition to the large volume, many of these data must be processed by high-complexity algorithms, highlighting the inherent difficulties of problems in large graphs (BigGraph), often used to model information from large databases. Although with limitations in graph processing, the MapReduce model has motivated the construction of several high-performance frameworks, in order to meet the demand for efficient large-scale general purpose systems. Such a context has led to the proposal of more specialized solutions, such as Pregel and GAS (Gather, Apply, Scatter), as well as MapReduce extensions to deal with graph processing. However, frameworks that implement these models still have limitations, such as multi-platform constraints and general propose programming models for graphs. In this work, we show how component-oriented parallel programming can deal with MapReduce and conventional Pregel constraints. For that, we have employed HPC shelf, a component-based cloud computing platform for HPC services. On top of this platform, we introduce Gust, a flexible, extensible and adaptable BigGraph framework based on MapReduce. Besides the gains in software architecture, due to the use of a component-oriented approach, we have obtained competitive performance results compared to the state-of-the-art through an experimental study, using estatistical methods to increase confidence. / Diante do progressivo crescimento da produção de dados a serem processados por sistemas de computação, produto do contexto tecnológico vigente e de aplicações emergentes tanto de interesse industrial quanto científico, têm-se buscado soluções para alavancar a capacidade de processamento e análise de dados em larga escala. Além de volumosos, estão propícios a serem processados por algoritmos de alta complexidade, destacando as dificuldades inerentes a problemas em grafos grandes (BigGraph), frequentemente usados para modelar informações de grandes bases de dados. O modelo MapReduce, embora com limitações nesse domínio, abriu o caminho para a construção de vários arcabouços de alto desempenho, buscando atender à demanda por eficiente processamento de larga escala com propósito geral. Isso motivou o surgimento de soluções mais especializadas, voltadas a grafos, tais como os modelos Pregel e GAS (Gather, Apply, Scatter), bem como extensões do próprio MapReduce. Contudo, arcabouços que implementam esses modelos possuem ainda limitações, como restrições a multiplataformas e modelos mais gerais de programação. Neste trabalho, mostramos como a programação paralela orientada a componentes pode lidar com as limitações MapReduce e de modelos convencionais Pregel. Isso é feito usando a HPC Shelf, uma plataforma de computação em nuvem baseada em componentes para serviços HPC. Visando essa plataforma, apresentamos o Gust, um arcabouço BigGraph flexível, extensível e adaptável baseado em MapReduce. Através de estudo experimental, os resultados têm sido competitivos com o estado da arte, tanto em desempenho com na engenharia de software paralelo, com base em interesses funcionais e não funcionais.

Submitted by Maria Cristina (library@lncc.br) on 2017-05-02T19:25:42Z No. of bitstreams: 1 dissertacao Daniel.pdf: 13436496 bytes, checksum: e52ea76aa8685ff28f62aea6a22f98cf (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2017-05-02T19:25:53Z (GMT) No. of bitstreams: 1 dissertacao Daniel.pdf: 13436496 bytes, checksum: e52ea76aa8685ff28f62aea6a22f98cf (MD5) / Made available in DSpace on 2017-05-02T19:26:02Z (GMT). No. of bitstreams: 1 dissertacao Daniel.pdf: 13436496 bytes, checksum: e52ea76aa8685ff28f62aea6a22f98cf (MD5) Previous issue date: 2017-02-21 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Many emerging challenges currently arising in science relate to understanding the dynamics and structure of complex systems consisting of interacting components. People on online social networks, power grids, air transportation networks, human brain connections, and agents in the financial market are some examples of network systems present in many domains. These systems, given their scale and non-trivial connectivity patterns, are called complex networks. In this sense, the dimension of these networks turns imperative the adoption of computing systems in support to their analysis. In this case, graphs are the usual tool for the representation of complex networks. Moreover, as the scientific investigation for these graphs is of great significance for many domains, the researcher and developer communities have proposed many computing platforms for their processing. However, the multitude of graph processing platforms brings up questions about the implications of their adoption, given the analysis, network and computing environment characteristics of the analysts. Therefore, in this dissertation, we propose a multi-perspective model for the performance evaluation of graph processing platforms which differs from related works in simultaneously approaching the topic from four perspectives: algorithms, computing environment, networks, and platforms. Additionally, we carry out a performance evaluation study that follows the directives indicated by the proposed model for a representative set of algorithms, platforms, and networks, demonstrating the proposed model applicability as exhibits the relationship between algorithms, networks and platforms efficiency. / Alguns dos desafios mais relevantes que surgem no cenário científico atual envolvem a compreensão da dinâmica e estrutura de sistemas complexos constituídos por componentes em interação. Pessoas em redes sociais online, sistemas de distribuição de energia, malhas aéreas, conexões no cérebro humano ou mesmo agentes no mercado financeiro são apenas alguns exemplos de tais sistemas em rede oriundos de diversas áreas. Esses sistemas, por causa de sua escala e da não trivialidade de seus padrões de conectividade, são chamados de redes complexas. Nesse contexto, a dimensão dessas redes torna imprescindível a utilização de sistemas computacionais em apoio às suas análises, sendo grafos a ferramenta típica de representação de redes complexas para sua modelagem computacional e estudo. Mais ainda, como a análise de grafos em diversos domínios é de grande relevância, muitas plataformas computacionais para o seu processamento têm sido propostas recentemente; o que provoca questionamentos pertinentes de quais as implicações da escolha de uma delas, dadas as características de análise, rede e ambiente computacional dos interessados. Portanto, esta dissertação propõe um modelo multiperspectiva de avaliação de desempenho de plataformas de processamento de grafos, o qual se distingue da literatura ao abordar o problema considerando simultaneamente quatro perspectivas: algoritmos, arquitetura computacional, plataformas e redes. Além disso, um estudo de avaliação de desempenho de um conjunto diverso e representativo de algoritmos, plataformas computacionais e redes é realizado utilizando as diretivas indicadas pelo modelo, demonstrando sua aplicabilidade ao expor o relacionamento entre as características de redes complexas e algoritmos com a eficiência computacional das plataformas.

Data analysis techniques can be useful in decision-making processes, when patterns of interest can indicate trends in specific domains. Such trends might support evaluation, definition of alternatives, or prediction of events. Currently, datasets have increased in size and complexity, posing challenges to modern hardware resources. In the case of large datasets that can be represented as graphs, issues of visualization and scalable processing are of current concern. Distributed frameworks are commonly used to deal with this data, but the deployment and the management of computational clusters can be complex, demanding technical and financial resources that can be prohibitive in several scenarios. Therefore, it is desirable to design efficient techniques for processing and visualization of large scale graphs that optimize hardware resources in a single computational node. In this course of action, we developed a visualization technique named StructMatrix to find interesting insights on real-life graphs. In addition, we proposed a graph processing framework M-Flash that used a novel, bimodal block processing strategy (BBP) to boost computation speed by minimizing I/O cost. Our results show that our visualization technique allows an efficient and interactive exploration of big graphs and our framework MFlash significantly outperformed all state-of-the-art approaches based on secondary memory. Our contributions have been validated in peer-review events demonstrating the potential of our finding in fostering the analytical possibilities related to large-graph data domains. / Técnicas de análise de dados podem ser úteis em processos de tomada de decisão, quando padrões de interesse indicam tendências em domínios específicos. Tais tendências podem auxiliar a avaliação, a definição de alternativas ou a predição de eventos. Atualmente, os conjuntos de dados têm aumentado em tamanho e complexidade, impondo desafios para recursos modernos de hardware. No caso de grandes conjuntos de dados que podem ser representados como grafos, aspectos de visualização e processamento escalável têm despertado interesse. Arcabouços distribuídos são comumente usados para lidar com esses dados, mas a implantação e o gerenciamento de clusters computacionais podem ser complexos, exigindo recursos técnicos e financeiros que podem ser proibitivos em vários cenários. Portanto é desejável conceber técnicas eficazes para o processamento e visualização de grafos em larga escala que otimizam recursos de hardware em um único nó computacional. Desse modo, este trabalho apresenta uma técnica de visualização chamada StructMatrix para identificar relacionamentos estruturais em grafos reais. Adicionalmente, foi proposta uma estratégia de processamento bimodal em blocos, denominada Bimodal Block Processing (BBP), que minimiza o custo de I/O para melhorar o desempenho do processamento. Essa estratégia foi incorporada a um arcabouço de processamento de grafos denominado M-Flash e desenvolvido durante a realização deste trabalho.Foram conduzidos experimentos a fim de avaliar as técnicas propostas. Os resultados mostraram que a técnica de visualização StructMatrix permitiu uma exploração eficiente e interativa de grandes grafos. Além disso, a avaliação do arcabouço M-Flash apresentou ganhos significativos sobre todas as abordagens baseadas em memória secundária do estado da arte. Ambas as contribuições foram validadas em eventos de revisão por pares, demonstrando o potencial analítico deste trabalho em domínios associados a grafos em larga escala.

Data analysis techniques can be useful in decision-making processes, when patterns of interest can indicate trends in specific domains. Such trends might support evaluation, definition of alternatives, or prediction of events. Currently, datasets have increased in size and complexity, posing challenges to modern hardware resources. In the case of large datasets that can be represented as graphs, issues of visualization and scalable processing are of current concern. Distributed frameworks are commonly used to deal with this data, but the deployment and the management of computational clusters can be complex, demanding technical and financial resources that can be prohibitive in several scenarios. Therefore, it is desirable to design efficient techniques for processing and visualization of large scale graphs that optimize hardware resources in a single computational node. In this course of action, we developed a visualization technique named StructMatrix to find interesting insights on real-life graphs. In addition, we proposed a graph processing framework M-Flash that used a novel, bimodal block processing strategy (BBP) to boost computation speed by minimizing I/O cost. Our results show that our visualization technique allows an efficient and interactive exploration of big graphs and our framework MFlash significantly outperformed all state-of-the-art approaches based on secondary memory. Our contributions have been validated in peer-review events demonstrating the potential of our finding in fostering the analytical possibilities related to large-graph data domains. / Técnicas de análise de dados podem ser úteis em processos de tomada de decisão, quando padrões de interesse indicam tendências em domínios específicos. Tais tendências podem auxiliar a avaliação, a definição de alternativas ou a predição de eventos. Atualmente, os conjuntos de dados têm aumentado em tamanho e complexidade, impondo desafios para recursos modernos de hardware. No caso de grandes conjuntos de dados que podem ser representados como grafos, aspectos de visualização e processamento escalável têm despertado interesse. Arcabouços distribuídos são comumente usados para lidar com esses dados, mas a implantação e o gerenciamento de clusters computacionais podem ser complexos, exigindo recursos técnicos e financeiros que podem ser proibitivos em vários cenários. Portanto é desejável conceber técnicas eficazes para o processamento e visualização de grafos em larga escala que otimizam recursos de hardware em um único nó computacional. Desse modo, este trabalho apresenta uma técnica de visualização chamada StructMatrix para identificar relacionamentos estruturais em grafos reais. Adicionalmente, foi proposta uma estratégia de processamento bimodal em blocos, denominada Bimodal Block Processing (BBP), que minimiza o custo de I/O para melhorar o desempenho do processamento. Essa estratégia foi incorporada a um arcabouço de processamento de grafos denominado M-Flash e desenvolvido durante a realização deste trabalho.Foram conduzidos experimentos a fim de avaliar as técnicas propostas. Os resultados mostraram que a técnica de visualização StructMatrix permitiu uma exploração eficiente e interativa de grandes grafos. Além disso, a avaliação do arcabouço M-Flash apresentou ganhos significativos sobre todas as abordagens baseadas em memória secundária do estado da arte. Ambas as contribuições foram validadas em eventos de revisão por pares, demonstrando o potencial analítico deste trabalho em domínios associados a grafos em larga escala.