Re: [f-cpu] Prefetcher (instruction cache L0) our first draft

[Michael Riepe <michael+fcpu@stud.uni-hannover.de>]

On Mon, Jan 12, 2004 at 10:46:10PM +0100, Pierre Tardy wrote:
[...]
> > I'd just ask you to not re-indent my code.  It's too hard to track
> > changes that way.
> arg sorry, it is a reflex.. ESC-C-q..
> 
> diff -E is your friend..

CVS is my friend.  And on many machines, diff -E isn't available at all
since it's a GNUism.

[...]
> > 	Any fetcher line can be in one of at least three different states:
> > 
> > 		1 - the line is invalid
> > 		2 - the line is being prefetched but not yet valid
> > 		3 - the line is valid
> > 
> > 	In case the current line is not valid, let the CPU stall until
> > 	it is.	If the line is in `invalid' state, start prefetching
> > 	and proceed to state 2.
> I do not need the state 2 in my implementation.

Because it's only a simulation.
In hardware, you *will* need it.

[...]
> > 	When "loadaddr[i]" is executed, take the target address, mask
> > 	off the least significant 5 bits, and start prefetching at the
> > 	resulting address (if the corresponding line isn't already
> > 	being prefetched or even valid).  In either case, associate
> > 	the register number with the corresponding fetcher line.
> ok, but in the case of the 3 embraced loops, we have seen that the
> prefetcher stops prefetching the line immediatly, as the current stream
> is not yet in cache.

That's probably a weakness of your implementation.
<disclaimer>
I didn't test it myself.
</disclaimer>

[...]
> > 	Whenever a register is overwritten (note: this applies to ALL
> > 	instructions!), break the association between the register
> > 	number and the corresponding fetcher line.  If the line is
> > 	no longer associated with any register afterwards, it may
> > 	(but need not) be invalidated.	Note that an instruction
> > 	may modify more than one register, so it may be necessary to
> > 	invalidate several associations at once.  On the other hand,
> > 	it is impossible that any register is associated with more
> > 	than a single fetcher line (because it can hold only one
> > 	address at any time).
> ok this is done by putting 0xff in the register's line pointer.

No, it's not done at all for most instructions.  Or did I overlook
something?

[...]
> > 	There are also special events to consider, e.g. instructions
> > 	like `jump r1,r1' must be correctly handled.
> What do jump r1,r1? Jump then invalidation?

The instruction performs

	tmp := PC + 4
	PC := R1
	R1 := tmp

After it, line previously associated with R1 shall be the current line,
while the old current line (or old next line) is being associated
with R1.

[...]
> > 	If the fetcher is "full" -- that is, all lines are in use --,
> > 	invalidate and overwrite the least recently used (LRU) line
> > 	that is NOT associated with the instruction pointer (current
> > 	line) or the prefetcher.
> We do not do like that. This is impling a slow search is'nt it?

Depends on how you implement it.

> You can see by tracing our exemple how the prefetcher will simply
> erase sometimes usefull lines, but its a L0, it is simple..

There may be cases where the prefetcher erases exactly the instruction
that is going to be fetched next.  Can you imagine the consequences?

-- 
 Michael "Tired" Riepe <Michael.Riepe@stud.uni-hannover.de>
 "All I wanna do is have a little fun before I die"
*************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe f-cpu       in the body. http://f-cpu.seul.org/