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.

In this work, we design parallel Monte Carlo algorithms for the Ising spin model on a hierarchical cluster. A hierarchical cluster can be considered as a cluster of homogeneous nodes which are partitioned into multiple supernodes such that communication across homogenous clusters is represented by a supernode topological network. We consider different data layouts and provide equations for choosing the best data layout under such a network paradigm. We show that the data layouts designed for a homogeneous cluster will not yield results as good as layouts designed for a hierarchical cluster. We derive theoretical results on the performance of the algorithms on a modified version of the LogP model that represents such tiered networking, and present simulation results to analyze the utility of the theoretical design and analysis. Furthermore, we consider the 3-D Ising model and design parallel algorithms for sweep spin selection on both homogeneous and hierarchical clusters. We also discuss the simulation of hierarchical clusters on a homogeneous set of machines, and the efficient implementation of the parallel Ising model on such clusters. / Master of Science