The aim of this Diploma thesis is to get acquitained with the approaches to parallel programming and possibilities of their practical implementation, including possibilities of their usage in management. An important part of the Diploma thesis is the practical implementation of parallel program in a PC cluster environment, which was implemented in computer laboratory of Faculty of Management VŠE. The practical part consists of an example of decision-making under uncertainty (risk) which is solved with the employment of the Monte Carlo method.

Esta dissertação apresenta o PMPI, uma implementação do padrão MPI em plataformas heterogêneas. Diferentemente de outras implementações de MPI, o PMPI permite que a aplicação paralela seja realizada num sistema multi-plataforma, e que programas em linguagens de programação diferentes participem da mesma computação. PMPI é construído sobre o Dotnet Framework. Com o PMPI, os nós de processamento chamam funções MPI que são executadas transparentemente em outros nós participantes da computação paralela pela rede de comunicação. O PMPI pode atravessar múltiplos domínios administrativos distribuídos geograficamente. Para os programadores, o grid se parece como uma computação MPI local. O modelo de computação é indistinguível da computação MPI padrão. Esta dissertação estuda a implementação de PMPI com o Microsoft Dotnet Framework e com o MONO para prover uma biblioteca que suporta ambiente de multi-linguagens de programação e multi-plataformas. São analisados os resultados obtidos dos testes executados em sistemas heterogêneos usando PMPI. Os resultados obtidos mostram que a implementação PMPI é uma solução viável, possuindo várias vantagens que ainda podemos explorar melhor. / This dissertation describes PMPI, an implementation of the MPI standard on a heterogeneous platform. Unlike other MPI implementations, PMPI permits MPI computation to run on a multiplatform system. In addition, PMPI permits programs executing on different nodes to be written in different programming languages. PMPI is build on the top of Dotnet framework. With PMPI, nodes call MPI functions that are transparently executed on the participating nodes across the network. PMPI can span multiple administrative domains distributed geographically. To programmers, the grid looks like a local MPI computation. The model of computation is indistinguishable from that of standard MPI computation. This dissertation studies the implementation of PMPI with Microsoft Dotnet framework and MONO Dotnet framework to provide a common layer for a multiprogramming language multiplatform MPI library. Results obtained from tests running PMPI on a heterogeneous system are analyzed. The obtained results show that PMPI implementation is feasible and has many advantages that can be explored.

Esse trabalho propõe uma solução de um Data Warehouse distribuído para implementação de um sistema de CRM, Customer Relationship Management, com o objetivo de uso no ambiente bancário possibilitando que ações de relacionamento com clientes sejam planejadas e implementadas. É proposta uma arquitetura para implementação de um Data Warehouse em ambiente distribuído, utilizando programação paralela. Com o aumento no volume de dados armazenados nos Data Warehouse, as arquiteturas tradicionais exigem processadores e sistemas de entrada e saída cada vez mais robustos em termos de desempenho. Isso fica mais bem caracterizado quando são executadas procuras complexas (Ad hoc). A utilização de ambientes distribuídos em conjunto com programação paralela é uma alternativa para redução de custo e aumento de desempenho. É apresentada, aqui, uma proposta de arquitetura de Data Warehouse distribuído, integrado ao uso de programação paralela. / This lecture proposes a solution for Data Warehouse in an distributed environment for implementation of a CRM, Customer Relationship Management in a banking system. It\'s possible to create, plan and implement relationship actions with clients. Architecture is proposed for implementation of a Data Warehouse in a distributed environment, using parallel programming. With the increase of volume of data stored in Data Warehouse, the traditional architectures needs high performance in terms of processors and input and output systems. This kind of problem is well characterized when high complex queries (Ad hoc) is performed. Using distributed environment, together with parallel programming is a good choice to increase the performance and reduce cost. It\'s presented, here, a proposal for architecture of distributed Data Warehouse, integrated with the use of parallel programming.

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.

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.

Com a disponibilidade de redes que ligam estações cada vez mais poderosas a baixos custos, o interesse em torno de ferramentas que suportam a programação paralela em arquiteturas deste tipo tem aumentado significativamente. Esta dissertação trata do projeto e implementação de YALI (Yet Another Linda Implementation), uma ferramenta destinada ao desenvolvimento e execução de programas paralelos em redes heterogêneas de computadores. Com o objetivo de oferecer uma interface simples e flexível para os usuários programadores, YALI baseia-se no modelo Linda[GEL85], que destaca-se por utilizar uma abstração de alto nível para a cooperação entre processos. Em Linda, processos interagem por intermédio de uma memória associativa logicamente compartilhada, denominada Espaço de Tuplas. Entre outras vantagens deste modelo pode-se citar a simplicidade de suas primitivas e a possibilidade de incorporá-las a uma linguagem seqüencial conhecida, o que contribui fortemente para sua fácil assimilação, mesmo por usuários com pouca experiência em programação paralela. Após uma descrição detalhada do modelo Linda, este trabalho discute varias questões envolvidas no projeto e implementação de sistemas nele baseados. Para oferecer uma visão pratica das soluções mais freqüentemente adotadas para estas questões, quatro sistemas que implementam o modelo para programação paralela em redes são apresentados e avaliados. São eles: Glenda, uma implementacao do modelo baseada na ferramenta PVM (Parallel Virtual Machine); POSYBL (PrOgramming SYstem for distriButed appLications), um sistema construído através de recursos de sistemas operacionais compatíveis com Unix; p4-Linda, construído a partir da ferramenta de programação paralela p4 e, por fim, Network-Linda, uma implementação comercial do modelo. Depois do estudo dos quatro sistemas acima, o projeto de YALI e discutido detalhadamente. Decidiu-se, inicialmente, que YALI deveria incorporar o modelo Linda a linguagem C, que é largamente utilizada no desenvolvimento de programas de propósito geral. Além disso, optou-se por estender o modelo com algumas novas primitivas, de modo a oferecer maior poder de expressão ao usuário. Basicamente, as primitivas que YALI acrescenta ao modelo servem para dar suporte a operações globais e a criação dinâmica de threads. Operações globais servem para expressar a comunicação e a sincronização entre múltiplos processos, sendo utilizadas com bastante freqüência em vários tipos de programas paralelos. YALI suporta operações globais de maneira totalmente ortogonal ao modelo Linda, garantindo melhor desempenho sem afetar o nível de abstração oferecido. o suporte a criação dinâmica de threads, por outro lado, tem o objetivo de permitir a exploração de um paralelismo de granularidade fina, adequado ate mesmo a execução de rotinas simples em paralelo. Para suportar o desenvolvimento e execução de aplicações paralelas, YALI e implementado através de três componentes distintos. O primeiro e um pré-processador, que garante uma interface simplificada com o usuário. 0 segundo e uma biblioteca, que contem as rotinas de suporte as primitivas YALI e deve ser ligada aos programas de usuários. O terceiro componente, por fim, e um utilitário destinado a controlar a inicialização e o termino de aplicações paralelas, que baseia-se em uma configuração estabelecida pelo usuário para distribuir processos sobre uma rede de computadores. Ao contrário da maioria dos sistemas baseados em Linda, YALI implementa um espaço de tuplas distribuído entre os processos que compõem uma aplicação paralela, dispensando o use de processos especializados no gerenciamento de tuplas. Para isso, YALI utiliza múltiplas threads em cada processo definido pelo usuário, e distribui tuplas sobre estes processos através de um mecanismo baseado em hashing. A implementação de YALI leva em conta a heterogeneidade inerente a ambientes de rede, permitindo que maquinas com diferentes arquiteturas e sistemas operacionais sejam utilizadas na execução de programas paralelos. Por fim, YALI é totalmente implementado a partir de recursos presentes em sistemas compatíveis com Unix, de modo a aumentar sua portabilidade e garantir sua eficiência. / With the availability of networks connecting powerful workstations at a low cost, increasing interest has been devoted to systems that support parallel programming in such architectures. This document describes the design and implementation of YALI (Yet Another Linda Implementation), a tool that allows the development and execution of parallel programs in heterogeneous computer networks. Aiming to provide a simple and flexible interface for its users, YALI is based on the Linda parallel programming model[GEL85], that outstands in providing a high level abstraction for cooperation between processes. In Linda, communication and synchronization take place through an associative, logically shared memory called Tuple Space. Among the advantages of this model, one can mention the simplicity of its primitives, and the possibility of incorporate them in a well-known sequential language. These characteristics make Linda easy to learn, even to users with little experience in parallel programming. After a detailed description of the Linda model, this document discusses some design and implementation issues related to Linda-based systems. In order to provide a practical view of some usual solutions to address these issues, four Linda-based systems are presented and evaluated. These systems are: Glenda, an implementation of Linda built on top of PVM (Parallel Virtual Machine); POSYBL (PrOgramming SYstem for distriButed appLications), that relies on features provided by Unix-like operating systems to implement the model; p4-Linda, built on top of p4 parallel programming tool and, at last, Network-Linda, a comercial product based on Linda. All these systems, as YALI, are specially tailored to parallel programming in computer networks. Following the study of the four systems, this documents presents the design of the YALI system. One of the first design decisions was to incorporate the Linda primitives to the C language, that is broadly used as a general purpose programming language. In addition, a set of new primitives was designed as an extension to the original model, in order to increase YALI's expressivenes. Basically, the new primitives support global operations and dynamic thread creation. Global operations are useful to express communication and synchronization among multiple processes, and are frequently used many classes of parallel programs. YALI gives support to global operations in a way that is totally ortoghonal to the Linda model, ensuring better performance without affecting the abstraction level inherent to Linda-based systems. The support to dynamic thread creation, on the other hand, is helpful to explore lightweight parallelism, which allows the execution of simple routines in parallel. To support the development and execution of parallel applications, YALI is made up of three distinct components. The first is a pre-processor, that provides a simple user interface. The second is a library, that must be linked to the user programs since it's where YALI primitives are actuall y implemented. Finally, the third component is an utility that controls initialization and termination of parallel applications, which takes configuration parameters from the user to distribute processes over a newtork. In contrast with most Linda-based systems, YALI relies on a tuple space that is distributed among the processes in the same parallel application, so that intermediate tuple managers are not necessary To implement that, multiple threads are embedded in each user process, and tuples are spread over the processes in the basis of a hashing mechanism. YALI's implementation takes in account the inherent heterogeneity of network environments, allowing machines with different architectures and operating systems to be used in the execution of parallel programs. Finally, YALI is build on top of common features of Unix-like operating systems, in order to increase its efficiency and portability.

Memória Transacional tem se demonstrado um paradigma promissor na implementação de aplicações concorrentes sob memória compartilhada que busquem evitar um modelo de sincronização baseado em locks. Em vez de sujeitar a execução a um acesso exclusivo com base no valor de um lock que é compartilhado por threads concorrentes, uma aplicação sob Memória Transacional tenta executar seções críticas de modo otimista, desfazendo as modificações no caso de um conflito de acesso à memória. Entretanto, apesar de a abordagem baseada em locks ter adquirido um número significativo de ferramentas automatizadas para a depuração, profiling e otimização automatizados (por ser uma das técnicas de sincronização mais antigas e mais bem pesquisadas), o campo da Memória Transacional ainda é comparativamente recente, e programadores frequentemente precisam adaptar manualmente suas aplicações transacionais ao encontrar problemas de eficiência. Este trabalho propõe um sistema no qual o profiling de código em uma implementação de Memória Transacional simulada é utilizado para caracterizar uma aplicação transacional, formando a base para uma parametrização automatizada do respectivo sistema especulativo para uma execução eficiente do código em questão. Também é proposta uma abordagem de escalonamento de threads guiado por profiling em uma implementação de Memória Transacional baseada em software, usando dados coletados pelo profiler para prever a probabilidade de conflitos e determinar que thread escalonar com base nesta previsão. São apresentados os resultados de experimentos sob ambas as abordagens. / Transactional Memory has shown itself to be a promising paradigm for the implementation of shared-memory concurrent applications that eschew a lock-based model of data synchronization. Rather than conditioning exclusive access on the value of a lock that is shared across concurrent threads, Transactional Memory attempts to execute critical sections optimistically, rolling back the modifications in the event of a data access conflict. However, while the lock-based approach has acquired a significant body of debugging, profiling and automated optimization tools (as one of the oldest and most researched synchronization techniques), the field of Transactional Memory is still comparably recent, and programmers are usually tasked with an unguided manual tuning of their transactional applications when facing efficiency problems. We propose a system in which code profiling in a simulated hardware implementation of Transactional Memory is used to characterize a transactional application, which forms the basis for the automated tuning of the underlying speculative system for the efficient execution of that particular application. We also propose a profile-guided approach to the scheduling of threads in a software-based implementation of Transactional Memory, using collected data to predict the likelihood of conflicts and determine what thread to schedule based on this prediction. We present the results achieved under both designs.

Les techniques de programmations pour le calcul de haute performanceont adopté les modèles basés sur parallélisme de tâche qui sontcapables de s’adapter plus facilement à des superordinateurs avec desarchitectures hybrides. La performance des applications basées surtâches dépende fortement des heuristiques d'ordonnancement dynamiqueset de sa capacité à exploiter les ressources de calcul et decommunication.Malheureusement, les stratégies d'analyse de performancetraditionnelles ne sont pas convenables pour comprendre les supportsd'exécution dynamiques et les applications basées sur tâches. Cesstratégies prévoient un comportement régulier avec des phases decalcul et de communication, par contre, des applications basées surtâches ne manifestent pas de phases précises. Par ailleurs, la granularitéplus fine des applications basées sur tâches typiquement provoque descomportements stochastiques qui donnent lieu aux structuresirrégulières qui sont difficiles à analyser.Dans cette thèse, nous proposons des stratégies d'analyse deperformance qui exploitent la combinaison de la structure del'application, d'ordonnancement et des informations de laplate-forme. Nous présentons comment nos stratégies peuvent aider àcomprendre des problèmes de performance dans des applications baséesur tâches qui exécutent dans des plates-formes hybrides. Nosstratégies d'analyse de performance sont construites avec des outilsmodernes pour l'analyse de données, ce que permettre la création despanneaux de visualisation personnalisés. Ces panneaux permettent lacompréhension et l'identification de problèmes de performancesoccasionnés par de mauvaises décisions d'ordonnancement etconfiguration incorrect du support d'exécution et de laplate-forme. Grâce à combinaison de simulation et débogage nouspouvons aussi construire une représentation visuelle de l'état interneet des estimations calculées par l'ordonnancer durant l'ordonnancementd'une nouvelle tâche.Nous validons notre proposition parmi de l'analyse de tracesd'exécutions d'une factorisation de Cholesky implémenté avec lesupport d'exécution StarPU et exécutée dans une plate-forme hybride(CPU/GPU). Nos études de cas montrent comment améliorer la partitiondes tâches entre le multi-(GPU, coeur) pour s'approcher des bornesinférieures théoriques, comment améliorer le pipeline des opérationsMPI entre le multi-(noeud, coeur, GPU) pour réduire le démarrage lentedans les noeuds distribués et comment optimiser le support d'exécutionpour augmenter la bande passante MPI. Avec l'emploi des stratégies desimulation et débogage, nous fournissons un workflow pourl'examiner, en détail, les décisions d'ordonnancement. Cela permet deproposer des changements pour améliorer les mécanismes d'ordonnancementet prefetch du support d'exécution. / Programming paradigms in High-Performance Computing have been shiftingtoward task-based models that are capable of adapting readily toheterogeneous and scalable supercomputers. The performance oftask-based applications heavily depends on the runtime schedulingheuristics and on its ability to exploit computing and communicationresources.Unfortunately, the traditional performance analysis strategies areunfit to fully understand task-based runtime systems and applications:they expect a regular behavior with communication and computationphases, while task-based applications demonstrate no clearphases. Moreover, the finer granularity of task-based applicationstypically induces a stochastic behavior that leads to irregularstructures that are difficult to analyze.In this thesis, we propose performance analysis strategies thatexploit the combination of application structure, scheduler, andhardware information. We show how our strategies can help tounderstand performance issues of task-based applications running onhybrid platforms. Our performance analysis strategies are built on topof modern data analysis tools, enabling the creation of customvisualization panels that allow understanding and pinpointingperformance problems incurred by bad scheduling decisions andincorrect runtime system and platform configuration.By combining simulation and debugging we are also able to build a visualrepresentation of the internal state and the estimations computed bythe scheduler when scheduling a new task.We validate our proposal by analyzing traces from a Choleskydecomposition implemented with the StarPU task-based runtime systemand running on hybrid (CPU/GPU) platforms. Our case studies show howto enhance the task partitioning among the multi-(GPU, core) to getcloser to theoretical lower bounds, how to improve MPI pipelining inmulti-(node, core, GPU) to reduce the slow start in distributed nodesand how to upgrade the runtime system to increase MPI bandwidth. Byemploying simulation and debugging strategies, we also provide aworkflow to investigate, in depth, assumptions concerning the schedulerdecisions. This allows us to suggest changes to improve the runtimesystem scheduling and prefetch mechanisms.

This is a problem of sampling. The number of classical states of an N-body system grows with O( 3 ^ N ). To sample this space, advanced techniques are required. Replica Exchange (RE), also known as parallel tempering, is an example that uses parallelization, and Hamiltonian Replica Exchange is a subset of RE that scales the energy of the replicas. The number of simulations required grows at O( N^(1/2) ), where N is number of atoms in the system. Replica Exchange with Dynamical Scaling (REDS) attempts to address this problem to decrease computational cost. It has been shown to increase efficiency 10-fold. We implemented REDS in GROMACS 2018. (Abraham 2015) All changes to the source code were written in the form of parallel methods. Scripts were written in Python and Perl to automate the experiment entirely. An exchange connects a region of high energy space, far above the surface of the landscape, to low energy space, which approaches the surface of the landscape, which represents the natural conformational progression of the molecule. Using REDS we were able to achieve exchanges at temperatures spaced too far apart to exchange using normal RE. Ergo, the flexibility of dynamical scaling allowed regions of phase space that would have gone unsampled to be mapped, addressing our initial problem of sampling.