Concurrency
General 1
Mutual exclusion 2
Software approach 3
Hardware approach 4
State sharing 5
Dataflow computations 6
Software Transactional Memory 8
Parallelism 12
Hardware perspective 13
SIMD 13
Software perspective 15
Speedup 16
GPGPU 18
GPU architecture 18
Execution model 19
Programming model 20
Accelerate 24
Data parallelism 25
Patterns 25
Performance analysis 30
,General
Concurrency Composition of independently executing processes
Multiple tasks occurring at the same time in any given order without conflict
- Dealing with lots of things at once
- Collection of independently executing processes
- Two or more threads are making progress
- How to structure your program
Parallelism Simultaneous execution of (possibly related) computations
- Doing lots of things at once
- At least two threads are executing simultaneously
- Parallelism can be achieved through the use of concurrency
Concurrency Concurrency + parallelism
(Single-Core CPU) (Multi-Core CPU)
___ ___ ___
|th1| |th1|th2|
| | | |___|
|___|___ | |___
|th2| |___|th2|
___|___| ___|___|
|th1| |th1|
|___|___ | |___
|th2| | |th2|
Tasks are concurrent with respect to each other if:
- They may be executed out-of-order
- Implies they can be executed at the same time (but this is not required)
Tasks are parallel if they are executed simultaneously:
- Requires multiple processing elements
- The primary motivation for parallel programming is to reduce the overall running time of
the program: parallel execution
Multithreading: concurrent threads share an address space
Multiprogramming: concurrent processes execute on a uniprocessor
Multiprocessing: concurrent processes on a multiprocessor
Distributed processing: concurrent processes executing on multiple nodes connected by a
network
Atomic action A set of instructions that needs to be executed at once, and treated as if they
were just one instruction
- This can be enforced using a critical section, which forces processes to get a lock on the
section to be able to use it (only one thread gets access at a time)
- For example: appending a new node to the end of a linked list
1
, Access/Concurrency control
- Compete for resources
- Processes may not be aware of each other
- Execution must not be affected by each other
- OS is responsible for controlling access
- Cooperate by sharing a common resource
- Programmer responsible for controlling access
- Hardware/OS/programming language may provide support
Control problems
- Mutual exclusion: only one process at a time is allowed in a critical section
- Modifications to critical sections should appear to happen atomically
- Deadlock: processes need multiple resources and are dependant on each other to give
up (some of) the resources they need
- A lock is deadlock free if threads want to get the lock, and it is not currently being
used, they can can acquire it
- If failure of a process anywhere (outside critical section) causes other processes
to deadlock (cannot access lock anymore), then the lock is not deadlock free
- For example, attempt 1 of mutual exclusion, where one processes always
passes control to the other process and is dependant on that one passing
it back to obtain the lock again
- Livelock: states of the group of processes are constantly changing with regard to each
other, but none are progressing (e.g. trying to obtain a lock, but backing off if that fails to
give another thread the opportunity to obtain it, but the other thread is doing the same)
- Starvation: a process is trying to access a resource but is never allowed to
- Livelock can be a form of starvation
Properties required for concurrency control:
- Starvation-freedom: no starvation
- Deadlock-freedom: no deadlocking
- Mutual exclusion: only one thread allowed in some
block of code
- For example, the code on the right does not
provide mutual exclusion, because it is
possible for two threads to reach the
writeIORef ref True part
Mutual exclusion
→ Only one thread at a time is allowed in the critical
section for a resource
- This needs to be implemented without causing a deadlock or starvation on attempting to
enter or leave the critical section
Implementation requirements
- A thread must not be delayed access to a critical section when there is no other thread
using it
2
General 1
Mutual exclusion 2
Software approach 3
Hardware approach 4
State sharing 5
Dataflow computations 6
Software Transactional Memory 8
Parallelism 12
Hardware perspective 13
SIMD 13
Software perspective 15
Speedup 16
GPGPU 18
GPU architecture 18
Execution model 19
Programming model 20
Accelerate 24
Data parallelism 25
Patterns 25
Performance analysis 30
,General
Concurrency Composition of independently executing processes
Multiple tasks occurring at the same time in any given order without conflict
- Dealing with lots of things at once
- Collection of independently executing processes
- Two or more threads are making progress
- How to structure your program
Parallelism Simultaneous execution of (possibly related) computations
- Doing lots of things at once
- At least two threads are executing simultaneously
- Parallelism can be achieved through the use of concurrency
Concurrency Concurrency + parallelism
(Single-Core CPU) (Multi-Core CPU)
___ ___ ___
|th1| |th1|th2|
| | | |___|
|___|___ | |___
|th2| |___|th2|
___|___| ___|___|
|th1| |th1|
|___|___ | |___
|th2| | |th2|
Tasks are concurrent with respect to each other if:
- They may be executed out-of-order
- Implies they can be executed at the same time (but this is not required)
Tasks are parallel if they are executed simultaneously:
- Requires multiple processing elements
- The primary motivation for parallel programming is to reduce the overall running time of
the program: parallel execution
Multithreading: concurrent threads share an address space
Multiprogramming: concurrent processes execute on a uniprocessor
Multiprocessing: concurrent processes on a multiprocessor
Distributed processing: concurrent processes executing on multiple nodes connected by a
network
Atomic action A set of instructions that needs to be executed at once, and treated as if they
were just one instruction
- This can be enforced using a critical section, which forces processes to get a lock on the
section to be able to use it (only one thread gets access at a time)
- For example: appending a new node to the end of a linked list
1
, Access/Concurrency control
- Compete for resources
- Processes may not be aware of each other
- Execution must not be affected by each other
- OS is responsible for controlling access
- Cooperate by sharing a common resource
- Programmer responsible for controlling access
- Hardware/OS/programming language may provide support
Control problems
- Mutual exclusion: only one process at a time is allowed in a critical section
- Modifications to critical sections should appear to happen atomically
- Deadlock: processes need multiple resources and are dependant on each other to give
up (some of) the resources they need
- A lock is deadlock free if threads want to get the lock, and it is not currently being
used, they can can acquire it
- If failure of a process anywhere (outside critical section) causes other processes
to deadlock (cannot access lock anymore), then the lock is not deadlock free
- For example, attempt 1 of mutual exclusion, where one processes always
passes control to the other process and is dependant on that one passing
it back to obtain the lock again
- Livelock: states of the group of processes are constantly changing with regard to each
other, but none are progressing (e.g. trying to obtain a lock, but backing off if that fails to
give another thread the opportunity to obtain it, but the other thread is doing the same)
- Starvation: a process is trying to access a resource but is never allowed to
- Livelock can be a form of starvation
Properties required for concurrency control:
- Starvation-freedom: no starvation
- Deadlock-freedom: no deadlocking
- Mutual exclusion: only one thread allowed in some
block of code
- For example, the code on the right does not
provide mutual exclusion, because it is
possible for two threads to reach the
writeIORef ref True part
Mutual exclusion
→ Only one thread at a time is allowed in the critical
section for a resource
- This needs to be implemented without causing a deadlock or starvation on attempting to
enter or leave the critical section
Implementation requirements
- A thread must not be delayed access to a critical section when there is no other thread
using it
2
