Dissertação
{en_GB=Parallel Implementation of Data Balancing Algorithms} {} EVALUATED
{pt=Esta tese descreve a análise e implementação em paralelo do algoritmo de balanceamento de informação Input-Output de Rodrigues. Serão apresentados os desafios computacionais deste algoritmo, através da discussão de possíveis pontos de otimização. A implementação é feita utilizando PETSc, uma biblioteca computacional que oferece implementações paralelas das várias operações algébricas, entre matrizes e vetores. É feita igualmente uma descrição detalhada da utilização deste pacote. Este documento apresenta as principais dificuldades no desenvolvimento da solução, com especial atenção à escalabilidade da mesma. A solução encontrada experimenta uma melhor distribuição de carga e permutação de matrizes, no sentido de obter melhor resultados computacionais. Os testes decorreram através da utilização de um cluster de computadores, calculando tempos de execução para diferentes casos de teste. Adicionalmente, para uma melhor abrangência, foram utilizados casos de estudo reais e artificiais. Estes testes são carregados de ficheiros Octave existentes, sendo a informação posteriormente distribuída pelas diferentes máquinas. São concideradas várias permutações, de forma a testar diferentes estruturas de matrix. Neste sentido, diferentes optimizações são ativas ou desativas durante sua execução., en=The goal of this thesis is to describe our work on the development of a parallel implementation for the Input-Output data balancing algorithm of Rodrigues. This application aims to out-perform sequential methods, providing quicker solutions. An analysis is made to find the must computational challenge operations of this algorithm, and discusses possible optimization points. To support out implementation we use PETSc, a parallel library which provides highly optimised routines for linear algebra using vectors and matrices. We describe in detail how this tool is used to fulfil our requirements. This document presents the principal problems found during development, addressing the different solutions. Scalability was the main issue in this project. To overcome this problem we experimented with processor load balancing and matrix permutation. The performance was evaluated in a computer cluster, logging and comparing execution times for various test problems. Real-life, as well as artificial problems were used. The input data is provided in Octave files. The application loads this input file, creating and distributing the data across all machines. Various matrix permutations are considered and computational scalability are tested for different matrix structures. To do this we executed our application, activating or deactivating such optimizations at run-time. }
maio 23, 2016, 13:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
José Carlos Alves Pereira Monteiro
Departamento de Engenharia Informática (DEI)
Professor Associado
