Dataflow architecture

Dataflow architecture

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 (at least conceptually) the executability and execution of instructions is solely determined based on the availability of input arguments to the instructions. Although no commercially successful general-purpose computer hardware has used a dataflow architecture, it has been successfully implemented in specialized hardware such as in digital signal processing, network routing, graphics processing and more recently in data warehousing. It is also very relevant in many software architectures today including database engine designs and parallel computing frameworks.

Synchronous dataflow architectures tune to match the workload presented by real-time data path applications such as wire speed packet forwarding. Dataflow architectures that are deterministic in nature enable programmers to manage complex tasks such as processor load balancing, synchronization and accesses to common resources [1].

Hardware architectures for dataflow was a major topic in computer architecture research in the 1970s and early 1980s. Jack Dennis of MIT pioneered the field of static dataflow architectures while the Manchester Dataflow Machine[2] and MIT Tagged Token architecture were major projects in dynamic dataflow.

Designs that use conventional memory addresses as data dependency tags are called static dataflow machines. These machines did not allow multiple instances of the same routines to be executed simultaneously because the simple tags could not differentiate between them. Designs that use content-addressable memory (CAM) are called dynamic dataflow machines. They use tags in memory to facilitate parallelism.

Normally, compilers analyze program source code for data dependencies between instructions in order to better organize the instruction sequences in the binary output files. The instructions are organized sequentially but the dependency information itself is not recorded in the binaries. Binaries compiled for a dataflow machine contain this dependency information. A dataflow compiler records these dependencies by creating unique tags for each dependency instead of using variable names. By giving each dependency a unique tag, it allows the non-dependent code segments in the binary to be executed out of order and in parallel.

Programs are loaded into the CAM of a dynamic dataflow computer. When all of the tagged operands of an instruction become available (that is, output from previous instructions and/or user input), the instruction is marked as ready for execution by an execution unit. This is known as activating or firing the instruction. Once an instruction is completed by an execution unit, its output data is stored (with its tag) in the CAM. Any instructions that are dependent upon this particular datum (identified by its tag value) are then marked as ready for execution. In this way, subsequent instructions are executed in proper order, avoiding race conditions. This order may differ from the sequential order envisioned by the human programmer, the programmed order.

An instruction, along with its required data operands, is transmitted to an execution unit as a packet, also called an instruction token. Similarly, output data is transmitted back to the CAM as a data token. The packetization of instructions and results allows for parallel execution of ready instructions on a large scale. Dataflow networks deliver the instruction tokens to the execution units and return the data tokens to the CAM. In contrast to the conventional von Neumann architecture, data tokens are not permanently stored in memory, rather they are transient messages that only exist when in transit to the instruction storage.

The research, however, never overcame the problems related to:

  • Efficiently broadcasting data tokens in a massively parallel system.
  • Efficiently dispatching instruction tokens in a massively parallel system.
  • Building CAMs large enough to hold all of the dependencies of a real program.

Instructions and their data dependencies proved to be too fine-grained to be effectively distributed in a large network. That is, the time for the instructions and tagged results to travel through a large connection network was longer than the time to actually do the computations.

Nonetheless, Out-of-order execution has become the dominant computing paradigm since the 1990s. It is a form of restricted dataflow. This paradigm introduced the idea of an execution window. The execution window follows the sequential order of the von Neumann architecture, however within the window, instructions are allowed to be completed in data dependency order. This is accomplished in CPUs that dynamically tag the data dependencies of the code in the execution window. The logical complexity of dynamically keeping track of the data dependencies, restricts OoO CPUs to a small number of execution units (2-6) and limits the execution window sizes to the range of 32 to 200 instructions, much smaller than envisioned for full dataflow machines.

See also

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Dataflow — This article is about software engineering. For the flow of data within a computer network see packet flow For the graphical representation of flow of data within an information system, see data flow diagram Dataflow is a term used in computing,… …   Wikipedia

  • Architecture Dataflow — Un ordinateur dataflow (flot de données) décrit une architecture où les données sont des entités actives qui traversent le programme de manière asynchrone, contrairement à l architecture classique von Neumann où elles attendent passivement en… …   Wikipédia en Français

  • Dataflow programming — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computing …   Wikipedia

  • Architecture Design and Assessment System — The Architecture Design and Assessment System (ADAS) was a set of software programs offered by the Research Triangle Institute from the mid 1980s untilthe early 1990s. [G.A. Frank, D.L. Franke, and W.F. Ingogly, An Architecture Design and… …   Wikipedia

  • dataflow — ˈ ̷ ̷  ̷ ̷ ˌ ̷ ̷ noun : a computer architecture that utilizes multiple parallel processors to perform simultaneous operations as data becomes available …   Useful english dictionary

  • Transport triggered architecture — The transport triggered architecture (TTA) is an application specific instruction set processor ( ASIP ) architecture template that allows easy customization of microprocessor designs. The basic idea of transport triggering is to allow programs… …   Wikipedia

  • Transport triggered architecture — (TTA)  вариант архитектуры микропроцессоров, в которой программы непосредственно управляют внутренними соединениями (шинами) между блоками процессора (например, АЛУ, Регистровый файл). Вычисления являются побочным эффектом передачи данных… …   Википедия

  • DataRush Technology — DataRush Technology, introduced in 2009 by Austin based technology company Pervasive Software, uses multicore technology to process data sets for analytics and other business applications. The technology enables performance on a single server or… …   Wikipedia

  • Datenfluss-Architektur — Eine Datenfluss Architektur ist eine alternative Rechnerarchitektur zur sogenannten von Neumann Architektur, nach der die allermeisten heute gängigen Rechner implementiert sind. Ein nach der Datenfluss Architektur implementierter Rechner heißt… …   Deutsch Wikipedia

  • Datenflussarchitektur — Eine Datenfluss Architektur ist eine alternative Rechnerarchitektur zur sog. von Neumann Architektur, nach der die allermeisten heute gängigen Rechner implementiert sind. Ein nach der Datenfluss Architektur implementierter Rechner heißt… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”