instruction stack
Ivan Tikhonov
http://lambda-the-ultimate.org/node/3227
=============
Since Forth is usually implemented on a traditional von Neumann
machine, one thinks of the return stack as holding "return addresses".
However, in these days of large instruction caches, in which entire
cache lines are read from the main memory in one transaction, this
view should be updated. It is well-known that non-scientific programs
have a very high rate of conditional branches, with the mean number of
instructions between branches being on the order of 10 or less.
Forth programs are also very short, with "straight-line" (non-
branching) sequences averaging 10 items or less. In these
environments, it makes more sense to view the return stack itself as
the instruction buffer cache! In other words, the return stack doesn't
hold "return addresses" at all, but the instructions themselves! When
a routine is entered, the entire routine is dumped onto the top of the
return stack, and execution proceeds with the top item of this stack.
Since routines are generally very short, the transfer of an entire
routine is about the same amount of work as transferring a complete
cache line in present architectures. Furthermore, an instruction stack-
cache-buffer is normally accessed sequentially, and therefore can be
implemented using shift register technology. Since a shift register
can be shifted faster than a RAM can be accessed, the "access time" of
this instruction stack-cache-buffer will not be a limiting factor in a
machine's speed.
Executing a loop in an instruction stack-cache-buffer is essentially
the making of connections necessary to create a cyclic shift register
which literally cycles the instructions of the loop around the cyclic
shift register.
=============
Implementations?
rickman
> http://home.pipeline.com/~hbaker1/ForthStack.htmlviahttp://lambda-the-ultimate.org/node/3227
This was discussed before last month. The upshot is that when you
modify the cache to also be a stack/shift register or modify the stack/
shift register to work like a cache, you lose the advantages of both
and end up with a slower device than you would have if you just made
it one or the other. The key is that at some times you need the
instruction store to be random access (jumps and calls) and other
times you need it to be linear and/or looping. I gave this some
thought and I found nothing that would make this more useful or
expedient in any way than existing cache and a program counter.
Do you have some new angle on the matter? You appear to be saying the
same things that were said before.
Rick
pml5...@gmail.com
.
.
> This was discussed before last month. The upshot is that when you
> modify the cache to also be a stack/shift register or modify the stack/
> shift register to work like a cache, you lose the advantages of both
> and end up with a slower device than you would have if you just made
> it one or the other.
Not if something else has already incurred a cost in this area, so
there is no additional cost (a special case, I know, but a real one -
I mentioned a batch script system that fits this).
The key is that at some times you need the
> instruction store to be random access (jumps and calls)
It's quite possible to handle this need the same way a lot of the
time.
and other
> times you need it to be linear and/or looping. I gave this some
> thought and I found nothing that would make this more useful or
> expedient in any way than existing cache and a program counter.
No, it depends on the special cases. Those hardly ever matter, so this
generalisation is a good rule of thumb, but it's not a 100% complete
and accurate description.
>
> Do you have some new angle on the matter? You appear to be saying the
> same things that were said before.
I think I'd better get back to the old thread and post a follow up (I
got caught up in other stuff). P.M.Lawrence.