Synchronous Data Flow

Last updated

Synchronous Dataflow is a restriction of Kahn process networks where nodes produce and consume a fixed number of data items per firing. This allows static scheduling.

Kahn process networks

Kahn process networks is a distributed model of computation where a group of deterministic sequential processes are communicating through unbounded FIFO channels. The resulting process network exhibits deterministic behavior that does not depend on the various computation or communication delays. The model was originally developed for modeling distributed systems but has proven its convenience for modeling signal processing systems. As such, KPNs have found many applications in modeling embedded systems, high-performance computing systems, and other computational tasks. KPNs were first introduced by Gilles Kahn.

In computing, scheduling is the method by which work specified by some means is assigned to resources that complete the work. The work may be virtual computation elements such as threads, processes or data flows, which are in turn scheduled onto hardware resources such as processors, network links or expansion cards.

See also


Related Research Articles

SDF may refer to:

Dataflow is a term used in computing which has various meanings depending on application and the context in which the term is used. In the context of software architecture, data flow relates to stream processing or reactive programming.

Signal programming is used in the same sense as dataflow programming, and is similar to event-driven programming.

In computer programming, dataflow programming is a programming paradigm that models a program as a directed graph of the data flowing between operations, thus implementing dataflow principles and architecture. Dataflow programming languages share some features of functional languages, and were generally developed in order to bring some functional concepts to a language more suitable for numeric processing. Some authors use the term datastream instead of dataflow to avoid confusion with dataflow computing or dataflow architecture, based on an indeterministic machine paradigm. Dataflow programming was pioneered by Jack Dennis and his graduate students at MIT in the 1960s.

Dataflow architecture is a computer architecture that directly contrasts the traditional von Neumann architecture or control flow architecture. Dataflow architectures do not have a program counter, or the executability and execution of instructions is solely determined based on the availability of input arguments to the instructions, so that the order of instruction execution is unpredictable: i. e. behavior is nondeterministic.

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how a set of outputs are computed given a set of inputs. This model describes how units of computations, memories, and communications are organized. The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology.

A synchronous programming language is a computer programming language optimized for programming reactive systems. Computer systems can be sorted in three main classes: (1) transformational systems that take some inputs, process them, deliver their outputs, and terminate their execution; a typical example is a compiler; (2) interactive systems that interact continuously with their environment, at their own speed; a typical example is the web; and (3) reactive systems that interact continuously with their environment, at a speed imposed by the environment; a typical example is the automatic flight control system of modern airplanes. Reactive systems must therefore react to stimuli from the environment within strict time bounds. For this reason they are often also called real-time systems, and are found often in embedded systems.

Lustre is a formally defined, declarative, and synchronous dataflow programming language for programming reactive systems. It began as a research project in the early 1980s. A formal presentation of the language can be found in the 1991 Proceedings of the IEEE. In 1993 it progressed to practical, industrial use in a commercial product as the core language of the industrial environment SCADE, developed by Esterel Technologies. It is now used for critical control software in aircraft, helicopters, and nuclear power plants.

Stream (computing) sequence of data elements made available over time

In computer science, a stream is a sequence of data elements made available over time. A stream can be thought of as items on a conveyor belt being processed one at a time rather than in large batches.

In computer programming, flow-based programming (FBP) is a programming paradigm that defines applications as networks of "black box" processes, which exchange data across predefined connections by message passing, where the connections are specified externally to the processes. These black box processes can be reconnected endlessly to form different applications without having to be changed internally. FBP is thus naturally component-oriented.

Dryad was a research project at Microsoft Research for a general purpose runtime for execution of data parallel applications. Microsoft made several preview releases of this technology available as add-ons to Windows HPC Server 2008 R2. However, in October 2011, Microsoft discontinued active development on Dryad, shifting focus to the Apache Hadoop framework.

ISO 1745:1975 Information processing – Basic mode control procedures for data communication systems is an early ISO standard defining a Telex-oriented communications protocol that used the non-printable ASCII transmission control characters SOH, STX, ETX, EOT, ENQ (Enquiry), ACK (Acknowledge), DLE, NAK, SYN, and ETB.

Preesm

PREESM is an open-source rapid prototyping and code generation tool. It is primarily employed to simulate signal processing applications and generate code for multi-core Digital Signal Processors. PREESM is developed at the Institute of Electronics and Telecommunications-Rennes (IETR) in collaboration with Texas Instruments France in Nice.

Globally asynchronous locally synchronous (GALS) is an architecture for designing electronic circuits which addresses the problem of safe and reliable data transfer between independent clock domains. GALS is a Model of Computation (MoC) that emerged in the 1980s. It allows to design computer systems consisting of several synchronous islands interacting with other islands using asynchronous communication, e.g. with FIFOs.

Apache Flink framework and distributed processing engine for stateful computations over unbounded and bounded data streams

Apache Flink is an open source stream processing framework developed by the Apache Software Foundation. The core of Apache Flink is a distributed streaming dataflow engine written in Java and Scala. Flink executes arbitrary dataflow programs in a data-parallel and pipelined manner. Flink's pipelined runtime system enables the execution of bulk/batch and stream processing programs. Furthermore, Flink's runtime supports the execution of iterative algorithms natively.

A vision processing unit (VPU) is an emerging class of microprocessor; it is a specific type of AI accelerator, designed to accelerate machine vision tasks.

Apache Beam

Apache Beam is an open source unified programming model to define and execute data processing pipelines, including ETL, batch and stream (continuous) processing. Beam Pipelines are defined using one of the provided SDKs and executed in one of the Beam’s supported runners including Apache Apex, Apache Flink, Apache Gearpump (incubating), Apache Samza, Apache Spark, and Google Cloud Dataflow

Asynchronous procedure call is a unit of work in a computer. Usually program works executing a series of synchronous procedure calls on some thread. But if some data are not ready, then keeping thread in wait state is impractical, as a thread allocates considerable amount of memory for procedure stack, and this memory is not used. So such a procedure call is formed as an object with small amount of memory for input data, and this object is passed to the service which receive user inputs. When the user's reply is received, the service puts it in the object and passes that object to an execution service. Execution service consists of one or more dedicated worker threads and a queue for tasks. Each worker thread reads in a loop task queue and, when a task is retrieved, executes it. When there is no tasks, worker threads are waiting and so their memory is not used, but the number of worker threads is small enough.