synchronous concurrent algorithm

Quick Reference


An algorithm that consists of a network of processors computing and communicating in parallel and synchronized by means of a global clock, or possibly a family of clocks. The algorithm operates continually in discrete time, processing infinite streams of input data; its behavior can be represented by a stream transformer. SCAs are deterministic, and can be considered as special types of timed deterministic dataflow algorithms. Hardware systems, such as systolic arrays or microprocessors, are made from SCAs. Other examples of SCAs include certain neural networks, cellular automata, spatially extended discrete-time dynamical systems, and finite-element algorithms. Through the concept of an SCA, a wide variety of deterministic parallel algorithms can be given a common mathematical theory and programming methodology. The theory is based on the use of equational specifications and abstract computability theory, and the programming tools on imperative languages using concurrent assignments.

Subjects: Computing.

Reference entries