Dissertations / Theses on the topic 'Concurrent/parallel systems and technologies'

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-04-06T13:27:55Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) versao_biblioteca.pdf: 3051240 bytes, checksum: ac1a91e08d64c78a372cb0e151bcb7c7 (MD5)
Made available in DSpace on 2016-04-06T13:27:55Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) versao_biblioteca.pdf: 3051240 bytes, checksum: ac1a91e08d64c78a372cb0e151bcb7c7 (MD5) Previous issue date: 2015-02-24
CAPEs
Empowering application programmers to make energy-aware decisions is a critical dimension in improving energy efficiency of computer systems. Despite the growing interest in designing software development processes, frameworks, and programming models to facilitate application-level energy management, little is known on how to design application-level energy-efficient solutions for concurrent software running on parallel architectures. This is unfortunate for at least two reasons: (1) thanks to the proliferation of multicore CPUs, concurrent programming is a standard practice in modern software engineering; (2) a CPU with more cores (say 32) often consumes more power than one with fewer cores (say 1 or 2). However, application developers still do not understand how their code modifications impact energy consumption in a parallel system. Analyzing STACKOVERFLOW showed evidence that this is a real problem; Even though the interest in energy consumption issues is increasing over the years, developers still hold misconceptions and assumptions that are not always true. This lack of knowledge is primarily due to a lack of appropriate tools to measure/identify/refactor energy consumption hotspots. This thesis begins to bridge the chasm of the first problem — the lack of knowledge — by presenting an extensive experimental space exploration over two concurrent programming building blocks: (1) thread-safe collections and (2) thread management constructs. Through a list of findings that are not always obvious, we illuminate the relationship between the choices and settings of design decisions and energy consumption of parallel systems. This thesis then starts to bridge the gap of the second problem — the lack of tools. Lessons learned in our previous studies showed that ForkJoin tasks often operate on an indexable data structure, with subtasks operating only on part of this data structure. One naïve solution is to copy part of the data structure and use it in the next computation. In a recursive framework such as ForkJoin, given an array-based representation, each recursive call will create n new arrays, where n is the width of forking. To address this, we derive a refactoring that, instead of copy part of the data structure, it shares it, allowing subtasks to operate on contiguous partitions of the data structure. We manually applied this refactoring into 15 open source projects. Our refactoring succeed in saving energy for each one of them (12% average saving). We sent the refactored versions to the project owner and, during a timeframe of 40 days, 7 out of 9 projects that replied to our patches have already accepted and merged them. Discussions during the merge process revealed that developers were not aware of this optimization. We then implemented this refactoring as an Eclipse plug-in so that other developers can (1) detect uses of copy where it would be beneficial to use sharing and (2) refactor the code in an automated way.
Fornecer meios para que desenvolvedores de software tomem decisões energeticamente eficientes é uma dimensão crítica para se melhorar o consumo de energia de sistemas computacionais. Apesar do crescente interesse em processos de desenvolvimento de software, arcabouços, e modelos de programação de forma a facilitar o gerenciamento de energia no nível da aplicação, pouco se sabe sobre como arquitetar sistemas concorrentes energéticamente eficientes que rodem em arquiteturas paralelas. Isso é inoportuno por pelo menos duas razões: (1) graças a proliferação de CPUs multicore, programação concorrente se tornou uma prática padrão na engenharia de software moderna; (2) uma CPU com várias unidades de processamento (por exemplo, 32) geralmente dissipa mais potência do que uma com um número menor (por exemplo, 1 ou 2). No entanto, desenvolvedores ainda não entendem como suas modificações de código impactam no consumo de energia de uma aplicação paralela. Uma análise do StackOverflow mostrou evidências que esse é um problema real; mesmo embora exista um crescente interesse em questões relacionadas ao consumo de energia, desenvolvedores ainda cometem equívocos e mantêm suposições que não são sempre verdadeiras. Essa falta de conhecimento é primariamente devido a falta de ferramentas apropriadas para medir/identificar/refatorar hotspots de consumo de energia. Essa tese então começa a pavimentar o abismo do primeiro problema — a falta de conhecimento — através de uma extensa exploração experimental de dois dos pilares fundamentais da programação concorrente: (1) coleções thread-safe e (2) construções para o gerenciamento de threads. Através de uma lista de achados que não são sempre óbvios, esta tese ilumina o relacionamento entre escolhas de design de código paralelo com seu consumo de energia. Esta tese começa então a pavimentar a lacuna do segundo problema — a falta de ferramentas. Lições aprendidas em um dos estudos anteriores mostraram que várias tarefas do arcabouço ForkJoin operam em estrutura de dados indexáveis, com sub-tarefas operando somente em parte dessa estrutura de dados. Uma solução ingênua é de copiar parta da estrutura de dados e utiliza-la na computação sub-sequente. Em um arcabouço recursivo como o ForkJoin, dado uma representação baseada em arrays, cada chamada recursiva criará n novos arrays, onde n é a profundidade do fork. Como solução, esta tese apresenta uma refatoração que, ao invés de copiar parte da estrutura de dados, ela compartilha-a, possibilitando que sub-tarefas operem em partições contíguas da estrutura de dados. Essa refatoração foi avaliada em 15 projetos de código aberto, a qual foi capaz de economizar energia em todos os casos (média de 12% de economia). A versão refatorada foi enviada aos mantenedores do projeto original e, durante um período de 40 dias, 7 dos 9 mantenedores que responderam aos patches enviados já haviam aceitado-os e integrado-os. Discussões durante o processo de integração revelaram que desenvolvedores não estão cientes desta otimização. Esta tese então implementou essa refatoração como um plug-in da IDE Eclipse de forma que outros desenvolvedores possam (1) detectar usos de cópia em cenários o quais seriam beneficiais o uso do modelo de compartilhamento and (2) refatorar o código de forma automática.

The recent development of multi-core computer architectures has largely affected the creation of everyday applications, requiring the adoption of concurrent programming to significantly utilize the divided processing power of computers. Applications must be split into sections able to execute in parallel, without any of these sections conflicting with one another, thereby necessitating some form of synchronization to be declared. The most commonly used methodology is lock-based synchronization; although, to improve performance the most, developers must typically form complex, low-level implementations for large applications, which can easily create potential errors or hindrances. An abstraction from database systems, known as transactions, is a rising concurrency control design aimed to circumvent the challenges with programmability, composability, and scalability in lock-based synchronization. Transactions execute their operations speculatively and are capable of being restarted (or rolled back) when there exist conflicts between concurrent actions. As such issues can occur later in the lifespans of transactions, entire rollbacks are not that effective for performance. One particular method, known as nesting, was created to counter that drawback. Nesting is the act of enclosing transactions within other transactions, essentially dividing the work into pieces called sub-transactions. These sub-transactions can roll back without affecting the entire main transaction, although general nesting models only allow one sub-transaction to perform work at a time. The first main contribution in this thesis is SPCN, an algorithm that parallelizes nested transactions while automatically processing any potential conflicts that may arise, eliminating the burden of additional processing from the application developers. Two versions of SPCN exist: Strict, which enforces the sub-transactions' work to be made visible in a serialized order; and Relaxed, which allows sub-transactions to distribute their information immediately as they finish (therefore invalidation may occur after-the-fact and must be handled). Despite the additional logic required by SPCN, it outperforms traditional closed nesting by 1.78x at the lowest and 3.78x at the highest in the experiments run. Another method to alter transactional execution and boost performance is to relax the rules of visibility for parallel operations (known as their isolation). Depending on the application, correctness is not broken even if some transactions see external work that may later be undone due to a rollback, or if an object is written while another transaction is using an older instance of its data. With lock-based synchronization, developers would have to explicitly design their application with varying amounts of locks, and different lock organizations or hierarchies, to change the strictness of the execution. With transactional systems, the processing performed by the system itself can be set to utilize different rulings, which can change the performance of an application without requiring it to be largely redesigned. This notion leads to the second contribution in this thesis: AsR, or As-Serializable transactions. Serializability is the general form of isolation or strictness for transactions in many applications. In terms of execution, its definition is equivalent to only one transaction running at a time in a given system. Many transactional systems use their own internal form of locking to create Serializable executions, but it is typically too strict for many applications. AsR transactions allow the internal processing to be relaxed while additional meta-data is used external to the system, without requiring any interaction from the developer or any changes to the given application. AsR transactions offer multiple orders of magnitude more in throughput in highly-contentious scenarios, due to their capability to outlast traditional levels of isolation.
Master of Science

Memory management errors in concurrent software running on multi-core architectures can be difficult and costly to detect and repair. Examples of errors are usage of uninitialized memory, memory leaks, and data corruptions due to unintended overwrites of data that are not owned by the writing entity. If memory management errors could be detected at an early stage, for example when using a simulator before the software has been delivered and integrated in a product, significant savings could be achieved. This thesis investigates and develops methods for detection of usage of uninitialized memory in software that runs on a virtual hardware platform. The virtual hardware platform has models of Ericsson Radio Base Station hardware for baseband processing and digital radio processing. It is a bit-accurate representation of the underlying hardware, with models of processors and peripheral units, and it is used at Ericsson for software development and integration. There are tools available, such as Memcheck (Valgrind), and MemorySanitizer and AddressSanitizer (Clang), for memory management error detection. The features of such tools have been investigated, and memory management error detection algorithms were developed for a given processor’s instruction set. The error detection algorithms were implemented in a virtual platform, and issues and design considerations reflecting the application-specific instruction set architecture of the processor, were taken into account. A prototype implementation of memory error presentation with error locations mapped to the source code of the running program, and presentation of stack traces, was done, using functionality from a debugger. An experiment, using a purpose-built test program, was used to evaluate the error detection capability of the algorithms in the virtual platform, and for comparison with the error detection capability of Memcheck. The virtual platform implementation detects all known errors, except one, in the program and reports them to the user in an appropriate manner. There are false positives reported, mainly due to the limited awareness about the operating system used on the simulated processor
Minneshanteringsfel i parallell mjukvara som exekverar på flerkärniga arkitekturer kan vara svåra att detektera, samt kostsamma att åtgärda. Exempel på fel kan vara användning av ej initialiserat minne, minnesläckage, samt att data blir överskrivna av en process som inte är ägare till de data som skrivs över. Om minneshanteringsfel kan detekteras i ett tidigt skede, t ex genom att använda en simulator, som körs innan mjukvaran har levererats och integrerats i en produkt, skulle man kunna erhålla signifikanta kostnadsbesparingar. Detta examensarbete undersöker och utvecklar metoder för detektion av ej initialiserat minne i mjukvara som körs på en virtuell plattform. Den virtuella plattformen innehåller modeller av delar av den digitala hårdvara, för basband och radio, som finns i en Ericsson radiobasstation. Modellerna är bit-exakta representationer av motsvarande hårdvarublock, och innefattar processorer och periferienheter. Den virtuella plattformen används av Ericsson för utveckling och integration av mjukvara. Det finns verktyg, exempelvis Memcheck (Valgrind), samt MemorySanitizer och AddressSanitizer (Clang), som kan användas för att detektera minneshanteringsfel. Egenskaper hos sådana verktyg har undersökts, och algoritmer för detektion av minneshanteringsfel har utvecklats, för en specifik processor och dess instruktioner. Algoritmerna har implementerats i en virtuell plattform, och kravställningar och design-överväganden som speglar den tillämpnings-specifika instruktionsrepertoaren för den valda processorn, har behandlats. En prototyp-implementation av presentation av minneshanteringsfel, där källkodsraderna samt anropsstacken för de platser där fel har hittats pekas ut, har utvecklats, med användning av en debugger. Ett experiment, som använder sig av ett för ändamålet utvecklat program, har använts för att utvärdera feldetektions-förmågan för de algoritmer som implementerats i den virtuella plattformen, samt för att jämföra med feldetektions-förmågan hos Memcheck. De algoritmer som implementerats i den virtuella plattformen kan, för det program som används, detektera alla kända fel, förutom ett. Algoritmerna rapporterar också falska felindikeringar. Dessa rapporter är huvudsakligen ett resultat av att den aktuella implementationen har begränsad kunskap om det operativsystem som används på den simulerade processorn.

This thesis investigates automata-theoretic techniques for the verification of physically distributed machines communicating via unbounded reliable channels. Each of these machines may run several recursive programs (multi-threading). A recursive program may also use several unbounded stack and queue data-structures for its local-computation needs. Such real-world systems are so powerful that all verification problems become undecidable. We introduce and study a new parameter called split-width for the under-approximate analysis of such systems. Split-width is the minimum number of splits required in the behaviour graphs to obtain disjoint parts which can be reasoned about independently. Thus it provides a divide-and-conquer approach for their analysis. With the parameter split-width, we obtain optimal decision procedures for various verification problems on these systems like reachability, inclusion, etc. and also for satisfiability and model checking against various logical formalisms such as monadic second-order logic, propositional dynamic logic and temporal logics. It is shown that behaviours of a system have bounded split-width if and only if they have bounded clique-width. Thus, by Courcelle's results on uniformly bounded-degree graphs, split-width is not only sufficient but also necessary to get decidability for MSO satisfiability checking. We then study the feasibility of distributed controllers for our generic distributed systems. We propose several controllers, some finite state and some deterministic, which ensure that the behaviours of the system have bounded split-width. Such a distributedly controlled system yields decidability for the various verification problems by inheriting the optimal decision procedures for split-width. These also extend or complement many known decidable subclasses of systems studied previously.