Previous: Stack Overflow/Underflow.
Up: The Stacksystem
Previous Page: Stack Overflow/Underflow.
Next Page: Pipeline
Previous: Stack Overflow/Underflow.
Up: The Stacksystem
Previous Page: Stack Overflow/Underflow.
Next Page: Pipeline
In the following, ``stack'' denotes only the on--chip part of the stack, ``register'' denotes stack elements as well as general purpose (``normal'') registers. The register file of CAST is a dual port memory with 256 cells. Each stack has a size of 32 elements, and the other 128 cells are used for general purpose registers. The register file is divided conceptually into five parts. The elements 0 to 127 are normal registers, and the stacks M, H, I and A reach from 128 to 255. Register 0 is hardwired to 0 as in most other RISC processors. The address of a register is therefore 8 bits wide. The address of a normal register consists of 7 bits, which is filled up with 0 in the most significant bit.
Two pointer define the active area for each stack.
These are the top-pointer, which identifies the topmost element of a stack,
and the last-pointer, which points one element below the bottom of the stack.
Each stack is identified by its number,
which is used to specify its top-pointer and last-pointer and
contains the bits 6 and 7 of the register address.
This number is mapped by a decoder to the actual internal
stack number.
A flag called ZSt is involved in this mapping. If it is 0, the
decoder does not modify the number, otherwise the numbers two and three
are exchanged.
This allows switching the stacks A and I by simply inverting the ZSt flag.
An address of a stack element therefore consists of two parts:
a 2-bit stack-number St and a 5-bit stack index i.
The address in the register file is built as follows:
1 ! DecSt(
) ! (TopPt[DecSt(
)]
)
A top-pointer is 5 bits, a last-pointer 32 bits wide. This is an implicit realization of the stacks as circular buffers. The last-pointer also defines the swap--area of each stack in memory. The contents of the 32-bit register points to the topmost element of that part of the stack which is held in memory.
Let be the index of a read operation.
In this implementation the top-pointers are only 5 bits wide to save chip area
and to reduce cycle time, since a 5--bit subtraction is faster than one on 32 bits.
Therefore, is it not possible to use the expressions give above for the detection
of a stack over/underflow.
Let
and
be natural numbers, then
denotes the last
bits
of the binary representation of
.
This way we can denote operations on a restricted bit range.
Now the following equivalences hold for
(on the left side,
denotes the 32-bit value of
with respect to the invariants from 0.2.1):
Now we have two expression on 5-bit numbers, which can be used for the detection of stack overflow/underflow.
A load from memory must be used
to access an element with .
It is quite difficult to determine the correct memory address for the element.
With a 32-bit top-pointer the computation of the memory address is very easy,
it is simply
.
Since a top-pointer is only 5 bits wide, this calculation gets a little
bit more complicated.
The 32-bit value of the top-pointer can be determined by