Call for Partners - New Horizons in R&D
Xputer operations are driven by data sequencers (instead of an instruction sequencer). Instead of control flow, i. e. a sequence of instruction addresses, an Xputers are driven by sequences of data addresses. Since data flow is different from address flow, we do not want to use the term "driven by data flow". So we call asequence of data locations (addresses) a scan pattern. Not only for better visualization we prefer a two-dimensional memory organization, where we obtain scan patterns linke the examples shown in fig. 21. To obtain a very rich repertory of scan patterns novel architectural principles of sequencers have been developed at Kaiserslautern [1] [2] (also see fig. 25)..
Fig. 21. A few scan pattern examples:
Figure 22 shows a scan pattern in detail, which can be generated by the GAG (generic address generator) having been invented and developed at Kaiserslautern [1] [2]. The figure shows the well known JPEG zigzag scan pattern used for still image (de)compression. This pattern scans a 10-by-10 pixel segment of the image by a kind of 45 degree video scan. The example illustrates the systematic strcture [3], which a surprisingly large naumber of other real world scan patterns have.
A small and simple language called MoPL (Map-oriented Programming Language) [4] has been developed at Kaiserslautern and implemented as an extension of the language C [5]. The JPEG zig zag has been programmed by using three subprograms, one for the blue subpattern in fig. 22, one for the green scan pattern, and a third one for the yellow pattern. The third subsoutine is just a version of the first one, obtained from this by reversal of sequence and by 180 degree rotation. The second pattern is very simple. It is a linear sequence of smallest steps.
< >Fig. 23. MoM Xputer Principles: Illustration of scan windows
Fig. 24 a illustrates the Xputer implementation of a constant gemoetry Fast Fourier Transform (cgFFT), where the data path reconfigured into the rALU, such as e. e. a Kress Array, reads three words from a 2-by-2 scan window, and writes a single word into a second scan window of size 1 by 1, and into Scan window number 3 of the same size. These three scan windows moving simultaneaously permit data path level parallelism, such that a complex data path communicates with three register files hidden behind three scan windows. So we have shown, that within an Xputer multiple sequencers make sense - incontrast to von Neumann processors. The MoM-3 architecture provides 8 data sequencers, so that even higher parallelism may be implemented, depending on the application.
Fig. 24 b illustrates the total compound scan pattern for moving these three windows in parallel. The green arrows show the triple parallel inner loop. Wenever such a parallel inner loop is finished (after 8 time steps), the outer loop (light blue arraws) moves this inner scan pattern two address units to the right, where it is started again. Finally the three windows end up at the locations marked by red scan windows. This examples shows both, loop nesting and loop parallelism. Such compound scan patterns can be concisely described by the MoPL mini language [4].
Due to continuous rapid progress in von Neumann processor technology
the processor to memory communication gap widens more and more, and has
reached two orders of magnitude. But GAGs can generate very long
address
sequences without needing any memory cycles other than for
initialization.
This means, that the processor to memory communication gap has
disppeared
for such scan pattern loops. During various performance xeperiments we
have found applications, where on a von Neumann basis an address
computation
loop siphons off up to 94% of total computation time (see section FQA
on Xputers). In such a case switching to the Xputer paradigm this
yields
a speed-up by one and a half order of magnitude, since these 94% do not
eat up memory cycles any more. But avoiding addressing overhead is not
the only source of acceleration in using Xputers. For other effects see
section FQA
on Xputers.
If yes, please, inform our webmaster. Our goal is the steady improvement of this list of questions.
©
copyright 1996, Universitaet Kaiserslautern, Kaiserslautern,
Germany
----- Webmaster
