Concurrent computing organizes computations whose execution intervals can overlap. They may interleave on one processor or run simultaneously on several; concurrency therefore differs from hardware parallel computing. Two workers incrementing a shared counter by separate read-modify-write steps can lose an update if both read the same old value. Synchronization constrains such interactions, while message passing organizes communication through explicit exchanges. A correct concurrent program must account for permitted schedules, not merely the particular order seen during one successful run.
An execution trace records the ordered steps or observations of one program execution under a chosen observation model. It might record machine instructions, state changes, procedure calls or visible communication events. The model determines what is hidden; two traces cannot be compared meaningfully without knowing their event vocabulary.
For two threads each incrementing a shared counter, a trace can record both reading zero before either writes one. Its final counter value is one even though two increments were requested. A different interleaving can produce two. One observed successful trace therefore does not establish correctness of all permitted interleavings. In communicating sequential processes, a trace conventionally records visible CSP events; internal transitions are omitted. Such a trace records what occurred but does not by itself say which unperformed events were available.
Parallel computing performs multiple parts of a computation simultaneously, typically on several processors or execution units. It requires decomposing work and coordinating data dependencies, communication and synchronization. Concurrent computing also permits overlapping activities on a single processor, so concurrency alone does not imply simultaneous hardware execution.
If fraction of a fixed computation remains serial and the rest divides perfectly among processors, the idealized runtime is . Thus Amdahl's law gives speedup
for . With a 10 percent serial fraction and 10 processors, the ideal speedup is about 5.26, before communication overhead. The calculation assumes a fixed workload; changing the workload size changes the question. Load imbalance and limited memory bandwidth can further reduce the achieved gain.
Amdahl's law bounds the speedup obtained by accelerating only part of a fixed computation. Let fraction of its original execution time remain serial, while fraction divides perfectly among identical processors. Then
The terms add because the serial and accelerated parts still both have to finish. If , ten processors give ; even infinitely many cannot exceed speedup ten.
Gene M. Amdahl's 1967 argument emphasized sequential work and irregularities in real computations.[ref] The displayed idealized formula follows from the stated time decomposition. Communication, synchronization, unequal work and limited memory bandwidth can reduce actual speedup. Increasing the problem size changes the serial fraction and asks a different scaling question.
A Scala library for constructing communicating concurrent processes with typed message-passing channels, parallel composition and guarded alternation.[ref]
A choice among enabled communication events, committing one ready event. An event whose Boolean guard is false is not offered. Output events must be selected before their value-producing expression or post-send state update is performed.
A process algebra describes interacting systems through CSP events, composition operators and equations relating their behaviours. Communicating sequential processes is one such framework.
A process algebra in which components communicate through synchronized CSP events. Its operational description uses a labelled transition system; standard observations include CSP traces, CSP stable failures and CSP divergences.[ref]
Rules deriving the labelled transition system of a composite CSP process from transitions of its components.
An algebraic expansion listing the initially possible CSP events and their continuations. It translates operational transition cases into CSP external choice expressions.
For a suitably guarded recursion, two solutions of the same defining equation denote the same CSP process. There is also a mutually recursive version, comparing tuples of solutions.
A representation of a CSP process by specified kinds of observable behaviour. The CSP traces model, CSP stable-failures model and CSP failures-divergences model record progressively more information about refusals and internal activity.
Implementation has only behaviours permitted by specification in CSP semantic model . In particular, CSP traces model refinement means ; the other models additionally constrain CSP stable failures or CSP divergences.
Record CSP stable failures and CSP divergences, treating behaviour after a CSP divergence as unrestricted. This can detect both stable refusal of progress and endless internal activity.
Represent a CSP process by its set of CSP traces.
The possibility, after a finite visible CSP trace, of an infinite sequence of consecutive CSP internal actions. The CSP failures-divergences model records this possibility explicitly.[ref]
After CSP trace , the CSP process can reach a CSP stable state offering no event in the refusal set . Refusal is existential over reachable stable alternatives.[ref]
A finite sequence of visible CSP events performed by a CSP process, omitting CSP internal actions.
A component specified by possible CSP events and successor behaviours. has no transitions. CSP prefixing, CSP choice and CSP parallel composition construct larger components.
Behave as until it performs a visible CSP event in , then switch to . The triggering event is included in the visible CSP trace.
Allow to proceed while is ready to interrupt. The first visible CSP event of discards and leaves the derivative of . A CSP internal action of alone does not discard .
Turn CSP events in into CSP internal actions. Infinite hidden activity can create CSP divergence.
Relabel visible CSP events according to a function or relation, preserving CSP internal actions. An injective relabelling preserves event identity; a non-injective one can merge distinct actions. In relational renaming, an original event with no image is disabled. Thus partial relational renaming can also restrict an interface.
Events in require both CSP processes; other visible CSP events advance one participant independently. CSP internal actions do not synchronize.
The alphabets assigned to participants determine their shared CSP events. An event in both assigned alphabets requires both participants; one assigned only to a single participant advances that participant. Replicated composition synchronizes all participants whose assigned alphabets contain the event.
In communicating sequential processes, CSP choice combines possible process behaviours. With external choice , an offered CSP event selected by the environment can determine which branch proceeds. Internal choice leaves the branch selection nondeterministic from the environment's viewpoint. For example, choosing externally between receiving left and receiving right offers both alternatives; internally choosing a branch can remove one offer before the environment acts. Sets of execution traces alone can hide this distinction, so CSP failures semantics also records CSP refusal sets of CSP events that may be declined.
CSP failures semantics augments visible traces with refusal information. In the stable failures model, a pair means that after visible trace , the process can reach a stable state with no internal transition and no offered event in . It records a possible refusal, not a requirement that every state reached after refuse .[ref]
External choice between offering and offering cannot initially refuse either offered event. Internal choice between the same branches may select the branch and refuse . Their visible trace sets can agree even though these refusals differ. Failures-divergences semantics additionally records possible infinite internal activity; it is a distinct model.
A CSP refusal set is a set of visible CSP events that a process can decline together in a stable state. Stability excludes an enabled internal transition. Pairing with a preceding trace gives a failure observation; different internal resolutions after the same trace can produce different refusal sets.[ref]
For an event alphabet , a state offering only can refuse but cannot refuse . Every subset of a possible refusal is also possible. In a model without a separate successful-termination event, refusing the entire event alphabet signals deadlock. Refusals therefore distinguish a missing offer from an event merely not selected by the environment.
The process may internally choose either branch, independently of the environment's offered CSP events. Consequently it can have more CSP stable failures than the corresponding CSP external choice, despite having the same CSP traces.
The first visible CSP event resolves the choice; the environment can select an event offered by only one branch. CSP internal actions can advance a branch without selecting it.
Perform CSP event , then behave as CSP process .
An unobservable transition that the environment cannot block. CSP hiding turns selected visible CSP events into CSP internal actions.
A state with no outgoing CSP internal action. A CSP stable failure records a refusal only after such a state has been reached.
An instantaneous visible interaction. A channel event such as combines a channel name with a communicated value. Participants synchronize on one event rather than separately sending and receiving it.
A property of a component whose specified behavior remains correct when operations are invoked concurrently by several threads under the stated synchronization assumptions.

Articles by others on the same topic (0)

There are currently no matching articles.