The Data Stream Page
Why Reinvent Compting? Pse, study Thomas Sterling's interview entitled: 'I Think We Will Never Reach Zettaflops'. See HPCwire (mirror). Thomas Sterling takes us through some of the most critical developments in high performance computing, explaining why the transition to exascale is going to be very different than the ones in the past. I agree. However, I believe, we will reach Zetaflops --- by Reconfigurable Computing.
Data Stream Computing has nothing to do with Data Flow Computing!! Let us have a look at the history: Stressing differences to „Control-Flow“ Computers a research area called „Dataflow“ Computers was started in the mid‘ 70ies at MIT. However, instead of on data these devices work on a complicated "Tagged Token Flow", which they also call "I-structure". On February 1982 a paper entitled "A Second Opinion on Data Flow Machines and Languages" was published in IEEE COMPUTER by D. D. Gajski, D. A. Padua, D. J. Kuck, and R. H. Kuhn: " ..... data flow techniques attract a great deal of attention. Other alternatives, however, offer more hope for the future. ....." Starting a little bit later than this dataflow scene we Xputer area people were forced to sidestep by using other terms like „data-driven“ or „data streams“…
Datastream Computers have been implemented already in the late 80ies at Kaiserslautern, also called Xputers. For programming a straight forward FPGA such a datastream model looks quite natural, since there are no instruction streams running through. We at Kaiserslautern defined its underlying "anti machine" paradigm as the counterpart of the von Neumann paradigm. The anti machine uses data counters instead of a program counter. Using a reconfigurable address generator (e.g. GAG) we avoided memory-cycle-hungry instruction streams for address computation, parts of asM modules ("auto-seqeuencing memories").
We implemented an Xputer architecture which we called "MoM" (map-oriented machine), within the "PISA" project: a VLSI design rule check accelerator. When the design was started in 1984, first Xilinx FPGAs just coming to the market have been very small. To avoid needing 256 XILINX FPGAs we designed and implemented our own much more area-efficient reconfigurable chip called DPLA. It has been fabricated within the "E.I.S. Projekt" multi project chip intrastructure. Compared to classical software implementation we obtained a speed-up by more than 15,000 - i. e. more than 15 years erlier than any other projects reaching similar speed-up facors.
Our data stream features data-transport-triggered execution (in contrast to instruction-stream-driven execution). For terminology also see here. We also created and implemented a datastream programming language MoPL (Map-oriented Programming Language), supporting also more than one dimension for the data address space. For instance, the PISA poject, based on modified image processing, it suppoerted a 2-dimensional data address space. The MoPL compiler input we call "Flowware" which is the counter part of "Software". For terminology see table 1.
In the 80ies and 90ies we at Kaiserslautern published a lot about datastream computing, partly in the context of reconfigurable computing. See literature list below, which mentions only a part of our related papers. For a more complete and up-to-date list of literature see www.fpl.uni-kl.de/xputer-pages/ASIC_X.htm
(in German Language) |
Auto-sequencing memory (asM) |
Generic Address Generator (GAG) |
|Search Google (number of hits: see the line " Results")
Bing (for the number of hits see
the line " Results")
|RL FPGA | "Reconfigurable Computing" | FPGA & "oil and gas" | FPGA & "automotive" | FPGA & "medical" | FPGA & "chemical" | FPGA & "bio" | FPGA & "defense" | FPGA & "physics" | FPGA & "molecular" | FPGA & "supercomputing" | FPGA & "HPC" | FPGA & "high performance computing" | GAG generic address generator | von Neumann syndrome | Map-oriented Machine | Map-oriented Programming Language PISA design rule check | Xputer paradigm | hardware description language KARL |||FPGA | "Reconfigurable Computing" | FPGA & "oil" | FPGA & "gas" | FPGA & "automotive" | FPGA & "medical" | FPGA & "chemical" | FPGA & "bio" | FPGA & "defense" | FPGA & "physics" | FPGA & "molecular" | FPGA & "supercomputing" | FPGA & "HPC" | FPGA & "high performance computing" | GAG generic address generator | von Neumann syndrome | Map-oriented Machine | Map-oriented Programming Language | PISA design rule check | Xputer paradigm | hardware description language KARL ||
Data-stream-based machines do not have a von Neumann bottle neck and have much less overhead
phenomena than von Neumann machines. For data-intensive very high performance
applications data-stream-based computing is the drastically more
promising solution than von Neumann. This is the reason, why data-stream-.based
computing goes mainstream - additionally stimulated by the break-through
of reconfigurable computing. Datastream-based
computing is also a reason for the fast advance of embedded-memory-related
markets and R&D (see flowware page
and see here (click on the red field) and
also see here).
Table no. 1: toward a consensus on basic terminology:
Acronyms: r = reconfigurable | FP = field-programmable | GA = gata array | DPU = DataPath Unit | DPA = DPU array |
The von Neumann machine model
The von Neumann machine is instruction-stream-based and uses a CPU which can sequence only a single instruction stream by means of a program counter. The CPU includes a datapath unit (DPU) and a single inctruction sequencer (see fig. 1). The memory of a von Neumann machine has no sequencers, since the memory addresses are delivered by the CPU.
The anti machine model
The anti machine is
and uses only a DPU, i. e. without a sequencer, or, a DPU
array (DPA) without sequencers (see fig. 1).
anti machine model locates sequencers as part of the memory.
register is the data counter, the address generator located within
memory (see left side of fig. 3). A
anti machine may have one or multiple data counters and may be
by a single data stream or multiple data-streams (see left side
3). For the anti machine the data streams have to be programmed to
determine, which data item has to meet which DPU port or DPA port at
time (fig. 2). Such data-stream-based program
we call flowware, in contrast to traditional
No dataflow machine
The anti machine is
like also the von Neumann machine. The historic term "dataflow
however, has been used for an indeterministic machine, driven by an
so that the order of execution cannot be predicted. The anti machine is
no "dataflow machine".
Reconfigurable anti machine
In contrast to the
Neumann machine, anti machines also support reconfigurable data paths
or DPAs). Configuration may be considered to be a kind of "instruction
fetch" before run time (at configuration time), where such an
may be much more powerful than a typical on Neumann instruction. About
reconfigurability and Reconfigurable Computing see the morphware
The dicholomy of machine paradigms: software versus flowware
Fig. 4 compares both machine paradigms. Fig. 5 compares software programming languages versus flowware programming languages. There massive similarities, since the only difference is the use of a program counter versus a use of data counters, The only difference stems from the anti machine property which allows multiple data counters, so that flowware languages support more RT level parallelism than software languages..
Literature (for more details see here)