Les architectures multicœurs changent notre façon d'écrire des programmes. L'écriture de programmes concurrents est bien connue pour être difficile. Traditionnellement, l'utilisation de verrous (locks) permettant au code de s'exécuter en exclusion mutuelle, a été l'abstraction la plus largement utilisée pour l'écriture des programmes concurrents. Malheureusement, il est difficile d'écrire des programmes concurrents efficaces et corrects reposant sur des verrous. En outre, les verrous présentent d'autres problèmes, notamment celui du passage à l'échelle. Le concept de mémoire transactionnelle a été proposé comme une solution à ces difficultés. Les transactions peuvent être considérées comme une abstraction de haut niveau, ou une méthodologie pour l'écriture de programmes concurrents, ce qui permet au programmeur de pouvoir déclarer des sections de code devant être exécutés de façon atomique, sans avoir à se soucier des détails de synchronisation. Malheureusement, bien qu'assurément plus facile à utiliser que les verrous, la mémoire transactionnelle souffre encore de problèmes de performance et de facilité d'utilisation. En fait, de nombreux concepts relatifs à l'utilisation et à la sémantique des transactions n'ont pas encore des normes convenues. Cette thèse propose de nouvelles solutions permettant de faciliter l'utilisation des mémoires transactionellles. La thèse débute par un chapitre qui donne un bref aperçu de la mémoire transactionnelle logicielle (STM) ainsi qu'une discussion sur le problème de la facilité d'utilisation. Les contributions à la recherche sont ensuite divisées en quatre chapitres principaux, chacun proposant une approche différente afin de rendre les STMs plus facile à utiliser. / Multicore architectures are changing the way we write programs. Writing concurrent programs is well known to be difficult task. Traditionally, the use of locks allowing code to execute in mutual exclusion has been the most widely used abstraction to write concurrent programs. Unfortunately, using locks it is difficult to write correct concurrent programs that perform efficiently. Additionally, locks present other problems such as scalability issues. Transactional memory has been proposed as a possible promising solution to these difficulties of writing concurrent programs. Transactions can be viewed as a high level abstraction or methodology for writing concurrent programs, allowing the programmer to be able to declare what sections of his code should be executed atomically, without having to worry about synchronization details. Unfortunately, although arguably easier to use then locks, transactional memory still suffers from performance and ease of use problems. In fact many concepts surrounding the usage and semantics of transactions have no widely agreed upon standards. This thesis specifically focuses on these ease of use problems by discussing how previous research has dealt with them and proposing new solutions putting ease of use first. The thesis starts with a chapter giving a brief overview of software transactional memory (STM) as well as a discussion of the problem of ease of use that is focused on in the later chapters. The research contributions are then divided into four main chapters, each looking at different approaches working towards making transactional memory easier to use.

O teste de programas concorrentes e uma atividade desaadora, devido a fatores que não estão presentes em programas sequenciais, como comunicação, sincronização e não determinismo. Algumas técnicas de teste têm sido propostas para o contexto de programação concorrente, mas raramente sua aplicabilidade e avaliada por estudos teóricos ou experimentais. Este trabalho contribui nesse sentido, propondo e conduzindo um estudo experimental para avaliar o custo, eficácia e aspecto complementar dos critérios de teste estruturais para programas concorrentes no contexto de memória compartilhada, implementados usando o padrão PThreads (Posix Threads). A ferramenta de teste ValiPThread e usada para auxiliar a condução do experimento. Os programas usados no experimento foram selecionados de benchmarks, como o Inspect, Helgrind e Rungta. Esses benchmarks são comumente usados no estudo de técnicas de teste para programas concorrentes. Programas que resolvem problemas clássicos da programação concorrente também foram incluídos no estudo. Com base nos resultados obtidos foi definida uma estratégia de aplicação, considerando aspectos de custo e eficácia dos critérios de teste. Além disso, todo o material utilizado e gerado durante o experimento foi reunido em um pacote de laboratório, a fim de contribuir com a comunidade de pesquisa, possibilitando replicações e comparações desses critérios com outras técnicas de teste no contexto de programas concorrentes / Concurrent program testing is a challenging activity due to the communication, synchronization and nondeterminism of this application domain. Despite that, some testing techniques for concurrent programs have been proposed, but their applicability is rarely evaluated by theoretical or experimental studies. This work contributes in this direction proposing and conducting an experimental study to evaluate the cost, effectiveness and strength of structural testing criteria for multithreaded programs, implemented using the Pthreads standard (POSIX Threads). The testing tool ValiPThread is used to support the conduction of the experiment. The programs used in this experiment were selected from classical benchmarks, such as Inspect, Helgring and Rungta. These benchmarks are commonly used to study testing techniques for concurrent programs. We also include programs that solve concurrent classical problems. Based on the obtained results, we defined an application testing strategy, considering cost and effectiveness aspects of the testing criteria. Furthermore, all material used and generated during the experiment was incorporated in a lab package, in order to contribute with further research studies making possible replications and comparisons of these testing criteria with other testing techniques in context of concurrent programs

In this thesis, we present a simple and efficient automated analysis tool called DoSSO that detects shared objects in multithreaded Java programs. DoSSO reports only the shared objects that are modified by at least one thread. Based on this tool, we propose a new approach in developing concurrent software where programmers implement the system without considering synchronization issues first and then use appropriate locking mechanism only for the objects reported by DoSSO. To evaluate the applicability of DoSSO, we have conducted a case study on a distributed and concurrent system with graphical user interfaces. Case study results showed that DoSSO is able to identify objects that become shared among explicitly defined threads and event threads, and objects that become shared through RMI.

Una característica fundamental de los sistemas de software es que se construyen desde el principio sabiendo que deberán incorporar cambios a lo largo de su ciclo de vida. Todos los libros que tratan sobre ingeniería de software coinciden en que los sistemas son evolutivos. Incluso al evaluar el esfuerzo que se debe invertir en un proyecto de software, se considera que un 20% está en el desarrollo y 80% se aplica al mantenimiento (Pfleeger & Atlee, 2009). Ian Sommerville estima que el 17% del esfuerzo de mantenimiento se invierte en localizar y eliminar los posibles defectos de los programas (Sommerville, 2006). Por ello, conseguir programas libres de errores es uno de los principales objetivos que se plantea (o se debería plantear) el desarrollador frente a cualquier proyecto de software. Por otro lado, las limitaciones a la integración impuestas por factores físicos como son la temperatura y el consumo de energía, se han traducido en la integración de unidades de cómputo en un único chip, dando lugar a los procesadores de múltiples núcleos. Para obtener la máxima eficiencia de estas arquitecturas, es necesario el desarrollo de programas concurrentes (Grama, Gupta, Karypis, & Kumar, 2003). A diferencia de los programas secuenciales, en un programa concurrente existen múltiples hilos en ejecución accediendo a datos compartidos. El orden en que ocurren estos accesos a memoria puede variar entre ejecuciones, haciendo que los errores sean más difíciles de detectar y corregir. En cómputo de altas prestaciones donde los tiempos de ejecución de las aplicaciones pueden variar de un par de horas hasta días, la presencia de un error no detectado en la etapa de desarrollo adquiere una importancia mayor. Por este motivo, resulta indispensable contar con herramientas que ayuden al programador en la tarea de verificar los algoritmos concurrentes y desarrollar tecnología robusta para tolerar los errores no detectados. En este contexto, la eficiencia de los programas monitorizados se ve comprometida por el overhead que introduce el proceso de monitorización. Este trabajo forma parte de las investigaciones para la tesis doctoral del autor en el tema "Software para arquitecturas basadas en procesadores de múltiples núcleos. Detección automática de errores de concurrencia". Como tal, su aporte constituye un estudio de las técnicas y métodos vigentes en la comunidad científica aplicados a la detección y corrección de errores de programación en programas concurrentes. Las siguientes secciones constituyen una introducción al proceso de detectar, localizar y corregir errores de software en programas secuenciales y se explican las complicaciones introducidas por los programas concurrentes. El Capítulo 2 trata los distintos errores que se pueden manifestar en programas concurrentes. El Capítulo 3 resume los antecedentes en técnicas de detección y corrección de errores de concurrencia y se justifica la elección de las violaciones de atomicidad como caso de error más general. El Capítulo 4 explica las características de un algoritmo de detección de violaciones de atomicidad, y da detalles de su implementación. El Capítulo 5 contiene las características de la plataforma de experimentación y de la metodología empleada. El Capítulo 6 proporciona los resultados del trabajo experimental. Finalmente, se presentan las conclusiones del trabajo y se proponen las líneas de investigación futuras.

The problems of semantics and translation for concurrent programming languages are studied in this thesis. A structural operational approach is introduced to specify the semantics of parallelism and communication. Using this approach, semantics for the concurrent programming languages CSP (Hoare's Communicating Sequential Processes), multitasking and exception handling in Ada, Brinch-Hansen's Edison and CCS (Milner's Calculus of Communicating Systems) are defined and some of their properties are studied. An operational translation theory for concurrent programming languages is given. The concept of the correctness of a translation is formalised, the problem of composing transitions is studied and a composition theorem is proved. A set of sufficient conditions for proving the correctness of a translation is given. A syntax-directed translation from CSP to CCS is given and proved correct. Through this example the proof techniques of this approach is demonstrated. Finally, as an application of operational semantics and translation, a proposal for implementing multitasking in Ada is given via a two-step syntax-directed translation.

Submitted by Gustavo José de Sousa null (gustavo.jo.sousa@gmail.com) on 2017-11-07T18:17:35Z No. of bitstreams: 1 dissertacao.pdf: 1114730 bytes, checksum: 360fec3dffa930a34e0cdc2bb0ff960d (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-11-21T13:38:05Z (GMT) No. of bitstreams: 1 sousa_gj_me_sjrp.pdf: 1114730 bytes, checksum: 360fec3dffa930a34e0cdc2bb0ff960d (MD5) / Made available in DSpace on 2017-11-21T13:38:05Z (GMT). No. of bitstreams: 1 sousa_gj_me_sjrp.pdf: 1114730 bytes, checksum: 360fec3dffa930a34e0cdc2bb0ff960d (MD5) Previous issue date: 2017-08-30 / Omissão de lock é uma técnica onde operações de aquisição e liberação de lock são omitidas (especulação) de forma a permitir que regiões críticas compartilhando um mesmo lock possam executar concorrentemente, permitindo assim se explorar um nível maior de concorrência em programas que utilizam esse método popular de sincronização. Para se manter o princípio de atomicidade, as modificações no estado do programa realizadas pela região crítica são mantidas em um buffer interno e são efetivadas apenas ao fim da mesma. Em caso de inconsistências, diferentes políticas em como proceder são possíveis, o que diferencia as diversas abordagens de omissão de lock encontradas na literatura. Por exemplo, a abordagem original, Speculative Lock Elision (SLE), que é implementada no nível microarquitetural, recorre a adquirir o lock de forma tradicional quando uma especulação falha. Em algumas situações, esta política conservadora acaba por restringir o ganho em desempenho originalmente pretendido por impor um volume de sincronização desnecessário (lemming effect). Uma forma de superar tal limitação é o emprego de omissão de lock transacional (Transactional Lock Elision, em inglês), onde a especulação de regiões críticas se dá por meio de transações e o controle de execução é devolvido ao software em eventos de transações abortadas, o que permite que diferentes estratégias sejam empregadas com o objetivo de permitir execução concorrente mesmo em presença de falha de especulação. Neste contexto, uma das abordagens possíveis é o esquema chamado Software-assisted Conflict Management (SCM), onde um lock auxiliar é utilizado para sincronizar transações abortadas e, assim, manter o lock original livre, permitindo que outras transações prossigam sua execução. No presente trabalho, uma extensão ao SCM é proposta, o esquema Fine-grained Software-assisted Conflict Management (FGSCM), onde múltiplos locks são utilizados para permitir que transações abortadas por conflitos em diferentes regiões de memória possam ser executadas de forma concorrente. O algoritmo proposto foi implementado utilizando a interface RTM da extensão Intel® TSX e experimentos foram realizados em um máquina quadcore, para os quais, em casos com predominância de operações de leitura em memória, observou-se um ganho em desempenho médio de 11% e 36% com relação à abordagem SCM original e ao uso de um spin lock comum, respectivamente. / Lock elision is a technique that omits acquire/release lock operations (speculation) so as to allow critical regions sharing the same lock to run concurrently, which yields a higher level of concurrency explored by programs that use such popular synchronization mechanism. In order to honor atomicity, modifications on the program's state made by the critical regions are kept in an internal buffer and only applied at the end of the speculation. If inconsistency is found, different policies on how to proceed are possible, which make up the several existing approaches found in the literature. As an example, the original one, namely Speculative Lock Elision (SLE), which is implemented at the level of microarchitecture, falls back to acquire the lock in a standard manner when there is speculation error. In some situations, such conservative policy ends up restricting the intended performance gains due to the unnecessary synchronization imposed (lemming effect). A way to address this issue is through Transactional Lock Elision (TLE) techniques, in which speculation of critical regions is done by means of transactions and execution control is passed back to software on abort events, which makes possible the use of different strategies to allow concurrent execution even in presence of speculation error. In this context, one possible approach is called Software-assisted Conflict Management (SCM), where an auxiliary lock is used to serialize aborted transactions and, as such, keep the original one free, so that others may proceed on their execution. The work presented in this document proposes an extension of SCM, called Fine-grained Software-assisted Conflict Management (FGSCM), where multiple auxiliary locks are applied in order to allow transactions aborted due to conflict on different regions of memory to be executed concurrently. The proposed algorithm was implemented by using the RTM interface from Intel®'s TSX extension and experiments were performed on a quadcore machine. On read-dominated workloads, an average performance gain of 11% and 36% was observed against the original SCM and a typical spin lock, respectively.

A Programação Concorrente tornou-se uma forma popular de desenvolvimento de software. Este paradigma de desenvolvimento e essencial para construir aplicações com o intuito de reduzir o tempo computacional em muitos domínios como, por exemplo, previsão tempo, processamento de imagem, entre outros. Estes programas têm novas características como a comunicação, a sincronização e o não determinismo, que precisam ser considerados durante a atividade de teste. O teste de software e uma atividade que busca garantir a qualidade por meio da identificação de falhas no produto. O Teste de Mutação e um critério de teste que se baseia nos enganos que podem ser cometidos pelos desenvolvedores de software. Porém, o teste de mutação não pode ser aplicado em programas concorrentes da mesma maneira como e aplicado em programas sequenciais por causa das particularidades presentes nos programas concorrentes. Um problema de aplicar o teste de mutação nesse contexto e o comportamento não determinístico das aplicações. Este trabalho investiga a definição do teste de mutação para programas concorrentes implementados em MPI (Message Passing Interface), os quais realizam comunicação e sincronização por meio de troca de mensagens. Para isso, defeitos típicos nesse domínio foram considerados, buscando modelar operadores de mutação para tratar os aspectos de comunicação e sincronização dessas aplicações. Também foi proposto um procedimento para dar suporte a análise comportamental dos mutantes. As idéias foram implementadas em uma ferramenta de teste chamada ValiMPI Mut / Concurrent programming became a popular paradigm for software development. This paradigm is essential to build applications which aim to reduce the computational time in many areas, such as, weather forecast, image processing, among others. These programs present new features such as communication, synchronization, and nondeterminism, which must be considered during the testing activity. Software testing is an activity that looks to ensure quality by identifying faults in the product. Mutation Testing is a criterion based on the most common mistakes that might be made by software developers. However, the mutation testing cannot be applied in concurrent programs the same way as applied in sequential ones due to the peculiarities present in concurrent programs. One of the problems in applying mutation testing in this context is the non-deterministic behavior. This work investigates the definition of mutation testing for concurrent programs implemented in MPI (Message Passing Interface), which perform communication and synchronization using message passing. For this, typical faults in this area were considered in order to model mutation operators addressing the aspects of communication and synchronization of these applications. Also, we are proposing a new procedure to support the behavioral analysis of the mutants. The ideas were implemented in a testing tool called ValiMPI Mut

Transactional memory (TM), a new programming paradigm, is one of the latest approaches to write programs for next generation multicore and multiprocessor systems. TM is an alternative to lock-based programming. It is a promising solution to a hefty and mounting problem that programmers are facing in developing programs for Chip Multi-Processor (CMP) architectures by simplifying synchronization to shared data structures in a way that is scalable and compos-able. Software Transactional Memory (STM) a full software approach of TM systems can be defined as non-blocking synchronization mechanism where sequential objects are automatically converted into concurrent objects. In this thesis, we present performance comparison of four different STM implementations – RSTM of V. J. Marathe, et al., TL2 of D. Dice, et al., TinySTM of P. Felber, et al. and SwissTM of A. Dragojevic, et al. It helps us in deep understanding of potential tradeoffs involved. It further helps us in assessing, what are the design choices and configuration parameters that may provide better ways to build better and efficient STMs. In particular, suitability of an STM is analyzed against another STM. A literature study is carried out to sort out STM implementations for experimentation. An experiment is performed to measure performance tradeoffs between these STM implementations. The empirical evaluations done as part of this thesis conclude that SwissTM has significantly higher throughput than state-of-the-art STM implementations, namely RSTM, TL2, and TinySTM, as it outperforms consistently well while measuring execution time and aborts per commit parameters on STAMP benchmarks. The results taken in transaction retry rate measurements show that the performance of TL2 is better than RSTM, TinySTM and SwissTM.

Actuellement, la majorité des architectures de processeurs sont fondées sur une mémoire partagée avec cohérence de caches. Des prototypes intégrant de grandes quantités de cœurs, reliés par une infrastructure de transmission de messages, indiquent que, dans un proche avenir, les architectures de processeurs vont probablement avoir ces caractéristiques. Ces deux tendances exigent que les processus s'exécutent en parallèle et rendent la programmation concurrente nécessaire. Cependant, la difficulté inhérente du raisonnement sur la concurrence peut rendre ces nouvelles machines difficiles à programmer. Nous explorons trois approches ayant pour but de faciliter la programmation concurrente. Nous proposons WFR-TM, une approche fondé sur la mémoire transactionnelle (TM), un paradigme de programmation concurrente qui utilise des transactions afin de synchroniser l'accès aux données partagées. Une transaction peut soit terminer (commit), rendant visibles ses modifications, soit échouer (abort), annulant toutes ses modifications. WFR-TM tente de combiner des caractéristiques désirables des TM optimistes et pessimistes. Une TM pessimiste n'échoue jamais aucune transaction; néanmoins les algorithmes existants utilisent des verrous pour exécuter de manière séquentielle les transactions qui contiennent des opérations d'écriture. Les algorithmes TM optimistes exécutent toutes les transactions en parallèle mais les terminent seulement si elles n'ont pas rencontré de conflit au cours de leur exécution. WFR-TM fournit des transactions en lecture seule qui sont wait-free, sans jamais exécuter d'opérations de synchronisation coûteuse (par ex. CAS, LL\SC, etc) ou sacrifier le parallélisme entre les transactions d'écriture. Nous présentons également Dense, une implémentation concurrente de graphe. Les graphes sont des structures de données polyvalentes qui permettent la mise en oeuvre d'une variété d'applications. Cependant, des applications multi-processus qui utilisent des graphes utilisent encore largement des versions séquentielles. Nous introduisons un nouveau modèle de graphes concurrents, permettant l'ajout ou la suppression de n'importe quel arc du graphe, ainsi que la traversée atomique d'une partie (ou de l'intégralité) du graphe. Dense offre la possibilité d'effectuer un snapshot partiel d'un sous-ensemble du graphe défini dynamiquement. Enfin, nous ciblons les futures architectures. Dans l'intérêt de la réutilisation du code il existe depuis quelques temps une tentative d'adaptation des environnements d'exécution de logiciel - comme par ex. JVM, l'environnement d'exécution de Java - initialement prévus pour mémoire partagée, à des machines sans cohérence de caches. Nous étudions des techniques générales pour implémenter des structures de données distribuées en supposant qu'elles vont être utilisées sur des architectures many-core, qui n'offrent qu'une cohérence partielle de caches, voir pas de cohérence du tout. / Though a majority of current processor architectures relies on shared, cache-coherent memory, current prototypes that integrate large amounts of cores, connected through a message-passing substrate, indicate that architectures of the near future may have these characteristics. Either of those tendencies requires that processes execute in parallel, making concurrent programming a necessary tool. The inherent difficulty of reasoning about concurrency, however, may make the new processor architectures hard to program. In order to deal with issues such as this, we explore approaches for providing ease of programmability. We propose WFR-TM, an approach based on transactional memory (TM), which is a concurrent programming paradigm that employs transactions in order to synchronize the access to shared data. A transaction may either commit, making its updates visible, or abort, discarding its updates. WFR-TM combines desirable characteristics of pessimistic and optimistic TM. In a pessimistic TM, no transaction ever aborts; however, in order to achieve that, existing TM algorithms employ locks in order to execute update transactions sequentially, decreasing the degree of achieved parallelism. Optimistic TMs execute all transactions concurrently but commit them only if they have encountered no conflict during their execution. WFR-TM provides read-only transactions that are wait-free, without ever executing expensive synchronization operations (like CAS, LL/SC, etc), or sacrificing the parallelism between update transactions. We further present Dense, a concurrent graph implementation. Graphs are versatile data structures that allow the implementation of a variety of applications. However, multi-process applications that rely on graphs still largely use a sequential implementation. We introduce an innovative concurrent graph model that provides addition and removal of any edge of the graph, as well as atomic traversals of a part (or the entirety) of the graph. Dense achieves wait-freedom by relying on light-weight helping and provides the inbuilt capability of performing a partial snapshot on a dynamically determined subset of the graph. We finally aim at predicted future architectures. In the interest of ode reuse and of a common paradigm, there is recent momentum towards porting software runtime environments, originally intended for shared-memory settings, onto non-cache-coherent machines. JVM, the runtime environment of the high-productivity language Java, is a notable example. Concurrent data structure implementations are important components of the libraries that environments like these incorporate. With the goal of contributing to this effort, we study general techniques for implementing distributed data structures assuming they have to run on many-core architectures that offer either partially cache-coherent memory or no cache coherence at all and present implementations of stacks, queues, and lists.

No description available.