Anki Deck Changes

A functional unit is a component of a CPU (or core) that performs a certain task, e.g. executing integer arithmetic operations. An execution unit is one such a functional unit.

A program has a race condition if, during any possible execution with the same inputs, its observable behaviour (results, output, ...) may change if events happen in different order. Events here are typically scheduler interactions causing different interleavings, but could also be, e.g. changing network latency. Race condition is often used interchangeably with data race.

Given multiple threads, each executing a sequence of instructions, an interleaving is a sequence of instructions obtained from merging the individual sequences. A sequentially consistent interleaving is one where the relative order of statements from one thread is preserved.

Parallelism means doing multiple things at the same time (as opposed to concurrency: dealing with multiple things at the same time). Performing computations simultaneously; either actually, if sufficient computation units are available, or virtually, via some form of alternation. Often used interchangeably with concurrency. Parallelism can be specified explicitly by manually assigning tasks to threads or implicitly by using a framework that distributes tasks automatically.

Locality has several meanings in parallel programming: 1. Locally reason about one thread at a time (thread modularity) - simplifies correctness arguments. 2. Data locality: related memory locations are accessed shortly after each other - improves cache usage. 3. Code locality: straight-line code increases opportunities for instruction level parallelism.

A liveness property is a property of a system: "something good eventually happens". Can only be violated in infinite time. Infinite loops and starvation are typical liveness properties.

T_1 (sequential execution time) is the time that is required to perform some work on a single processor.

Efficiency expresses how much of the available CPU performance can be used. Heavily limited by the sequential part of a program. Efficiency = S_p/p.

The maximum possible speedup (parallelism) is T_1/T_∞. Here T_p is the time required to perform work on p processors, while T_∞ is the time required with infinite processors (only sequential part matters). T_1 is the sequential execution time.

Process context is all state associated with a process, including CPU state (registers, program counter), program state (stack, heap, resource handles), and additional management information. A thread also has a context, but it is typically much smaller.

The ForkJoin framework embraces divide and conquer parallelism. Tasks can be spawned (forked) and joined by the framework. The ForkJoin framework automatically assigns tasks to Java threads and may execute multiple tasks in one thread to avoid thread context switching overhead.

A lock is reentrant if it can be acquired (and released) multiple times by the same thread. If a lock is non-reentrant, trying to acquire it again might cause an exception or other problems.

A lock is a token/resource that can be acquired by at most one thread at a time. Locks are typically used to enforce mutual exclusion by guarding/protecting a critical section. A lock can be acquired/locked by a thread, and is then held until it is released/unlocked. In Java, each object can be used as a lock (intrinsic/monitor lock).