4. Other papers (secondary abstracts)

[18] Reiner W. Hartenstein, Karin Schmidt: Combining Structural and Procedural Programming by Parallelizing Compilation; Proceedings of the Symposium on Applied Computing, Nashville, TN, Feb. 1995

A new architectural class of high performance data-parallel machines, called Xputers, is presented which combine structural programming with traditional von Neumann control flow (procedural) programming. From this combination a new programming paradigm arises which is not familiar to the usual software developer. To counteract this deficiency an automatic parallelization and compilation method for Xputers has been developed for the input language C. Sources are restructured and partitioned into an Xputer-suitable execution sequence providing parallelism at expression and at statement level. Data is mapped in a regular form onto the Xputer memory space to be accessible by the Xputers data sequencer hardware which provides a generic set of fast address sequences. The data operations within each part of the derived execution sequence are coded as a structural description for further synthesis towards the reconfigurable ALU which is based on field-programmable logic. Additionally, assembly code is produced in order to control program execution through the data sequencer hardware. The entire method performing the paradigm shift works without further user interaction and all steps are driven by parameters describing the actual target hardware configuration.

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

A new architectural class of high performance data-parallel machines, called Xputers, is presented which combines structural programming with traditional von Neumann control flow programming. From this combination a new programming paradigm arises which is not familiar to the usual software developer. To counteract this drawback a program partitioning, restructuring, and mapping method for Xputers has been developed for the input language C. Sources are restructured and partitioned into an Xputer-suitable execution sequence providing parallelism at expression and at statement level. Data is mapped in a regular form onto the Xputer memory space to be accessible by the Xputer's data sequencer hardware which provides a generic set of fast address sequences. The data operations within each part of the derived execution sequence are coded as a structural description for further synthesis towards the reconfigurable ALU which is based on field-programmable logic. Additionally, assembly code is produced in order to control program execution through the data sequencer hardware. The entire method performing the paradigm shift works without further user interaction and all steps are driven by parameters describing the actual target hardware configuration.

[20] R. W. Hartenstein, et al.: A New FPGA Architecture for Word-oriented Datapaths; 4rd Int. Workshop On Field Programmable Logic And Applications, FPL¹94, Prague, September 7-10, 1994, Lecture Notes in Computer Science, Springer, 1994; also in: Canadian Workshop on Field-Programmable Devices, FPD¹94, Kingston, Ontario, June 13-16, 1994

An FPGA architecture (reconfigurable datapath architecture, rDPA) for word-oriented datapaths is presented, which has been developed to support a variety of Xputer architectures. In contrast to von Neumann machines an Xputer architecture strongly supports the concept of the "soft ALU" (rALU). Fine grained parallelism is achieved by using simple reconfigurable processing elements which are called datapath units (DPUs). The word-oriented datapath simplifies the mapping of applications onto the architecture. Pipelining is supported by the architecture. It is extendable to almost arbitrarily large arrays and is dynamically reconfigurable in-circuit. The programming environment allows automatic mapping of the operators from high level descriptions. The corresponding scheduling techniques for I/O operations are explained. The rDPA can be used as a reconfigurable ALU for bus-oriented host based systems as well as for rapid prototyping of high speed datapaths.

[21] R. W. Hartenstein, et al.: A Dynamically Reconfigurable Wavefront Array Architecture for Evaluation of Expressions; Proceedings of the Int. Conference on Application-Specific Array Processors, ASAP¹94, San Francisco, IEEE Computer Society Press, Los Alamitos, CA, Aug. 1994. A reconfigurable wavefront array rDPA (reconfigurable datapath architecture) for evaluation of any arithmetic and logic expression is presented. Introducing a global I/O bus to the array simplifies the use as a coprocessor in a single bus oriented processor system. Fine grained parallelism is achieved using simple reconfigurable processing elements which are called datapath units (DPUs). The word-oriented datapath simplifies the mapping of applications onto the architecture. Pipelining is supported by the architecture. It is extendible to arbitrarily large arrays and dynamically in-circuit reconfigurable. The programming environment allows automatic mapping of the operators from high level descriptions. The corresponding scheduling techniques for I/O operations are explained. The rDPA can be used as reconfigurable ALU for bus oriented host based systems as well as for rapid prototyping of high speed datapaths.

[22] A. Ast, R. W. Hartenstein, 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.

This paper illustrates a novel class of computational devices called Xputers, which are by up to several orders of magnitude more efficient than the von Neumann paradigm of computers. The paradigm is partially based on using field-programmable logic. The paper shows how the new paradigm is partly derived from accelerating features of image processors and digital signal processors, and it illustrates Xputer execution mechanisms and associated programming techniques by means of simple algorithm examples.

[23] A. Ast, R. Hartenstein, et al.: Novel High Performance Machine Paradigms and Fast-Turnaround ASIC Design Methods: a Consequence of, and, a Challenge to, Field-programmable Logic; Lecture Notes on Computer Science: H. Grünbacher, R.W. Hartenstein (eds.): "FPGAs, Architectures and Tools for Rapid Prototyping", Springer Verlag, 1993

New high performance computational paradigms have been introduced, such as Xputers. Xputers have a reconfigurable ALU using FPGA-like technology. This results in an efficient novel machine paradigm, competitive to many ASIC solutions. It permits systematic derivation of machine code from high level algorithm specs or programs. After testing and debugging real gate array specs may be derived by retargeting. This is a shortcut on the way from algorithm to silicon: less effort and shorter time to market. Compared to conventional ASIC design this means: a) real execution instead of simulation, b) higher source language level and thus more concise specification.

[24] R. W. Hartenstein: CASHE using a new machine paradigm; Codes/CASHE Igls 1993, Collection of Foils

The presentation shows a new machine paradigm based on field-programmable logic for computer aided SW/HW engineering (CASHE). For accelerating bottlenecks in algorithms, a new procedural machine paradigm is needed, the Xputer paradigm. This paradigm supports the use of a Œsoft ALU¹ (reconfigurable ALU). It has a data-procedural execution mechanism and it is deterministic in contrast to dataflow machines. High performance improvements have been achieved for a class of regular, scientific computations. The Xputer serves as a universal accelerator co-processor platform or as a stand alone platform for embedded systems. It offers new ways to quick ASIC implementation and new ways to supercomputing.

[25] A. Ast, J. Becker, R. Hartenstein, H. Reinig, K. Schmidt, M. Weber: XPUTER: ASIC or Standard Circuit?; Invited Paper: GME Fachtagung "Mikroelektronik" in Dresden 08. 10. 93, 1993.

This paper illustrates an innovative compilation technique which is important for a novel class of computational devices called Xputers, which are by up to several orders of magnitude more efficient than the von Neumann paradigm of computers. Xputers are as flexible and as universal as computers. The flexibility of Xputers is achieved by using field-programmable logic (interconnect-reprogrammable media) as the essential technology platform (whereas the universality of computers stems from using the RAM). The paper first briefly illustrates the Xputer paradigm as a prerequisite needed to understand the fundamental issues of this new compilation technology.

[26] A. Ast, R. Hartenstein, et al.: Novel High Performance Machine Paradigms and Fast-Turnaround ASIC Design Methods: a Consequence of, and a Challenge to, Field-programmable Logic; Proceedings of the 2nd Int. Workshop on Field-Programmable Logic and Applications, 31. 08. - 02. 09. 92, Vienna Austria, 1992.

New high performance computational paradigms have been introduced, such as Xputers. Xputers have a reconfigurable ALU using FPGA-like technology. This results in an efficient novel machine paradigm, competitive to many ASIC solutions. It permits systematic derivation of machine code from high level algorithm specs or programs. After testing and debugging real gate array specs may be derived by retargeting. This is a shortcut on the way from algorithm to silicon: less effort and shorter time to market. Compared to conventional ASIC design this means: a) real execution instead of simulation, b) higher source language level and thus more concise specification.

[27] A. Ast, R. Hartenstein, H. Reinig, K. Schmidt, M. Weber: A Novel High-performance Machine Paradigm and ASIC Design Methodology; IEEE Int. Design Automation Workshop ("IEEE Russian Workshop"), 29. - 30. 06. 92, Moskau, 1992.

This paper illustrates an innovative compilation technique which is important for a novel class of computational devices called Xputers, which are by up to several orders of magnitude more efficient than the von Neumann paradigm of computers. Xputers are as flexible and as universal as computers. The flexibility of Xputers is achieved by using field-programmable logic (interconnect-reprogrammable media) as the essential technology platform (whereas the universality of computers stems from using the RAM). The paper first briefly illustrates the Xputer paradigm as a prerequisite needed to understand the fundamental issues of this new compilation technology.

[28] R. Hartenstein, A. Hirschbiel, K. Schmidt, M. Weber: A Novel Paradigm of Parallel Computation and its Use to Implement Simple High-Performance-HW, Future Generation Computer Systems 7 91/92, p. 181-198, North Holland

This paper introduces a novel (non-von Neumann) paradigm of parallel computation supporting a much more efficient implementation of parallel algorithms. Acceleration factors of up to more than 2000 have been obtained experimentally on the MoM architecture for a number of important applications - although using a hardware being more simple than that of a single RISC microprocessor. The machine organization and the most important hardware features of xputers are briefly introduced. The programming paradigm and its flexibility is illustrated by simple DSP and image processing examples. 

[29] R. W. Hartenstein, K. Schmidt, H. Reinig, M. Weber: A Novel Compilation Technique for a Machine Paradigm Based on Field-Programmable Logic; in Will Moore, Wayne Luk (ed.): FPGAs; Oxford 1991 International Workshop on Field Programmable Logic and Applications, Abingdon EE&CS Books, Abingdon, 1991.

This paper introduces an innovative compilation technique which is essential to a novel class of computational devices called Xputers, being by up to several orders of magnitude more efficient than von Neumann paradigm of computers. Xputers areas flexible and as universal as computers. But the central technology platform of flexibility is field-programmable logic (we would prefer the term interconnect-reprogrammable media), rather than the RAM which gives the flexibility of computers. The paper first briefly summarizes the Xputer paradigm as a prerequisite needed to understand the fundamental issues of this new compilation technology.

[30] R. W. Hartenstein: Xputer: ein neues Maschinen-Paradigma für Höchstleistungsrechner; Lessacher Informatik-Kolloquien, Lessach, Österreich, 18.-21. September 1990.

[31] R. W. 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, 1991.

Computers (based on von Neumann principles) are extremely inefficient. That¹s why this paper introduces a novel computational paradigm based on new hardware machine principles. Such machines, called "xputers" avoid most of the bottlenecks known from (von Neumann) computers, so that a hardware efficiency is obtained which is higher by several orders of magnitude. By means of a few algorithm examples the new paradigm will be introduced as a new programming paradigm, which is data-procedural (which is more direct than the control-procedural von Neumann paradigm). Finally the paper gives a survey on the novel application development environments needed for xputers and their advantages over such tools for computers. Such application support for xputers includes two alternative source levels: high level programs, or very high level algorithm specifications.

[32] R. W. 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. Conference on System Sciences, Koloa Hawaii, 1991. - 2nd best paper award "honourable mention" -

This paper introduces a novel (non-von Neumann) programming paradigm of parallel computation featuring a much more efficient implementation of parallel algorithms, as well as a novel (hardware) machine paradigm efficiently supporting such implementations. Acceleration factors of up to more than 2000 have been obtained experimentally on an example architecture for a number of important applications - although using a hardware being more simple than that of a single RISC microprocessor. Due to its auto-sequencing data memory the machine principles are partly related to the organization of associative memories or systems. The machine organization and its most important hardware features are briefly introduced. The programming paradigm and its flexibility based on field-programmable logic is illustrated by a few application examples.

[33] R. W. Hartenstein, A. G. Hirschbiel, M. Weber: Xputers: Very High Throughput by Innovative Computing Principles; 5th Jerusalem Conference on Information Technology (JCIT), Jerusalem, Israel, October 1990, Published by IEEE Computer Society, Los Alamitos, CA, USA, 1990, p. 43-50, 1990.

The paper first introduces the novel machine organization of xputers - in contrast to von Neumann type computer principles. Then the paper introduces the novel xputer paradigm as a model to implement parallel algorithms (important e. g. in image processing, digital signal processing, computer graphics, VLSI layout verification), to run by orders of magnitude faster on xputers than on computers. The paper illustrates this model and the novel execution mechanisms of xputers by a few simple application examples. Xputer principles are sufficiently simple to open up a large new R&D area to define a wide variety of innovative architectures. The paper gives some throughput figures and hardware cost figures having been obtained experimentally from application examples running an xputer architecture and from code having been generated by a compiler, both having been implemented. Finally it discusses technology issues and the use of the xputer paradigm as a novel method for very fast and cheap design of ASICs.

[34] R. W. Hartenstein, A. G. Hirschbiel, K. Lemmert, M. Riedmüller, K. Schmidt, M. Weber: Xputer Use in Image Processing and Digital Signal Processing; SPIE Visual Communication and Image Processing¹90, Lausanne, Schweiz, Published by IntŒl Society for Optical Engineering, Bellingham, WA, USA, 1990, p. 778 -789, 1990.

This paper introduces a novel (non-von Neumann) paradigm of parallel computation supporting a much more efficient implementation of parallel algorithms. Acceleration factors of up to more than 2000 have been obtained experimentally on the MoM architecture for a number of important applications. - although using a processor hardware being more simple than that of a single RISC microprocessor. The most important hardware features of Xputer will be briefly introduced. By simple DSP and image processing algorithm examples the programming paradigm and its flexibility will be illustrated.

[35] R. W. Hartenstein, A. G. Hirschbiel, K. Schmidt, M. Weber: A Novel ASIC Design Approach based on a New Machine Paradigm; European Solid-State Circuits Conference 1990, Grenoble, France.

This paper first introduces a novel machine paradigm as a model for very high performance implementation of parallel algorithms in important application areas such as image processing, digital signal processing, computer graphics, VLSI layout verification, routing and others. The paper illustrates this model by means of a simple application example. Then the paper introduces a novel method for fast and cheap design of ASICs and highly flexible accelerators, which is based on this paradigm. The paper gives some hardware throughput and hardware cost figures having been obtained experimentally.

[36] R. W. Hartenstein, A. G. Hirschbiel, M. Riedmüller, K. Schmidt, M. Weber: Automatic Synthesis of Cheap Hardware Accelerators for Signal Processing and Image Preprocessing; 12. DAGM-Symposium Mustererkennung, Oberkochen-Aalen, 1990. - best paper award -

The paper introduces a novel (non-von Neumann) paradigm of parallel computation supporting a much more efficient implementation of parallel algorithms. Acceleration factors of up to more than 2000 have been obtained experimentally on the MoM architecture for a number of important applications. - although using a processor hardware being more simple than that of a single RISC microprocessor. The most important hardware features of Xputer will be briefly introduced. By simple DSP and image preprocessing algorithm examples the paradigm and its flexibility will be illustrated.

[37] R. W. Hartenstein, A. G. Hirschbiel, M. Weber: A Novel Paradigm of Parallel Computation and its Use to Implement Simple High Performance Hardware; CONPAR¹90 - VAPP IV, Zürich, 1990.

This paper introduces a novel (non-von Neumann) paradigm of parallel computation supporting a much more efficient implementation of parallel algorithms. Acceleration factors of up to more than 2000 have been obtained experimentally on the MoM architecture for a number of important applications. - although using a processor hardware being more simple than that of a single RISC microprocessor. The most important hardware features of Xputer will be briefly introduced. By simple DSP and image processing algorithm examples the programming paradigm and its flexibility will be illustrated.

[38] R. W. Hartenstein, A. G. Hirschbiel, M. Weber: The Machine Paradigm of Xputers and its Application to Digital Signal Processing Acceleration; 1990 Int. Conference on Parallel Processing, St. Charles, Illinois, 1990.

The paper gives an introduction to using xputers (a novel class of high performance processors - based on one of the most important machine concepts since von Neumann) for acceleration of digital signal processing. Its novel programming paradigm of data sequencing is illustrated by a FFT digital signal processing example.

[39] R. W. Hartenstein, A. G. Hirschbiel, M. Weber: Xputers - An Open Family of Non von Neumann Architectures; Proc. of 11th ITG/GI-Conference: Architektur von Rechensystemen, VDE-Verlag, 1990.

The paper introduces the principles of xputers - in contrast to the principles of von Neumann type computers. The paper characterizes a class of algorithms which run by orders of magnitude faster on xputers than on computers and explains the novel execution mechanisms of xputers as well as novel compilation techniques to generate high performance xputer machine code. The paper proves, that xputers are as universal as computers. Based on a capacity analysis of communication mechanisms within the hardware the paper also shows the competitiveness of xputers against MIMD concurrent computers, VLIW computers, and data flow machines, and illustrates, that the design space of xputer architectures opens up a promising new area of research and development in processor architecture.

[40] R. W. 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.

A method SYS2 to MoM to map systolic systems onto the MoM (map-oriented machine) is introduced in this paper. This mapping method is needed to derive a methodology of MoM application development support from the theory of systolic array synthesis. The MoM is a flexible non-von-Neumann computer principle having been developed at Kaiserslautern. MoM "programming" uses combinational code (for path programming) instead of sequential code (for sequencing). That's why for a wide variety of computation problems the MoM provides substantial acceleration factors over von Neumann machines. The MoM can also be used as an inexpensive and highly flexible programmable pseudo-systolic processor for emulation of systolic arrays, such as e.g. in experimenting with alternative systolic architectures at very early phases of the systolic array design process.

[41] R. W. Hartenstein, A. G. Hirschbiel, M. Weber: A Pseudo Parallel Architecture for Systolic Algorithms; Proc. of the IFIP Workshop on Parallel Architectures on Silicon, Grenoble, 1989.

This paper introduces a family of non-von-Neumann innovative computing devices, called Xputers. The map-oriented machine (MoM), an example Xputer architecture, is a flexible non-von-Neumann accelerator machine having been developed at Kaiserslautern University. This machine uses a two-dimensional map-oriented data memory. Over this memory a variable-sized window cache can be moved in arbitrary move schemes to analyse and change the data via the problem-oriented logic unit, which delivers powerful, programmable pattern matching mechanisms. The MoM can be used to speed up signal processing, image processing and VLSI layout processing and many other applications, but it may also serve as a systolic array simulator and evaluator. Moreover it can be also used as a low-cost, simple, flexible, and programmable array emulation computer. In contrast to a systolic array, where data streams are moving through an array of PEs, the MoM keeps data at fixed locations in its memory and moves its scan cache window in an application-specific manner across this memory space.

[42] R. W. Hartenstein, A. G. Hirschbiel, M. Weber: A Pseudo Parallel Architecture for Systolic Algorithms; Proc. of the Int. Conference on VLSI and CAD, Seoul (Korea), 1989.

The map-oriented machine (MoM) is a flexible non-von-Neumann accelerator having been developed at Kaiserslautern University. This machine uses a 2-dimensional map-oriented data memory, over which a variable-sized window cache can be moved in arbitrary schemes to analyse and change data via the problem-oriented logic unit, which delivers powerful, programmable pattern matching mechanisms. The MoM can be used to speed up signal processing, image processing, VLSI layout processing and many other applications, and it may serve as a systolic array simulator and evaluator. Moreover it can be used as a low-cost, simple, flexible and programmable array emulation computer. In contrast to systolic arrays, where data streams are moving through an array of PEs, the MoM keeps data at fixed locations in its memory and moves its window cache in an application-specific manner across this memory space.

[43] R. W. Hartenstein, A. G. Hirschbiel, M. Weber: The Map-oriented Machine (MoM), a Custom-designed Architecture Compared to Standard Designs; CompEuro 89, IEEE Press, Publ. by IEEE, IEEE Service Center, Piscataway, NJ, USA, 1989, p 5/7-9, 1989. The von Neumann principle has 2 bottlenecks: program accessing and data accessing. An innovative non-von-Neumann principle, having been introduced at Kaiserslautern, eliminates one of them. Its new processor, the Map-oriented Machine (MoM), is compared with the von Neumann concept. The MoM is the key resource to a completely new philosophy of data processing which we call "map-oriented processing". It does not use sequential programs, since it has no program sequencer. The way how it is programmed we call Œcombinational programming¹. For surprisingly many applications it provides acceleration factors of up to several orders of magnitude, compared to von-Neumann-type processing. Existing computer application support tools (assemblers, compilers, operating systems, etc.) cannot be used for the MoM since they produce sequential code. That¹s why a new programming theory and new application support tools are introduced such, that the MoM is based on a marriage between standard IC use and ASIC techniques.

[44] R. W. Hartenstein, A. G. Hirschbiel, M. Weber: MoM - Map Oriented Machine, An Innovative Computing Architecture; Internal Report No. 181/88, University of Kaiserslautern, 1988. In this paper we describe an innovative computing architecture, called Map Oriented Machine (MOM). Concerning speed, cost and flexibility today there mainly exist two extreme solutions: the totally flexible, but slow von Neumann computer and the very fast, but expensive and inflexible fully parallelized solution directly implemented on customized silicon. With some applications running on the MOM we show that it not only fills this gap, but also is a very good instrument to implement algorithms which have a map-oriented organization such as image processing. The basic idea of speeding up the algorithms is to parallelize the program access by combinational hardware, whose development is supported by some CAD tools. 


Paper Download Page


Back  Xputer Home Page  Universitaet Kaiserslautern Home Page 

© Copyright 1996, University of Kaiserslautern, Kaiserslautern, Germany Webmaster