An alternative implementation

Article: Haswell Transactional Memory Alternatives
By: Maynard Handley (name99.delete@this.redheron.com), November 20, 2012 10:52 pm
Room: Moderated Discussions
"Intel’s TSX tracks the read-set and write-set at cache line (64B) granularity during a transaction. An RS conflict occurs if a cache line in the read-set is written by another thread."

Is it really necessary to do things this way? What I have in mind is something like this:
- to save memory most code packs a variety of related variables together (ie nearby in the same cache line)
- these sorts of schemes (track by the cache line) mean that the optimistic viewpoint (transaction goes through without having to rollback) IF either no-one else wants to touch this data at the same time OR someone else does touch the data at the same time, but everything they touch lives in a different cache block.

These strike me as unsatisfactory conditions. The first requires the lock not to be too busy, the second requires that some thought was applied (along with coaxing the compiler in some way) to try to segregate different blocks of data into different cache lines. Both of these are inimical to the primary goal here, which is that we want to be able to write highly threaded code with just a single BGL (big giant lock) which protects pretty much everything, and still have it run fast. (Ie we require our programmers to know enough to know that they should protect shared data with the BGL or equivalent, but we don't require that they have to micromanage tons of small locks for efficiency's sake.)

So how could we do better? How about the following alternative implementation?
Rather than a single bit per cache line, we have something like 2 bits per 32-bit block in the cache line. These 2 bits indicate one of 3 simultaneous transactions going on. (00 is the usual "standard bits, no transaction here" identifier, giving us only 3 "real" identifiers. This allows us to detect a collision if transaction 10 tries to write to a 32-bit block that is already "claimed" by transaction 11.

This sort of scheme, it seems to me, allows the finer granularity that we want, of allowing multiple threads to update data that is close together (in the same cache line) as long as they don't actually use the exact same bytes.

Obviously there is flexibility here to best balance capabilities vs transistors. For example you can use three bits rather than two and allow up to seven transactions, or you can make the tracking granularity larger (64 bits wide? maybe even 128 bits wide?) or smaller (16 or even 8 bits wide).
< Previous Post in ThreadNext Post in Thread >
TopicPosted ByDate
Article: Haswell TM AlternativesDavid Kanter08/21/12 10:17 PM
  Article: Haswell TM AlternativesHåkan Winbom08/22/12 12:52 AM
    Article: Haswell TM AlternativesDavid Kanter08/22/12 02:06 AM
  Article: Haswell TM Alternativesanon08/22/12 09:46 AM
    Article: Haswell TM AlternativesLinus Torvalds08/22/12 10:16 AM
      Article: Haswell TM AlternativesDoug S08/24/12 09:34 AM
    AMD's ASF even more limitedPaul A. Clayton08/22/12 10:20 AM
      AMD's ASF even more limitedLinus Torvalds08/22/12 10:41 AM
        Compiler use of ll/sc?Paul A. Clayton08/28/12 10:28 AM
          Compiler use of ll/sc?Linus Torvalds09/08/12 01:58 PM
            Lock recognition?Paul A. Clayton09/10/12 02:17 PM
              Sorry, I was confusedPaul A. Clayton09/13/12 11:56 AM
  Filter to detect store conflictsPaul A. Clayton08/22/12 10:19 AM
  Article: Haswell TM Alternativesbakaneko08/22/12 03:02 PM
    Article: Haswell TM AlternativesDavid Kanter08/22/12 03:45 PM
      Article: Haswell TM Alternativesbakaneko08/22/12 10:56 PM
  Cache line granularity?Paul A. Clayton08/28/12 10:28 AM
    Cache line granularity?David Kanter08/31/12 09:13 AM
      A looser definition might have advantagesPaul A. Clayton09/01/12 07:29 AM
    Cache line granularity?rwessel08/31/12 08:54 PM
      Alpha load locked granularityPaul A. Clayton09/01/12 07:29 AM
        Alpha load locked granularityanon09/02/12 06:23 PM
          Alpha pages groupsPaul A. Clayton09/03/12 05:16 AM
  An alternative implementationMaynard Handley11/20/12 10:52 PM
    An alternative implementationbakaneko11/21/12 06:52 AM
      Guarding unread values?Paul A. Clayton11/21/12 09:39 AM
        Guarding unread values?bakaneko11/21/12 12:25 PM
    TM granularity and versioningPaul A. Clayton11/21/12 09:27 AM
      TM granularity and versioningMaynard Handley11/21/12 11:52 AM
        Indeed, TM (and coherence) has devilish details (NT)Paul A. Clayton11/21/12 11:56 AM
Reply to this Topic
Name:
Email:
Topic:
Body: No Text
How do you spell blue?