Disjoint-access parallelism does not entail scalability

Disjoint Access Parallelism (DAP) stipulates that operations involving disjoint sets of memory words must be able to progress independently, without interfering with each other. In this work we argue towards revising the two decade old wisdom saying that DAP is a binary condition that splits concurrent programs into scalable and non-scalable. We first present situations where DAP algorithms scale poorly, thus showing that not even algorithms that achieve this property provide scalability under all circumstances. Next, we show that algorithms which violate DAP can sometimes achieve the same scalability and performance as their DAP counterparts. We continue to show how by violating DAP and without sacrificing scalability we are able to circumvent three theoretical results showing that DAP is incompatible with other desirable properties of concurrent programs. Finally we introduce a new property called generalized disjoint-access parallelism (GDAP) which estimates how much of an algorithm is DAP. Algorithms having a large DAP part scale similar to DAP algorithms while not being subject to the same impossibility results.

Disjoint-Access Parallelism Does Not Entail Scalability

Rachid Guerraoui, Mihai Letia

2014

Inferring Scalability from Program Pseudocode

Mihai Letia

Recent trends have led hardware manufacturers to place multiple processing cores on a single chip, making parallel programming the intended way of taking advantage of the increased processing power. However, bringing concurrency to average programmers is considered to be one of the major challenges in computer science today. The difficulty lies not only in writing correct parallel programs, but also in achieving the required efficiency and performance. For parallel programs, performance is not only about obtaining low execution times on a fixed number of cores, but also about maintaining efficiency as the number of available cores is increased. Ideally, programmers should have in their toolkit techniques that can be used when designing parallel programs, before any code is available for testing on production hardware, and which are then able to predict scalability once the program is implemented. Existing methods are either unreliable at predicting scalability, such as the case of disjoint-access parallelism, or do not apply to lock-based programs, which currently make up a large part of existing concurrent programs. Furthermore, using some of these techniques is so complicated that it outweighs the time required to implement, debug and test the program on real hardware. In this thesis we study the problem of predicting the scalability of concurrent programs without implementing them. This allows programmers in the design phase of a concurrent algorithm to choose only one or a few promising solutions that will be implemented, debugged and tested on production hardware. We first consider disjoint-access parallelism, an existing property that applies only to a very restricted class of programs. After an extensive practical evaluation spanning across a variety of scenarios, we find it to be ineffective at predicting scalability. For predicting the scalability of more general concurrent algorithms, we propose the obstruction degree, a new scalability metric based on the consistency requirements of algorithms. It applies to programs using locks, invalidation primitives and transactional memory. Our metric allows programmers to compare two given algorithms as well as predict their scalability limit, the maximum number of processors to which they can scale, thus allowing programmers to choose the appropriate size hardware for running their programs. We also examine the composition of relaxed memory transactions in order to combine the ease of programming offered by transactional memory with the increased scalability of transactions that circumvent the traditional transactional model. We present outheritance, a property we show to be both necessary and sufficient for ensuring the correct composition of relaxed transactions, and we show how to calculate the obstruction degree of compositions that use this new property. We use outheritance to build OE-STM, a new software transactional memory algorithm having elastic transactions that correctly compose.

EPFL2014

Obstruction degree: measuring concurrency in shared memory systems

Rachid Guerraoui, Mihai Letia

This paper presents the notion of obstruction degree, a new metric for reasoning about the scalability of concurrent algorithms. Essentially, this simple metric gives an indication as to which of two concurrent algorithms is expected to scale better, as well as approximate the maximum number of processors up to which a concurrent algorithm is expected to scale. The scope of the metric is the arguably large class of concurrent algorithms obtained by augmenting sequential algorithms with locks (pessimistic), invalidation primitives (optimistic) or transactional memory. We illustrate the metric through various algorithms and we convey the accuracy of our scalability predictions through extensive experimental measures.

2012

Inferring Scalability from Program Pseudocode

Mihai Letia

EPFL2014