go to Xputer pages

homepage | impressumsurvey |  MM | last update 2001, 2012

The Anti-Machine Page


Sitemap      Sitemap_2

TU Kaiserslautern

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

"Anti-Machine" (or Xputer) stands for the counterpart of the von Neumann paradigm. The anti-machine uses data counters instead of a programm counter. It is datastream-based and does not run any instruction streams.

Reconfigurable Computing 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).    [mirror]

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  going heterogeneous via Reconfigurable Computing.

[ anti-machine | configware | data-streams | flowware | home | impressum | kressarray | morphware | von Neumann Syndrome | wrongroadmap | xputer |

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

The Xputer supporting the Mead-&-Conway Microchip Design Revolution
: DRC speed-up by a factor of 15.000 (see the PISA project).


The Success of the Software Industry is RAM-based.

RAM-based, also the Xputer and the Configware Industry will succeed.

FPL map






Why a Generalization of Software Engineering ?

Panel discussions and keynote addresses are booming since the computing crisis caused by the von Neumann syndrome. Because of the coincidence of several disruptive developments we need to Reinvent Computing [1]. We cannot afford any more the CPU-centric, i. e. instruction-stream-centric Software-centric  Aristotelian world model of computing. We are forced to go toward heterogeneous computing systems based on a Kopernican World model of Computing (Figure A) [2]. We urgently need the Generalization of Software Eingineering (SE) into Program Engineering (PE) which interlaces two machine paradigms:

  • the instruction-stream-based traditional von Neumann paradigm, controlled by a program counter. Its programming source is called "Software", which is a subject of SE (software engineering). see fig. A. We need to reinvent software engineering [4].


  • the data-stream-based anti-machine-paradigm  [3] controlled by data counters instead of a program counter [3] Its programming source is called "Flowware" (FE, see fig. A), which programs data streams to run through reconfigurable hardware like FPGAs, which can be viewed as pipe networks, the generalization of systolic arrays. Sinks and sources of data streams are auto-sequencing memory blocks (asM).

By migration of applications from software to configware/flowware speed-up factors and power saving factors by up to several orders of magnitude can be obtained [8]. We also need a third area: Configware Engineering (CE). See  [5] - [7] and fig. A

  • Configware is the programming code for reconfigurable platforms like FPGAs. Flowware can be programmed only, when reconfiguration from configware is finished, so that the datapaths inside have been set up.

We have to set up Program Engineering (PE) education to replace Software Engineering (SE) Education because programming heterogeneous systems requires a mix of skills from all three side of the PE world (Fig. A), i. e. even also from Configware Engineering (CE). By migration of an application from SE to FE / CE, for instance, a different algorithm may be needed. So, for instance, the sequential Bubble Sort algorithms has to be converted into the Shuffle Sort algorithm to avoid accessing conflicts caused by parallelism [9].

Figure A; Going heterogeneous: our Copernican World Model of Computing

Why a Duality of Machine Paradigms ?

The von Neumann machine paradigm

The von Neumann machine paradigm does not support configware. However, configware is supported by our data-stream-based Xputer machine paradigm (anti machine paradigm). Such data stream machines are programmed from 2 different sources: by flowware, which programs the data streams flowing from and to the machine's DPU (data path unit) or DPA (DPU array), and, by configware.The von Neumann paradigm describes the CPU such, that it encapsulates the DPU (DataPath Unit, or ALU) together with the program counter (figure 1).  The behaviour of the program counter is programmed by Software (figure 2).

Figure 1.  The von Neumann bottleneck

Figure 2. Software controls the Program counter

The compact instruction code of a CPU is tightly coupled with the structure of the DPU. This is the reason why the instruction-stream-based von Neumann paradigm does not support morphware. Whenever you try to reconfigure the DPU, the architecture of the CPU gets destroyed. We need a second machine paradigm: the Xputer (Anti Machine).

The Anti-Machine (Xputer)

First we started with the generalization of the Systolic Array (first popularized by H. T. Kung [10]) which is datastream-based. The von Neumann paradigm, however, is instruction-stream-based. The systolic array (Kung array) could be used only for applications with strictly regular data-dependencies yielding pipe networks with only uniform linear pipes. Why this restriction? The question has been: "how to synthesize this pipe network?" Being a mathematician Kung's reply has been: "of coure algebraic" which means by linear projection. The second question has been: "how to generate the datastreams?" Kung's reply has been: "This is not our job!!". Maybe, he was looking for an EE student coming with a soldering iron to connect the array to some signal sources. So he missed to invent a general purpose machine paradigm.

This reminds me to my mentor Karl Steinbuch telling that it is not sufficient to invent something, but that you need to recognize that you have invented something. [11]. We at Kaiserslautern invented and implemented the generalization of this systolicarray by a new synthesis methodology, replacing algebraic mapping methods by general optimization via simulated annealing [12, 13], so also any wildly irregular forms of non-regular data dependencies are supported, so that reconfigurability really makes sense.

But H. T. Kung's tunnel vision went even further by his decision: "generating the data streams is not our job!", since without a sequencer it is not a machine paradigm. So he missed to correct the worst decision in the history of computing, We at Kaiserslautern reinvented data-stream-based computing by creating the anti-machine (Xputer) paradigm together with an innovative reconfigurable data sequencer methodology avoiding memory-cycle-hungry address computations [14].

Fig. 3.  Data counter behavior programmed by flowware

Fig. 4. Anti-Machine: data counter(s) located within asM(s)

The Xputer machine (anti machine) is data-stream-based, but not instruction-stream-based. The Xputer machine (anti machine) has no CPU. If it is hardwired, it has a DPU instead, or even a DPA (DPU array). If it is reconfigurable, it has a rDPU or rDPA instead (fig. 4). Instead of a program counter the Xputer machine (anti machine) has one or several data counters, which are located with the memory bank (fig. 4), but not with the (r)DPU nor (r)DPA. The run time bevaviour of the  data counter(s) is programmed by Flowware (fig. 3).

Now a remark about terminology. The term "dataflow machine" or "dataflow computer" should not be confused with "data streams". "Dataflow Computer" has been a research area, which has died meanwhile. Their name came from compilation techniques based on DAG input. Their machine, however, had an indeterministic operation. For each particular instruction the CPU was always asking, wether all required operands are already available. If not, it had to try again later for such an instruction, mostly very often again and again. To clearly distinguish our highly efficient Xputer principles from this highly inefficient old paradigm we use the term "data stream".

Fig 5. Hardwired Anti Machines: programmed by flowware only.
          b)                                   a) 

Figure 6. Heterogeneous systems need all three: a) (von Neumann) CPUs are programmed by Software; b) reconfigurable anti machines are programmedby two sources: resource set-up before run time by configware code,  run time behavior (data streams) by flowware.


Apropos Kung: in the early days of the systolic array, three different scientist carrying the name "Kung" have been involved here: (1.) H. T. Kung (at that time at Carnegie-Mellon, now at Harvard, USA) who has been visible first in this scene by popularizing systolic arrays, (2.) S.Y. Kung (Princeton) who has written an early book on systolic arrays, and, (3.) also a student with the name Kung (sorry, I forgot his first names and affiliation), having been co-author of some early papers on systolic arrays.

*) this word-play joke works only in Germany language                              

Figure 7. A simple processor execution example: computing in time
needing many memory cycles.

Figure 8: example from fig. 7, but by computing
in space: no memory cycles needed.

Programming in Time versus Programming in Time and Space

Structural programming by Configware means Programming in Space. That's why Configware versus Software means Computing in Space and Time versus Computing in Time only.

Instruction-stream-based programming in time only (Software Engineering): one source needed: Softwar only (fig. 6 a).  However, programming morphware (Configware Engineering) means programming in time and space, where two program sources are needed (fig. 6 b): configware for the space domain configures the resources before run time.#, and, flowware for the time domain: for scheduling the data streams flowing during run time.

Speed-up by time to space migration

Figure 8 (Kress-array-based machine version) illustrates, why time to space migration removes the memory cycles needed for the instruction-stream-based CPU-executed version shown in fig. 7. Fig. 9 lists a few speed-up factors having been published. A more recent speed-up factor is 28000 for cracking encrypted code. Fig. 10 summarizes some speed-up mechanisms obtained by time to space migration.

Fig. 9. Some speed-up examples: time to space migration, for example from CPU to FPGA, or, to PACT platform













Fig. 10: Some mechanisms for speed-up by time to space migration.

References        For reading the theses click here, for publications click here

[1]  Burton Smith (keynote): Reinventing Computing; LACSI Symposium 2006, Santa Fe, NM, USA, http://www.cct.lsu.edu/~estrabd/LACSI2006/Smith.pdf

[2] R. Hartenstein: The Grand Challenge To Reinvent Computing - A new World Model of Computing; CSBC_2010 - XXX Congresso da Sociedade Brasileira de Computação, July 20 - 23, 2010, Belo Horizonte, MG, Brasil  http://www.inf.pucminas.br/sbc2010/anais/pdf/semish/st03_02.pdf

[3]  R. Hartenstein, A. G. Hirschbiel, M. Weber: MOM-map-oriented machine-a partly custom-designed architecture compared to standard hardware; Proc. IEEE CompEuro, Hamburg, Germany, May 1989

[4] R. Hartenstein (keynote): Reconfigurable Computing: boosting Software Education for the Multicore Era; IV Southern Programmable Logic Conference (SPL 2010), Porto Galinhas Beach, Pernambuco, Brasil, 24-26 March 2010

[5] Joao Cardoso, Michael Huebner (Editors): ―Reconfigurable Computing‖ Springer Verlag 2010

[6] Voros, Nikolaos; Rosti, Alberto; Hübner, Michael (Eds.): "Dynamic System Reconfiguration in Heterogeneous Platforms - The MORPHEUS Approach"; Springer Verlag, 2009

[7] Ch. Bobda: Introduction to Reconfigurable Computing - Architectures, Algorithms, Applications; Springer, 2007

[8] R. Hartenstein: The von Neumann Syndrome; Stamatis Vassiliadis Memorial Symp., Sep 2007,  Delft, NL

[9] M. Duhl: Incremental Development and Description of a Shuffle Sort Array Circuit in hyperKARL from the Algorithm Representation of the Bubble Sort Algorithm; Projektarbeit, Informatik, TU Kaiserslautern 1988

[10] M. J. Foster, H. T. Kung: Design of Special Purpose VLSI Chips; IEEE 7th International Symposium on Computer Architecture (ISCA), La Baule, France, May 6 - 8, 1980; preprint version in: Computer Magazine 13(1):26-40, January 1980

[11] R. Hartenstein: Karl Steinbuch about how to invent something; Memo, Informatik, TU Kaiserslautern 2015

[12] S. Kirkpatrick, C. D. Getlett, M. P. Vechi: Optimization by simulated annealing; 1983, Science 220 621 - 630

[13] Rainer Kress: A Fast Reconfigurable ALU for Xputers; Ph. D. Dissertation, TU Kaiserslautern 1996

[14] R. Hartenstein, A. G. Hirschbiel, M. Riedmüller, K. Schmidt, M. Weber: A High Performance Machine Paradigm based on Auto-Sequencin Data Memory; HICSS - 24th Hawaii International Conference on System Sciences, Koloa, Hawaii, USA, January 1991




Reconfigurable Computing

goes into every application [X]


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

invited papers | Impressum


Computer Structures Group
Department of Computer Science
University of Kaiserslautern
© Copyright 2001-2012, University of Kaiserslautern, Kaiserslautern, Germany Webmaster  last updateJune 2001 and 2012.