transactional memory in Parrot
Erik Paulson
Hello,
As a class project, we're looking at transactional memory, and one of things
we'd like to try and do is add some basic TM support to Parrot.
To start out with, we'd add three new opcodes - one to begin, end, and
abort the current transaction. the BeginTX op would save a continuation,
abort would just restore that continuation, and commit would throw away the
old continuation and move on.
Then we'd actually try and add transactional memory :)
Some basic questions: is there a notion of "current time" in Parrot, like
a cycle counter or anything? I don't see any instructions I could get one
from inside a PASM program, and I didn't see any of the .c files keeping
track of one...
When we turn on transactions in any thread, any shared variable that is
written to will need to have a timestamp added to it noting when the last
write occurred. Threads that are in transactions will have to keep
track of all the data they read, and when they goes to commit they will
have to check the last-written timestamp on each of the elements in the
readset.
(We don't actually need timestamps, we can do something where we have
a list off each shared variable and take two passes through it to
prepare for and then enter the transaction. The timestamp just makes it
easier)
This seems sort of easy to do with PMCs, since we can just latch on to the
vtable and do our bookkeeping there (but wow, that's a lot of functions
that a PMC might implement). How does it work with the builtin types like
int?
Like most other TM systems, we're punting on I/O for now. It's also not
realistic, but for now you can only be in one transaction.
Google has found a couple of notes from people saying that TM is cool and
Parrot should do it - but nothing much beyond that. Is there anything
besides Chip Salzenberg's ticket* that we should be aware of?
Thanks!
-Erik
Leopold Toetsch
On Nov 16, 2005, at 19:27, Erik Paulson wrote:
>
> Hello,
>
> As a class project, we're looking at transactional memory, and one of
> things
> we'd like to try and do is add some basic TM support to Parrot.
Cool.
> To start out with, we'd add three new opcodes - one to begin, end, and
> abort the current transaction. the BeginTX op would save a
> continuation,
> abort would just restore that continuation, and commit would throw
> away the
> old continuation and move on.
I'm fine with the 3 new opcodes, ops/experimental.ops is the place to
add these. I don't see yet, how Continuations come into the game, but
it could very well be ;-)
> Then we'd actually try and add transactional memory :)
>
> Some basic questions: is there a notion of "current time" in Parrot,
> like
> a cycle counter or anything? I don't see any instructions I could get
> one
> from inside a PASM program, and I didn't see any of the .c files
> keeping
> track of one...
No there is nothing like a timestamp / cycle counter.
> When we turn on transactions in any thread, any shared variable that is
> written to will need to have a timestamp added to it noting when the
> last
> write occurred. Threads that are in transactions will have to keep
> track of all the data they read, and when they goes to commit they will
> have to check the last-written timestamp on each of the elements in the
> readset.
Hmm. My half-baken implementation model is based on vtables. Vaguely
like this:
- a shared PMC has a different vtable than a non-shared one
- a shared PMC has basically 3 fields additionally: owner, read_vtable,
write_vtable
- the owner (each writer) has a copy of the data and just writes to it
- non-owners (readers) read the original data
A very terse draft is at http://perlcabal.org/~lt/STM.txt
> This seems sort of easy to do with PMCs, since we can just latch on to
> the
> vtable and do our bookkeeping there (but wow, that's a lot of functions
> that a PMC might implement). How does it work with the builtin types
> like
> int?
We have to split the vtable somewhen into interfaces. A plain Integer
doesn't have to implement e.g. an arrayish push or pop operation.
> Like most other TM systems, we're punting on I/O for now. It's also not
> realistic, but for now you can only be in one transaction.
Yup
> Thanks!
I thank you
> -Erik
leo
Larry Wall
: >Some basic questions: is there a notion of "current time" in Parrot,
: >a cycle counter or anything? I don't see any instructions I could get
: >one
: >from inside a PASM program, and I didn't see any of the .c files
: >keeping
: >track of one...
:
: No there is nothing like a timestamp / cycle counter.
Conceptually, being able to virtualize time may be THE crucial
concept of STM. Otherwise it just degenerates to ordinary locking.
But with virtual time you can often optimize things to not block
merely by pretending things happened in a different order, when that
order doesn't matter. STM lets you take advantage of the holes in
partial ordering without imposing complete ordering. At least,
that's my take on it, but I'm no expert. I'm just the resident
philosopher--and unfortunately being a "friend of sophos" is no
guarantee of being right...
Larry
Leopold Toetsch
> Some basic questions: is there a notion of "current time" in Parrot, like
> a cycle counter or anything?
It would be rather easy to add a cycle counter. I was thinking of:
- new field interpreter->cycle_counter
- increment it on each opcode executed that involves PMC argument(s) [1]
- as core_ops_*.c is generated by deep magic aka perl scripts [2] it
should be simple to create an opcode body like:
++interpreter->cycle_counter;
{
// opbody $source goes here
}
> -Erik
[1] only PMCs can be shared and I don't like slowdown of native integer
or float code of course
[2] see build_tools/ops2.pl, lib/Parrot/Op.pm (maybe: lib/Parrot/OpTrans* )
leo