• View
• Edit
• History
• Print

Thu6Apr06

Speculation and Transactional Memory subgroup meeting. IT103, 14:30, Thu 6 Apr 06

Present

Ian Watson, Ian Rogers, Andrew Dinn, Jisheng Zhao, Behrem Khan, Matt Horsnell, Mohammad Ansari, Jeremy Singer.

Agenda

Follow-up discussion from last week relating to IanWatson 's proposal about object-based transactional hardware. See document at ~watson/misc/transmem.pdf for details.

Discussion

(iw) I think that the scheme I proposed and outlined last week does not depend on objects at all. We could regard each object (from the original scheme) as a page of virtual memory, together with a map that records which words in the page have been modified. So - why not divide memory into small pages and treat object caching as page-based caching instead?

(ir) Concerns over space in TLB? We don't want to have to store too many cached address translations.

...

(ir) Is a page an object (Pearcolator view) or is an object a page (iw's new view)?

(iw) Bitmaps can be associated with each transaction. Speculative memory can be divided into pages, rather than word-level.

(ad) What about the issue of false sharing on commits? This is possible if multiple objects are stored on a single page.

(iw) It would be neater to avoid multiple objects per page.

(ad) Yes, because otherwise you would copy more info than you needed during transactional write (cloning) - if you only write to a single object in a multi-object page.

(iw) Unused pages are only wasting virtual memory address space, which is considerable in a 64-bit environment.

(ir) What about page-based synonyms? In conventional virtual memory, two virtual addresses can map to the same physical address. This kind of sharing wouldn't work for object IDs.

(bk) The scheme needs some correction. More maps have to be examined than previously thought when object state overflows from cache.

(ad) Then there is the issue of when to propagate bitmaps. At commit-time, or earlier? Is it useful to detect violations earlier?

(iw) That leads to the standard problem for early detection systems. If the transaction doesn't commit, it can still be responsible for killing other transactions that wouldn't have been killed otherwise.

(ad) But shouldn't you only kill things that are more speculative than you?

(iw) That assumes a transaction ordering, which may not be the case? Matt, are there any studies about early detection of violations?

(mh) Yes, but they always assume that the least speculative thread will be able to commut. This is my concern with TCC, since all transactions are unordered. Lots of little transactions can cause violations that will prevent larger transactions from making forward progress. Lack of ordering can prevent guarantees of progress!

(ad) Yes, it is essential tp guarantee completion by partial ordering of transactions.

(iw) Should transactions be ordered by creation time?

(ad) Yes, the schemes I have looked at are ordered by creation timestamp and processor id. Or perhaps by a global clock, which only needs to be accessed at transaction creation.

(js) Perhaps you (IanWatson) could talk us through your object-based (or not!) transactional scheme some time?

(iw) Good idea.

(ma) How are objects stored to memory in the scheme?

(iw) Virtual address space is divided into object-sized boundaries. The virtual address is composed of an object id (oid) and field offset. The only change for the runtime system should be memory management, to make sure that memory requests are satisfied on correctly aligned boundaries.

(ad) What about null? Is that oid zero?

(iw) I presume so.

(ir) What about large arrays?

(iw) These can be allocated on consecutive pages.

(ir) What about object headers for each page?

(ad) Large objects (including arrays) could be allocated in a different object-space.

(iw) I don't think this is necessary. You only need the arry index to overflow the object boundary into the next page. There are only problems if each page needs a separate header, which I don't think is the case.

conversation moved to Matt's speculation scheme

(mh) The simulator is ready for speculation. I have made lots of code cleanups recently, so now ready to do speculation experiments.

(iw) I assume that my scheme should be implementable in your modular simulator?

(mh) should be.

(ad) But does it require dramatic changes in the runtime?

(iw) Not sure it does. Think you only need to modify memory allocation. Other than that everything is transparent, encoded in the addressing scheme.

(ad) What about accessing large objects?

(ir) You need transaction ids as well as oids.

(iw) Potentially objects will have part committed and part still transactional, but I don't see that as a problem.

(ma) How will you manage the committed/speculative split?

(iw) Well, consider loop parallelization. Individual pieces of memory can be manipulated as separate transactional sub-objects. Fractions of pages can be transactional in this way.

(ad) So you are allowing multiple copies of objects per transaction?

(iw) The scheme needs a lot more thinking through!

Next week

In two week's time, Thu20Apr06?, IanWatson will give a presentation of his object-based (page-based?) transactional memory scheme to the entire group, meeting for an hour from 2-3pm. Then Matt will present his work at the APT meeting on the same day from 4-5pm.