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.

A utilização majoritária da malha ferroviária brasileira para o transporte de cargas e a sua incompatibilidade para desenvolvimento de altas velocidades inviabiliza a oferta de serviços competitivos para o transporte intermunicipal de passageiros. A questão explorada nesta tese é sobre qual tecnologia ferroviária provê melhores resultados socioeconômicos no contexto de uma nova rede para o transporte intermunicipal de passageiros com operação exclusiva de Trens de Alto Desempenho (High Performance Trains - HPTs) ou Trens de Alta Velocidade (High Speed Trains - HSTs), caracterizados por velocidades médias de 150 km/h e 300 km/h respectivamente. Nesse sentido, a hipótese é que a diferença entre benefícios e custos socioeconômicos da oferta de serviços de HSTs resultam em valores positivos e maiores do que aquelas decorrentes da operação de HPTs, mediante parâmetros específicos de avaliação socioeconômica e uma configuração hipotética de rede na Região Sudeste do Brasil. Assim, o objetivo principal da tese é estimar e comparar os custos e benefícios socioeconômicos de uma rede ferroviária pela estimativa dos investimentos para a construção de novos traçados ferroviários, estimativa do número de viagens intermunicipais na Região Sudeste em um horizonte de planejamento estratégico e a propensão à escolha modal, estabelecimento de uma formulação de Análise Custo-Benefício (Cost Benefit Analysis - CBA) e aplicação dos modelos em cenários considerando a operação exclusiva de HPTs ou de HSTs. A resolução do problema de otimização de traçados ferroviários, com uma abordagem de computação paralela aplicada a um Algoritmo Genético, indica que os investimentos em infraestrutura variam majoritariamente em função da topografia, os custos de desapropriações são proporcionalmente pequenos e as restrições geométricas dos traçados não influenciam significativamente nesses resultados. Após a projeção do número de viagens intermunicipais por modelos analíticos, os dados coletados em uma pesquisa de preferência declarada são utilizados para modelagem da propensão à escolha modal. Finalmente, uma proposta de formulação para o cálculo dos principais itens de custos e benefícios de uma avaliação socioeconômica para o transporte ferroviário de passageiros viabiliza a análise de cenários em função de produtividade da construção da infraestrutura, variabilidade dos investimentos estimados e capacidade de atração de demanda reprimida. Os resultados dos cenários indicam que a diferença entre os benefícios estritamente econômicos (receita operacional e valor residual dos investimentos em infraestrutura) e os custos de construção e operacionais são negativos para qualquer tarifa ferroviária, apesar dos resultados para a rede de HSTs serem maiores do que para a de HPTs. Considerando os aspectos sociais, os benefícios totais da operação ferroviária sobrepõem-se aos seus custos em situações tarifárias específicas, novamente com resultados maiores para uma rede de HSTs, cuja tendência também é observada quando apenas os benefícios sociais são relacionados com custos totais através de uma Razão Benefício-Custo (Benefit-Cost Ratio - BCR). Portanto, segundo as premissas desta tese, há indícios que o investimento em uma infraestrutura ferroviária aparentemente não é uma decisão promissora em termos de viabilidade socioeconômica, apesar da operação de HSTs ser mais conveniente do que HPTs nas condições analisadas. / The major use of the Brazilian railway network for freight transport and its incompatibi-lity with high speed trains does not enable running competitive services of intercity passenger transport. The research question of this thesis is which rolling stock technology provides better socioeconomic results on a new intercity passenger network with exclusive operation of High Performance Trains (HPTs) or High Speed Trains (HSTs) with average speeds of 150 km/h and 300 km/h respectively. The hypothesis is that the difference between the socioeconomic benefits and costs of operating HSTs results in positive values and greater than those from the operation of HPTs given specific socioeconomic parameters and a hypothetical network in the Southeastern region of Brazil. The main goal of this research is to estimate and compare the major socioeconomic costs and benefits of a hypothetical railway network by first estimating the required investments of new alignments. Furthermore, the number of trips among cities in the Southeastern Region over a strategic planning horizon and the mode choice are estimated and a Cost-Benefit Analysis formulation is provided to be applied to scenarios of exclusive operation of HPTs or HSTs. The solution of the railway alignment optimization problem with a parallel computing approach applied to a Genetic Algorithm shows that the infrastructure investments vary mainly due to the topography, whereas the expropriation costs are proporti-onally small and the railway geometric constraints do not significantly affect the results. The number of trips by transport mode over a planning horizon is expanded analytically and the collected data of a stated preference survey is applied to a mode choice modeling approach. Finally, a formulation for the major items of costs and benefits of a socioeconomic assessment for a rail passenger transport project is proposed and it is applied to specific scenarios where the effects of the infrastructure building productivity, variability of the estimated investments, and the ability to attract new passengers are analyzed. The results from these scenarios show that the difference between the operating income and the net residual value of investments in infrastructure, construction and operating costs are negative for any rail fare, despite the results for the network of HSTs being higher than for HPTs. Furthermore, the overall benefits of the railway operation outweigh the costs in specific pricing policies with better results for a network operating HSTs. This trend is also noticed when only the social benefits are compared to the total costs by a Benefit-Cost Ratio (BCR). Therefore, there is evidence that the investment in railway infrastructure for passenger transport apparently is not a promising decision in terms of socioeconomic feasibility under the assumptions of this thesis, despite the operation of HSTs being more attractive than HPTs under the specified conditions.

Grade computacional é uma alternativa para melhorar o desempenho de aplicações paralelas, por permitir o uso simultâneo de vários recursos distribuídos. Entretanto, para que a utilização de uma grade seja adequada, é necessário que os recursos sejam utilizados de maneira a permitir a otimização de algum critério. Para isto, várias estratégias de escalonamento têm sido propostas, mas o grande desafio é extrair o potencial que os recursos oferecem para a execução de aplicações paralelas. Uma estratégia bastante usada em sistemas de escalonamento atuais é escalonar uma aplicação paralela nos recursos de um único cluster. Contudo, apesar da estratégia ser simples, ela é muito limitada, devido principalmente a baixa utilização dos recursos. Este trabalho propõe e implementa o sistema GCSE (Grid Cooperative Scheduling Environment) que provê uma estratégia de escalonamento cooperativo para usar eficientemente os recursos distribuídos. Os processos de uma aplicação paralela podem ser distribuídos em recursos de vários clusters e computadores, todos conectados a redes de comunicação públicas. GCSE também gerencia a execução das aplicações, bem como oferece um conjunto de primitivas que fornece informações sobre os ambientes de execução para o suporte à comunicação entre processos. Além disto, uma estratégia de antecipação de dados é proposta para aumentar ainda mais o desempenho das aplicações. Para realizar um bom escalonamento é preciso descobrir os recursos distribuídos. Neste sentido, o sistema LIMA (Light-weIght Monitoring Architecture) foi projetado e implementado. Este sistema provê um conjunto de estratégias e mecanismos para o armazenamento distribuído e acesso eficiente às informações sobre os recursos distribuídos. Além disto, LIMA adiciona facilidades de descobrimento e integração com o GCSE e outros sistemas. Por fim, serão apresentados os testes e avaliações dos resultados com o uso integrado dos sistemas GCSE e LIMA, compondo um ambiente robusto para a execução de aplicações paralelas. / Computing grid is an alternative for improving the parallel application performance, because it allows the simultaneous use of many distributed resources. However, in order to take advantage of a grid, the resources must be used in such a way that some criteria can be optimized. Thus, various scheduling strategies have been proposed, but the great challenge is the exploitation of the potential that the resources provide to the parallel application execution. A strategy often used in current scheduling systems is to schedule a parallel application on resources of a single cluster. Even though this strategy is simple, it is very limited, mainly due to low resource utilization. This thesis proposes and implements the GCSE system (Grid Cooperative Scheduling Environment) that provides a cooperative scheduling strategy for efficiently using the distributed resources. The processes of a parallel application can be distributed in resources of many clusters and computers, and they are all connected by public communication networks. GCSE also manages the application execution, as well as offering a primitive set that provide information about the execution environments for ensuring the communication between processes. Moreover, a data advancement strategy is proposed for improving the application performance. In order to perform a good scheduling, the distributed resources must be discovered. Therefore, the LIMA system (Light-weIght Monitoring Architecture) was designed and implemented. This system provides both strategy and mechanism set for distributed storage and efficient access to information about the distributed resources. In addition, LIMA offers facilities for resource discovering and integrating its functionalities both GCSE and other systems. Finally, the tests and result evaluations are presented with the integrated use of both GCSE and LIMA systems, composing a robust environment for executing parallel application.

Neste trabalho demos continuidade ao estudo desenvolvido por Colla (2007) que utilizou-se do arcabouço de álgebra linear com técnicas de fatoração de matrizes esparsas aplicadas à inferência em redes Bayesianas. Com isso, a biblioteca computacional resultante possui uma separação clara entre a fase simbólica e numérica da inferência, o que permite aproveitar os resultados obtidos na primeira etapa para variar apenas os valores numéricos. Aplicamos técnicas de paralelização para melhorar o desempenho computacional, adicionamos inferência para Redes Credais e novos algoritmos para inferência em Redes Bayesianas para melhor eciência dependendo da estrutura do grafo relacionado à rede e buscamos tornar ainda mais independentes as etapas simbólica e numérica. / In this work we continued the study by Colla (2007), who used the framework of linear algebra techniques with sparse matrix factorization applied to inference in Bayesian networks. Thus, the resulting computational library has a clear separation between the symbolic and numerical phase of inference, which allows you to use the results obtained in the rst step to vary only numeric values. We applied parallelization techniques to improve computational performance, we add inference to Credal Networks and new algorithms for inference in Bayesian networks for better eciency depending on the structure of the graph related to network and seek to become more independent symbolic and numerical steps.

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.

Este trabalho trata da avaliação do desempenho de máquinas de usinagem cujas arquiteturas se baseiem em estruturas cinemáticas paralelas planas. Inicialmente analisa dois tipos distintos de arquiteturas paralelas, avaliando as suas mobilidades, possíveis formas de atuação, além de apresentar seus modelos teóricos cinemáticos e dinâmicos correspondentes. A seguir, descrevem-se no texto algumas simulações realizadas em oito modelos propostos, de modo a se observar os comportamentos das arquiteturas consideradas, quando da execução de possíveis trajetórias da ferramenta em movimento plano (2D). A seleção dos modelos e a discussão dos resultados são guiadas por índices de desempenho presentes na literatura e outros propostos ou adaptados. O trabalho discute ainda as melhores soluções, com foco nas trajetórias prédefinidas e em critérios importantes para os mecanismos de arquitetura paralela. / This dissertation concerns the performance evaluation of machine-tool with architectures based on planar parallel kinematic structures. The text starts analyzing two distinct types of parallel architectures, their mobility, feasible schemes of actuation and presents their kinematic and dynamic models. From this point, simulations are described to figure out some characteristics of chosen architectures, in eight different models, focused on execution of tool trajectories in plane motion (2D). The model selection and the discussion about obtained results are guided by performance indexes from the literature and others either proposed or adapted. The work also discusses the best solutions, for pre-defined tool trajectories and important points for mechanisms with parallel structures.

Neste trabalho de mestrado foi desenvolvido o projeto de uma máquina paralela dedicada para solução de sistemas de equações lineares. Este é um problema presente em uma grande variedade de aplicações científicas e de engenharia e cuja solução torna-se uma tarefa computacionalmente intensiva , a medida em que o número de incógnitas aumenta. Implementou-se uma Arquitetura Sistólica unidimensional, conectada numa topologia em anel, que mapeia métodos de solução iterativos. Essa classe de arquiteturas paralelas apresenta características de simplicidade, regularidade e modularidade que facilitam implementações em hardware, sendo muito utilizadas em sistemas de computação dedicados à solução de problemas específicos, que possuem como características básicas a grande demanda computacional e a necessidade de respostas em tempo real. Foram adotadas metodologias e ferramentas avançadas para projeto de hardware que aceleram o ciclo de desenvolvimento e para a implementação foram utilizados circuitos reconfiguráveis FPGAs (Field Programmable Gate Arrays). Os resultados de desempenho são apresentados e avaliados apontado a melhor configuração da arquitetura para atingir um speedup em relação a implementações em máquinas seqüenciais. Também são discutidas as vantagens e desvantagens deste tipo de abordagem e metodologia na solução de problemas que possuem requisitos de tempo. / This dissertation presents the project of a parallel machine dedicated for solving linear systems. This is a problem that appears in a great variety of scientific and engineering applications with a solution that becomes a computationally intensive task, measured by the increasing number of unknown variables. An Systolic Architecture was implemented, connected in a ring topology, mapping an iterative solution method. This class of parallel architectures presents characteristics of simplicity, regularity and modularity that facilitate hardware implementations, being very used in dedicated computation systems to the solution of specific problems, which possess as requirements to handle great computational demand and real-time response. Advanced methodologies and tools for hardware project were adopted to accelerate the development cycle. The architecture has been implemented and verified on FPGAs (Field Programmable Gate Arrays). The performance results are presented and discussed, indicating the feasibility and efficiency of the adopted approach and methodology for this kind of problem.

Neste trabalho apresentamos a metodologia de orientação ao objeto no desenvolvimentos de uma biblioteca de classes para facilitar o processo de programação numérica paralela. Na implementação dos métodos das classes utilizamos as rotinas do pacote ScaLAPACK, sendo que essas classes oferecem métodos para manipulações matriciais básicas e para a diagonalização de matrizes, onde essas matrizes podem ser reais e complexas, de simples e dupla precisão. Este trabalho apresenta detalhes de implementação e uma análise comparativa de desempenho, a fim de mostrarmos a eficiência e as facilidades de uso da orientação ao objeto no desenvolvimento de programas científicos paralelos. / In this work current vs. voltage (I vs. V) and alternating conductivity (ac) measurements were carried out in poly[(2-methoxy- 5-hexyloxy)-pphenylenevinilene] ? MEH-PPV light-emitting diodes having zinc oxide (ZnO) as transparent anode and Al as metallic cathode. MEH-PPV is a PPV derivative, which emits in the red spectral region; ZnO has a work function similar to that of ITO, but it is less aggressive to the polymer, less expensive and easily processed. The retificated I vs. V curves shows that the direct current depends on the temperature. Moreover, the real and imaginary components of alternating conductivity (ac) present typical behavior of somewhat disordered material: the imaginary component grows as a function of the frequency and the real component was observed to be frequency independent for lower frequencies, and follows a power-law above a certain frequency. The Random Energy Free Barrier model approaches and a resistance in series for the interface phenomenon were developed and adjusted for the ac results. From this experimental-theoretical fitting we obtained important parameters of the devices as well as, quantitative informations about the MEH-PPV transport phenomenon.

A temática envolvendo o processamento de grandes quantidades de dados é um tema amplamente discutido nos tempos atuais, envolvendo seus desafios e aplicabilidade. Neste trabalho é proposta uma ferramenta de programação para desenvolvimento e um ambiente de execução para aplicações com grandes quantidades de dados. O uso da ferramenta visa obter melhor desempenho de aplicações neste cenário, explorando o uso de recursos físicos como múltiplas linhas de execução em processadores com diversos núcleos e a programação distribuída, que utiliza múltiplos computadores interligados por uma rede de comunicação, de forma que estes operam conjuntamente em uma mesma aplicação, dividindo entre tais máquinas sua carga de processamento. A ferramenta proposta consiste na utilização de blocos de programação, de forma que tais blocos sejam compostos por tarefas, e sejam executados utilizando o modelo produtor consumidor, seguindo um fluxo de execução definido. A utilização da ferramenta permite que a divisão das tarefas entre as máquinas seja transparente ao usuário. Com a ferramenta, diversas funcionalidades podem ser utilizadas, como o uso de ciclos no fluxo de execução ou no adiantamento de tarefas, utilizando a estratégia de processamento especulativo. Os resultados do trabalho foram comparados a duas outras ferramentas de processamento de grandes quantidades de dados, Hadoop e que o uso da ferramenta proporciona aumento no desempenho das aplicações, principalmente quando executado em clusters homogêneos. / The topic involving the processing of large amounts of data is widely discussed subject currently, about its challenges and applicability. This work proposes a programming tool for development and an execution environment for applications with large amounts of data. The use of the tool aims to achieve better performance of applications in this scenario, exploring the use of physical resources such as multiple lines of execution in multi-core processors and distributed programming, which uses multiple computers interconnected by a communication network, so that they operate jointly in the same application, dividing such processing among such machines. The proposed tool consists of the use of programming blocks, so that these blocks are composed of tasks, and the blocks are executed using the producer consumer model, following an execution flow. The use of the tool allows the division of tasks between the machines to be transparent to the user. With the tool, several functionalities can be used, such as cycles in the execution flow or task advancing using the strategy of speculative processing. The results were compared with two other frameworks, Hadoop and Spark. These results indicate that the use of the tool provides an increase in the performance of the applications, mostly when executed in homogeneous clusters.

A Transformada Distância é uma importante ferramenta para o processamento de imagens digitais. A partir dela podemos calcular a dimensão fractal e obter o esqueleto de um objeto. Estas operações são muito importantes na análise de formas e no reconhecimento de padrões. Porém poucas são as implementações em hardware específico para este processamento. Neste trabalho apresentamos a implementação de arquiteturas paralelas para a determinação da Transformada Distância e para a geração de esqueletos baseados no algoritmo de Dilatação Exata e Propagação de Rótulos. Propomos também uma implementação do algoritmo utilizando a biblioteca MPI para o processamento paralelo. / Distance Transform is an important tool for digital imaging processing. Using the Distance Transform it is possible to evaluate the fractal dimension and skeletons of objects. Fractal dimension and skeletons are very important in shape analysis and pattern recognition operations, few are the hardware implementation for these operations. In this work we present a parallel implementation based on the exact dilation and label propagation for the evaluation of the Distance Transform and skeletons generation. We also propose an algorithm implementation using the MPI library for parallel processing.