Given a very large dataset of moderate-to-high dimensionality, how to mine useful patterns from it? In such cases, dimensionality reduction is essential to overcome the well-known curse of dimensionality. Although there exist algorithms to reduce the dimensionality of Big Data, unfortunately, they all fail to identify/eliminate non-linear correlations that may occur between the attributes. This MSc work tackles the problem by exploring concepts of the Fractal Theory and massive parallel processing to present Curl-Remover, a novel dimensionality reduction technique for very large datasets. Our contributions are: (a) Curl-Remover eliminates linear and non-linear attribute correlations as well as irrelevant attributes; (b) it is unsupervised and suits for analytical tasks in general not only classification; (c) it presents linear scale-up on both the data size and the number of machines used; (d) it does not require the user to guess the number of attributes to be removed, and; (e) it preserves the attributes semantics by performing feature selection, not feature extraction. We executed experiments on synthetic and real data spanning up to 1.1 billion points, and report that our proposed Curl-Remover outperformed two PCA-based algorithms from the state-of-the-art, being in average up to 8% more accurate. / Dada uma grande base de dados de dimensionalidade moderada a alta, como identificar padrões úteis nos objetos de dados? Nesses casos, a redução de dimensionalidade é essencial para superar um fenômeno conhecido na literatura como a maldição da alta dimensionalidade. Embora existam algoritmos capazes de reduzir a dimensionalidade de conjuntos de dados na escala de Terabytes, infelizmente, todos falham em relação à identificação/eliminação de correlações não lineares entre os atributos. Este trabalho de Mestrado trata o problema explorando conceitos da Teoria de Fractais e processamento paralelo em massa para apresentar Curl-Remover, uma nova técnica de redução de dimensionalidade bem adequada ao pré-processamento de Big Data. Suas principais contribuições são: (a) Curl-Remover elimina correlações lineares e não lineares entre atributos, bem como atributos irrelevantes; (b) não depende de supervisão do usuário e é útil para tarefas analíticas em geral não apenas para a classificação; (c) apresenta escalabilidade linear tanto em relação ao número de objetos de dados quanto ao número de máquinas utilizadas; (d) não requer que o usuário sugira um número de atributos para serem removidos, e; (e) mantêm a semântica dos atributos por ser uma técnica de seleção de atributos, não de extração de atributos. Experimentos foram executados em conjuntos de dados sintéticos e reais contendo até 1,1 bilhões de pontos, e a nova técnica Curl-Remover apresentou desempenho superior comparada a dois algoritmos do estado da arte baseados em PCA, obtendo em média até 8% a mais em acurácia de resultados.

Transformada de distância euclidiana (TDE) é a operação que converte uma imagem binária composta de pontos de objeto e de fundo em outra, chamada mapa de distâncias euclidianas, onde o valor armazenado em cada ponto corresponde à menor distância euclidiana entre este ponto e o fundo da imagem. A TDE é muito utilizada em visão computacional, análise de imagens e robótica, mas é uma transformação muito demorada, principalmente em imagens 3-D. Neste trabalho são utilizados dois tipos de computadores paralelos, (i) multiprocessadores simétricos (SMPs) e (ii) agregados de computadores, para reduzir o tempo de execução da TDE. Dois algoritmos de TDE são paralelizados. O primeiro, um algoritmo de TDE por varredura independente, é paralelizado em um SMP e em um agregado. O segundo, um algoritmo de TDE por propagação ordenada, é paralelizado no agregado. / The Euclidean distance transform is the operation that converts a binary image made of object and background pixels into another image, the Euclidean distance map, where each pixel has a value corresponding to the Euclidean distance from this pixel to the background. The Euclidean distance transform has important uses in computer vision, image analysis and robotics, but it is time-consuming, mainly when processing 3-D images. In this work two types of parallel computers are used to speed up the Euclidean distance transform, (i) symmetric multiprocessors (SMPs) and (ii) clusters of workstations. Two algorithms are parallelized. The first one, an independent line-column Euclidean distance transform algorithm, is parallelized on a SMP, and on a cluster. The second one, an ordered propagation Euclidean distance transform algorithm, is paralellized on a cluster.

Este trabalho apresenta uma arquitetura de hardware, baseada em FPGA (Field-Programmable Gate Array) e com multi-câmeras, para o problema de localização e mapeamento simultâneos - SLAM (Simultaneous Localization And Mapping) aplicada a sistemas robóticos embarcados. A arquitetura é composta por módulos de hardware altamente especializados para a localização do robô e para geração do mapa do ambiente de navegação em tempo real com features extraídas de imagens obtidas diretamente de câmeras CMOS a uma velocidade de 30 frames por segundo. O sistema é totalmente embarcado em FPGA e apresenta desempenho superior em, pelo menos, uma ordem de magnitude em relaçãoo às implementações em software processadas por computadores pessoais de última geração. Esse desempenho deve-se à exploração do paralelismo em hardware junto com o processamento em pipeline e às otimizações realizadas nos algoritmos. As principais contribuições deste trabalho são as arquiteturas para o filtro de Kalman estendido - EKF (Extended Kalman Filter) e para a detecção de features baseada no algoritmo SIFT (Scale Invariant Feature Transform). A complexidade para a implementaçãoo deste trabalho pode ser considerada alta, uma vez que envolve uma grande quantidade de operações aritméticas e trigonométricas em ponto utuante e ponto fixo, um intenso processamento de imagens para extração de features e verificação de sua estabilidade e o desenvolvimento de um sistema de aquisição de imagens para quatro câmeras CMOS em tempo real. Adicionalmente, foram criadas interfaces de comunicação para o software e o hardware embarcados no FPGA e para o controle e leitura dos sensores do robô móvel. Além dos detalhes e resultados da implementação, neste trabalho são apresentados os conceitos básicos de mapeamento e o estado da arte dos algoritmos SLAM com visão monocular e estéreo / This work presents a hardware architecture for the Simultaneous Localization And Mapping (SLAM) problem applied to embedded robots. This architecture, which is based on FPGA and multi-cameras, is composed by highly specialized blocks for robot localization and feature-based map building in real time from images read directly from CMOS cameras at 30 frames per second. The system is completely embedded on an FPGA and its performance is at least one order of magnitude better than a high end PC-based implementation. This result is achieved by investigating the impact of several hardwareorientated optimizations on performance and by exploiting hardware parallelism along with pipeline processing. The main contributions of this work are the architectures for the Extended Kalman Filter (EKF) and for the feature detection system based on the SIFT (Scale Invariant Feature Transform). The complexity to implement this work can be considered high, as it involves a significant number of arithmetic and trigonometric operations in oating and fixed-point format, an intensive image processing for feature detection and stability checking, and the development of an image acquisition system from four CMOS cameras in real time. In addition, communication interfaces were created to integrate software and hardware embedded on FPGA and to control the mobile robot base and to read its sensors. Finally, besides the implementation details and the results, this work also presents basic concepts about mapping and state-of-the-art algorithms for SLAM with monocular and stereo vision.

O aumento crescente no número de processadores das arquiteturas paralelas que estão no topo dos rankings de desempenho, apesar de permitir uma maior capacidade de processamento, também traz consigo um aumento na taxa de falhas diretamente proporcional ao número de processadores. Atualmente, as técnicas de tolerância a falhas com recuperação retroativa são as mais empregadas em aplicações MPI, principalmente a técnica de checkpoint coordenado. No entanto, previsões afirmam que essa última técnica será inadequada para as arquiteturas emergentes. Em contrapartida, as técnicas de log de mensagens possuem características que as tornam mais apropriadas no novo cenário que se estabelece. O presente trabalho consiste em uma proposta de log de mensagens pessimista remoto com checkpoint não-coordenado e a avaliação de desempenho da comunicação MPI sobre Publish/Subscriber no qual se baseia o log de mensagens. O trabalho compreende: um estudo das técnicas de tolerância a falhas mais empregadas em ambientes de alto desempenho e a motivação para a escolha dessa variante de log de mensagens; a proposta de log de mensagens; uma implementação de comunicação Open MPI sobre OpenAMQ e sua respectiva avaliação de desempenho com comunicação tradicional TCP/IP e com o log de mensagens pessimista local da distribuição do Open MPI. Os benchmarks utilizados foram o NetPIPE, o NAS Parallel Benchmarks e a aplicação Virginia Hydrodynamics (VH-1). / The growing number of processors in parallel architectures at the top of performance rankings allows a higher processing capacity. However, it also brings an increase in the fault rate which is directly proportional to the number of processors. Nowadays, coordinated checkpoint is the most widely used rollback technique for system recovery in the occurrence of faults in MPI applications. Nevertheless, projections point that this technique will be inappropriate for the emerging architectures. On the other hand, message logging seems to be more appropriate to this new scenario. This work consists in a proposal of pessimistic message logging (remote based) with non-coordinated checkpoint and the performance evaluation of an MPI communication mechanism that works over Publish/Subscriber channels in which the proposed message logging is based. The work is organized as following: an study of fault tolerant techniques used in HPC and the motivation for choosing this variant of message logging; a message logging proposal; an implementation of Open MPI communication over OpenAMQ; performance evaluation and comparision with the tradicional TCP/IP communication and a pessimistic message logging (sender based) from Open MPI distribution. The benchmark set is composed of NetPIPE, NAS Parallel Benchmarks and Virginia Hydrodynamics (VH-1).

Atualmente, o computador pessoal (PC) moderno poder ser considerado como um cluster heterogênedo de um nodo, o qual processa simultâneamente inúmeras tarefas provenientes das aplicações. O PC pode ser composto por Unidades de Processamento (PUs) assimétricas, como a Unidade Central de Processamento (CPU), composta de múltiplos núcleos, a Unidade de Processamento Gráfico (GPU), composta por inúmeros núcleos e que tem sido um dos principais co-processadores que contribuiram para a computação de alto desempenho em PCs, entre outras. Neste sentido, uma plataforma de execução heterogênea é formada em um PC para efetuar cálculos intensivos em um grande número de dados. Na perspectiva desta tese, a distribuição da carga de trabalho de uma aplicação nas PUs é um fator importante para melhorar o desempenho das aplicações e explorar tal heterogeneidade. Esta questão apresenta desafios uma vez que o custo de execução de uma tarefa de alto nível em uma PU é não-determinístico e pode ser afetado por uma série de parâmetros não conhecidos a priori, como o tamanho do domínio do problema e a precisão da solução, entre outros. Nesse escopo, esta pesquisa de doutorado apresenta um sistema sensível ao contexto e de adaptação em tempo de execução com base em um compromisso entre a redução do tempo de execução das aplicações - devido a um escalonamento dinâmico adequado de tarefas de alto nível - e o custo de computação do próprio escalonamento aplicados em uma plataforma composta de CPU e GPU. Esta abordagem combina um modelo para um primeiro escalonamento baseado em perfis de desempenho adquiridos em préprocessamento com um modelo online, o qual mantém o controle do tempo de execução real de novas tarefas e escalona dinâmicamente e de modo eficaz novas instâncias das tarefas de alto nível em uma plataforma de execução composta de CPU e de GPU. Para isso, é proposto um conjunto de heurísticas para escalonar tarefas em uma CPU e uma GPU e uma estratégia genérica e eficiente de escalonamento que considera várias unidades de processamento. A abordagem proposta é aplicada em um estudo de caso utilizando uma plataforma de execução composta por CPU e GPU para computação de métodos iterativos focados na solução de Sistemas de Equações Lineares que se utilizam de um cálculo de stencil especialmente concebido para explorar as características das GPUs modernas. A solução utiliza o número de incógnitas como o principal parâmetro para a decisão de escalonamento. Ao escalonar tarefas para a CPU e para a GPU, um ganho de 21,77% em desempenho é obtido em comparação com o escalonamento estático de todas as tarefas para a GPU (o qual é utilizado por modelos de programação atuais, como OpenCL e CUDA para Nvidia) com um erro de escalonamento de apenas 0,25% em relação à combinação exaustiva. / A modern personal computer can be now considered as a one-node heterogeneous cluster that simultaneously processes several applications’ tasks. It can be composed by asymmetric Processing Units (PUs), like the multi-core Central Processing Unit (CPU), the many-core Graphics Processing Units (GPUs) - which have become one of the main co-processors that contributed towards high performance computing - and other PUs. This way, a powerful heterogeneous execution platform is built on a desktop for data intensive calculations. In the perspective of this thesis, to improve the performance of applications and explore such heterogeneity, a workload distribution over the PUs plays a key role in such systems. This issue presents challenges since the execution cost of a task at a PU is non-deterministic and can be affected by a number of parameters not known a priori, like the problem size domain and the precision of the solution, among others. Within this scope, this doctoral research introduces a context-aware runtime and performance tuning system based on a compromise between reducing the execution time of the applications - due to appropriate dynamic scheduling of high-level tasks - and the cost of computing such scheduling applied on a platform composed of CPU and GPUs. This approach combines a model for a first scheduling based on an off-line task performance profile benchmark with a runtime model that keeps track of the tasks’ real execution time and efficiently schedules new instances of the high-level tasks dynamically over the CPU/GPU execution platform. For that, it is proposed a set of heuristics to schedule tasks over one CPU and one GPU and a generic and efficient scheduling strategy that considers several processing units. The proposed approach is applied in a case study using a CPU-GPU execution platform for computing iterative solvers for Systems of Linear Equations using a stencil code specially designed to explore the characteristics of modern GPUs. The solution uses the number of unknowns as the main parameter for assignment decision. By scheduling tasks to the CPU and to the GPU, it is achieved a performance gain of 21.77% in comparison to the static assignment of all tasks to the GPU (which is done by current programming models, such as OpenCL and CUDA for Nvidia) with a scheduling error of only 0.25% compared to exhaustive search.

O uso de técnicas de cópia-zero e desvio do sistema operacional permitem a diminuição da latência de comunicação e o aumento da largura de banda. Menores latências e maiores larguras de banda contribuem para que o desempenho das aplicações paralelas seja mais alto, bem como torna-as mais escaláveis. Protocolos de comunicação que utilizam-se destas técnicas são conhecidos como protocolos de comunicação em nível de usuário. Baseado nas experiências de outros grupos de pesquisa na implementação de bibliotecas de comunicação e bibliotecas de programação paralelas sobre VIA e na experiência do GPPD na implementação da biblioteca DECK, este texto apresenta a implementação das primitivas DECK sobre o padrão VIA, o qual é classificado como sendo um protocolo de nível de usuário. O objetivo desta dissertação é implementar o DECK sobre VIA evitando qualquer cópia intermediária na comunicação de uma mensagem, atingindo assim cópia-zero. Dentre as bibliotecas de comunicação sobre VIA, DECK/VIA foi a única biblioteca que teve o compromisso ser totalmente livre de cópias intermediárias, embora houvesse que forçar um sincronismo na comunicação para manter este compromisso. Para a implementação do DECK/VIA, utilizou-se a implementação VI-GM de VIA para redes Myrinet. A biblioteca DECK/VIA demonstrou uma latência de 86.85 μs e uma largura de banda máxima de 205 Mbytes/s, 82% da banda nominal da rede Myrinet. Para validar a biblioteca foi executada a aplicação FT do pacote NPB. Apresenta-se comparações destes resultados frente aos resultados obtidos pela execução da mesma aplicação no DECK/GM, para redesMyrinet e DECK/TCP, para redes Ethernet. Constatou-se que mesmo com uma camada a mais de software e realizando todas as comunicações em três vias em virtude do handshake, DECK/VIA conseguiu valores de speedup bastante próximos de DECK/GM e de DECK/TCP para Gigabit Ethernet, superando os valores de DECK/TCP para Fast Ethernet. Conclui-se que o ideal na implementação de bibliotecas de programação paralela é encontrar uma solução balanceada entre a busca pelo desempenho e a manutenção da semântica original da biblioteca. O trabalho contribuiu com um survey de diversas soluções encontradas por outros grupos no desenvolvimento de bibliotecas de comunicação, que pode servir de guia para outros pesquisadores no desempenho da mesma tarefa. Também contribui com a introdução de um algoritmo para prevenção de deadlocks causados por comunicações síncronas. / Techniques like zero-copy and operating system bypass can decrease communication latency and increase bandwidth. Smaller latencies and greater bandwidths contribute for better performance in parallel applications and became them more scalables as well. Communication protocols using these techiniques are known as user-level communication protocols. Based on experiences from another research groups implementing communication libraries and parallel programming libraries over VIA and experience from GPPD implementing DECK, the text presents the implementation of DECK primitives over VIA standard, which is classified as an user-level protocol. The goal of this master’s thesis is implement DECK over VIA avoiding any intermediate copy between the data source and destination, reaching zero-copy. DECK/VIA is the unique library among all libriaries over VIA here studied totally free of intermediate copies, although a synchronous behavior was forced to keep this compromise. VI-GM, an implementation of VIA for Myrinet networks was used to implement DECK/VIA library. The implementation of DECK/VIA has shown a one-way latency of 86.85 μs and a maximum bandwidth of 205 Mbytes/s, 82% of nominal bandwidth of Myrinet network. To validate the library, the FT application from NPB was executed. Their results were compared with the results obtained with DECK/GM, for Myrinet networks and DECK/TCP, for Ethernet networks. Even with one additional software layer and doing all communication using a handshake, DECK/VIA reaches speedup values very closer of DECK/GMand DECK/TCP on Gigabit Ethernet and was better than DECK/TCP on Fast Ethernet. When implementing parallel programming libraries, we concluded the ideal solution is that meets the good balance between the quest for performance and the keeping of original library’s semantics. This work contibutes with a survey of communication libraries development, their problems and their solutions, which can guide others researchers performing the same task. Also it contributes with an algorithm to prevent deadlocks caused by synchonism.

Previsões meteorológicas para longos períodos de tempo estão se tornando cada vez mais importantes. A preocupação mundial com as consequências da mudança do clima tem estimulado pesquisas para determinar o seu comportamento nas próximas décadas. Ao mesmo tempo, os passos necessários para definir uma melhor modelagem e simulação do clima e/ou tempo estão longe da precisão desejada. Aumentar o refinamento da superfície terrestre e, consequentemente, aumentar o número de pontos discretos (utilizados para a representação da atmosfera) na modelagem climática e precisão das soluções computadas é uma meta que está em conflito com o desempenho das aplicações numéricas. Aplicações que envolvem a interação de longos períodos de tempo e incluem um grande número de operações possuem um tempo de execução inviável para as arquiteturas de computadores tradicionais. Para superar esta situação, um modelo climatológico pode adotar diferentes níveis de refinamento da superfície terrestre, utilizando mais pontos discretos somente em regiões onde uma maior precisão é requerida. Este é o caso de Ocean-Land-AtmosphereModel, que permite o refinamento estático de uma determinada região no início da execução do código. No entanto, um refinamento dinâmico possibilitaria uma melhor compreensão das condições climáticas específicas de qualquer região da superfície terrestre que se tivesse interesse, sem a necessidade de reiniciar a execução da aplicação. Com o surgimento das arquiteturas multi-core e a adoção de GPUs para a computação de propósito geral, existem diferentes níveis de paralelismo. Hoje há paralelismo interno ao processador, entre processadores e entre computadores. Com o objetivo de extrair ao máximo a performance dos computadores atuais, é necessário utilizar todos os níveis de paralelismo disponíveis durante o desenvolvimento de aplicações concorrentes. No entanto, nenhuma interface de programação paralela explora simultaneamente bem os diferentes níveis de paralelismo existentes. Baseado neste contexto, esta tese investiga como explorar diferentes níveis de paralelismo em modelos climatológicos usando interfaces clássicas de programação paralela de forma combinada e como é possível prover refinamento de malhas em tempo de execução para estes modelos. Os resultados obtidos a partir de implementações realizadas mostraram que é possível reduzir o tempo de execução de uma simulação atmosférica utilizando diferentes níveis de paralelismo, através do uso combinado de interfaces de programação paralela. Além disso, foi possível prover maior desempenho na execução de aplicações climatológicas que utilizam refinamento de malhas em tempo de execução. Com isso, uma malha de maior resolução para a representação da atmosfera terrestre pode ser adotada e, consequentemente, as previsões numéricas serão mais precisas. / Weather forecasts for long periods of time has emerged as increasingly important. The global concern with the consequences of climate changes has stimulated researches to determine the climate in coming decades. At the same time the steps needed to better defining the modeling and the simulation of climate/weather is far of the desired accuracy. Upscaling the land surface and consequently to increase the number of points used in climate modeling and the precision of the computed solutions is a goal that conflicts with the performance of numerical applications. Applications that include the interaction of long periods of time and involve a large number of operations become the expectation for results infeasible in traditional computers. To overcome this situation, a climatic model can take different levels of refinement of the Earth’s surface, using more discretized elements only in regions where more precision are required. This is the case of Ocean-Land- Atmosphere Model, which allows the static refinement of a particular region of the Earth in the early execution of the code. However, a dynamic mesh refinement could allow to better understand specific climatic conditions that appear at execution time of any region of the Earth’s surface, without restarting execution. With the introduction of multi-core processors and GPU boards, computers architectures have many parallel layers. Today, there are parallelism inside the processor, among processors and among computers. In order to use the best performance of the computers it is necessary to consider all parallel levels to distribute a concurrent application. However, nothing parallel programming interface abstracts all these different parallel levels. Based in this context, this thesis investigates how to explore different levels of parallelism in climatological models using mixed interfaces of parallel programming and how these models can provide mesh refinement at execution time. The performance results show that is possible to reduce the execution time of atmospheric simulations using different levels of parallelism, through the combined use of parallel programming interfaces. Higher performance for the execution of atmospheric applications that use online mesh refinement was also provided. Therefore, more mesh resolution to describe the Earth’s atmosphere can be adopted, and consequently the numerical forecasts are more accurate.

A presente tese trata o problema do reescalonamento de processos durante a execução da aplicação, oferecendo rebalanceamento dinâmico de carga entre os recursos disponíveis. Uma vez que os cenários da computação distribuída envolvem cada vez mais recursos e aplicações dinâmicas, a carga é uma medida variável e um mapeamento inicial processos-recursos pode não permanecer eficiente no decorrer do tempo. O estado dos recursos e da rede podem variar no decorrer da aplicação, bem como a quantidade de processamento e a interação entre os processos. Consequentemente, o remapeamento de processos para novos recursos é pertinente para aumentar o uso dos recursos e minimizar o tempo de execução da aplicação. Nesse contexto, essa tese de doutorado apresenta um modelo de reescalonamento chamado MigBSP, o qual controla a migração de processos de aplicações BSP (Bulk Synchronous Parallel). O modelo de aplicação BSP foi adotado visto que torna a programação paralela mais fácil e é muito comum nos cenários de desenvolvimento de aplicações científicas. Considerando o escopo de aplicações BSP, as novas idéias de MigBSP são em número de três: (i) combinação de três métricas - Memória, Computação e Comunicação - em uma outra escala com o intuito de medir o Potencial de Migração de cada processo BSP; (ii) emprego de um Padrão de Computação e outro Padrão de Comunicação para controlar a regularidade dos processos e; (iii) adatação eficiente na freqüência do lançamento do reescalonamento de processos. A infra-estrutura de máquina paralela considera sistemas distribuídos heterogêneos (diferentes velocidades de processador e de rede). Os processos podem passar mensagens entre si e a máquina paralela pode agregar redes locais e clusters. O modelo de reescalonamento provê um formalismo matemático para decidir as seguintes questões: (i) Quando lançar o reescalonamento dos processos; (ii) Quais processos são candidatos a migração e; (iii) Para onde os processos selecionados serão migrados. A técnica de simulação foi usada para validar MigBSP. Além do próprio MigBSP, três aplicações científicas foram foram desenvolvidas e executadas usando o simulador Simgrid. Os resultados mostraram que MigBSP oferece oportunidade de ganhar desempenho sem alterações no código fonte da aplicação. MigBSP torna possível ganhos de desempenho na casa de 20%, bem como produz uma baixa sobrecarga quando migrações são inviáveis. Sua sobrecarga média ficou abaixo de 8% do tempo de execução normal da aplicação. Essa taxa foi obtida desabilitando quaisquer migrações indicadas por MigBSP. Os resultados mostraram que a união das métricas consideradas é uma boa solução para o controle de migração de processos. Além disso, eles revelaram que as adaptações desenvolvidas na freqüência do reescalonamento são cruciais para tornar a execução de MigBSP viável, principalmente em ambientes desbalanceados. / This thesis treats the processes rescheduling problem during application runtime, offering dynamic load rebalancing among the available resources. Since most distributed computing scenarios involve more and more resources and dynamic applications, the load is a variable measure and an initial processes-processors deployment may not remain efficient with time. The resources and the network states can vary during application execution, as well as the amount of processing and the interactions among the processes. Consequently, the remapping of processes to new processors is pertinent to improve resource utilization and to minimize application execution time. In this context, this thesis presents a rescheduling model called MigBSP, which controls the processes migration of BSP (Bulk Synchronous Parallel) applications. BSP application model was adopted because it turns parallel programming easier and is very common in scientific applications development scenarios. Considering the scope of BSP applications, the novel ideas of MigBSP are threefold: (i) combination of three metrics - Memory, Computation and Communication - in a scalar one in order to measure the potential of migration of each BSP process; (ii) employment of both Computation and Communication Patterns to control processes’ regularity and; (iii) efficient adaptation regarding the periodicity to launch processes rescheduling. In our infrastructure, we are considering heterogeneous (different processor and network speed) distributed systems. The processes can pass messages among themselves and the parallel machine can gather local area networks and clusters. The proposed model provides a mathematical formalism to decide the following questions about load (BSP processes) balancing: (i) When to launch the processes rescheduling; (ii) Which processes will be candidates for migration and; (iii) Where to put the processes that will be migrated actually. We used the simulation technique to validate MigBSP. Besides MigBSP, three scientific application were developed and executed using Simgrid simulator. In general, the results showed that MigBSP offers an opportunity to get performance in an effortless manner to the programmer since its does not need modification on application code. MigBSP makes possible gains of performance up to 20% as well as produces a low overhead when migrations do not take place. Its mean overhead is lower than 8% of the normal application execution time. This rate was obtained disabling any processes migration indicated by MigBSP. The results show that the union of considered metrics is a good solution to control processes migration. Moreover, they revealed that the developed adaptations are crucial to turn MigBSP execution viable, mainly on unbalanced environments.

Dans cette thèse , nous proposons d’étudier des questions sur le parallélism de tâche avec dépendance de données dans le cadre de machines multicoeur avec des accélérateurs. La solution proposée a été développée en utilisant l’interface de programmation haute niveau XKaapi du projet MOAIS de l’INRIA Rhône-Alpes. D’abord nous avons étudié des questions liés à une approche d’exécution totalement asyncrone et l’ordonnancement par vol de travail sur des architectures multi-GPU. Le vol de travail avec localité de données a montré des résultats significatifs, mais il ne prend pas en compte des différents ressources de calcul. Ensuite nous avons conçu une interface et une modèle de coût qui permettent d’écrire des politiques d’ordonnancement sur XKaapi. Finalement on a évalué XKaapi sur un coprocesseur Intel Xeon Phi en mode natif. Notre conclusion est double. D’abord nous avons montré que le modèle de programmation data-flow peut être efficace sur des accélérateurs tels que des GPUs ou des coprocesseurs Intel Xeon Phi. Ensuite, le support à des différents politiques d’ordonnancement est indispensable. Les modèles de coût permettent d’obtenir de performance significatifs sur des calculs très réguliers, tandis que le vol de travail permet de redistribuer la charge en cours d’exécution. / Esta tese investiga os desafios no uso de paralelismo de tarefas com dependências de dados em arquiteturas multi-CPU com aceleradores. Para tanto, o XKaapi, desenvolvido no grupo de pesquisa MOAIS (INRIA Rhône-Alpes), é a ferramenta de programação base deste trabalho. Em um primeiro momento, este trabalho propôs extensões ao XKaapi a fim de sobrepor transferência de dados com execução através de operações concorrentes em GPU, em conjunto com escalonamento por roubo de tarefas em multi-GPU. Os resultados experimentais sugerem que o suporte a asincronismo é importante à escalabilidade e desempenho em multi-GPU. Apesar da localidade de dados, o roubo de tarefas não pondera a capacidade de processamento das unidades de processamento disponíveis. Nós estudamos estratégias de escalonamento com predição de desempenho em tempo de execução através de modelos de custo de execução. Desenvolveu-se um framework sobre o XKaapi de escalonamento que proporciona a implementação de diferentes algoritmos de escalonamento. Esta tese também avaliou o XKaapi em coprocessodores Intel Xeon Phi para execução nativa. A conclusão desta tese é dupla. Primeiramente, nós concluímos que um modelo de programação com dependências de dados pode ser eficiente em aceleradores, tais como GPUs e coprocessadores Intel Xeon Phi. Não obstante, uma ferramenta de programação com suporte a diferentes estratégias de escalonamento é essencial. Modelos de custo podem ser usados no contexto de algoritmos paralelos regulares, enquanto que o roubo de tarefas poder reagir a desbalanceamentos em tempo de execução. / In this thesis, we propose to study the issues of task parallelism with data dependencies on multicore architectures with accelerators. We target those architectures with the XKaapi runtime system developed by the MOAIS team (INRIA Rhône-Alpes). We first studied the issues on multi-GPU architectures for asynchronous execution and scheduling. Work stealing with heuristics showed significant performance results, but did not consider the computing power of different resources. Next, we designed a scheduling framework and a performance model to support scheduling strategies over XKaapi runtime. Finally, we performed experimental evaluations over the Intel Xeon Phi coprocessor in native execution. Our conclusion is twofold. First we concluded that data-flow task programming can be efficient on accelerators, which may be GPUs or Intel Xeon Phi coprocessors. Second, the runtime support of different scheduling strategies is essential. Cost models provide significant performance results over very regular computations, while work stealing can react to imbalances at runtime.

A programação paralela tem sido freqüentemente adotada para o desenvolvimento de aplicações que demandam alto desempenho computacional. Com o advento das arquiteturas multi-cores e a existência de diversos níveis de paralelismo é importante definir estratégias de programação paralela que tirem proveito desse poder de processamento nessas arquiteturas. Neste contexto, este trabalho busca avaliar o desempenho da utilização das arquiteturas multi-cores, principalmente o oferecido pelas unidades de processamento gráfico (GPUs) e CPUs multi-cores na resolução de um problema térmico inverso. Algoritmos paralelos para a GPU e CPU foram desenvolvidos utilizando respectivamente as ferramentas de programação em arquiteturas de memória compartilhada NVIDIA CUDA (Compute Unified Device Architecture) e a API POSIX Threads. O algoritmo do método do gradiente conjugado pré-condicionado para resolução de sistemas lineares esparsos foi implementado totalmente no espaço da memória global da GPU em CUDA. O algoritmo desenvolvido foi avaliado em dois modelos de GPU, os quais se mostraram mais eficientes, apresentando um speedup de quatro vezes que a versão serial do algoritmo. A aplicação paralela em POSIX Threads foi avaliada em diferentes CPUs multi-cores com distintas microarquiteturas. Buscando um maior desempenho do código paralelizado foram utilizados flags de otimização as quais se mostraram muito eficientes na aplicação desenvolvida. Desta forma o código paralelizado com o auxílio das flags de otimização chegou a apresentar tempos de processamento cerca de doze vezes mais rápido que a versão serial no mesmo processador sem nenhum tipo de otimização. Assim tanto a abordagem utilizando a GPU como um co-processador genérico a CPU como a aplicação paralela empregando as CPUs multi-cores mostraram-se ferramentas eficientes para a resolução do problema térmico inverso. / Parallel programming has been frequently adopted for the development of applications that demand high-performance computing. With the advent of multi-cores architectures and the existence of several levels of parallelism are important to define programming strategies that take advantage of parallel processing power in these architectures. In this context, this study aims to evaluate the performance of architectures using multi-cores, mainly those offered by the graphics processing units (GPUs) and CPU multi-cores in the resolution of an inverse thermal problem. Parallel algorithms for the GPU and CPU were developed respectively, using the programming tools in shared memory architectures, NVIDIA CUDA (Compute Unified Device Architecture) and the POSIX Threads API. The algorithm of the preconditioned conjugate gradient method for solving sparse linear systems entirely within the global memory of the GPU was implemented by CUDA. It evaluated the two models of GPU, which proved more efficient by having a speedup was four times faster than the serial version of the algorithm. The parallel application in POSIX Threads was evaluated in different multi-core CPU with different microarchitectures. Optimization flags were used to achieve a higher performance of the parallelized code. As those were efficient in the developed application, the parallelized code presented processing times about twelve times faster than the serial version on the same processor without any optimization. Thus both the approach using GPU as a coprocessor to the CPU as a generic parallel application using the multi-core CPU proved to be more efficient tools for solving the inverse thermal problem.