Direction of Stack Growth

Some early machines had five addresses in each op code. I recall a

56-bit word. The addresses I can recall are two operands, a destination, and the address of the next instruction. I can't remember what the fifth was.

Then the program counter was invented, and one address (and the bits in its word) could be dispensed with. operations to deal with the PC had to be added.

After that came the accumulator, a double goody. By using it as one operand source and also as the destination, two more addresses could be eliminated from the data bus. Of course, it made necessary a host of load and store operations, but that was a small price. The 1801 was designed to be a no-address machine, and it came close. Was it the first?

Jerry

--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

I could get into much detail about that, but I'll refrain. :-)

Jerry

--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

That's how it was once, youngster.

Jerry, the Old Far+

--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

The IBM 650, for example, did just that. Of course instruction words were stored on disk. A key optimization was to arrange them so that the next instruction (as defined by the link field) would be in position for the head to read it with minimal latency after the execution of the prior instruction had finished.

Another non-traditional program counter design is to use an LFSR rather than a counter, so that consecutive instructions are actually in a sequence defined by a pseudo-random number generator. That has the disadvantage of making at least one location unreachable (assuming a maximum period LFSR), not to mention making a complete hash* of your address space, but has the advantage that the LFSR can be significantly smaller and faster than an actual adder. The TMS1000 microcontrollers did that, for example.

*pun fully intended

And you optimized your program by placing the instructions at the appropriate places on the magnetic drum so that when each instruction was finished executing, the next one in the list was just getting to the R/W heads.

Or so I'm told. I'm young. My experience only goes back as far as paper tape on an ASR-33 and punch-cards on an IBM model

029.

--
Grant Edwards                   grante             Yow!  FEELINGS are
                                  at               cascading over me!!!
                               visi.com

mov var1, +(r5) com @r5 add #5, @r5 mov (r5)-,var2

Exactly the same.

And this machine is the same PDP-11

Archi

The fifth address was usually the address to jump on a selected condition. This approach was used for drum (and delay line) memory computers, where it was desirable to cram as much as possible in each instruction, and most critical to place the likely next instruction such that it would be coming up to the read head just as the current one completed. Program counters predate these architectures, probably going back at least to the point where stored program memory was first added to Whirlwind.

Marc [who once wrote code for a functioning drum computer]

+--------------- | I am pretty sure that this is yet another artifact of the way that DEC | was the dominating computer science supplier in the 1970s. Now, why | DEC did things the way they did, I don't know. +---------------

Don't forget, DEC did it *both* ways! The PDP-10's hardware stack grew "up"; the PDP-11's grew "down". The overlap in the lifecycle of those two product lines was quite considerable. In fact, many later PDP-10s used PDP-11s as front-end processors, so you even had both ways in one system! ;-}

-Rob

p.s. The VAX copied the -11, so it doesn't count.

p.s. O.k., o.k., the PDP-10 copied the PDP-6, but who other than a few diehard DEC fans [such as yours truly] even *remember* the PDP-6...?

----- Rob Warnock

627 26th Avenue San Mateo, CA 94403 (650)572-2607

sorry, no way with hardware stack pointer. Do not forget that there are uncontrollable events like interrupts, so stack should be completely "down" all the time - there is no need for negative indexes. If you use frame pointer - then yes? but you pay wit extra register and "entry" code.

Archi

+--------------- | On Oct 22, 7:11 pm, Randy Yates wrote: | > Steve Underwood writes: | > > There are various machines where there program counter doesn't | > > actually count at all, but each instruction points to the next. Most | > > microcoded systems do that, but a few higher level programmable | > > machines have done so as well. | >

| > A linked list of instructions? | | The IBM 650, for example, did just that.

+---------------

As did the Royal Precision RPC-4000.

+--------------- | Of course instruction words were stored on disk. A key optimization | was to arrange them so that the next instruction (as defined by the | link field) would be in position for the head to read it with minimal | latency after the execution of the prior instruction had finished. +---------------

Ditto, and ditto.

+--------------- | Another non-traditional program counter design is to use an LFSR | rather than a counter, so that consecutive instructions are | actually in a sequence defined by a pseudo-random number generator. +---------------

The LGP-30 [a simpler predecessor to the RPC-4000] *did* have a sequentially-increasing program counter, but successive locations

*weren't* successive sectors on the drum! Instead, they were separated by 6 or 7 other sectors, which meant that if you could arrange your code to reference one of the intervening sectors with its memory argument, then the instruction could finish in time to fetch the instruction at the next sequential program counter value without haven't to "lose a rev" and go all the way around the drum (and a bit more). Such instructions were called "optimized"; all other instructions were "non-optimized". [Note: As it was a head-per-track drum, the track number didn't matter, only the sector number.] There was even an "optimizing assembler" to help you place your temps and constants, if you were too lazy to count sectors yourself.

-Rob

----- Rob Warnock

627 26th Avenue San Mateo, CA 94403 (650)572-2607

I'd forgotten that one. Some modern mixed signal chips could probably benefit from that. Often the biggest part of the digital noise pollution in the analogue sections is due to the substantial current flows associated with code loop related address line patterns. Long ago I scrambled the addresses in circular buffers built from multiple devices, to reduce these effects. I tried to do something similar to be reasonably tolerant of dead rows or columns in RAMs used for voice messages, but it worked out really messy. I ended up using diagonal addressing there.

Steve

For reasons I have never been able to figure out, even though the arithmetic on the 704 was sign/magnitude, indexing did an unsigned subtract of the index register from the base address to get the effective address. If they didn't store arrays backwards, they'd have had to negate any computed index values before using them.

The 704 had three index registers numbered 1, 2, and 4. If you specified a register number with more than one bit set, it or'ed them before subtracting. Cool though this feature was, in later computers they came to their senses and provided 7 separate registers.

Drum? Our Packard Bell 250 (the original PB which later sold its computer division to Raytheon, not the Korean company that bought the name out of bankruptcy decades later) used magnetostrictive delay lines. By default it executed instructions in sequence but that was really slow since it meant one instruction per cycle of the delay line. There was a bit in each instruction that said to pick up the next instruction from the location after the operand, which could be a lot faster. We tended to write out our programs on big pieces of paper.

R's, John

Archi wrote: (I wrote)

Most now have a separate stack for interrupts and other system functions, pretty much needed for any protected mode system.

I do remember from the 8080 days someone working on the design of a terminal. It was found that the fastest way to clear the screen memory was to point the stack pointer at one end of the buffer and push blanks. Mysterious characters kept appearing on the screen, though, which turned out to be due to interrupts during the clear loop.

-- glen

I have seen (i.e. written) exactly one program where the direction of stack growth made a crucial difference:

On x86 with a very limited register set and downward growing stacks, I once needed to process an array of (register-sized) words, but didn't have enough registers to hold all the critical variables.

At that point I realized that I could decrement the stack pointer by the size of the chunks to be processed, load the array into this area, and then use "pop reg" to retrieve each array element in order.

This freed up the crucial extra register, and had the nice side-effect of keeping the code size small, since POP is a single-byte opcode. :-)

It does blow away any kind of return stack cache of course, but that doesn't matter when I could handle a full L1 cache worth of data in each iteration.

Terje

--
- 
"almost all programming can be viewed as an exercise in caching"

"The Story of Mel":

Here's a relevant quote:

Terje

--
- 
"almost all programming can be viewed as an exercise in caching"

In article , snipped-for-privacy@rpw3.org (Rob Warnock) writes: |> |> Don't forget, DEC did it *both* ways! The PDP-10's hardware stack |> grew "up"; the PDP-11's grew "down". The overlap in the lifecycle |> of those two product lines was quite considerable. In fact, many |> later PDP-10s used PDP-11s as front-end processors, so you even had |> both ways in one system! ;-}

Oh, indeed. Now, why the PDP-11 should have disproportionately more influence on computer scientists (and this is not the only respect), I leave to the sociologists.

Regards, Nick Maclaren.

If anecdotes are your only exposure to that kind of programming, you've lead a sheltered life. :-) Much is still coded for specialist machines where there is no real program counter, and every instruction points to the next. It makes patches wonderfully arcane :-)

Back in the good old days, when AMD was the king of the DSP chip makers, practically all DSP programming was done that way (and it took a lot of AMD chips to make one machine).

Steve

I suppose if I'm going to say its still done, I should quote a real world example. Try looking at the high performance programmable timers used for things like car engine control. Some of those work in this way.

Steve