[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Rep:[f-cpu] Hot issue : external LSU ?




----- Original Message -----
From: "nico" <nicolas.boulay@ifrance.com>
To: <f-cpu@seul.org>
Sent: Friday, August 30, 2002 10:35 PM
Subject: Re: Rep:[f-cpu] Hot issue : external LSU ?


> On other world, does ll/sc are there to "emulate" true CAS ?

Not exactly, with "ll/sc" we can much more things than a CAS does. Instead
of a comparison like in CAS we can have other tests or no test at all to do.
We can do several interesting operations between a "ll" and "sc". CAS is in
fact more specifical than "ll/sc". It is why I could find  "ll/sc" more
elegant than CAS from a software viewpoint.

> In that cases, it's much more easy to create a kind of CAS instruction.
> This could be maid by linking 2 or more instructions (the first
> instruction raise a flag, and if the second instruction come, it's a
> true CAS).

I'm not sure about that... CAS must be an atomical read-check-modify
operation. So if you want to split into two instructions, it is no longer a
CAS and still a bit too specific. "ll/sc" is like a more general CAS
splitted into two instructions but with no comparison to do (indeed you are
free to choose what to do between the first instruction and the second one).
Up to now, it looks for me easier and more advantageous to implement "ll/sc"
than a CAS, since "ll/sc" are in fact simpler operations than CAS. But as a
programmer, I must admit I find the pair "ll/sc" more attractive than CAS.

> Then the system emit the CAS functionnality that should have the bus
> system. Exactly the same could be handle for CAS2 (could you reexplain
> why we need CAS2, Cedric explain to me that it isn't usefull, CAS is
> enough).

Well, there are several cases where CAS is not enough because of the ABA
problem : sometimes you need to change the value of a pointer along with a
version stamping to avoid this situation. For example, you want to scan a
list to delete an element. Instead of having a mutex, you can just increase
an associated version stamping when modifing a pointer to be sure you can
change this value of pointer without creating uncoherency. In fact you need
modify the version stamps AND the pointer atomically, so you need CAS2. Of
course, you can use three CAS (if I remember well) to simulate a CAS2 but
you ususally ruin performance that way.

P.S.:
What is the ABA problem ? a task partially acquires an object being in state
A, modifes its contents; another task fully acquires the object, changes its
state to B and modify its contents then releases it in state A. The first
task, which has been interrupted by the second task tries to finish.
Normally it should rollback because the second task has invalidated what the
changes the first task has done. But it is fooled by the fact it only checks
the state (using a simple CAS on state, here A) and not the contents and
believes no other task acquired the same object meanwhile. To solve this
problem we can associate a version stamping. For each attempt to acquire we
increase the version stamp. That way, we haven't a reversible state which
can fool a task. So a CAS2 is necessary to solve this problem and is better
than a simple CAS for more complex algorithms.

But of course, people can always deny the interest of a CAS2... I'm not sure
there is a lot of people who really know who is right.

That's all folks !


*************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe f-cpu       in the body. http://f-cpu.seul.org/