An alternative implementation

Article: Haswell Transactional Memory Alternatives
By: bakaneko (nyan.delete@this.hyan.wan), November 21, 2012 6:52 am
Room: Moderated Discussions
Maynard Handley (name99.delete@this.redheron.com) on November 20, 2012 10:52 pm wrote:
> "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.)

Using a single BGL to protect all possibly shared data is
not a good idea. The problem is that with a multithreaded
program all important data moves into the shared region.


So you need to use something more fine-grained anyway
otherwise you end up with a program where most threads are
waiting on the lock to read/copy/write program data.

You can help this up a bit with locks which care about
readers/writers and COW, but it's still a bottleneck and
workarounds will make things more and more complicated and
fragile.

If you want to have programs which can use multiple cores,
either the compiler, the language, or you need to take care
of it.

> 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).
>

You are right, the granularity is annoying, but i would just
go with protecting byte ranges. There is no need to
compromise once you stop doing transactions as an implicit
consequence of cacheline management.

This way you don't need to add superfluous reads to protect
objects which span multiple cachelines, which is as annoying
as multiple unrelated objects in one cacheline.

But I'm a bit sceptical that it is needed. My opinion is
that using multithreading without a time increase during
development works only with good languages and compilers,
and then you are very far away from the metal (think state
machines/functional languages, lack of control over memory
layout). IOW, the compiler can take care of the granularity
and right instructions.
< 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?