Existem muitos fatores capazes de influenciar o desempenho de um programa paralelo MPI (Message Passing Interface). Dentre esses fatores, podemos citar a quantidade de dados processados, o número de nós envolvidos na solução do problema, as características da rede de interconexão, o tipo de switch utilizado, entre outros. Por isso, realizar predições de desempenho sobre programas paralelos que utilizam passagem de mensagem não é uma tarefa trivial. Com o intuito de modelar e predizer o comportamento dos programas citados anteriormente, nosso trabalho foi desenvolvido baseado em uma metodologia de análise e predição de desempenho de programas paralelos MPI. Inicialmente, propomos um modelo gráfico, denominado DP*Graph+, para representar o código das aplicações. Em seguida, desenvolvemos modelos analíticos, utilizando técnicas de ajuste de curvas, para representar o comportamento das estruturas de repetição compostas por primitivas de comunicação e/ou computação local. Além disso, elaboramos modelos para predizer o comportamento de aplicações do tipo mestre/escravo. Durante o desenvolvimento das atividades de análise e predição de desempenho, implementamos algumas funções para automatizar tarefas e facilitar nosso trabalho. Por último, modelamos e estimamos o desempenho de duas versões diferentes de um programa de multiplicação de matrizes, a fim de validar os modelos propostos. Os resultados das predições realizadas sobre os programas de multiplicação de matrizes foram satisfatórios. Na maioria dos casos preditos, os erros ficaram abaixo de 6 %, confirmando a validade e a precisão dos modelos elaborados. / There are many factors able to influence the performance of a MPI (Message Passing Interface) parallel program. Within these factors, we may cite: amount of data, number of nodes, characteristics of the network and type of switch, among others. Then, performance prediction isn’t a easy task. The work was developed based on a methodology of analysis and performance prediction of MPI parallel programs. First of all, we proposed a graphical model, named DP*Graph+, to represent the code of applications. Next, we developed analytical models applying curve fitting techniques to represent the behavior of repetition structure compounds by comunication primitives and/or local computations. Besides, we elaborated models to predict aplications of type master/slave. For development of performance prediction activities, some functions was developed to automate tasks and make our work easy. Finally, we modeled and predicted the performance of two different programs of matrix multiplication to prove the accuracy of models. The results of predictions on the programs were good. In the majority of predicted cases, the errors were down 6 %. With these results, we proved the accuracy of developed models.

O desenvolvimento de programas paralelos e distribuídos encontra na programação baseada em passagem de mensagens uma abordagem eficaz para explorar adequadamente as características das máquinas de memória distribuída. Com o uso de clusters e de bibliotecas de suporte às trocas de mensagens, como o padrão MPI (Message Passing Interface), aplicações eficientes e economicamente viáveis podem ser construídas. Em tais sistemas, o tempo despendido nas comunicações constitui um importante fator de desempenho a ser considerado e requer a utilização de procedimentos e cuidados para a sua correta caracterização. Neste trabalho, modelos analíticos de primitivas de comunicação bloqueante MPI são desenvolvidos segundo uma metodologia de análise e predição apropriada. São tratadas algumas das principais operações ponto-a-ponto e coletivas e, utilizando técnicas de ajuste de curvas e tempos experimentais, o comportamento das primitivas de comunicação é representado em equações, possibilitando ainda a realização de análises e predições de desempenho em função do tamanho das mensagens e do número de processos envolvidos. Através de testes em um cluster de estações de trabalho, a precisão dos modelos elaborados é comprovada. Sendo a maioria dos erros percentuais inferiores a 8%, os resultados obtidos confirmam a validade do processo de modelagem. Além disso, o trabalho apresenta um conjunto de funções construídas com o objetivo de oferecer suporte a atividades de análise e predição, procurando facilitar e automatizar sua execução. / The development of parallel and distributed programs finds at message-passing programming a powerful approach to explore properly the distributed memory machines issues. Using clusters and message-passing libraries, as MPI standard (Message Passing Interface), efficient and cost effective applications can be constructed. In these systems, the time spent with communications means a important performance factor to be considered and its correct characterization requires procedures and cautions. In this work, analytic models for MPI blocking communication primitives are developed according one appropriate methodology for analysis and prediction. Some of the main peer-to-peer and collective operations are treated, and through curve fitting techniques and experimental times the behavior of the communication primitives is represented in equations, allowing also the accomplishment of performance analysis and prediction in function of the message length and the number of processes. Tests realized in a cluster of workstations prove the accuracy of the elaborated models. With most of errors within 8%, the obtained results show the validity of the modeling process. Also, the work presents a set of functions constructed with the purpose of support analysis and prediction activities, in order to facilitate and automate them.

O desenvolvimento de programas paralelos e distribuídos encontra na programação baseada em passagem de mensagens uma abordagem eficaz para explorar adequadamente as características das máquinas de memória distribuída. Com o uso de clusters e de bibliotecas de suporte às trocas de mensagens, como o padrão MPI (Message Passing Interface), aplicações eficientes e economicamente viáveis podem ser construídas. Em tais sistemas, o tempo despendido nas comunicações constitui um importante fator de desempenho a ser considerado e requer a utilização de procedimentos e cuidados para a sua correta caracterização. Neste trabalho, modelos analíticos de primitivas de comunicação bloqueante MPI são desenvolvidos segundo uma metodologia de análise e predição apropriada. São tratadas algumas das principais operações ponto-a-ponto e coletivas e, utilizando técnicas de ajuste de curvas e tempos experimentais, o comportamento das primitivas de comunicação é representado em equações, possibilitando ainda a realização de análises e predições de desempenho em função do tamanho das mensagens e do número de processos envolvidos. Através de testes em um cluster de estações de trabalho, a precisão dos modelos elaborados é comprovada. Sendo a maioria dos erros percentuais inferiores a 8%, os resultados obtidos confirmam a validade do processo de modelagem. Além disso, o trabalho apresenta um conjunto de funções construídas com o objetivo de oferecer suporte a atividades de análise e predição, procurando facilitar e automatizar sua execução. / The development of parallel and distributed programs finds at message-passing programming a powerful approach to explore properly the distributed memory machines issues. Using clusters and message-passing libraries, as MPI standard (Message Passing Interface), efficient and cost effective applications can be constructed. In these systems, the time spent with communications means a important performance factor to be considered and its correct characterization requires procedures and cautions. In this work, analytic models for MPI blocking communication primitives are developed according one appropriate methodology for analysis and prediction. Some of the main peer-to-peer and collective operations are treated, and through curve fitting techniques and experimental times the behavior of the communication primitives is represented in equations, allowing also the accomplishment of performance analysis and prediction in function of the message length and the number of processes. Tests realized in a cluster of workstations prove the accuracy of the elaborated models. With most of errors within 8%, the obtained results show the validity of the modeling process. Also, the work presents a set of functions constructed with the purpose of support analysis and prediction activities, in order to facilitate and automate them.

Existem muitos fatores capazes de influenciar o desempenho de um programa paralelo MPI (Message Passing Interface). Dentre esses fatores, podemos citar a quantidade de dados processados, o número de nós envolvidos na solução do problema, as características da rede de interconexão, o tipo de switch utilizado, entre outros. Por isso, realizar predições de desempenho sobre programas paralelos que utilizam passagem de mensagem não é uma tarefa trivial. Com o intuito de modelar e predizer o comportamento dos programas citados anteriormente, nosso trabalho foi desenvolvido baseado em uma metodologia de análise e predição de desempenho de programas paralelos MPI. Inicialmente, propomos um modelo gráfico, denominado DP*Graph+, para representar o código das aplicações. Em seguida, desenvolvemos modelos analíticos, utilizando técnicas de ajuste de curvas, para representar o comportamento das estruturas de repetição compostas por primitivas de comunicação e/ou computação local. Além disso, elaboramos modelos para predizer o comportamento de aplicações do tipo mestre/escravo. Durante o desenvolvimento das atividades de análise e predição de desempenho, implementamos algumas funções para automatizar tarefas e facilitar nosso trabalho. Por último, modelamos e estimamos o desempenho de duas versões diferentes de um programa de multiplicação de matrizes, a fim de validar os modelos propostos. Os resultados das predições realizadas sobre os programas de multiplicação de matrizes foram satisfatórios. Na maioria dos casos preditos, os erros ficaram abaixo de 6 %, confirmando a validade e a precisão dos modelos elaborados. / There are many factors able to influence the performance of a MPI (Message Passing Interface) parallel program. Within these factors, we may cite: amount of data, number of nodes, characteristics of the network and type of switch, among others. Then, performance prediction isn’t a easy task. The work was developed based on a methodology of analysis and performance prediction of MPI parallel programs. First of all, we proposed a graphical model, named DP*Graph+, to represent the code of applications. Next, we developed analytical models applying curve fitting techniques to represent the behavior of repetition structure compounds by comunication primitives and/or local computations. Besides, we elaborated models to predict aplications of type master/slave. For development of performance prediction activities, some functions was developed to automate tasks and make our work easy. Finally, we modeled and predicted the performance of two different programs of matrix multiplication to prove the accuracy of models. The results of predictions on the programs were good. In the majority of predicted cases, the errors were down 6 %. With these results, we proved the accuracy of developed models.

Submitted by Pedro Henrique Rodrigues (pedro.henriquer@ufpe.br) on 2015-03-05T17:24:50Z No. of bitstreams: 2 thesis-garme.pdf: 4355850 bytes, checksum: 99bfb83bbe20bef9c48abe89d91706a0 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-05T17:24:51Z (GMT). No. of bitstreams: 2 thesis-garme.pdf: 4355850 bytes, checksum: 99bfb83bbe20bef9c48abe89d91706a0 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2012-03-09 / Com o aumento da complexidade e demanda por desempenho dos sistemas embarcados e redução do custo dos microprocessadores, projetistas de sistemas embarcados têm considerado sistemas multiprocessadores como as soluções para suas aplicações. Com o avanço nas tecnologias de integração tornou-se possível integrar em um chip bilhões de transistores. Desde que um microprocessador embarcado utiliza somente alguns poucos milhões de transistores, dez ou mais microprocessadores podem ser integrados em um único chip para formar um Multi- Processor System-on-Chip (MPSoC). No projeto desses sistemas, são necessárias a especificação e validação do comportamento funcional da aplicação do sistema antes da implementação final, através de modelos funcionais executáveis e estruturas de testbenches. Técnicas, como Projeto Baseado em Plataforma (PBP), procuram, através de reuso de componentes, bem como de modelos abstratos em nível de sistema, fornecer mecanismos para simplificar e tornar mais dinâmico o processo de desenvolvimento de MPSoCs, aumentando assim a produtividade dos projetistas. Nesta abordagem, o sistema a ser desenvolvido é, inicialmente, especificado através de uma descrição em alto nível, que sofrerá refinamentos até atingir a implementação final em hardware. As funções do sistema, contidas nessa especificação, são selecionadas para serem implementadas em software ou em hardware. Estes componentes fazem parte de uma arquitetura predefinida, conhecida como plataforma, que pode ser modificada para ser adaptada às restrições de projeto. MPSoCs são compostos por muitos componentes de processamento que executam processo concorrentes que se comunicam, portanto suas arquiteturas de comunicação on-chip devem atender às necessidades de comunicação das aplicações. Assim, enquanto existe uma grande quantidade de trabalhos que suportam as fases de particionamento/mapeamento, comparativamente, pouca pesquisa tem endereçado o problema de análise de comunicação para auxiliar o projeto de arquiteturas de comunicação dessas sistemas. As técnicas existentes para explorar as opções de configuração da estrutura de comunicação são imprecisas, pois fazem estimativas estáticas, descartando efeitos dinâmicos da arquitetura, como contenção de barramento, ou possuem baixa eficiência, pois têm que simular cada configuração do espaço de projeto. O objetivo deste trabalho é oferecer suporte de análise de comunicação nos processos de vi seleção e refinamento das arquiteturas de comunicação, após a aplicação ter sido particionada e mapeada para uma plataforma, de acordo com o PBP. O uso da abordagem proposta permite que o projetista obtenha estimativas precisas de desempenho de comunicação para as configurações de barramento de todo o espaço de projeto, e, consequentemente, possa selecionar uma configuração que melhor atenda às restrições de comunicação do projeto.

Processamento distribuído tem sido utilizado amplamente para melhorar o desempenho de aplicações com alta demanda computacional. Diferentes arquiteturas e topologias distribuídas têm sido pesquisadas e utilizadas para prover o alto desempenho, proporcionando assim o recurso necessário para a exploração do paralelismo presente nas aplicações. A facilidade para construir sistemas computacionais de alto desempenho a partir de estações de trabalho interligadas através de redes de alta velocidade, aliada ao custo relativamente baixo e ao crescente avanço da tecnologia de circuitos integrados, possibilita a montagem de redes de computadores de baixo custo para a execução de aplicações paralelas. Devido a este fato, diversos sistemas de software para redes de estações têm sido desenvolvidos, visando a integração dos componentes distribuídos para a agregação das suas capacidades de processamento. No entanto, o processo de desenvolvimento de aplicações é complexo e difícil, dado que são necessários identificar o paralelismo existente nestas aplicações, e providenciar as comunicações necessárias. Neste trabalho, é apresentada uma proposta de metodologia de análise e predição de desempenho de programas paralelos, implementados com interface de passagem de mensagem (MPI), em ambientes de redes de estações de trabalho. É definida neste trabalho uma extensão da classe de grafos de tempo T-graph, denominado T-graph*, que representa, em alto nível, os programas paralelos instrumentados com MPI no nível de grafos. Com a construção de um grafo nesta classe, é possível conhecer o fluxo da execução do programa, do ponto de vista algorítmico. Ainda, é definida uma outra classe de grafos, denominada DP*Graph, que representa os programas paralelos com alto grau de detalhes, como mostrar de forma clara pontos de ocorrência de comunicação entre os nós de processamento do sistema computacional. Em paralelo com recursos e técnicas de modelagem analítica, são definidas estratégias para a avaliação de desempenho dos sistemas computacionais envolvidos. Uma vez obtidas as representações em grafos do programa paralelo e junto com as modelagens já refinadas e definidas, é possível efetuar avaliações necessárias e obter assim predições de desempenho, baseadas em dados experimentais obtidos previamente. Finalmente, os resultados experimentais obtidos mostram a viabilidade da metodologia definida nesta proposta, tanto a sua utilização e quanto à coerência das estratégias aplicadas neste trabalho. / Distributed processing has been widely used to improve the performance of applications that highly demand computational power. Different distributed architectures and topologies have been used in a search for high performance, providing further the necessary resource for the parallelism exploitation present in the applications. The ease to build high performance computer systems, by interconnecting workstations using a high speed network, together with relatively low cost and IC technology advances, it\'s possible to assembly a low cost computer network for the execution of parallel applications. Due to this fact, several applications and software systems for network of workstations have been developed, aiming the integration of distributed components for the aggregation of their processing power. Unfortunately, the process of application developing is complex and difficult, given that it is necessary identify the existing parallelism in these applications, and provide the communication needed. The control of multiple processes and their interactions are the main reasons for such complexity. It is shown, in this work, a methodology proposal for the performance analysis and prediction of parallel programs, implemented with message passing interface (MPI) in a network of workstations environment. We define, still in this work, an extension for T-graph (timing graphs), named T-graph*, a newer class of graphs from which we can represent parallel programs with MPI functions by using timing graphs. Together with resources and analytical modeling techniques, strategies are defined for the performance evaluation of computer systems involved. Once obtained the graph representation of a parallel program, in parallel with defined and refined models designed, it is possible to proceed with necessary evaluations and from this, performance prediction data, based on the experimental data obtained previously. Finally, experimental results obtained show the viability of the methodology proposed in this research, coherent strategies applied in this work and also, correct utilization of the techniques.

The parallel and distributed platforms of High Performance Computing available today have became more and more heterogeneous (CPUs, GPUs, FPGAs, etc). Graphics Processing Units (GPU) are specialized co-processor to accelerate and improve the performance of parallel vector operations. GPUs have a high degree of parallelism and can execute thousands or millions of threads concurrently and hide the latency of the scheduler. GPUs have a deep hierarchical memory of different types as well as different configurations of these memories. Performance prediction of applications executed on these devices is a great challenge and is essential for the efficient use of resources in machines with these co-processors. There are different approaches for these predictions, such as analytical modeling and machine learning techniques. In this thesis, we present an analysis and characterization of the performance of applications executed on GPUs. We propose a simple and intuitive BSP-based model for predicting the CUDA application execution times on different GPUs. The model is based on the number of computations and memory accesses of the GPU, with additional information on cache usage obtained from profiling. We also compare three different Machine Learning (ML) approaches: Linear Regression, Support Vector Machines and Random Forests with BSP-based analytical model. This comparison is made in two contexts, first, data input or features for ML techniques were the same than analytical model, and, second, using a process of feature extraction, using correlation analysis and hierarchical clustering. We show that GPU applications that scale regularly can be predicted with simple analytical models, and an adjusting parameter. This parameter can be used to predict these applications in other GPUs. We also demonstrate that ML approaches provide reasonable predictions for different cases and ML techniques required no detailed knowledge of application code, hardware characteristics or explicit modeling. Consequently, whenever a large data set with information about similar applications are available or it can be created, ML techniques can be useful for deploying automated on-line performance prediction for scheduling applications on heterogeneous architectures with GPUs. / As plataformas paralelas e distribuídas de computação de alto desempenho disponíveis hoje se tornaram mais e mais heterogêneas (CPUs, GPUs, FPGAs, etc). As Unidades de processamento gráfico são co-processadores especializados para acelerar operações vetoriais em paralelo. As GPUs têm um alto grau de paralelismo e conseguem executar milhares ou milhões de threads concorrentemente e ocultar a latência do escalonador. Elas têm uma profunda hierarquia de memória de diferentes tipos e também uma profunda configuração da memória hierárquica. A predição de desempenho de aplicações executadas nesses dispositivos é um grande desafio e é essencial para o uso eficiente dos recursos computacionais de máquinas com esses co-processadores. Existem diferentes abordagens para fazer essa predição, como técnicas de modelagem analítica e aprendizado de máquina. Nesta tese, nós apresentamos uma análise e caracterização do desempenho de aplicações executadas em Unidades de Processamento Gráfico de propósito geral. Nós propomos um modelo simples e intuitivo fundamentado no modelo BSP para predizer a execução de funções kernels de CUDA sobre diferentes GPUs. O modelo está baseado no número de computações e acessos à memória da GPU, com informação adicional do uso das memórias cachês obtidas do processo de profiling. Nós também comparamos três diferentes enfoques de aprendizado de máquina (ML): Regressão Linear, Máquinas de Vetores de Suporte e Florestas Aleatórias com o nosso modelo analítico proposto. Esta comparação é feita em dois diferentes contextos, primeiro, dados de entrada ou features para as técnicas de aprendizado de máquinas eram as mesmas que no modelo analítico, e, segundo, usando um processo de extração de features, usando análise de correlação e clustering hierarquizado. Nós mostramos que aplicações executadas em GPUs que escalam regularmente podem ser preditas com modelos analíticos simples e um parâmetro de ajuste. Esse parâmetro pode ser usado para predizer essas aplicações em outras GPUs. Nós também demonstramos que abordagens de ML proveem predições aceitáveis para diferentes casos e essas abordagens não exigem um conhecimento detalhado do código da aplicação, características de hardware ou modelagens explícita. Consequentemente, sempre e quando um banco de dados com informação de \\textit esteja disponível ou possa ser gerado, técnicas de ML podem ser úteis para aplicar uma predição automatizada de desempenho para escalonadores de aplicações em arquiteturas heterogêneas contendo GPUs.

Processamento distribuído tem sido utilizado amplamente para melhorar o desempenho de aplicações com alta demanda computacional. Diferentes arquiteturas e topologias distribuídas têm sido pesquisadas e utilizadas para prover o alto desempenho, proporcionando assim o recurso necessário para a exploração do paralelismo presente nas aplicações. A facilidade para construir sistemas computacionais de alto desempenho a partir de estações de trabalho interligadas através de redes de alta velocidade, aliada ao custo relativamente baixo e ao crescente avanço da tecnologia de circuitos integrados, possibilita a montagem de redes de computadores de baixo custo para a execução de aplicações paralelas. Devido a este fato, diversos sistemas de software para redes de estações têm sido desenvolvidos, visando a integração dos componentes distribuídos para a agregação das suas capacidades de processamento. No entanto, o processo de desenvolvimento de aplicações é complexo e difícil, dado que são necessários identificar o paralelismo existente nestas aplicações, e providenciar as comunicações necessárias. Neste trabalho, é apresentada uma proposta de metodologia de análise e predição de desempenho de programas paralelos, implementados com interface de passagem de mensagem (MPI), em ambientes de redes de estações de trabalho. É definida neste trabalho uma extensão da classe de grafos de tempo T-graph, denominado T-graph*, que representa, em alto nível, os programas paralelos instrumentados com MPI no nível de grafos. Com a construção de um grafo nesta classe, é possível conhecer o fluxo da execução do programa, do ponto de vista algorítmico. Ainda, é definida uma outra classe de grafos, denominada DP*Graph, que representa os programas paralelos com alto grau de detalhes, como mostrar de forma clara pontos de ocorrência de comunicação entre os nós de processamento do sistema computacional. Em paralelo com recursos e técnicas de modelagem analítica, são definidas estratégias para a avaliação de desempenho dos sistemas computacionais envolvidos. Uma vez obtidas as representações em grafos do programa paralelo e junto com as modelagens já refinadas e definidas, é possível efetuar avaliações necessárias e obter assim predições de desempenho, baseadas em dados experimentais obtidos previamente. Finalmente, os resultados experimentais obtidos mostram a viabilidade da metodologia definida nesta proposta, tanto a sua utilização e quanto à coerência das estratégias aplicadas neste trabalho. / Distributed processing has been widely used to improve the performance of applications that highly demand computational power. Different distributed architectures and topologies have been used in a search for high performance, providing further the necessary resource for the parallelism exploitation present in the applications. The ease to build high performance computer systems, by interconnecting workstations using a high speed network, together with relatively low cost and IC technology advances, it\'s possible to assembly a low cost computer network for the execution of parallel applications. Due to this fact, several applications and software systems for network of workstations have been developed, aiming the integration of distributed components for the aggregation of their processing power. Unfortunately, the process of application developing is complex and difficult, given that it is necessary identify the existing parallelism in these applications, and provide the communication needed. The control of multiple processes and their interactions are the main reasons for such complexity. It is shown, in this work, a methodology proposal for the performance analysis and prediction of parallel programs, implemented with message passing interface (MPI) in a network of workstations environment. We define, still in this work, an extension for T-graph (timing graphs), named T-graph*, a newer class of graphs from which we can represent parallel programs with MPI functions by using timing graphs. Together with resources and analytical modeling techniques, strategies are defined for the performance evaluation of computer systems involved. Once obtained the graph representation of a parallel program, in parallel with defined and refined models designed, it is possible to proceed with necessary evaluations and from this, performance prediction data, based on the experimental data obtained previously. Finally, experimental results obtained show the viability of the methodology proposed in this research, coherent strategies applied in this work and also, correct utilization of the techniques.

The parallel and distributed platforms of High Performance Computing available today have became more and more heterogeneous (CPUs, GPUs, FPGAs, etc). Graphics Processing Units (GPU) are specialized co-processor to accelerate and improve the performance of parallel vector operations. GPUs have a high degree of parallelism and can execute thousands or millions of threads concurrently and hide the latency of the scheduler. GPUs have a deep hierarchical memory of different types as well as different configurations of these memories. Performance prediction of applications executed on these devices is a great challenge and is essential for the efficient use of resources in machines with these co-processors. There are different approaches for these predictions, such as analytical modeling and machine learning techniques. In this thesis, we present an analysis and characterization of the performance of applications executed on GPUs. We propose a simple and intuitive BSP-based model for predicting the CUDA application execution times on different GPUs. The model is based on the number of computations and memory accesses of the GPU, with additional information on cache usage obtained from profiling. We also compare three different Machine Learning (ML) approaches: Linear Regression, Support Vector Machines and Random Forests with BSP-based analytical model. This comparison is made in two contexts, first, data input or features for ML techniques were the same than analytical model, and, second, using a process of feature extraction, using correlation analysis and hierarchical clustering. We show that GPU applications that scale regularly can be predicted with simple analytical models, and an adjusting parameter. This parameter can be used to predict these applications in other GPUs. We also demonstrate that ML approaches provide reasonable predictions for different cases and ML techniques required no detailed knowledge of application code, hardware characteristics or explicit modeling. Consequently, whenever a large data set with information about similar applications are available or it can be created, ML techniques can be useful for deploying automated on-line performance prediction for scheduling applications on heterogeneous architectures with GPUs. / As plataformas paralelas e distribuídas de computação de alto desempenho disponíveis hoje se tornaram mais e mais heterogêneas (CPUs, GPUs, FPGAs, etc). As Unidades de processamento gráfico são co-processadores especializados para acelerar operações vetoriais em paralelo. As GPUs têm um alto grau de paralelismo e conseguem executar milhares ou milhões de threads concorrentemente e ocultar a latência do escalonador. Elas têm uma profunda hierarquia de memória de diferentes tipos e também uma profunda configuração da memória hierárquica. A predição de desempenho de aplicações executadas nesses dispositivos é um grande desafio e é essencial para o uso eficiente dos recursos computacionais de máquinas com esses co-processadores. Existem diferentes abordagens para fazer essa predição, como técnicas de modelagem analítica e aprendizado de máquina. Nesta tese, nós apresentamos uma análise e caracterização do desempenho de aplicações executadas em Unidades de Processamento Gráfico de propósito geral. Nós propomos um modelo simples e intuitivo fundamentado no modelo BSP para predizer a execução de funções kernels de CUDA sobre diferentes GPUs. O modelo está baseado no número de computações e acessos à memória da GPU, com informação adicional do uso das memórias cachês obtidas do processo de profiling. Nós também comparamos três diferentes enfoques de aprendizado de máquina (ML): Regressão Linear, Máquinas de Vetores de Suporte e Florestas Aleatórias com o nosso modelo analítico proposto. Esta comparação é feita em dois diferentes contextos, primeiro, dados de entrada ou features para as técnicas de aprendizado de máquinas eram as mesmas que no modelo analítico, e, segundo, usando um processo de extração de features, usando análise de correlação e clustering hierarquizado. Nós mostramos que aplicações executadas em GPUs que escalam regularmente podem ser preditas com modelos analíticos simples e um parâmetro de ajuste. Esse parâmetro pode ser usado para predizer essas aplicações em outras GPUs. Nós também demonstramos que abordagens de ML proveem predições aceitáveis para diferentes casos e essas abordagens não exigem um conhecimento detalhado do código da aplicação, características de hardware ou modelagens explícita. Consequentemente, sempre e quando um banco de dados com informação de \\textit esteja disponível ou possa ser gerado, técnicas de ML podem ser úteis para aplicar uma predição automatizada de desempenho para escalonadores de aplicações em arquiteturas heterogêneas contendo GPUs.

Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2016-12-02T15:54:04Z No. of bitstreams: 2 Dissertação - Porthos Ribeiro de Albuquerque Motta - 2016.pdf: 10397634 bytes, checksum: 0610600c9a91143c40d1c6d22a401524 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2016-12-13T15:28:18Z (GMT) No. of bitstreams: 2 Dissertação - Porthos Ribeiro de Albuquerque Motta - 2016.pdf: 10397634 bytes, checksum: 0610600c9a91143c40d1c6d22a401524 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-12-13T15:28:18Z (GMT). No. of bitstreams: 2 Dissertação - Porthos Ribeiro de Albuquerque Motta - 2016.pdf: 10397634 bytes, checksum: 0610600c9a91143c40d1c6d22a401524 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-10-20 / Educational Data Mining, by the triad of quality improvement, cost reduction and educational effectiveness, acts and seeks to better understand the teaching and learning process. In this context, the aim of this work is an exploratory study of classification methods to predict student performance and dropout from data in university academic databases. In this study we used demographic, socio-economic and academic results, obtained from the Vestibular and the university database to analyze several classification techniques, as well as balancing and attribute selection techniques, identified through a systematic review of the literature. Following a trend found in the selected articles, we chose to use decision trees as the primary classification algorithm, although comparative studies showed better results with logistic regression techniques and Bayesian networks. This is because decision trees allow an analysis of the attributes used in the generated models while maintaining acceptable levels of accuracy, while other techniques work as a black box. Through the tests we found that you get better results using balanced sets. In this sense, the Resample technique that selects a balanced subset of the data showed better results than SMOTE technique that generates synthetic data for balancing the dataset. Regarding the use of attribute selection techniques, these did not bring significant advantages. Among the attributes used, grades and economic factors often appear as nodes in the generated models. An attempt to predict performance for each subject based on data from previous courses was less successful, maybe because of the use of ternary predictive classes. Nevertheless, the analysis carried out showed that the use of classifiers is a promising way to predict performance and dropout, but further studies are still needed. / A Mineração de Dados Educacionais, por meio da tríade melhoria da qualidade, redução do custo e eficácia do ensino, age e procura compreender melhor o processo de ensinoaprendizagem dos alunos. Neste contexto, o objetivo desta dissertação é o estudo exploratório de métodos de classificação para predizer o desempenho e o abandono de alunos a partir de dados existentes nas bases de dados acadêmicas das universidades. Neste trabalho foram usados dados demográficos, sócio-econômicos e resultados acadêmicos, oriundos do Vestibular e do banco de dados acadêmico da universidade para analisar diversas técnicas de classificação, assim como técnicas de balanceamento e seleção de atributos identificadas através de uma revisão sistemática da literatura. Seguindo uma tendência verificada nos artigos levantados, optou-se por utilizar como principal algoritmo de classificação o J48, apesar de estudos comparativos terem mostrado melhores resultados com técnicas de regressão logística e redes Bayesianas. Isto se deve ao fato das árvores de decisão permitirem uma análise dos atributos usados nos modelos gerados, mantendo ní- veis de acurácia aceitáveis, enquanto as outras técnicas funcionam como uma caixa preta. Neste sentido, a técnica de Resample, que escolhe um subconjunto balanceado dos dados, apresentou melhores resultados que a técnica de SMOTE, que gera dados sintéticos para balancear os dados. Quanto ao uso de técnicas de seleção de atributos, estas não trouxeram vantagens significativas. Dentre os atributos usados, notas e aspectos econômicos aparecem com frequência nos modelos gerados. Uma tentativa de prever desempenho por disciplina, com base em dados de disciplinas já cursadas em semestres anteriores foi menos bem sucedida, talvez pelo fato de usar classes preditoras ternárias. Apesar disto, as análises realizadas mostraram que o uso de classificadores é um caminho promissor para a predição de desempenho e abandono, mas estudos mais aprofundados ainda são necessários