nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

Multicore Software Engineering, Performance, and Tools

International Conference, MUSEPAT 2013, St. Petersburg, Russia, August 19-20, 2013. Proceedings

herausgegeben von: João M. Lourenço, Eitan Farchi

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed proceedings of the International Conference on Multiscore Software Engineering, Performance, and Tools, MUSEPAT 2013, held in Saint Petersburg, Russia, in August 2013. The 9 revised papers were carefully reviewed and selected from 25 submissions. The accepted papers are organized into three main sessions and cover topics such as software engineering for multicore systems; specification, modeling and design; programing models, languages, compiler techniques and development tools; verification, testing, analysis, debugging and performance tuning, security testing; software maintenance and evolution; multicore software issues in scientific computing, embedded and mobile systems; energy-efficient computing as well as experience reports.

Inhaltsverzeichnis

Frontmatter

Performance Analysis and Algorithms

Self-timed Scheduling and Execution of Nonlinear Pipelines with Parallel Stages

Abstract

Applications that process continuous streams of data, e.g., sensor signals, video images, network packets, etc. are well-suited for pipelined execution on multicore processors. In many cases, however, the applications are subject to real-time constraints, especially in embedded systems. Besides maximizing the throughput, it is therefore important to minimize deviations in the timing. To solve this problem, we propose a method for self-timed scheduling and parallel execution of stream-based applications in soft real-time environments. Our experimental results show significantly lower latencies compared to state-of-the-art approaches, while achieving high throughput.

Lars Lucas, Tobias Schuele, Wolfgang Schwitzer

MVA-Based Probabilistic Model of Shared Memory with a Round Robin Arbiter for Predicting Performance with Heterogeneous Workload

Abstract

Memory access contention can be a cause of performance problems and should be assessed at early stages of development. We devised a probabilistic model of shared memory for performance estimation. The calculation time is polynomial in the number of processors. The model is applicable for the region of high and heterogeneous bandwidth utilization. A round-robin arbiter is modeled using Mean Value Analysis (MVA) based approximations and incorporating non-linear dependence to the bandwidth utilization. To evaluate our model, estimated execution time is compared with the measured execution time of benchmark programs with memory access contention. We find a maximum error of 4.2% for the round-robin arbitration when we compensate for the burstiness of accesses.

Ryo Kawahara, Kouichi Ono, Takeo Nakada

MHS2: A Map-Reduce Heuristic-Driven Minimal Hitting Set Search Algorithm

Abstract

Computing minimal hitting sets (also known as set covers) for a collection of sets is an important problem in many domains (e.g., model/reasoning-based fault diagnosis). Being an NP-Hard problem, exhaustive algorithms are usually prohibitive for real-world, often large, problems. In practice, the usage of heuristic based approaches trade-off completeness for time efficiency. An example of such heuristic approaches is Staccato, which was proposed in the context of reasoning-based fault localization. In this paper, we propose an efficient distributed algorithm, dubbed MHS², that renders the sequential search algorithm Staccato suitable to distributed, Map-Reduce environments. The results show that MHS² scales to larger systems (when compared to Staccato), while entailing either marginal or small runtime overhead.

Nuno Cardoso, Rui Abreu

Programming Models and Optimization

Handling Parallelism in a Concurrency Model

Abstract

Programming models for concurrency are optimized for dealing with nondeterminism, for example to handle asynchronously arriving events. To shield the developer from data race errors effectively, such models may prevent shared access to data altogether. However, this restriction also makes them unsuitable for applications that require data parallelism. We present a library-based approach for permitting parallel access to arrays while preserving the safety guarantees of the original model. When applied to SCOOP, an object-oriented concurrency model, the approach exhibits a negligible performance overhead compared to ordinary threaded implementations of two parallel benchmark programs.

Mischael Schill, Sebastian Nanz, Bertrand Meyer

On the Relevance of Total-Order Broadcast Implementations in Replicated Software Transactional Memories

Abstract

Transactional Memory (TM), an attractive solution to support concurrent accesses to main-memory storage, is already being deployed by some of the major CPU and compiler manufacturers. To address scalability and dependability challenges, researchers are now combining replication, TM and certification-based protocols. To maintain consistency and ensure common transaction serialisation order, these protocols rely in a total-order broadcast primitive, usually provided by some Group Communication System (GCS). The total-order broadcast service can be implemented by different algorithms, which hold different properties. In this paper we present a detailed analysis of the impact of some algorithms implementing total-order broadcast in different TM workloads, opening up future work to improve performance of replicated TMs.

Tiago M. Vale, Ricardo J. Dias, João M. Lourenço

How to Cancel a Task

Abstract

Task parallelism is ubiquitous in modern applications for event-based, distributed, or reactive systems. In this type of programming, the ability to cancel a running task arises as a critical feature. Although there are a variety of cancellation techniques, a comprehensive account of their characteristics is missing. This paper provides a classification of task cancellation patterns, as well as a detailed analysis of their advantages and disadvantages. One promising approach is cooperative cancellation, where threads must be continuously prepared for external cancellation requests. Based on this pattern, we propose an extension of SCOOP, an object-oriented concurrency model.

Alexey Kolesnichenko, Sebastian Nanz, Bertrand Meyer

Testing and Debugging

Automatically Repairing Concurrency Bugs with ARC

Abstract

In this paper we introduce ARC – a fully automated system for repairing deadlocks and data races in concurrent Java programs. ARC consists of two phases: (1) a bug repair phase and (2) an optimization phase. In the first phase, ARC uses a genetic algorithm without crossover to mutate an incorrect program, searching for a variant of the original program that fixes the deadlocks and data races. As this first phase may introduce unneeded synchronization that can negatively affect performance, a second phase attempts to optimize the concurrent source code by removing any excess synchronization without sacrificing program correctness. We describe both phases of our approach and report on our results.

David Kelk, Kevin Jalbert, Jeremy S. Bradbury

A Modular Approach to Model-Based Testing of Concurrent Programs

Abstract

This paper presents a modular approach to testing concurrent programs that are modeled using labeled transition systems. Correctness is defined in terms of an implementation relation that is expected to hold between a model of the system and its implementation. The novelty of our approach is that the correctness of a concurrent software system is determined by testing the individual threads separately, without testing the system as a whole. We define a modular implementation relation on individual threads and show that modular relations can be tested separately in order to verify a (non-modular) implementation relation for the complete system. Empirical results indicate that our approach can significantly reduce the number of test sequences that are generated and executed during model-based testing.

Richard Carver, Yu Lei

A Dynamic Approach to Isolating Erroneous Event Patterns in Concurrent Program Executions

Abstract

Concurrency bugs are hard to find due to the nondeterministic behavior of concurrent programs. In this paper, we present an algorithm for isolating erroneous event patterns in concurrent program executions. Failed executions are characterized as a sequence of switch points, which capture the interleaving of read and write events on shared variables. The algorithm inputs the sequence of a failed execution, and outputs erroneous event patterns. We implemented our algorithm and conducted an experimental evaluation on several Java benchmark programs. The results of our evaluation show that our approach can effectively and efficiently identify erroneous event patterns in failed executions.

Jing Xu, Yu Lei, Richard Carver, David Kung

Backmatter

Titel: Multicore Software Engineering, Performance, and Tools
herausgegeben von: João M. Lourenço
Eitan Farchi
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-39955-8
Print ISBN: 978-3-642-39954-1
DOI: https://doi.org/10.1007/978-3-642-39955-8

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Performance Analysis and Algorithms

Self-timed Scheduling and Execution of Nonlinear Pipelines with Parallel Stages

MVA-Based Probabilistic Model of Shared Memory with a Round Robin Arbiter for Predicting Performance with Heterogeneous Workload

MHS2: A Map-Reduce Heuristic-Driven Minimal Hitting Set Search Algorithm

Programming Models and Optimization

Handling Parallelism in a Concurrency Model

On the Relevance of Total-Order Broadcast Implementations in Replicated Software Transactional Memories

How to Cancel a Task

Testing and Debugging

Automatically Repairing Concurrency Bugs with ARC

A Modular Approach to Model-Based Testing of Concurrent Programs

A Dynamic Approach to Isolating Erroneous Event Patterns in Concurrent Program Executions

Backmatter

Premium Partner