|
|
 | | From: | googler | | Subject: | Stack cache | | Date: | 17 Jan 2005 04:33:43 -0800 |
|
|
 | My question is about the stack cache that can be found in Java
processors like Sun's picoJava. I cannot understand how the stack cache
handles a function call or return. I know the stack cache maintains a
top and a bottom pointer to point to the top and bottom entries in the
stack cache (for the current method context). Then how does it maintain
multiple values (each pair of values corresponding to a function call)
of such pointers when a function call happens?
Please help. Thank you.
|
|
| | From: | googler | | Subject: | Re: Stack cache | | Date: | 18 Jan 2005 15:52:28 -0800 |
|
|
| Hi, thanks for the reply.
> My understanding is the base and bounds pair cover somewhere in the
> range of 1KByte to 4 KBytes of data. This is bigger than almost any
> function, and several functions can live in the stack cache
> simultaneously. (Remember this is stack caches in general, not how a
> Java machine might implement them).
Actually this is just 64 entries for picoJava where each entry is a 32
bit word.
>
> The process of 'calling' a procedure has the processor dump the old
> pointers on the stack where the 'return' process can pick them back
up.
> Say we are executing in procedure A and make a call to procedure B.
> Somewhere in the calling process, we have to take our frame pointer
and
> return address pointer and store them on the top of the stack. When
> procedure B wants to return to whomever called him, he deallocates
all
> his local area on the top of the stack and then loads the frame
pointer
> of the caller and then loads the return address into the
> instructionpointer--presto, he's back in the calling procedure with
the
> stack as it was. As seen at the stack cache, there may have been a
> stack overflow at the point of the call and a stack underflow during
> the return. All the gyration of this are managed inside the stack
cache
> by performing memory transactions to the memory hierarchy (loading
and
> storing of lines of memory).
OK.
>
> I suspect that Java might implement the stack as an allocation inside
> the heap (like everything else). In this case, the stack cache needs
to
> allocate a backwards pointer from heap allocation to heap allocation
so
> that the heap 'frames' can be given back to the heap allocator. So
when
> a new frame is allocated, the allocation size is augmented to contain
> this additional pointer, and this pointer is positioned at an easy to
> find location. This makes the name stack cache imprecise, probably
> heap/subroutine cache would work better, of frame cache (except some
> university research is using the name frame to be a great big trace)
In the picoJava architecture, the stack cache is basically like a
register file which caches the top 64 entries from the actual stack
(which is in the data cache anyway). Since it is a stack machine, it
has an operand stack (that is a part of the stack frame and lies on
top) which grows and shrinks as instructions are executed. If you are
interested, you can find a very good paper at
http://www.ece.purdue.edu/~arch/seminar/schedules/spring00-pdf/mcghan98.pdf
..
|
|
| | From: | MitchAlsup at aol.com | | Subject: | Re: Stack cache | | Date: | 18 Jan 2005 08:41:18 -0800 |
|
|
| I don't know anything about how any of the JAVA processors work.
However:
A stack cache is just like a regular cache except that the whole area
can be considered contiguous, and managed by a single pair of base and
bounds. When a linear address is computed it can be comapred to the
base and bounds and used to index the stack cache if it takes a hit in
the base and bounds. As procedures are added to the cache, the base and
bounds are adjusted (typicaly) downwards. Lines that fall off the
bottom are moved to the regular cache (or the regular memory
hierarchy). The reverse happens upon removing procedures from the stack
cache. Where a stack cache is interesting is that the movement of lines
can be performed rather lasily rather than immediately.
Under certain circumstances, a stack cache can be accessed by the
decoder (as opposed to the execution pipelines), turning what would
have becomes a memory reference into an immediate; saving latency.
Instructions like PUSH, POP, and RET fall into this paradigm. There are
some race condition to look out for, but overall they are manageable.
Mitch
|
|
| | From: | MitchAlsup at aol.com | | Subject: | Re: Stack cache | | Date: | 18 Jan 2005 14:06:16 -0800 |
|
|
| My understanding is the base and bounds pair cover somewhere in the
range of 1KByte to 4 KBytes of data. This is bigger than almost any
function, and several functions can live in the stack cache
simultaneously. (Remember this is stack caches in general, not how a
Java machine might implement them).
The process of 'calling' a procedure has the processor dump the old
pointers on the stack where the 'return' process can pick them back up.
Say we are executing in procedure A and make a call to procedure B.
Somewhere in the calling process, we have to take our frame pointer and
return address pointer and store them on the top of the stack. When
procedure B wants to return to whomever called him, he deallocates all
his local area on the top of the stack and then loads the frame pointer
of the caller and then loads the return address into the
instructionpointer--presto, he's back in the calling procedure with the
stack as it was. As seen at the stack cache, there may have been a
stack overflow at the point of the call and a stack underflow during
the return. All the gyration of this are managed inside the stack cache
by performing memory transactions to the memory hierarchy (loading and
storing of lines of memory).
I suspect that Java might implement the stack as an allocation inside
the heap (like everything else). In this case, the stack cache needs to
allocate a backwards pointer from heap allocation to heap allocation so
that the heap 'frames' can be given back to the heap allocator. So when
a new frame is allocated, the allocation size is augmented to contain
this additional pointer, and this pointer is positioned at an easy to
find location. This makes the name stack cache imprecise, probably
heap/subroutine cache would work better, of frame cache (except some
university research is using the name frame to be a great big trace)
Mitch
|
|
| | From: | googler | | Subject: | Re: Stack cache | | Date: | 18 Jan 2005 12:13:06 -0800 |
|
|
| As you said, there is a pair of pointers for the high and low end of
the stack cache (or equivalently a base and a bound). According to my
understanding, this pair (stored in registers) is for the current
function which is executing. When the current function A calls another
function B (so that B becomes the current function now), then how do
you save these high and low pointers for the function A, so that A can
start executing normally after B returns (supposing the stack cache
entries for function A are still there in the stack cache and have not
been spilled)? I presume this is saved on the actual stack before
control goes to function B, but just want to make sure this assumption
is correct. Also I want to have a little detailed explanation of that
implementation for some real processor (like picoJava).
Thank you.
|
|
| | From: | Jan_Vorbrüggen | | Subject: | Re: Stack cache | | Date: | Wed, 19 Jan 2005 09:28:06 +0100 |
|
|
| > Also I want to have a little detailed explanation of that
> implementation for some real processor (like picoJava).
Try to find documentation on the T9000's workspace cache - that does
exactly what you're looking for.
Jan
|
|
| | From: | googler | | Subject: | Re: Stack cache | | Date: | 18 Jan 2005 15:54:47 -0800 |
|
|
| Hi, thanks for the reply.
> My understanding is the base and bounds pair cover somewhere in the
> range of 1KByte to 4 KBytes of data. This is bigger than almost any
> function, and several functions can live in the stack cache
> simultaneously. (Remember this is stack caches in general, not how a
> Java machine might implement them).
Actually this is just 64 entries for picoJava where each entry is a 32
bit word.
>
> The process of 'calling' a procedure has the processor dump the old
> pointers on the stack where the 'return' process can pick them back
up.
> Say we are executing in procedure A and make a call to procedure B.
> Somewhere in the calling process, we have to take our frame pointer
and
> return address pointer and store them on the top of the stack. When
> procedure B wants to return to whomever called him, he deallocates
all
> his local area on the top of the stack and then loads the frame
pointer
> of the caller and then loads the return address into the
> instructionpointer--presto, he's back in the calling procedure with
the
> stack as it was. As seen at the stack cache, there may have been a
> stack overflow at the point of the call and a stack underflow during
> the return. All the gyration of this are managed inside the stack
cache
> by performing memory transactions to the memory hierarchy (loading
and
> storing of lines of memory).
OK.
>
> I suspect that Java might implement the stack as an allocation inside
> the heap (like everything else). In this case, the stack cache needs
to
> allocate a backwards pointer from heap allocation to heap allocation
so
> that the heap 'frames' can be given back to the heap allocator. So
when
> a new frame is allocated, the allocation size is augmented to contain
> this additional pointer, and this pointer is positioned at an easy to
> find location. This makes the name stack cache imprecise, probably
> heap/subroutine cache would work better, of frame cache (except some
> university research is using the name frame to be a great big trace)
In the picoJava architecture, the stack cache is basically like a
register file which caches the top 64 entries from the actual stack
(which is in the data cache anyway). Since it is a stack machine, it
has an operand stack (that is a part of the stack frame and lies on
top) which grows and shrinks as instructions are executed. If you are
interested, you can find a very good paper at
http://www.ece.purdue.edu/~arch/seminar/schedules/spring00-pdf/mcghan98.pdf
|
|
|
