The increasing prevalence of multi and many core processors has brought the issues of concurrency and parallelism to the forefront of everyday computing. Even for applications amenable to traditional parallelization techniques, the subtleties of concurrent programming are known to introduce concurrency bugs. Due to the potential of concurrency bugs, programmers find it hard to write correct concurrent code. To take full advantage of parallel shared memory platforms, application programmers need safe and efficient mechanisms that can support a wide range of parallel applications. In addition, a large body of applications are inherently hard-to-parallelize; their data and control dependencies impose execution order constraints that preclude the use of traditional parallelization techniques. Sensitive to their input data, a substantial number of applications fail to scale well, leaving cores idle. To improve the performance of such applications, application programmers need effective mechanisms that can fully leverage multi and many core architectures. These challenges stand in the way of realizing the true potential of emerging many core platforms. The techniques described in this dissertation address these challenges. Specifically, this dissertation contributes techniques to transparently detect and eliminate several concurrency bugs, including deadlocks, asymmetric write-write data races, priority inversion, live-locks, order violations, and bugs that stem from the presence of asynchronous signaling and locks. A second major contribution of this dissertation is a programming framework that exploits coarse-grain speculative parallelism to improve the performance of otherwise hard-to-parallelize applications. / Ph. D.

Model checking is a technique used to verify whether a model meets a given specification by exhaustively and automatically checking each reachable state in the model. It is a well-developed technique, but it suffers from some issues, perhaps most importantly the state space explosion problem. Models may contain so many states that must be checked means that the model checking procedure may be intractable. In this thesis we investigate whether procedure summaries can be used to improve the performance of model checking. Procedure summaries are concise representations of parts of a program, such as a function or method. We present a design and an implementation of dynamically generated summaries as an extension of Java PathFinder, a virtual machine executing Java bytecode that is able to model check programs written in Java by backtracking execution, to explore different schedulings etc. We find that our summaries incur an overhead that outweighs the benefits in most cases, but the approach shows promise in certain cases, in particular when stateless model checking is used. We also provide some statistics related to cases when our summaries are applicable that could provide guidance for future work within this field. / Model checking, eller modellkontroll, är en välkänd teknik inom programverifikation som används för att verifiera att en modell, ofta av ett program, uppfyller en given specifikation genom att undersöka alla nåbara tillstånd i modellen. Det är en välutvecklad teknik som lider av några brister, en av de viktigaste är det så kallade state space explosion-problemet. Modellerna kan bestå av så många olika tillstånd att \textit{model checking} inte går att använda. I den här rapporten undersöker vi om vi kan tillämpa så kallade procedur-sammanfattningar för att förbättra prestandan av model checking. Procedur-sammanfattningar är representationer av delar av program, till exempel metoder eller funktioner. Vi presenterar en design och implementation av dynamiskt genererade sammanfattningar i form av ett tillägg till Java PathFinder, en virtuell maskin som exekverar Java bytecode som kan utföra model checking genom att backa körningar för att till exempel utforska olika schemaläggningar. Våra procedur-sammanfattningar har i många fall en negativ effekt på körtid, men visar på lovande resultat i vissa fall, i synnerhet när så kallad stateless model checking används. Vi presenterar också resultat kopplat till fall när våra sammanfattningar är applicerbara som kan leda vägen för fortsatt arbete inom området.

Este trabalho apresenta a implementação e a utilização da migração de processos SPMD (Single Program Multiple Data), a qual realiza somente a transferência dos dados, que estão sendo manipulados pelo processo, para realizar a migração. Seu principal objetivo foi o estudo do impacto do balanceamento de carga no desempenho de aplicações, desenvolvidas utilizando o modelo de programação SPMD. Depois de realizados testes com aplicações SPMD reais, em sistemas computacionais distribuídos utilizando a migração de processos SPMD, foi possível verificar que ganhos de desempenho podem ser alcançados, tanto na migração de processos quanto no tempo de execução de aplicações paralelas SPMD. / This research presents the implementation and use of the SPMD (Single Program Multiple Data) process migration, which only does the transference of the data that are being used by the process, to perform the process migration. Its main objective was the study of the load balancing impact in the performance of applications developed using the SPMD programming model. After performing the tests with real SPMD applications, in distributed computational systems using the SPMD process migration, it was achieved good performance gains, both in the process migration and in the time execution of applications SPMD parallel applications.

Contexto: Embora diversas técnicas de teste de software tenham sido propostas para o contexto da programação concorrente, as informações sobre elas encontram-se de dispersas na literatura, não oferecendo uma caracterização apropriada e dados relevantes que possam auxiliar a compreensão e consequente aplicação efetiva dessas técnicas, dificultando o processo de transferência de conhecimento entre a academia e a comunidade interessada. Objetivo: Nesse contexto, o principal objetivo deste trabalho é oferecer subsídios, na forma de um framework, que seja capaz de apoiar a caracterização e seleção sistemática de técnicas de teste de software concorrente. Metodologia: Para atender esse objetivo, foi construído um corpo de conhecimento que reúne de maneira integrada informações relevantes ao processo de tomada de decisão sobre qual técnica de teste aplicar a um determinado projeto de software. Um design de experimentos é definido, funcionando como guia para condução de estudos empíricos que podem ser usados para a realimentação, atualização e evolução do corpo de conhecimento. Buscando sistematizar o processo de seleção de técnicas de teste, é definido um esquema de caracterização que considera as principais características da programação concorrente que influenciam a atividade de teste de software e calcula a adequação desses atributos aos atributos do projeto em desenvolvimento. Resultados e Conclusões: A fim de permitir que a comunidade interaja com o framework proposto, foi disponibilizada uma infraestrutura computacional que permite o acesso ao corpo de conhecimento e automatiza o processo de seleção de técnicas de teste de software concorrente. O estudo experimental conduzido para avaliação da proposta, mostrou que a abordagem contribui de maneira efetiva para caracterizar, comparar e quantificar a adequabilidade baseada em atributos, melhorando consideravelmente o processo de seleção de técnicas de teste para software concorrente segundo as expectativas dos usuários. / Background: Although a variety of concurrent software testing techniques have been proposed for the concurrent programming context, the information about them are scattered in the literature, not offering an appropriate characterization and relevant data that can aid the understanding and consequently the effective application of these techniques, hindering the process of knowledge transfer between the academia and the interested community. Objective: In this context, the main objective of this work is to provide subsidies in form of a framework which will be able to support the characterization and systematic selection of concurrent software testing techniques. Methodology: In order to meet this objective, a body of knowledge has been built that brings together, in an integrated way, information relevant for the decision-making process about what testing technique should be applied in a specific software project. A design of experiments is defined as a guide for conducting empirical studies that can be used for feedback, updating, and evolution of the body of knowledge. With the objective of systematizing the process of testing techniques selection is defined a characterization scheme that considers the main characteristics of the concurrent programming that influence the testing activity and calculates the adequacy for these attributes in comparison with the software project in development. Results and Conclusions: In order to allow the community interaction with the proposed framework was provided a computational infrastructure that allows access to the body of knowledge and the automation of the selection process. The empirical study conducted to evaluate the proposal showed that the approach effectively contributes to characterize, compare and quantify the adequacy based on the attributes, improving the selection process of concurrent software testing techniques according to the users expectations.

Concurrent programming has become an essential paradigm for reductions in the computational time in many application domains. However, the validation and testing activity is more complex than the testing for sequential programs due to the non-determinism, synchronization and inter-process communication. Mutation testing is based on mistakes produced by software developers and presents a high effectiveness to reveal faults. However, high computational costs limit its applicability even for sequential code, becoming higher for concurrent programs in which each test has to be executed with different (ideally all) thread schedules. To date, only selective mutation have been applied to reduce the number of mutants in concurrent programs, however, the problem of state explosion of thread schedules still remains. This Ph.D. thesis presents the SBBMuT approach that applies deterministic execution and genetic algorithm for the generation and execution of a set of synchronization sequences during the mutation testing of Java multithreaded programs. An experimental study was conducted, and the results showed that the set of synchronization sequences generated by SBBMuT achieved a higher mutation score in comparison with the use of the Java PathFinder model checking tool. / A programação concorrente tornou-se um paradigma essencial para a redução no tempo computacional em muitos domínios de aplicação. No entanto, as atividades de verificação, validação e teste são mais complexas do que o teste para programas sequenciais devido ao não determinismo, sincronização e comunicação entre processos ou threads. O teste de mutação é baseado em enganos cometidos por desenvolvedores de software e apresenta uma alta eficácia para revelar defeitos. No entanto, o alto custo computacional limita a sua aplicação mesmo para programas sequenciais, e tornando-se maior para programas concorrentes no qual cada teste deve ser executado com diferentes (idealmente todas) sequências de sincronizações. Na literatura, apenas mutação seletiva foi aplicada para reduzir o número de mutantes em programas concorrentes, no entanto, o problema de explosão no número de sequências de sincronização ainda permanece. Esta tese de doutorado apresenta a abordagem SBBMuT que aplica execução determinística e algoritmo genético para a geração e execução de um conjunto de sequências de sincronização durante o teste de mutação para programas Java multithread. Um estudo experimental foi conduzido e os resultados mostram que o conjunto de sequências de sincronização gerada pela SBBMuT conseguiu alcançar um escore de mutação maior em comparação com a utilização da ferramenta de validação de modelos Java PathFinder.

Existem várias linguagens e plataformas que permitem a programação baseada no modelo de atores, uma solução elegante para a programação concorrente proposta há algumas décadas. Segundo esse modelo, implementa-se o programa na forma de uma série de agentes que são executados em paralelo e se comunicam entre si somente por meio da troca de mensagens, sem a necessidade de memória compartilhada ou estruturas tradicionais de sincronização como semáforos e mutexes. Uma das áreas nas quais esse modelo seria particularmente adequado é a programação de aplicações web, isto é, aplicações cujas lógicas de negócios e de dados residem num servidor e que são acessadas pelo usuário por intermédio de um navegador. Porém, existem muitos obstáculos ao desenvolvimento de aplicações desse tipo, entre eles a falta de linguagens e ferramentas que permitam integrar tanto o servidor quanto o cliente (navegador) no modelo de atores, as dificuldades de conversões de dados que se fazem necessárias quando o servidor e o cliente são desenvolvidos em linguagens diferentes, e a necessidade de contornar as dificuldades inerentes aos detalhes do protocolo de comunicação (HTTP). O PAWEB é uma proposta de uma plataforma para o desenvolvimento e execução de aplicações web que fornece a infraestrutura necessária para que tanto o lado cliente quanto o lado servidor do aplicativo hospedado possam ser escritos numa mesma linguagem (Python), e possam criar e gerenciar atores que trocam mensagens entre si,tanto local quanto remotamente, de maneira transparente e sem a necessidade de implementar conversões de dados ou outros detalhes de baixo nível. / There are several programming languages and platforms that allow the development of systems based on the actor model, an elegant solution for concurrent programming proposed a few decades ago. According to this model, the program is implemented in the form of several agents that run concurrently and only communicate amongst themselves through the exchange of messages, without the need for shared memory or traditional synchronization structures such as semaphores and mutexes. One of the areas where this model would be particularly appropriate would be the development of web applications, that is, applications whose business and database logic reside on the server and are accessed by the user by means of a web browser. However, there are several obstacles to the development of this type of application, amongst them the lack of languages and tools that allow for the integration of both the server and the client (browser) into the actor model, data conversion difficulties arising from using different programming languages on the server and the client, and the need to circumvent the inherent difficulties posed by the details of the communications protocol (HTTP). PAWEB is a proposal for an application development and execution platform that supplies the infrastructure needed so that both the server and client sides of the hosted application can be written in the same language (Python) and so that they may create and manage actors that exchange messages with one another, both locally and remotely, in a transparent manner and without the need to implement data conversions or other low-level mechanisms.

The challenge this thesis addresses is to speed up the development of concurrent programs by increasing the efficiency with which concurrent programs can be tested and consequently evolved. The goal of this thesis is to generate methods and tools that help software engineers increase confidence in the correct operation of their programs. To achieve this goal, this thesis advocates testing of concurrent software using a systematic approach capable of enumerating possible executions of a concurrent program. The practicality of the systematic testing approach is demonstrated by presenting a novel software infrastructure that repeatedly executes a program test, controlling the order in which concurrent events happen so that different behaviors can be explored across different test executions. By doing so, systematic testing circumvents the limitations of traditional ad-hoc testing, which relies on chance to discover concurrency errors. However, the idea of systematic testing alone does not quite solve the problem of concurrent software testing. The combinatorial nature of the number of ways in which concurrent events of a program can execute causes an explosion of the number of possible interleavings of these events, a problem referred to as state space explosion. To address the state space explosion problem, this thesis studies techniques for quantifying the extent of state space explosion and explores several directions for mitigating state space explosion: parallel state space exploration, restricted runtime scheduling, and abstraction reduction. In the course of its research exploration, this thesis pushes the practical limits of systematic testing by orders of magnitude, scaling systematic testing to real-world programs of unprecedented complexity.

Orientador também citado por: CASTOR FILHO, Fernando / Submitted by Rafael Santana (rafael.silvasantana@ufpe.br) on 2017-05-04T19:07:33Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) dissertacao-final.pdf: 950190 bytes, checksum: 71ffd939c48d9c920666a09a05dc0c53 (MD5) / Made available in DSpace on 2017-05-04T19:07:33Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) dissertacao-final.pdf: 950190 bytes, checksum: 71ffd939c48d9c920666a09a05dc0c53 (MD5) Previous issue date: 2016-09-06 / Energy-efficiency has concerned hardware and low-level software designers for years. However, the rapid proliferation of battery-powered mobile devices combined with the growing worldwide movement towards sustainability have caused developers and researchers to study the energy impact of application software in execution. Recent work has studied the effect that factors such as code obfuscation, object-oriented refactorings, and data types have on energy efficiency. In this work, we attempt to shed light on the energy behavior of concurrent programs written in a purely functional language, Haskell. We conducted an empirical study to assess the performance and energy behavior of three different thread management approaches and three primitives for concurrency control using nine different benchmarks with an experimental space exploration of more than 400 configurations. In this study, we found out that small changes can make a big difference in terms of energy consumption. For instance, in one of our benchmarks, under a specific configuration, choosing one concurrency control primitive (MVar) over another (TMVar) can yield 60% energy savings. Also, the relationship between energy consumption and performance is not always clear. We found scenarios where the configuration with the best performance also exhibited the worst energy consumption. To support developers in better understanding this complex relationship, we have extended two existing performance analysis tools also to collect and present data about energy consumption. In addition, based on the results of our empirical study, we provide a list of guidelines for developers with good practices for writing energy-efficient code in this environment. / Há anos eficiência energética é uma preocupação para designers de hardware e software baixonível. Entretanto, a rápida proliferação de dispositivos móveis alimentados por bateria combinado com o crescente movimento global em busca de sustentabilidade tem motivado desenvolvedores e pesquisadores a estudar o impacto energético de softwares de aplicação em execução. Trabalhos recentes tem estudado o efeito que fatores como obsfucação de código, refatorações em linguagem orientadas à objetos e tipos de dados tem em eficiência energética. Este trabalho tenta lançar luz sobre o comportamento energético de programas concorrentes escritos em uma linguagem puramente funcional, Haskell. Nós conduzimos um estudo empírico para avaliar o desempenho e o comportamento energético de três diferentes abordagens para gerenciamento de threads e três primitivas para controle de concorrência usando nove diferentes benchmarks com um espaço de exploração experimental de mais de 400 configurações. Neste estudo, descobrimos que pequenas mudanças podem fazer uma grande diferença em termos de consumo de energia. Por exemplo, em um dos benchmarks, sob uma configuração específica, escolher uma primitiva de controle de concorrência (MVar) ao invés de outra (TMVar) pode acarretar em uma economia de 60% em consumo de energia. Percebemos também que nem sempre a relação entre consumo de energia e desempenho é clara. Em alguns cenários analisados, a configuração com melhor desempenho também apresentou o pior consumo de energia. Para ajudar desenvolvedores a entender melhor essa complexa relação, nós estendemos duas ferramentas de análise de desempenho existentes para coletar e apresentar dados sobre consumo de energia. Adicionalmente, baseado nos resultados do nosso estudo empírico, listamos um conjunto de recomendações para desenvolvedores com boas práticas de como escrever código energeticamente eficiente nesse ambiente.

Este trabalho apresenta a implementação e a utilização da migração de processos SPMD (Single Program Multiple Data), a qual realiza somente a transferência dos dados, que estão sendo manipulados pelo processo, para realizar a migração. Seu principal objetivo foi o estudo do impacto do balanceamento de carga no desempenho de aplicações, desenvolvidas utilizando o modelo de programação SPMD. Depois de realizados testes com aplicações SPMD reais, em sistemas computacionais distribuídos utilizando a migração de processos SPMD, foi possível verificar que ganhos de desempenho podem ser alcançados, tanto na migração de processos quanto no tempo de execução de aplicações paralelas SPMD. / This research presents the implementation and use of the SPMD (Single Program Multiple Data) process migration, which only does the transference of the data that are being used by the process, to perform the process migration. Its main objective was the study of the load balancing impact in the performance of applications developed using the SPMD programming model. After performing the tests with real SPMD applications, in distributed computational systems using the SPMD process migration, it was achieved good performance gains, both in the process migration and in the time execution of applications SPMD parallel applications.

No description available.