go to Xputer pages

homepage | impressum | survey | last update June 2001, May 2012

The Data Stream Page

http://data-streams.org

 

TU Kaiserslautern

 Karlsruhe Institute of Technology (KIT) homepageInstitut für Technik der Informationsverarbeitung (ITIV) des Karlsruher Institut für Technologie (KIT)

 

Reconfigurable Computing (RC) pages @ TU Kaiserslautern

These Reconfigurable Computing pages are about a route to Reinvent Compting. This term is not new. See the keynote by Burton Smith (former Cray CTO).

Why Reinvent Compting? Pse, study Thomas Sterling's interview entitled: 'I Think We Will Never Reach Zettaflops'. See  HPCwire. 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.

Dataflow Computing is not new

Datastream Computers have been implemented already in the late 80ies at Kaiserslautern. But at that time such computers, also called Xputers, have been classified as exotic. However, 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 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.

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.


Xputers | wrongroadmap | anti-machine | configware | morphware | flowware | data.streams | KressArray

 Xputers (in German Language) | Auto-sequencing memory (asM) | Generic Address Generator (GAG) | Reinvent Computing



Data-stream-based anti machines do not have a  von Neumann bottleneck


 

 

   

 

Search Google (for the number of hits see the line "Web ... Results" )
Search Yahoo (for the number of hits see the line "Search Results" )
"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" | "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" |

Why data-stream-based computing is going mainstream

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).

Table no. 1: toward a consensus on basic terminology:

platform

program source running on it

 machine paradigm

hardware (not programmable)  (none)
morphware fine grain rGA (FPGA) configware
coarse grain rDPU, rDPA
reconfigurable data stream processor flowware & configware anti machine
data stream processor (hardwired) flowware
instruction stream processor software von Neumann machine

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.


Fig. 1: CPU (von Neumann) versus DPU / DPA (anti machine)

The anti machine model

The anti machine is data-stream-based and uses only a DPU, i. e. without a sequencer, or, a DPU array (DPA) without sequencers (see fig. 1). The anti machine model locates sequencers as part of the memory. State register is the data counter, the address generator located within memory (see left side of fig. 3). A single  anti machine may have one or multiple data counters and may be driven by a single data stream or multiple data-streams  (see left side of fig. 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 which time (fig. 2). Such data-stream-based program sources we call flowware, in contrast to traditional  instruction-stream-driven software.


Fig. 2: Definition of Data Streams (Flowware)

No dataflow machine

The anti machine is deterministic, like also the von Neumann machine. The historic  term "dataflow machine", however, has been used for an indeterministic machine, driven by an arbiter, so that the order of execution cannot be predicted. The anti machine is no "dataflow machine".


Fig. 3: Configware / Flowware Co-Compilation

Reconfigurable anti machine

In contrast to the von  Neumann machine, anti machines also support reconfigurable data paths (DPUs or DPAs). Configuration may be considered to be a kind of "instruction fetch" before run time (at configuration time), where such an "instruction" may be much more powerful than a typical on Neumann instruction. About reconfigurability and Reconfigurable Computing see the morphware page.


Fig. 4: machine paradigms


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..


Fig. 5: programming language paradigms: software vs. flowware

Literature

R. Hartenstein, R.Hauck, A.Hirschbiel, W.Nebel, M.Weber) PISA - A CAD package and special hardware for pixel-oriented layout analysis, ICCAD, Santa Clara, 1984, IEEE, New York 1984

      
R. Hartenstein, A.Hirschbiel, M. Weber: MOM - Map Oriented Machine, Proceedings of the International Workshop on Hardware Accelerators, Oxford, UK Oct. 1987

      
R. Hartenstein, A.Hirschbiel, M.Weber: MOM - Map Oriented Machine, Conference on Parallel Processing and Applications, L'Aquila, Italy, Sept. 1987.

      
R. Hartenstein, A.Hirschbiel, M.Weber: A Flexible Architecture for Image Processing, Proceedings of the EUROMICRO Symposium, Portsmouth, UK, 1987

      
R. Hartenstein, M. Weber et al.: MOM - Map Oriented Machine; in: E. Chiricozzi (ed.): Parallel Processing and Applications, North-Holland, 1988

      
R. Hartenstein, K. Lemmert: CHDL-Based CAD System for the Synthesis of Systolic Architectures; in: McCanny, McWhirter, Swartzlander: Systolic Array Processors, Prentice Hall, London 1989. (proc. ASAP conference)

      
R. Hartenstein, . A.G. Hirschbiel, M.Weber: Mapping Systolic Arrays onto the Map-Oriented Machine (MoM); in: McCanny, McWhirter, Swartzlander: Systolic Array Processors, Prentice Hall, London 1989.

      
R. Hartenstein, Xputer: Rechner nach neuartigen Prinzipien; GI Informatik Spektrum, Dezember 1989, Springer-Verlag, Berlin / Heidelberg / New York, 1989. - translation of title -

      
NN.: Der Rechner aus dem Elfenbeinturm; Markt & Technik, Nr. 44/89, Okt. 1989. - translation of title: The Computer out of the Ivory-Tower)
R. Hartenstein, Xputer: Rechner nach neuartigen Prinzipien; GI Informatik Spektrum, Dezember 1989, Springer-Verlag, Berlin / Heidelberg / New York, 1989. -

      
R. Hartenstein, A.G. Hirschbiel, M.Weber: MOM - a partly custom-design architecture compared to standard hardware, Proc. IEEE Compeuro, Hamburg 1989, IEEE Press, 1989

      
R. Hartenstein, A.G. Hirschbiel, M.Weber: MOM - a partly custom-design architecture compared to standard hardware, Proc. IEEE Compeuro, Hamburg 1989, IEEE Press, 1989.

      
R. Hartenstein, A. G. Hirschbiel, M. Riedmüller, K. Schmidt, M. Weber: A High Performance Machine Paradigm Based on Auto-Sequencing Data Memory; HICSS-24 Hawaii Int'l Conference on System Sciences, Koloa Hawaii, January 1991

      
R. Hartenstein, H. Reinig, M. Riedmüller, K. Schmidt: A Novel Computational Paradigm: Much More Efficient Than Von Neumann Principles; 13th IMACS World Congress, Dublin Ireland, July 1991

      
R. Hartenstein, K. Schmidt, H. Reinig, M. Weber: A Novel Compilation Technique for a Machine Paradigm Based on Field-Programmable Logic; International Workshop on Field Programmable Logic and Applications, Oxford 1991

      
R. Hartenstein, A. Ast, H. Reinig, K. Schmidt, M. Weber: A General Purpose Xputer Architecture derived from DSP and Image Processing; in M.A. Bayoumi (ed.): VLSI Design Methodologies for Digital Signal Processing Architectures, Kluwer Academic Publishers, p. 365-394, 1994.

      
R. Hartenstein, H. Reinig, et al.: A New FPGA Architecture for Word-oriented Datapaths; 4th Int. Workshop On Field Programmable Logic And Applications, FPL'94, Prague, September 7-10, 1994, Lecture Notes in Computer Science, Springer, 1994

      
R. Hartenstein, A. Ast, J. Becker, et al.: Data-procedural Languages for FPL-based Machines; 4th Int. Workshop On Field Programmable Logic And Applications, FPL'94, Prague, September 7-10, 1994, Lecture Notes in Computer Science, Springer, 1994.

      
R. Hartenstein, Karin Schmidt: Parallelizing Compilation for a Novel Data-Parallel Architecture; J. P. Gray, F. Naghdy (Eds.), PCAT-94, Parallel Computing: Technology and Practice, Wollongong, Australia, pp. 126-137, Nov. 1994

      
R. Hartenstein, K. Schmidt: A Restructuring Compilation Method for the Xputer Paradigm: IWPP 94, Proceedings of the Int. Workshop on Parallel Processing, Bangalore, India, Dec. 1994

      

R. Hartenstein, J. Becker, R. Kress, H. Reinig, K. Schmidt: A Parallelizing Compilation Method for the Map-oriented Machine; Proc. ASAP '95 (the IEEE International Conference on Application Specific Array Processors)

      
(invited paper) R. Hartenstein, M. Herz, M. Miranda, Erik., F. Catthoor: Memory Organisation for Stream-based Reconfigurable Computing; 9th IEEE International Conference on Electronics, Circuits and Systems - ICECS 2002, September 15-18, 2002, Dubrovnik, Croatia


 

Xputers | wrongroadmap | anti-machine | configware | morphware |

flowware | data.streams | KressArray   Xputers (in German Language) |

Auto-sequencing memory (asM) | Generic Address Generator (GAG) |

Reinvent Computing

 

configware |

datastream |

flowware |

hardware |

morphware |

software

 

For the relations between these    terms see http://flowware.net/#table1

 

   

        

 
   
search Morphware with GoogleYahoo | BING  |

search Configware with GoogleYahooBING   |

search   Flowware with Google | Yahoo | BING  |

search Data Stream with GoogleYahooBING  |

search   Kress Array with Google | Yahoo | BING  | search  Anti Machine with Google | Yahoo | BING  | 

Impressum

search  Xputer with Google | Yahoo | BING  | 

 

Computer Structures Group
Department of Computer Science
University of Kaiserslautern
© Copyright 2001, 2005, 2012, TU Kaiserslautern, Kaiserslautern, Germany Webmaster