Parallel program performance analysis and prediction on NOW systems.

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