Data access is an essential part of any program, and is especially critical to the performance of parallel computing systems. The objective of this work is to investigate factors that affect data access parallelism in parallel computing systems, and design/evaluate methods to improve such parallelism - and thereby improving the performance of corresponding parallel systems. We focus on data access contention and network resource contention in representative parallel and distributed systems, including transactional memory system, Geo-replicated transactional systems and MapReduce systems. These systems represent two widely-adopted abstractions for parallel data accesses: transaction-based and distributed-system-based. In this thesis, we present methods to analyze and mitigate the two contention issues. We first study the data contention problem in transactional memory systems. In particular, we present a queueing-based model to evaluate the impact of data contention with respect to various system configurations and workload parameters. We further propose a profiling-based adaptive contention management approach to choose an optimal policy across different benchmarks and system platforms. We further develop several analytical models to study the design of transactional systems when they are Geo-replicated. For the network resource contention issue, we focus on data accesses in distributed systems and study opportunities to improve upon the current state-of-art MapReduce systems. We extend the system to better support map task locality for dual-map-input applications. We also study a strategy that groups input blocks within a few racks to balance the locality of map and reduce tasks. Experiments show that both mechanisms significantly reduce off-rack data communication and thus alleviate the resource contention on top-rack switch and reduce job execution time. In this thesis, we show that both the data contention and the network resource contention issues are key to the performance of transactional and distributed data access abstraction and our mechanisms to estimate and mitigate such problems are effective. We expect our approaches to provide useful insight on future development and research for similar data access abstractions and distributed systems.

Stream programming is a paradigm where a program is structured by a set of computational nodes connected by streams. Focusing on data moving between computational nodes via streams, this programming model fits well for applications that process long sequences of data. We call such applications reactive stream programs (RSPs) to distinguish them from stream programs with rather small and finite input data. In stream programming, concurrency is expressed implicitly via communication streams. This helps to reduce the complexity of parallel programming. For this reason, stream programming has gained popularity as a programming model for parallel platforms. However, it is also challenging to analyse and improve the performance without an understanding of the program's internal behaviour. This thesis targets an effi cient execution model for deploying RSPs on parallel platforms. This execution model includes a monitoring framework to understand the internal behaviour of RSPs, scheduling strategies for RSPs on uniform shared-memory platforms; and mapping techniques for deploying RSPs on heterogeneous distributed platforms. The foundation of the execution model is based on a study of the performance of RSPs in terms of throughput and latency. This study includes quantitative formulae for throughput and latency; and the identification of factors that influence these performance metrics. Based on the study of RSP performance, this thesis exploits characteristics of RSPs to derive effective scheduling strategies on uniform shared-memory platforms. Aiming to optimise both throughput and latency, these scheduling strategies are implemented in two heuristic-based schedulers. Both of them are designed to be centralised to provide load balancing for RSPs with dynamic behaviour as well as dynamic structures. The first one uses the notion of positive and negative data demands on each stream to determine the scheduling priorities. This scheduler is independent from the runtime system. The second one requires the runtime system to provide the position information for each computational node in the RSP; and uses that to decide the scheduling priorities. Our experiments show that both schedulers provides similar performance while being significantly better than a reference implementation without dynamic load balancing. Also based on the study of RSP performance, we present in this thesis two new heuristic partitioning algorithms which are used to map RSPs onto heterogeneous distributed platforms. These are Kernighan-Lin Adaptation (KLA) and Congestion Avoidance (CA), where the main objective is to optimise the throughput. This is a multi-parameter optimisation problem where existing graph partitioning algorithms are not applicable. Compared to the generic meta-heuristic Simulated Annealing algorithm, both proposed algorithms achieve equally good or better results. KLA is faster for small benchmarks while slower for large ones. In contrast, CA is always orders of magnitudes faster even for very large benchmarks.

Made available in DSpace on 2014-12-17T14:55:11Z (GMT). No. of bitstreams: 1 JoaoPQS.pdf: 1464588 bytes, checksum: ad1e7b6af306b0ce9b1ccb1fb510c4ab (MD5) Previous issue date: 2009-03-06 / The metaheuristics techiniques are known to solve optimization problems classified as NP-complete and are successful in obtaining good quality solutions. They use non-deterministic approaches to generate solutions that are close to the optimal, without the guarantee of finding the global optimum. Motivated by the difficulties in the resolution of these problems, this work proposes the development of parallel hybrid methods using the reinforcement learning, the metaheuristics GRASP and Genetic Algorithms. With the use of these techniques, we aim to contribute to improved efficiency in obtaining efficient solutions. In this case, instead of using the Q-learning algorithm by reinforcement learning, just as a technique for generating the initial solutions of metaheuristics, we use it in a cooperative and competitive approach with the Genetic Algorithm and GRASP, in an parallel implementation. In this context, was possible to verify that the implementations in this study showed satisfactory results, in both strategies, that is, in cooperation and competition between them and the cooperation and competition between groups. In some instances were found the global optimum, in others theses implementations reach close to it. In this sense was an analyze of the performance for this proposed approach was done and it shows a good performance on the requeriments that prove the efficiency and speedup (gain in speed with the parallel processing) of the implementations performed / As metaheur?sticas s?o t?cnicas conhecidas para a resolu??o de problemas de otimiza??o, classificados como NP-Completos e v?m obtendo sucesso em solu??es aproximadas de boa qualidade. Elas fazem uso de abordagens n?o determin?sticas que geram solu??es que se aproximam do ?timo, mas no entanto, sem a garantia de que se encontre o ?timo global. Motivado pelas dificuldades em torno da resolu??o destes problemas, este trabalho prop?s o desenvolvimento de m?todos paralelos h?bridos utilizando a aprendizagem por refor?o e as metaheur?sticas GRASP e Algoritmos Gen?ticos. Com a utiliza??o dessas t?cnicas em conjunto, objetivou-se ent?o, contribuir na obten??o de solu??es mais eficientes. Neste caso, ao inv?s de utilizar o algoritmo Q-learning da aprendizagem por refor?o, apenas como t?cnica de gera??o das solu??es iniciais das metaheur?sticas, este tamb?m aplicado de forma cooperativa e competitiva com o Algoritmo Gen?tico e o GRASP, em uma implementa??o paralela. Neste contexto, foi poss?vel verificar que as implementa??es realizadas neste trabalho apresentaram resultados satisfat?rios, tanto na parte de coopera??o e competi??o entre os algoritmos Q-learning, GRASP a Algoritmos Gen?ticos, quanto na parte de coopera??o e competi??o entre grupos destes tr?s algoritmos. Em algumas inst?ncias foi encontrado o ?timo global; quando n?o encontrado, conseguiu-se chegar bem pr?ximo de seu valor. Neste sentido foi realizada uma an?lise do desempenho da abordagem proposta e verificou-se um bom comportamento em rela??o aos quesitos que comprovam a efici?ncia e o speedup (ganho de velocidade com o processamento paralelo) das implementa??es realizadas

Die Informatik ist von besonderer Bedeutung für die Gestaltung unser alltäglichen Lebensumstände und ist eine Schlüsseltechnologie des 21. Jahrhunderts. Die Fakultät für Informatik vertritt dieses Fachgebiet umfassend und kompetent mit anwendungsorientierten Schwerpunktsetzungen. In unseren Forschungsschwerpunkten - Eingebettete selbstorganisierende Systeme - Intelligente multimediale Systeme - Parallele verteilte Systeme bieten wir international wettbewerbsfähige Forschung und Entwicklung zu aktuellen Problemstellungen. Unsere Lehre basiert auf dem Leitmotiv der beständigen Erneuerung aus der Forschung. Hieraus abgeleitet bieten wir zeitgemäße Bachelor- und Masterstudiengänge mit hervorragenden Studienbedingungen. Die Fakultät hat den Anspruch eines möglichst persönlichen Umgangs zwischen Lehrkörper und Studenten. Mit der Schriftenreihe „Chemnitzer Informatik Berichte“ geben wir Einblicke in die Forschungspraxis der Fakultät. Dabei werden unterschiedliche Forschungsthemen aus den drei Forschungsschwerpunkten und allen Professuren der Fakultät vorgestellt. / Computer science, as a key technology of the 21th century, has an exceptional impact on our everyday life and living standards. The Faculty of Computer Science represents this scientific field in a comprehensive and proficient manner with an application-orientated choice of topics. In the fields of - Embedded and self-organizing systems - Intelligent multimedia systems - Parallel and distributed systems we offer research and development for current problems and challenges on an internationally competitive level. The guiding principle of our education is the continuous innovation through advances in research. Consequently, we are able to provide modern Bachelor and Master programs with excellent academic conditions. The faculty strives to provide a maximally personal interaction between students and staff. With the series of publications „Chemnitz Computer Science Reports“ we give insigths into the reasearch practice of the faculty. We present different subjects of research from the tree research fields and all of the professorships of the Faculty of Computer Science.