Steve Underwood <steveu@dis.org> 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? -- % Randy Yates % "The dreamer, the unwoken fool - %% Fuquay-Varina, NC % in dreams, no pain will kiss the brow..." %%% 919-577-9882 % %%%% <yates@ieee.org> % 'Eldorado Overture', *Eldorado*, ELO http://www.digitalsignallabs.com
Direction of Stack Growth
Started by ●October 21, 2007
Reply by ●October 22, 20072007-10-22
Reply by ●October 22, 20072007-10-22
Steve Underwood wrote:> glen herrmannsfeldt wrote: >> Paul Keinanen wrote: >> (snip) >> >>> It depends how the stack pointer (or other general register) is >>> updated. With register pre-decrement and post-increment access, it is >>> natural to let the stack grow downwards, since the register will point >>> to the newly pushed value. If the stack grows upwards, the stack would >>> point to a useless (free) location of the stack and to access the last >>> value, you would have to use an offset. >> >> But a machine with a stack that grows upwards, and with register >> post-decrement and pre-increment would work just as well. >> If it has index registers, you would want to be able to index down. >> >> Note that the IBM 704, the first machine with Fortran, stored >> arrays in memory in decreasing address order. It seems that >> was more convenient with the index registers and addressing >> modes available. >> >> -- glen >> > I've seen that elsewhere, but I've never seen a machine with a > decrementing program counter. I bet there must be one somewhere. Every > other strange combination has been used. > > 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.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. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●October 22, 20072007-10-22
Randy Yates wrote:> nmm1@cus.cam.ac.uk (Nick Maclaren) writes: > >> In article <F72dnQOzPdLonIDanZ2dnUVZ_v6rnZ2d@rcn.net>, >> Jerry Avins <jya@ieee.org> writes: >> |> >> |> > The disadvantages of upwards-growing stacks are grossly overstated. >> |> >> |> Amen to that. Overstatement notwithstanding, the answer to the OP's >> |> question is slightly more than "That's the way it happened to evolve." >> |> Given an upwardly marching program counter and our natural propensity to >> |> avoid analyzing more than we need to, a downward marching stack pointer >> |> has a slight but ultimately controlling edge. ... >> >> You also need to take the code+stack (i.e. no heap) model as given. >> It was more that I was questioning. >> >> But I agree that, given an upwardly marching program counter and the >> simple code+stack model, a downward marching stack pointer has an >> edge. > > That's all I was talking about. > > Sheesh! The passions expressed in this thread remind me of > the "toilet paper orientation" issue (over versus under).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. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●October 22, 20072007-10-22
Randy Yates wrote:> Steve Underwood <steveu@dis.org> 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?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. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●October 22, 20072007-10-22
On Oct 22, 7:11 pm, Randy Yates <ya...@ieee.org> wrote:> Steve Underwood <ste...@dis.org> 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. 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
Reply by ●October 22, 20072007-10-22
Paul Keinanen wrote:> On 21 Oct 2007 21:25:48 GMT, nmm1@cus.cam.ac.uk (Nick Maclaren) wrote: > > With a stack growing upwards > > MOV VAR1, (R5)+ ; Push Var1 to top of stack > ; R5 now points above the value pushed > COM -2(R5) ; Do some operations on the value on the TOS > ADD #5,-2(R5) ; Some more operations on TOS > MOV -(R5),VAR2 ; Pop value from stackmov var1, +(r5) com @r5 add #5, @r5 mov (r5)-,var2 > This is 2 words (4 bytes) longer than the previous example. Exactly the same.> In processors with pre-increment and post-decrement addressing modes, > it would be natural to let the stack grow upwards.And this machine is the same PDP-11 Archi
Reply by ●October 22, 20072007-10-22
On 2007-10-23, Jerry Avins <jya@ieee.org> wrote:> Randy Yates wrote: >> Steve Underwood <steveu@dis.org> 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? > > That's how it was once, youngster.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
Reply by ●October 22, 20072007-10-22
Jerry Avins wrote:> 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.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]
Reply by ●October 22, 20072007-10-22
Nick Maclaren <nmm1@cus.cam.ac.uk> wrote: +--------------- | 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 <rpw3@rpw3.org> 627 26th Avenue <URL:http://rpw3.org/> San Mateo, CA 94403 (650)572-2607
Reply by ●October 23, 20072007-10-23
robertwessel2@yahoo.com <robertwessel2@yahoo.com> wrote: +--------------- | On Oct 22, 7:11 pm, Randy Yates <ya...@ieee.org> wrote: | > Steve Underwood <ste...@dis.org> 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 <rpw3@rpw3.org> 627 26th Avenue <URL:http://rpw3.org/> San Mateo, CA 94403 (650)572-2607
