Concurrent computing

Summary

Concurrent computing is a form of computing in which several computations are executed concurrently—during overlapping time periods—instead of sequentially—with one completing before the next starts. This is a property of a system—whether a program, computer, or a network—where there is a separate execution point or "thread of control" for each process. A concurrent system is one where a computation can advance without waiting for all other computations to complete. Concurrent computing is a form of modular programming. In its paradigm an overall computation is factored into subcomputations that may be executed concurrently. Pioneers in the field of concurrent computing include Edsger Dijkstra, Per Brinch Hansen, and C.A.R. Hoare. Introduction Parallel computing The concept of concurrent computing is frequently confused with the related but distinct concept of parallel computing, although both can be described as "multiple processes executing during the same period of time

Official source

https://en.wikipedia.org/wiki/Concurrent_computing

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (100)

Related publications

Related people (29)

, , , , , , , , ,

Related people

Related units (11)

Related units

Related concepts (85)

Related concepts

Related courses (20)

Related courses

Related lectures (47)

Related lectures

Automatic Validation of Concurrent Programming

Christof Bruetsch

2003

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

Theory of Transactional Memory

Michal Kapalka

Transactional memory (TM) is a promising paradigm for concurrent programming, in which threads of an application communicate, and synchronize their actions, via inmemory transactions. Each transaction can perform any number of operations on shared data, and then either commit or abort. When the transaction commits, the effects of all its operations become immediately visible to other transactions; when it aborts, however, those effects are entirely discarded. Transactions are atomic: programmers get the illusion that every transaction executes all its operations instantaneously, at some single and unique point in time. The TM paradigm has raised a lot of hope for mastering the complexity of concurrent programming. The aim is to provide programmers with an abstraction, i.e., the transaction, that makes handling concurrency as easy as with coarse-grained locking, while exploiting the parallelism of the underlying multi-core or multi-processor hardware as well as hand-crafted fine-grained locking (which is typically an engineering challenge). It is thus not surprising to see a large body of work devoted to implementing this paradigm efficiently, and integrating it with common programming languages. Very little work, however, was devoted to the underlying theory and principles. The aim of this thesis is to provide theoretical foundations for transactional memory. This includes defining a model of a TM, as well as answering precisely when a TM implementation is correct, what kind of properties it can ensure, what the power and limitations of a TM are, and what inherent trade-offs are involved in designing a TM algorithm. In particular, this manuscript contains precise definitions of properties that capture the safety and progress semantics of TMs, as well as several fundamental results related to computability and complexity of TM implementations. While the focus of the thesis is on theory, its goal is to capture the common intuition behind the semantics of TMs and the properties of existing TM implementations.

EPFL2010

Theory of Transactional Memory

Michal Kapalka

EPFL2010

EPFL2014