AMD working on scaleable hardware-based atomic transactions...
Chris M. Thomasson
me if you think that AMD has made significant strides toward a workable
multi-word atomic transactions:
Seems very interesting indeed! I need to read some more. But an interesting
one seems to pop out as #7133975. Also, refer to the following thread:
http://groups.google.com/group/comp.arch/browse_frm/thread/cedc2e76568ab0c5
(read the posts by Mitch...)
Sounds promising...
Chris M. Thomasson
"Chris M. Thomasson" <n...@spam.invalid> wrote in message
news:2eLtk.13900$Fr1....@newsfe03.iad...
> When you get some time, read through some of the following patents and
> tell me if you think that AMD has made significant strides toward a
> workable multi-word atomic transactions:
>
> http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=%2Fnetahtml%2FPTO%2Fsearch-adv.htm&r=0&p=1&f=S&l=50&Query=IN%2FAlsup+AND+AN%2FAdvanced%0D%0A&d=PTXT
Actually, read the recent applications first!!:
There ya go. Sorry for posting the wrong like to the granted patents. I was
more interested in the applications.
Anyway, it seems like they are getting very close!
Any thoughts?
Chris M. Thomasson
Dmitriy V'jukov
> Here ya go:
>
> http://www.amd64.org/fileadmin/user_upload/pub/epham08-asf-eval.pdf
Cool!
It recalls Sun's HTM design, but AMD's design gives explicit control
over what locations to lock and what not to lock.
Interesting, when we will see it in AMD hardware?
Also, if HTM will not be supported by Intel, usage will be very
problematic.
Dmitriy V'jukov
MitchAlsup
David Schwartz
> Here ya go:
>
> http://www.amd64.org/fileadmin/user_upload/pub/epham08-asf-eval.pdf
Is this intended to be usable in ordinary application code? It
appears, at least to me, to be basically unusable. Maybe I'm missing
something.
The problem is that once you pass the 'ACQUIRE' point, your code must
run without pre-emption until you hit the 'COMMIT' point. If there's
an interrupt, your code will be "aborted" (see section 3.3). The
specification provides a way to detect an abort -- you jump back
magically to your 'ACQUIRE' point and return an error. But I don't see
how that helps you if the abort occurred after some, but not all, of
your writes took place.
The example code, such as Figure 1's supposed DCAS doesn't even try to
handle this case. It will fail horribly if the code is interrupted or
pre-empted in the 'critical section'.
IMO, like so much synchronization code, the supposed 'simplicity' of
this approach (and maybe even its alleged performance advantage) will
evaporate when it has to handle all the nasty things that can happen
in the real world.
Maybe I'm missing something. If so, what?
DS
David Schwartz
> Maybe I'm missing something. If so, what?
Well, I've read it more carefully, and it seems to sort of say that
they 'undo' all writes if there's an abort with a special buffer.
Their description seems kind of confusing to me. If they hold all
writes in a special buffer, how big is it?
DS
Chris M. Thomasson
additional context for this topic can be found here:
http://groups.google.com/group/comp.arch/browse_frm/thread/cedc2e76568ab0c5
]
"David Schwartz" <dav...@webmaster.com> wrote in message
news:92d923c4-1fdf-4287...@i20g2000prf.googlegroups.com...
>> Is this intended to be usable in ordinary application code? It
>> appears, at least to me, to be basically unusable. Maybe I'm missing
>> something.
>> The problem is that once you pass the 'ACQUIRE' point, your code must
>> run without pre-emption until you hit the 'COMMIT' point. If there's
>> an interrupt, your code will be "aborted" (see section 3.3). The
>> specification provides a way to detect an abort -- you jump back
>> magically to your 'ACQUIRE' point and return an error. But I don't see
>> how that helps you if the abort occurred after some, but not all, of
>> your writes took place.
>> The example code, such as Figure 1's supposed DCAS doesn't even try to
>> handle this case. It will fail horribly if the code is interrupted or
>> pre-empted in the 'critical section'.
>> IMO, like so much synchronization code, the supposed 'simplicity' of
>> this approach (and maybe even its alleged performance advantage) will
>> evaporate when it has to handle all the nasty things that can happen
>> in the real world.
>> Maybe I'm missing something. If so, what?
This post might shed some light:
http://groups.google.com/group/comp.arch/msg/75109b08ea8a1ca4
Apparently, interrupts are deferred by the OS. I also believe that this
deferment is adjustable by mutating a so-called watch-dog counter.
"David Schwartz" <dav...@webmaster.com> wrote in message
news:faf93c3d-dd22-4035...@k36g2000pri.googlegroups.com...
I believe the buffer is big enough to hold at least 7-8 words. If your
transactions need more than that, then ASF is not the right tool for the
job...
Chris M. Thomasson
"Dmitriy V'jukov" <dvy...@gmail.com> wrote in message
news:86c0c11f-785f-4456...@56g2000hsm.googlegroups.com...
Good point. Humm... I guess that Intel will just have to acquire a license
from AMD!
;^)
David Schwartz
> Apparently, interrupts are deferred by the OS. I also believe that this
> deferment is adjustable by mutating a so-called watch-dog counter.
Up to a point configurable by the OS. That sounds pretty nice to me.
> > Well, I've read it more carefully, and it seems to sort of say that
> > they 'undo' all writes if there's an abort with a special buffer.
> > Their description seems kind of confusing to me. If they hold all
> > writes in a special buffer, how big is it?
> I believe the buffer is big enough to hold at least 7-8 words. If your
> transactions need more than that, then ASF is not the right tool for the
> job...
Well then I question how many real-world problems this will actually
help in any significant way, but the design seems sound. It will
certainly simplify the design of things like reader-writer locks.
Perhaps the biggest advantage will be easing the tradeoff between
correctness and performance. Right now, for example, it's easy to
create an obviously-correct implementation of a reader/writer lock
under x86 Linux. It's also not too hard to create a heavily-optimized
implementation of a reader/writer lock. It is, however, an unholy
bitch to create a heavily-optimized reader/writer lock that one can be
confident is correct. It takes serious expertise and reviews from
multiple people to make sure something doesn't slip by. With this, I
could do it in half an hour, and be quite confident it had no subtle
bugs.
DS
Zeljko Vrba
>
> confident is correct. It takes serious expertise and reviews from
> multiple people to make sure something doesn't slip by. With this, I
>
Could verification tools such as SPIN be of help there?
Dmitriy V'jukov
SPIN badly suitable for synchronization algorithm verification. It
doesn't support relaxed memory models, it doesn't support dynamic
memory allocation, it doesn't support OS blocking primitives etc etc.
And Promela is way too far from real programming languages, so it's
possible that your model on Promela is correct, but what you really
will use in production is still not correct.
One better use Relacy for synchronization algorithm verification. It's
created for verification of real-world algorithms, against real-world
memory models, written in real-world programming languages, using real-
world OS primitives.
http://groups.google.ru/group/relacy
Dmitriy V'jukov
Nick Maclaren
In article <86c0c11f-785f-4456...@56g2000hsm.googlegroups.com>,
"Dmitriy V'jukov" <dvy...@gmail.com> writes:
|> On 1 =D3=C5=CE=D4, 04:09, "Chris M. Thomasson" <n...@spam.invalid> wrote:
|> > Here ya go:
|> >
|> > http://www.amd64.org/fileadmin/user_upload/pub/epham08-asf-eval.pdf
|>
|> Cool!
Let's consider language architectures and how they interact with this
feature.
In several language standards, I have argued vigorously that features
like volatile (C, C++ and Fortran) should be an attribute of an
object's actual definition (i.e. might control where it is placed)
and not merely its declaration (i.e. how it is used). The reasons
for arguing that should be obvious in the context of this design.
I have lost, almost uniformly.
In all of those languages, you can add the volatile attribute to
objects not declared as volatile, with only a few restrictions on
parallel access as volatile and non-volatile. They are enough
restrictions to allow an implementation to forbid such access (sic)
in C++ and Fortran, with some loss of optimisation, but it's still a
bit iffy.
Now, my understanding is that any non-protected access to any protected
memory location between an ACQUIRE and COMMIT (whether read or write)
leads to undefined behaviour. Is that so? If not, what happens?
I hope this gets established, because this is an area where the
language standards need to stop using the criterion "We can't see
why it won't work, so let's allow it" and go back to the old one of
"We can't see why it will work, so let's forbid it".
Regards,
Nick Maclaren.
Michael Hohmuth
> On Sep 3, 4:43 pm, "Chris M. Thomasson" <n...@spam.invalid> wrote:
>> Apparently, interrupts are deferred by the OS. I also believe that
>> this deferment is adjustable by mutating a so-called watch-dog
>> counter.
>
> Up to a point configurable by the OS. That sounds pretty nice to me.
Disclaimer:
I work for AMD and am one of the coauthors of the paper that spawned
this thread. AMD has not announced support for ASF (Advanced
Synchronization Facility) in any future product. So please don't
get too excited. :-)
In the incarnation of ASF that we evaluated in the paper, there was no
interrupt-deferral mechanism. All interrupts occurring in the
critical section did indeed abort it.
>> [ David Schwartz: ]
>>> Well, I've read it more carefully, and it seems to sort of say
>>> that they 'undo' all writes if there's an abort with a special
>>> buffer. Their description seems kind of confusing to me. If they
>>> hold all writes in a special buffer, how big is it?
I'm sorry our description is confusing, and I promise to fix it should
we ever rewrite the paper. ;-) Feel free to point out what you find
confusing either here or in private email.
>> I believe the buffer is big enough to hold at least 7-8 words. If
>> your transactions need more than that, then ASF is not the right
>> tool for the job...
In the ASF implementation we simulated for our paper, the buffer
actually holds the backup copies of the protected memory locations
(which are written back to the memory hierarchy in case of an abort).
The simulated buffer's capacity has been exactly 8 cache lines.
> [...] Perhaps the biggest advantage will be easing the tradeoff
> between correctness and performance. Right now, for example, it's
> easy to create an obviously-correct implementation of a
> reader/writer lock under x86 Linux. It's also not too hard to create
> a heavily-optimized implementation of a reader/writer lock. It is,
> however, an unholy bitch to create a heavily-optimized reader/writer
> lock that one can be confident is correct. It takes serious
> expertise and reviews from multiple people to make sure something
> doesn't slip by. With this, I could do it in half an hour, and be
> quite confident it had no subtle bugs.
Nicely said -- yes, one major ASF use case definitely is removing
complexity from highly concurrent data-structure implementations.
Additionally, the simulations we've published in the paper indicate
that removing this complexity can yield a substantial performance
benefit as well.
Michael
--
Michael Hohmuth, AMD Operating System Research Center, Dresden, Germany
michael...@amd.com, www.amd64.org
David Schwartz
> In the incarnation of ASF that we evaluated in the paper, there was no
> interrupt-deferral mechanism. All interrupts occurring in the
> critical section did indeed abort it.
I don't really have a good gut sense of which way is better. I can see
arguments for a benefit to a small amount of deferral, but then the
chance of that actually doing anything is pretty small. If your
'critical region' is big enough that interrupts have a measurable
performance impact, you'd doing something wrong.
> I'm sorry our description is confusing, and I promise to fix it should
> we ever rewrite the paper. ;-) Feel free to point out what you find
> confusing either here or in private email.
Section 3.4 was very confusing, particularly the first two bullet
points and the paragraph that begins "The LLB allows". For example, in
the first bullet point, what makes a cache line "protected"? Is it the
ones that are locked? Or is it any cache line dirtied in the critical
section? Maybe I just didn't invest enough time trying to understand
it all, but reading the paper, I hit those points and hit an
understanding wall.
> In the ASF implementation we simulated for our paper, the buffer
> actually holds the backup copies of the protected memory locations
> (which are written back to the memory hierarchy in case of an abort).
> The simulated buffer's capacity has been exactly 8 cache lines.
Okay, so you actually pass writes during the critical section to the
L1 cache, but don't allow the cache to be written back to memory (or
the L2 cache). The buffer is only used in the case of an abort.
> > [...] Perhaps the biggest advantage will be easing the tradeoff
> > between correctness and performance. Right now, for example, it's
> > easy to create an obviously-correct implementation of a
> > reader/writer lock under x86 Linux. It's also not too hard to create
> > a heavily-optimized implementation of a reader/writer lock. It is,
> > however, an unholy bitch to create a heavily-optimized reader/writer
> > lock that one can be confident is correct. It takes serious
> > expertise and reviews from multiple people to make sure something
> > doesn't slip by. With this, I could do it in half an hour, and be
> > quite confident it had no subtle bugs.
> Nicely said -- yes, one major ASF use case definitely is removing
> complexity from highly concurrent data-structure implementations.
> Additionally, the simulations we've published in the paper indicate
> that removing this complexity can yield a substantial performance
> benefit as well.
If this does make it into products and becomes sufficiently widely-
implemented that you can rely on it being present, there are huge
advantages. For example, suppose I could benefit from a
synchronization primitive I don't have. Maybe I'd love a reader/writer
lock that's fully recursive. Maybe I'd like a reader/writer/
readpromote lock. Maybe I'd like a lock with queued grants, but a 'go
to the head of the line' lock function. Right now, I've either got to
live without this synchronization primitive, write it myself with high
risk, or write an unoptimized version myself. Most likely, I'll chose
the former and implement my code in a less-natural way.
With this, I can code the synchronization primitive I want myself,
with a nearly-optimal version that I can still easily inspect for
validity. This could easily result in more natural code flows, since I
have the synch primitive that best fits my logic. This could mean more
reliable and easier to debug code.
Obviously, if I built my own such locks, even out of optimized
synchronization primitives, it won't be nearly as nice as one built in
assembly with ASF.
DS
Michael Hohmuth
>> I'm sorry our description is confusing, and I promise to fix it
>> should we ever rewrite the paper. ;-) Feel free to point out what
>> you find confusing either here or in private email.
>
> Section 3.4 was very confusing, particularly the first two bullet
> points and the paragraph that begins "The LLB allows". For example,
> in the first bullet point, what makes a cache line "protected"? Is
> it the ones that are locked? Or is it any cache line dirtied in the
> critical section?
The former.
> Maybe I just didn't invest enough time trying to understand it all,
> but reading the paper, I hit those points and hit an understanding
> wall.
I agree that this is confusing.
>> In the ASF implementation we simulated for our paper, the buffer
>> actually holds the backup copies of the protected memory locations
>> (which are written back to the memory hierarchy in case of an
>> abort). The simulated buffer's capacity has been exactly 8 cache
>> lines.
>
> Okay, so you actually pass writes during the critical section to the
> L1 cache,
Yes, we do.
> but don't allow the cache to be written back to memory (or the L2
> cache).
In fact, we do! The nice property of having the backup copy is that
we don't have to wire the speculatively written values anywhere. In
case of an abort we just overwrite them with the old values before
anyone else can see them.
(That's what the paper's "The LLB allows..." paragraph is trying to
say.)
> The buffer is only used in the case of an abort.
Right.
Thanks for your other comments!
David Schwartz
> > but don't allow the cache to be written back to memory (or the L2
> > cache).
> In fact, we do! The nice property of having the backup copy is that
> we don't have to wire the speculatively written values anywhere. In
> case of an abort we just overwrite them with the old values before
> anyone else can see them.
> (That's what the paper's "The LLB allows..." paragraph is trying to
> say.)
Ahh, clever. This really optimizes the non-abort case, which is
exactly what you want.
> > The buffer is only used in the case of an abort.
>
> Right.
Okay, I'm convinced now. Nice work.
DS
MitchAlsup
> Let's consider language architectures and how they interact with this
> feature.
>
> In several language standards, I have argued vigorously that features
> like volatile (C, C++ and Fortran) should be an attribute of an
> object's actual definition (i.e. might control where it is placed)
> and not merely its declaration (i.e. how it is used). The reasons
> for arguing that should be obvious in the context of this design.
> I have lost, almost uniformly.
>
> In all of those languages, you can add the volatile attribute to
> objects not declared as volatile, with only a few restrictions on
> parallel access as volatile and non-volatile. They are enough
> restrictions to allow an implementation to forbid such access (sic)
> in C++ and Fortran, with some loss of optimisation, but it's still a
> bit iffy.
>
> Now, my understanding is that any non-protected access to any protected
> memory location between an ACQUIRE and COMMIT (whether read or write)
> leads to undefined behaviour. Is that so? If not, what happens?
In order for ASF to give the illusion of atomicity, there can be no
visibility to the protected cache lines betweeen ACQUIRE and COMMIT.
Visibility remains to the unprotected cache lines. In ASF you specify
which cache lines are protected and these lines are treated in a
special way, everything else remains 'normal' cach ecoherent memory
and retains its visibility. In effect, the HW is attaching volitile-
like semantics and then removing volitile-like semantics on an
instruction by instruction basis.
So, when you take the error exit at ACQUIRE you cannot be sure that
you have not executed any of the instructions between ACQUIRE and
COMMIT, or not. At the compiler level, each instruction between
ACQUIRE and COMMIT has an implicit back edge to ACQUIRE (as if each
instruction had a conditional branch as part of that instruction.)
Other interested parties will not see any intermediate state in
protected lines, but any other memory modified while in the code
between ACQUIRE and COMMIT may be seen (or not).
And, in fact, at lest while I was there; that is how you debug an ASF
event. You define a buffer in local memory (say your stack) and while
making progress over the atomic event, you lob various pieces of data
into this buffer, and if you end up taking the error exit from
ACQUIRE, the data that did arrive in this buffer, give tells you how
far through the atomic event you got before trouble happened. So at
least you have a chance of understanding what went on. Thus software
can help you understand what went on.
This leaves the door open for software to define this buffer in shared
memory (bad idea) or to pass a pointer to it through shared memory
(even worse) that allows another application visibiity to this buffer
while there is an atomic event lobbing data into the buffer. As a HW
person, I revert back to the "No programming language can prevent bad
programming practices" line of reasoning. SW can prevent this by
allocating these buffers away from shared memory, thereby, its not a
HW problem. Atomicity is maintained on the protected cache lines--
nothing else is guarenteed.
Notice that you simply cannot single step through an atomic event and
have any illusion of atomicity*. This is why debug exceptions are
supressed during the atomic event. Basicaly, you can be singel
stepping up to the first LOCKed load, and then the next step you will
find yourself either at the first instruction following COMMIT or at
the JNZ following the ACQUIRE with a failure code in the specified
register. Thus, this gives the illusion of atomicity, even to the
single stepping program.
Thus writes to unprotected memory may be undone (as will likely happen
in optimistic mode) or may persist (as needs to happen in
deterministic mode). So, what happens is not 'undefined', but it is
defined is a manner that current programming languages do not have
semantics to express.
> I hope this gets established, because this is an area where the
> language standards need to stop using the criterion "We can't see
> why it won't work, so let's allow it" and go back to the old one of
> "We can't see why it will work, so let's forbid it".
>
> Regards,
> Nick Maclaren.
Mitch
(*) We discussed a debugger that when it encounters an ASF event,
would find all other applications that share memory and put them in a
stopped state; and then you can single step through an atomic event
and retain the illusion of atomicity (at least from CPUs). And when
the ASF event was complete, the other protrams would be put back in a
running state.
Nick Maclaren
In article <0a4356fa-1f4d-43af...@m36g2000hse.googlegroups.com>,
MitchAlsup <Mitch...@aol.com> writes:
|>
|> In order for ASF to give the illusion of atomicity, there can be no
|> visibility to the protected cache lines betweeen ACQUIRE and COMMIT.
|> Visibility remains to the unprotected cache lines. In ASF you specify
|> which cache lines are protected and these lines are treated in a
|> special way, everything else remains 'normal' cach ecoherent memory
|> and retains its visibility. In effect, the HW is attaching volitile-
|> like semantics and then removing volitile-like semantics on an
|> instruction by instruction basis.
|>
|> So, when you take the error exit at ACQUIRE you cannot be sure that
|> you have not executed any of the instructions between ACQUIRE and
|> COMMIT, or not. At the compiler level, each instruction between
|> ACQUIRE and COMMIT has an implicit back edge to ACQUIRE (as if each
|> instruction had a conditional branch as part of that instruction.)
|> Other interested parties will not see any intermediate state in
|> protected lines, but any other memory modified while in the code
|> between ACQUIRE and COMMIT may be seen (or not).
Thanks very much. That clarifies the model considerably.
My belief is that a language should forbid such accesses, and a
compiler should warn very strongly if they are being done. Your
point about debugging is well-taken, but that is probably the only
justifiable use of non-protected accesses in a protected section.
But that is not a hardware matter.
|> (*) We discussed a debugger that when it encounters an ASF event,
|> would find all other applications that share memory and put them in a
|> stopped state; and then you can single step through an atomic event
|> and retain the illusion of atomicity (at least from CPUs). And when
|> the ASF event was complete, the other protrams would be put back in a
|> running state.
The lack of this is a generic nightmare with all forms of parallel
execution, and is why I rarely bothered with interactive debuggers.
The distortion to the sequencing usually caused the problems to change
enough that they were little help.
Regards,
Nick Maclaren.
MitchAlsup
> My belief is that a language should forbid such accesses, and a
> compiler should warn very strongly if they are being done. Your
> point about debugging is well-taken, but that is probably the only
> justifiable use of non-protected accesses in a protected section.
> But that is not a hardware matter.
My belief, is that once you have seen any interference (with respect
to the addresses you are using to access a CDS), that you should have
to go back to some 'sane' position and start searching thence. There
is every likelyhood that the structure has changed from the one you
looked at just a few instruction ago.
So, in this case, the registers and memory from within the atomic
event should not be considered useable to the applicaiton--if it has
the correct CDS access model.
Mitch
Nick Maclaren
In article <c82c9ba2-8b21-4d94...@x41g2000hsb.googlegroups.com>,
MitchAlsup <Mitch...@aol.com> writes:
|>
|> > My belief is that a language should forbid such accesses, and a
|> > point about debugging is well-taken, but that is probably the only
|> > justifiable use of non-protected accesses in a protected section.
|> > But that is not a hardware matter.
|>
|> My belief, is that once you have seen any interference (with respect
|> to the addresses you are using to access a CDS), that you should have
|> to go back to some 'sane' position and start searching thence. There
|> is every likelyhood that the structure has changed from the one you
|> looked at just a few instruction ago.
|>
|> So, in this case, the registers and memory from within the atomic
|> event should not be considered useable to the applicaiton--if it has
|> the correct CDS access model.
Indeed. Our two statements are more a difference of whose job it is
to ensure that is done! I am a great believer in languages and
compilers doing such 'enforcement', because it is something that is
best done systematically and can be done by following simple rules.
Regards,
Nick Maclaren.