[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [f-cpu] CAS in FC0
----- Original Message -----
From: Michael Riepe <michael@stud.uni-hannover.de>
To: <f-cpu@seul.org>
Sent: Tuesday, March 19, 2002 9:34 PM
Subject: Re: [f-cpu] CAS in FC0
> On Tue, Mar 19, 2002 at 03:29:28AM +0100, Yann Guidon wrote:
> [...]
> > in fact, the real problem is to think of CAS as an "instruction".
> > Things become _so_easy_ if we use a combination of instructions !!!
> > We do not need any "CAS instruction" but a variant of the usual
> > load and store instructions, just like the locked versions in ALPHA
> > (and other CPUs).
> >
> > * "load locked" will "tag" the line it selected for reading. it's just a
bit
> > that the issue logic has to set after decoding the instruction.
>
> Or a bunch of bits (e.g. one per byte, or maybe 64-bit word, inside the
line).
>
> > * "store conditional" will proceed if two conditions are met : the
specified
> > condition is true (we can check for LSB, MSB, zero...) and the "tag" is
still
> > set.
Which condition ? your tag should tell us if someone else has written to this
line before your store conditional. So there is no condition to test
beforehand.
Your tag is set with the instruction "load tag", but when someone write at the
same word, you must clear this tag so the "store conditional" would be warned
that someone else takes priority. Any "store" (conditional or not) at this word
must clear this tag.
> > I often wondered if it was worth it to add a conditional store, but now
> > i'm convinced. Except that we need a version that checks the "tag".
I'm pleased to hear you :). What you are speaking about is in fact "ll/sc"
(load-linked/store-conditional), what i spoke about in the french mailing-list.
> > What about the scheduling ? it's almost as fast, if there are all the
> > bypass networks !
> >
> > load_tag [r1],r2
> > xor r2,r3,r4
> > if r4==0 store_locked [r1],r3
> >
> > (or something like that)
And store_locked should return the tag in a register to know if store has be
done. This register can be zero if tag is clear (someone else has already
modified our word).
how to implement a software CAS :
// int CAS (int * /* pointer */ r1,int /* old value */ r2,int /* new value */
r3)
loadaddr 0f,r5
0:
move r2,r4
load_tagged [r1],r2 // r2 : read value and set tag for [r1]
xor r2,r4,r6
jump.nz r6,r0,r5 // the value is not that we expect !
store_tagged r3,[r1],r6 // r3 : value to write into [r1] if tag still set
(tag is cleared afterward)
jump.z r6,r0,r5 // tag was cleared before our store !
nxor r2,r0,r3 // r3 != 0 if [r1] == r2 until writing r3
into [r1]
jump r0,r63 // return to caller with result in R1
how to implement a PUSH :
loadaddr 0f,r5
move r2,r3 // our node address to push
0:
load_tagged [r1],r2 // read top
store r2,[r3] // node->link = top
store_tagged r3,[r1],r4 // top = node
jump.nz r4,r0,r63 // return to caller if ok
jump r0,r5
> If a task switch (or IRQ service) occurs between load_tag and
> store_locked, the tag may change behind the program's back (it might
> be cleared and set again - the ABA problem). In order to avoid that,
> a task switch should reset all tags.
Yes, that's the main backdraft.
> Oh btw: store_locked must return an indication that the store succeeded
> (that is, it's a 3r1w instruction), and of course it has to clear the tag.
:)
*************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe f-cpu in the body. http://f-cpu.seul.org/