Re: Intel details future Larrabee graphics chip

My guess would be the rise of separate I & D on-chip caches, which naturally leads to a Harvard approach inside the CPU/ALU pipeline, while the external memory interface remains (mostly) von Neumann [except for details of cache-flush/-invalidate ops needed to make the external memory be *truly* von Neumann].

Coincidentally, it was just over 20 years ago that AMD brought out the Am29000, which was a odd little Harvard hybrid (with *no* caches) with separate instruction & data busses and a *shared* address bus [and burst mode on both the I- & D-busses so once you'd started a burst on one you could use the address bus to start a burst for the other]. It may have had a small contribution to the terminology change in the

Though if the 29k had any real effect on long-term Marketing language, it was probably just that it caused other vendors with on-chip primary caches to look up and say, "Oh, *we* have a Harvard Architecture *too*, inside our CPU pipeline." [Which they did, all along, though nobody had talked about it that way much before.]

Well, they did get this bit right, IMHO:

Modern high performance CPU chip designs incorporate aspects of both Harvard and von Neumann architecture. On-chip cache memory is divided into an instruction cache and a data cache. Harvard architecture is used as the CPU accesses the cache. In the case of a cache miss, however, the data is retrieved from the main memory, which is not divided into separate instruction and data sections. Thus, while a von Neumann architecture is presented to the programmer, the hardware implementation gains the efficiencies of the Harvard architecture.

This seems to be conflating a number of issues which were more nearly orthogonal than your statement would lead one to believe:

1. How programming languages [other than assembler] talked about "code" versus "data". Mostly, they didn't! They only talked about "data". How the code got into memory in the first place was magic buried in the operating system and/or the linker. [One exception was Lisp, which usually included a full compiler/linker within the run-time system, and thus needed to know how to get "data" to become "code". But even there the user programmer didn't worry about it. You said (COMPILE 'FOO) and FOO was now a compiled code object instead of an interpreted s-expression data object. Not really "separate" at the language level, then.]

1. Sometimes "code" and "data" were split by (virtual) addressing only to separate access capabilities, as with the read-only "high segment" and read-write "low segment" of the DEC PDP-10. But note that even with this split, it was still a pure von Neumann machine: code could be fetched from either segment and a data LOAD from the high seg worked fine. There was still only one address bus & one instruction/data bus.

1. Some small-address-space machines needed to split the address space to get beyond the word-length limits of the machine. A classic example is the DEC PDP-11, which was initially a 16-bit von Neumann machine with 16-bit addressing, but which was later given 22 bits (or more) of physical addressing on the bus. User-mode (well, mapped) addressing was split into "code" and "data" accesses, and addresses could thus be re-used to double the effective virtual address space. [Since there was no way to store into "code" space, it became effectively read-only.] It was still von Neumann, though, even with that split.

Even weirder was the DEC PDP-8, which was a also pure von Neumann machine with 12-bit instructions/data, but in larger models with up to 15 bits of bus address. The CIF (Current Instruction Field) register held the upper 3 address bits of the current program counter. The CDF register held the upper 3 address bits used by *indirect* data references, but the upper 3 address bits for any direct data references came from the CIF.

1. True Harvard splits at the hardware level the physical paths by which "code" enters the CPU and the physical paths by which "data" enters the CPU. The Am29000 was such a machine, although it *shared* the virtual address space [and the address bus itself] between code & data, and thus was Harvard in hardware and von Neumann in software. [Well, except that there really was *no* way for the software to read instruction memory as "data" if the system designer hadn't provided some "sneak path" between the I- & D-busses, so in its pure form the only way to store "data" in "code" space was as a sequence of load-immediate instructions.]

1. Sometimes I & D were split because instructions and the data were of different widths!! E.g., the 8X300 with 16-bit instructions, 13-bit instruction addresses, 8-bit data, and just 9-bit data addresses (actually, two data spaces with 8-bit addressing on each, but sharing a single 8-bit data bus); the Microchip PIC 8-bit series, with 8-bit data and 12-, 13-, or 14-bit instructions (depending on model) and a mishmash of instruction addressing (depending on model/ROM size); etc.

Anyway, "code" & "data" were split or not for many different reasons, not just one, and sometimes it was just a partitioning of (virtual) addresses, sometimes a physical separation between busses; sometimes it was to increase bandwidth, sometimes to increase address space, and sometimes to separate access capabilities. If you look across all the architectures of the past 2-3 decades, somewhere you'll find a mix & match of almost all possible combinations of these reasons.

-Rob

----- Rob Warnock

In article , snipped-for-privacy@rpw3.org (Rob Warnock) writes: |> Nick Maclaren wrote: |> +--------------- |> | Aside: does anyone know why the "Harvard" approach was promoted from |> | being a trivial but important variation of Von Neumann to being of |> | equal rank, starting about 20 years ago? |> +--------------- |> |> My guess would be the rise of separate I & D on-chip caches, which |> naturally leads to a Harvard approach inside the CPU/ALU pipeline, |> while the external memory interface remains (mostly) von Neumann |> [except for details of cache-flush/-invalidate ops needed to make |> the external memory be *truly* von Neumann].

Well, separate I and D caches was a well-established technology by the 1960s (and probably a lot earlier). I suppose that the current crop of kiddies were taught by the sort of "computer scientists" who deified themselves in the 1980s and denigrated earlier work to do so.

|> +--------------- |> | so, despite the nonsense in Wikipedia... |> +--------------- |> |> Well, they did get this bit right, IMHO: |> |> Modern high performance CPU chip designs incorporate aspects of |> both Harvard and von Neumann architecture. ...

True.

|> +--------------- |> | and almost all programming languages have used separate code and data |> | "address spaces" since the invention of COBOL and FORTRAN, and were/are |> | always talked about as using the Von Neumann model (as they do). |> +--------------- |> |> This seems to be conflating a number of issues which were more |> nearly orthogonal than your statement would lead one to believe:

That's fair.

|> 0. How programming languages [other than assembler] talked about "code" |> versus "data". Mostly, they didn't! They only talked about "data". |> How the code got into memory in the first place was magic buried in |> the operating system and/or the linker. ...

Not really. Firstly, the code of a function was almost always an opaque read-only object, but pointers to it could often be manipulated just like any other pointers to opaque read-only data objects - even excluding LISP, that was true in BCPL, Algol 68 and others. Secondly, that "magic" aspect was largely true of data in many early languages - and is almost always true of genuinely high-level ones.

|> Anyway, "code" & "data" were split or not for many different reasons, |> not just one, ...

Indeed. But it STILL doesn't answer my question, which is why the revisionists have turned established terminology on its side, and propagate complete nonsense about Von Neumann (restricted sense) and Harvard being very different architectural models.

Regards, Nick Maclaren.

If you reread my post that caused you to start this particular sub- thread, you would find out that I actually refer to Von Neumann and Harvard as two very similar architectural models. So who are those evil revisionists?!

Agreed, sort of:

If you can do the same as most hw, i.e. punting at Inf/NaN/Denorm, then the real cost is in the multi-way branch on the exponent field, with the problem being the fact that Zero is quite common, so we cannot simply lump it together with the other extreme exponent cases but have to specialcase it:

if (exp + 1 > 1) { // Regular number ... } else if ((bits & ~SIGN) == 0) { // Zero ... } else if (exp == 0) { // Denorm ... } else { // Inf/NaN }

I didn't know that, but that would only be a single well-predicted branch up front in each routine, right? ... OK, using binary encoding makes a sw implementation quite easy! In fact, it seems like a useful working format for a sw implementation.

If I were going to implement 754R (using the mod_1000 encoding) in software I would have to handle all FADD/FSUB in some form of BCD, but FMUL would probably be faster by first converting to pure binary, or at least a much larger base, like 1E9.

FDIV in decimal isn't obvious, but I'd try a two-stage binary reciprocal approach, i.e. a 32-bit reciprocal used in two iterations with back-multiply and subtract.

Terje

A lot earlier than 60s? When would it be? According to Wikipedia article, the first machine on which you would even theoretically want such caches wasn't built until 1948 i.e. just

In article , snipped-for-privacy@yahoo.com writes: |>

|> > Indeed. But it STILL doesn't answer my question, which is why the |> > revisionists have turned established terminology on its side, and |> > propagate complete nonsense about Von Neumann (restricted sense) and |> > Harvard being very different architectural models. |> |> If you reread my post that caused you to start this particular sub- |> thread, you would find out that I actually refer to Von Neumann and |> Harvard as two very similar architectural models.

And I never said that you didn't.

|> So who are those evil revisionists?!

Dunno. But you can see evidence of their work on Wikipedia and in an increasing number of technical papers.

To some extent, even you are a revisionist, because the traditional terminology "Von Neumann architecture" includes the Harvard variant as a subclass. As it is.

This sort of revisionism causes much more serious problems than it might appear to, because it makes it much harder for anyone trying to propose a significant architectural change to do so. Even if they win their argument, other people are likely to claim that they are making a radical change by moving from Von Neumann to Harvard architectures!

Seriously.

Regards, Nick Maclaren.

In article , snipped-for-privacy@yahoo.com writes: |> >

|> > Well, separate I and D caches was a well-established technology by |> > the 1960s (and probably a lot earlier). |> |> A lot earlier than 60s? When would it be? |> According to Wikipedia article, the first machine on which you would |> even theoretically want such caches wasn't built until 1948 i.e. just |> 12 years before 60s.

I didn't say "by 1960" but "by the 1960s". The first machines I know of that had much in the way of transparent caching were late 1960s, and included several with separate I and D caches.

Regards, Nick Maclaren.

In article , Terje Mathisen writes: |>

|> > If you can decode an IEEE 754 value in 3-5 instructions, and get all |> > of the special cases right, then it has hardware assistance. Note |> > that merely breaking the number up into fields is the easy part of |> > the decoding. Stopping at that point isn't interesting. |> |> Agreed, sort of: |> |> If you can do the same as most hw, i.e. punting at Inf/NaN/Denorm,

No, you can't - that's not according to specification!

|> then |> the real cost is in the multi-way branch on the exponent field, with the |> problem being the fact that Zero is quite common, so we cannot simply |> lump it together with the other extreme exponent cases but have to |> specialcase it: ...

Don't bet on the others being rare - it's very application-dependent. In particular, denorms are NOT rare in many programs, and only some architectures have a "position of first bit" opcode.

|> > And I said "a hundred times as expensive", not "100 instructions", |> > though it could well be 100 executed instructions. The reason that |> > I said it was expensive is that it will often/usually have a lot of |> > mispredicted branches. You are aware that there are TWO formats of |> > decimal, aren't you? |> |> I didn't know that, but that would only be a single well-predicted |> branch up front in each routine, right?

In general, yes. But only one of them would be less than horrible to decode efficiently and correctly in software.

|> OK, using binary encoding makes a sw implementation quite easy! In fact, |> it seems like a useful working format for a sw implementation.

Even that is not nice. You have a hard-to-predict branch based on which of the two binary variants is used, plus the other tests. Also, unless IEEE 754R was changed radically after I stopped following it, even the binary representation supports cohorts - and decoding a number means getting that right, too.

A decent decoder would support the densely packed decimal format, too, which is NOT pretty in software!

Regards, Nick Maclaren.

So you are saying that since Von Neumann architecture could be seen as generalization of the Harvard then we should treat Harvard as a subset of Von Neumann? That sounds logically correct but ignores the practical engineering restrictions imposed by Von Neumann generalization. More importantly, historically, Von Neumann's big invention was treating of code and data as the same. So I don't see why machines that most certainly do not do anything like that neither at logical nor at physical layer should be referred as Von Neumann machines.

Conclusion: the people that use the term "Von Neumann architecture" as a common replacement for "architecture based on interpreting of serial or near-serial instruction streams fetched from random-access memory" are true revisionists.

In article , snipped-for-privacy@yahoo.com writes: |> >

|> Conclusion: the people that use the term "Von Neumann architecture" as |> a common replacement for "architecture based on interpreting of serial |> or near-serial instruction streams fetched from random-access memory" |> are true revisionists.

Ah. Well, I side with Backus - who is both massively more eminent than I am and of a previous generation.

Are you claiming that he was being a revisionist in that?

Regards, Nick Maclaren.

Sorry, ACM portal refuses to show me what you mean.

In article , snipped-for-privacy@yahoo.com writes: |> >

|> >

It refuses to show me, now. Try the following for the full article:

If that fails, use Google on "Von Neumann reference", select the second match, and look at "all 59 versions".

In particular, see the description of a Von Neumann computer and what Von Neumann languages are.

Regards, Nick Maclaren.

Are you aware of the binary-to-decimal conversion algorithm I discovered

Using a 32-bit cpu it will convert any input to decimal i about the same time as a single integer DIV opcode, i.e. 30-50 cycles.

Larger inputs should be split using reciprocal multiplication by

The same approach can handle 64-bit chunks on a 64-bit cpu, making even

Terje

Figured out that you most likely had in mind this particular citation: "Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of programming inherited from their common ancestor--the von Neumann computer... etc"

Yes, Backus is most certainly a revisionist. The property he is talking about predated Von Neumann contribution. If anything, he should have praised Von Neumann for showing us one possibly way out of maze although probably not the best one from performance perspective.

On Aug 24, 7:59 pm, "Wilco Dijkstra" wrote: [....]

Yes. There was a short circuit between the headphones.

real cost is in the multi-way branch on

so we cannot simply lump it together

I use a similar layout, but there is no need to decode the inputs at all:

// 32-bit IEEE float in x, y if (((x + 0x800000) & 0x7f000000) != 0 && ((y + 0x800000) & 0x7f000000)) != 0) { // normal case, now decode x, do operation and return } // now deal with special cases

In most cases I need just one easily predictable branch to catch the special cases without decoding the operands, and use conditional execution for the special cases. However for the binary operators you have to be careful when dealing with zero first:

// x * 0 or 0 * y -> return 0 if ((x And I said "a hundred times as expensive", not "100 instructions",

front in each routine, right?

Indeed, and only that if you need to write one routine to handle both formats.

Wilco

messagenews:g8ov69$4sc$ snipped-for-privacy@gemini.csx.cam.ac.uk...

The lookup, requires a trip to memory. Some processors, I think the Blackfin is one, have an add with reverse carry. You can use this to speed up the FFT sequence.

In article , MooseFET writes: |> On Aug 24, 8:25 pm, "Wilco Dijkstra" |> wrote: |> >

|> > > Some of the cryptographic algorithms are similar. Inverting bits |> > > (as used in FFTs) is, too, but I don't know any algorithms where |> > > that is a major bottleneck. |> >

|> > Indeed. Various architectures do implement bitreverse, but it is hardly |> > needed as CPUs already have the ultimate bitshuffle instruction: |> > the lookup table. |> |> The lookup, requires a trip to memory. Some processors, I think the |> Blackfin is one, have an add with reverse carry. You can use this to |> speed up the FFT sequence.

Yes. And that is the reason it is generally insane to implement it by a lookup table for large FFTs - the effects on the cache more than compensate for its increased speed. As it's a fairly minor component of the algorithm, anyway, what the hell?

Regards, Nick Maclaren.

at the time (in following email), i was still on kick about (the same) shared pages appearing at different virtual addresses in different virtual address spaces (or even the same shared pages appearing at different virtual address in the same virtual address space) ... misc. related posts

from long ago and far away (with regard to 3090):

Date: 11/17/83 13:40:41 To: wheeler

The machine has a split cache, the instruction cache is managed with real addresses. No problems.

The operand cache is managed with two directories: one holds LOGICAL addresses (i.e. mixture of real and virtual), and the other holds real addresses. It appears to the outside world to be managed with real addresses. I can think of no reason why shared pages will be peculiar in this environment.

... snip ...

related old email about the 3090 cache operation

in this post, also mentioning 801 (separate I&D cache) from 1975:

this (earlier) email mentions 5880 (amdahl mainframe clone) having separate I & D caches

misc. posts mentioning 801 (romp, rios, power/pc, etc).

One of the differences between 801 split cache and the 3090 (5880) split cache ... was that 3090 (& 5880) managed cache consistency (between I & D caches) in hardware ...while 801 required software to flush D-cache & invalidate I-cache (like program loaders which may have modified instruction streams ... in the data cache ... in order to make sure that modifications in the D-cache were correctly reflected in the I-cache instruction stream).

other old email mentioning 801

semi-related recent post in this thread (discussing virtual memory & paging from the 60s):

for related topic drift ... "small" shared segments in ROMP chip (801 used later in PC/RT)

in this post:

and (this time, Iliad chip ... another 801)

in this post:

similar post along this line