No conflict between theory and practice

By: Andrey (andrey.semashev.delete@this.gmail.com), April 11, 2021 5:05 am
Room: Moderated Discussions
Aspect of Anonimity (aoa.delete@this.kkbbhraspyfkjtcnvx.com) on April 10, 2021 11:30 pm wrote:
> I jumped into this thread saying that TM with abort is shit, basically because it's incomplete. Apparently
> now ppl are saying that if always retrying after abort is sufficient, then the HTM feature will be nice.
> But as Anon says, this then can be done by the hardware. In conclusion, we all could agree that with an
> "ideal" TM the user never needs to retry and thus never be bothered by aborts. Freaking contrarians.
>
> Which leaves transaction rewind as an implementation detail, one you think is indispensable.
> I sketched a method which uses blocking rather than rewind & retry, I'll elaborate.
>
> Imagine that a transaction always aborts when its memory is accessed by another thread,
> and that it always retries after an abort. Imagine that two threads try to do, from
> a code perspective, the same transaction at the same time. This is what happens:
>
> T1 starts (transaction)
> T2 starts
> T1 aborts
> T1 rewinds
> T1 starts
> T2 aborts
> T2 rewinds
> T2 starts
> T1 aborts
> ...
>
> This may not be a deadlock, but our program crashed. To prevent this we need to give precedence to
> the oldest transaction, i.e. lock its memory. If we do that then retrying is useless and it's better
> to block the newer transaction. Without execution rewinding our HTM will avoid many problems.
>
> Lets start with a limit of one cache-line locked per transaction, without taking into account
> task switching, cache eviction or irq's. The only thing we need to implement this HTM is
> a special prefetch instruction which locks the cache-line the following way:
> In the cache coherency protocol, the Exclusive state becomes
> sticky, until the line gets flushed explicitely.
>
> Nothing else needs modification (assuming we have a cache fush instruction) and we
> have atomic writes to cache-lines, with as far as I can tell optimal performance.
> To account for task switching we need to track per thread which cache-line is transactional,
> as well as mark all cache-entries with a TM bit, basically adding a Transactional
> state. This is enough state to keep blocking and to restore threads.
>
> For cache eviction in the middle of a transaction we need to add that same bit
> for every cache-line to the page table. This sucks, but is not too horrible.
> Our HTM cannot tolerate irq's accessing transactional memory, so Just
> Don't Do That or we will kill the thread doing the transaction.
>
> Our HTM is thus far quite simple and elegant, which changes when we want to lock multiple cache-lines
> in the same transaction. Immediately we make ABBA-deadlocking possible. To come back to your thoughts,
> this can normally be mitigated by your rewinding & retrying. But alternatively, all memory that needs
> to be atomic can be required to be specified atomically at the start of the transaction.

This would prohibit use cases when the addresses of memory accesses are discovered during the transaction. For example, double indirection.

> Not only is the choice of interface for how to do this increasingly challenging
> for more addresses, it affects the size of the thread state and the complexity
> of the cache coherency protocol & implementation proportionally.
>
> Finally, traditional TM has a model where code is part of the transaction, whereas we stick to
> pure memory. This means that a whole realm of dynamically generated memory accesses are pretty
> much impossible to specify prior to running code that should run during a transaction.
>
> What one gains is a HTM system that always works after compile
> time with no constraint on the code during a transaction.

< Previous Post in ThreadNext Post in Thread >
TopicPosted ByDate
Armv9 officially announcedJon Masters2021/03/30 11:41 AM
  Armv9 officially announcedGabriele Svelto2021/03/30 01:27 PM
    HTM and TLEFoo_2021/03/30 01:31 PM
      HTM and TLEdmcq2021/03/30 03:03 PM
      Intel RTM and HLE is a successGanon2021/03/30 05:22 PM
        Intel RTM and HLE is a success (is it?)Foo_2021/03/31 01:16 AM
          Intel RTM and HLE was an abject failureanonymou52021/03/31 03:04 AM
          Intel RTM and HLE is a success (is it?)Andrey2021/03/31 05:27 AM
            Intel RTM and HLE is a success (is it?)Foo_2021/03/31 05:58 AM
              Intel RTM and HLE is a success (is it?)Andrey2021/03/31 07:45 AM
                Intel RTM and HLE is a success (is it?)Foo_2021/03/31 09:32 AM
                  Intel RTM and HLE is a success (is it?)Andrey2021/03/31 09:57 AM
                    Intel RTM and HLE is a success (is it?)anonymou52021/03/31 10:39 AM
                      ^ feel free to delete this one -- broken HTML there (NT)anonymou52021/03/31 10:40 AM
                      Intel RTM and HLE is a success (is it?)Andrey2021/03/31 10:47 AM
                    Intel RTM and HLE is a success (is it?)anonymou52021/03/31 10:40 AM
                Intel RTM and HLE is a success (is it?)Ganon2021/03/31 09:58 AM
                  Intel RTM and HLE is a success (is it?)anonymou52021/03/31 10:42 AM
                  Intel RTM and HLE is a success (is it?)Linus Torvalds2021/03/31 11:54 AM
                    Intel RTM and HLE is a success (is it?)Linus Torvalds2021/03/31 12:00 PM
                      Any idea about IBM?Mark Roulo2021/03/31 12:15 PM
                        Any idea about IBM?Linus Torvalds2021/03/31 12:37 PM
                          Any idea about IBM?dmcq2021/03/31 03:04 PM
                            Any idea about IBM?Linus Torvalds2021/03/31 04:44 PM
                              A non straw man view of hardware transactional memoryGanon2021/03/31 07:52 PM
                                A non straw man view of hardware transactional memoryanon22021/03/31 11:03 PM
                                  A non straw man view of hardware transactional memoryCarson2021/04/02 01:11 AM
                                    A non straw man view of hardware transactional memoryanon22021/04/02 05:28 AM
                              IBM zArch TM - guaranteed progressDavid Kanter2021/03/31 08:37 PM
                              Any idea about IBM?Andrey2021/03/31 11:31 PM
                                Any idea about IBM?Linus Torvalds2021/04/01 10:54 AM
                                  Any idea about IBM?Andrey2021/04/02 12:50 PM
                        Any idea about IBM?someone2021/04/01 12:02 AM
                      Intel RTM and HLE is a success (is it?)anon22021/03/31 03:46 PM
                        Intel RTM and HLE is a success (is it?)Linus Torvalds2021/03/31 05:08 PM
                          Leaving it to software is tricky!David Kanter2021/03/31 08:41 PM
                            And a hardware predicttor needs access to fallback timingCarson2021/04/01 11:13 PM
                              Hardware fallback pathAnon2021/04/02 10:51 AM
                              And a hardware predicttor needs access to fallback timingLinus Torvalds2021/04/03 10:41 AM
                                And a hardware predicttor needs access to fallback timingLinus Torvalds2021/04/03 11:11 AM
                                  And a hardware predicttor needs access to fallback timingsr2021/04/03 11:30 AM
                                    And a hardware predicttor needs access to fallback timingLinus Torvalds2021/04/03 12:14 PM
                                      And a hardware predicttor needs access to fallback timingsr2021/04/03 12:39 PM
                                        And a hardware predicttor needs access to fallback timingAnon2021/04/03 02:08 PM
                                          And a hardware predicttor needs access to fallback timingsr2021/04/03 02:33 PM
                                            And a hardware predicttor needs access to fallback timingdmcq2021/04/04 05:35 AM
                                        And a hardware predicttor needs access to fallback timingLinus Torvalds2021/04/03 02:22 PM
                                          Transactional memory isn't exclusive to lockingsr2021/04/04 12:17 AM
                                            Transactional memory isn't exclusive to lockingAspect of Anonimity2021/04/04 03:49 AM
                                            Transactional memory isn't exclusive to lockingAndrey2021/04/04 04:58 AM
                                              Transactional memory isn't exclusive to lockingsr2021/04/04 10:10 AM
                                                Transactional memory isn't exclusive to lockingAndrey2021/04/04 10:33 AM
                                                  Transactional memory isn't exclusive to lockingsr2021/04/05 02:41 AM
                                      And a hardware predicttor needs access to fallback timingGeertB2021/04/04 07:08 PM
                            Leaving it to software is tricky!Andrey2021/04/02 03:00 PM
                          Intel RTM and HLE is a success (is it?)@never_released2021/04/01 08:21 AM
                            Intel RTM and HLE is a success (is it?)@never_released2021/04/01 08:30 AM
                            Intel RTM and HLE is a success (is it?)Linus Torvalds2021/04/01 10:00 AM
                              Intel RTM and HLE is a success (is it?)dmcq2021/04/01 10:35 AM
                                Intel RTM and HLE is a success (is it?)Linus Torvalds2021/04/01 10:59 AM
                                  Is HTM actually in ARMv9?dncq2021/04/01 11:26 AM
                                    Is HTM actually in ARMv9?Linus Torvalds2021/04/01 12:13 PM
                              Intel RTM and HLE is a success (is it?)Jörn Engel2021/04/01 09:15 PM
                          Intel RTM and HLE is a success (is it?)---2021/04/02 10:00 AM
                      Intel RTM and HLE is a success (is it?)Jon Masters2021/04/01 10:56 AM
                        RockMichael S2021/04/01 12:29 PM
            Intel RTM and HLE is a success (is it?)Linus Torvalds2021/03/31 11:50 AM
              Intel RTM and HLE is a success (is it?)anon22021/03/31 03:57 PM
                Intel RTM and HLE is a success (is it?)anon32021/03/31 04:09 PM
          Intel RTM and HLE is a success (is it?)someone2021/03/31 11:56 PM
            Intel RTM and HLE is a success (is it?)someone2021/04/01 12:21 AM
              Intel RTM and HLE is a success (is it?)none2021/04/01 04:31 AM
                Intel RTM and HLE is a success (is it?)anonymou52021/04/01 09:24 AM
                  Intel RTM and HLE is a success (is it?)anony2021/04/01 10:26 AM
                  Intel RTM and HLE is a success (is it?)none2021/04/01 11:20 AM
                Intel RTM and HLE is a success (is it?)Brendan2021/04/01 05:23 PM
                  Intel RTM and HLE is a success (is it?)Adrian2021/04/02 01:03 AM
      Transactional memory similarity to garbage collectionPaul A. Clayton2021/04/05 01:53 PM
        Maybe notMark Roulo2021/04/05 03:07 PM
        Transactional memory similarity to garbage collectionAnon2021/04/05 03:14 PM
        No conflict between theory and practiceAspect of Anonimity2021/04/05 07:57 PM
          No conflict between theory and practiceNoSpammer2021/04/05 09:38 PM
            No conflict between theory and practicedmcq2021/04/06 07:05 AM
              No conflict between theory and practicesr2021/04/06 09:22 AM
                No conflict between theory and practiceBen LaHaise2021/04/06 03:43 PM
                  No conflict between theory and practicesr2021/04/07 09:42 AM
                    No conflict between theory and practiceAnon2021/04/07 10:06 AM
                    No conflict between theory and practiceLinus Torvalds2021/04/07 10:35 AM
                      No conflict between theory and practicesr2021/04/07 12:34 PM
                        If HTM were well implemented, nobody would complain (NT)Anon2021/04/07 12:54 PM
                          If HTM were well implemented, nobody would complaindmcq2021/04/07 03:36 PM
                            If HTM were well implemented, nobody would complainAnon2021/04/07 04:04 PM
                          If HTM were well implemented, nobody would complain---2021/04/08 09:37 AM
                        No conflict between theory and practiceLinus Torvalds2021/04/07 01:20 PM
                          No conflict between theory and practiceAndrey2021/04/07 02:32 PM
                            No conflict between theory and practicedmcq2021/04/07 03:32 PM
                              No conflict between theory and practiceanonymou52021/04/07 04:26 PM
                              No conflict between theory and practiceAndrey2021/04/07 05:54 PM
                                No conflict between theory and practiceLinus Torvalds2021/04/08 08:41 AM
                                  No conflict between theory and practiceAndrey2021/04/08 09:12 AM
                                  No conflict between theory and practiceRobert Williams2021/04/08 09:15 AM
                                    No conflict between theory and practiceLinus Torvalds2021/04/08 09:56 AM
                                      No conflict between theory and practiceRobert Williams2021/04/08 07:50 PM
                                        No conflict between theory and practiceLinus Torvalds2021/04/09 09:25 AM
                                          TSX for all?Robert Williams2021/04/09 12:46 PM
                                            It helps adoption when developers can run the code an their machines.Mark Roulo2021/04/09 12:54 PM
                                              It helps adoption when developers can run the code an their machines.me2021/04/09 02:21 PM
                                                It helps adoption when developers can run the code an their machines.Andrey2021/04/10 07:08 AM
                                                  It helps adoption when developers can run the code an their machines.me2021/04/10 12:43 PM
                                                    It helps adoption when developers can run the code an their machines.Robert Williams2021/04/10 07:05 PM
                                                      It helps adoption when developers can run the code an their machines.Andrey2021/04/11 01:42 AM
                                                        It helps adoption when developers can run the code an their machines.Michael S2021/04/11 04:23 AM
                                              It helps adoption when developers can run the code an their machines.Robert Williams2021/04/10 08:24 AM
                                                It helps adoption when developers can run the code an their machines.Andrey2021/04/10 10:36 AM
                                                  It helps adoption when developers can run the code an their machines.Michael S2021/04/10 10:58 AM
                                                    It helps adoption when developers can run the code an their machines.Robert Williams2021/04/10 11:42 AM
                                                    It helps adoption when developers can run the code an their machines.Brendan2021/04/10 11:27 PM
                                                      It helps adoption when developers can run the code an their machines.Michael S2021/04/11 03:34 AM
                                                        It helps adoption when developers can run the code an their machines.Brendan2021/04/11 04:18 PM
                                            TSX for all?wumpus2021/04/09 01:10 PM
                                            TSX for all?Linus Torvalds2021/04/09 03:03 PM
                                              [CLICK BAIT?] Torvalds to recommend arm64!anonymous22021/04/09 03:17 PM
                                              TSX for all?Linus Torvalds2021/04/09 03:22 PM
                                                amen! (NT)anonymou52021/04/09 05:42 PM
                                            TSX for all?Emil Briggs2021/04/10 05:52 AM
                                              TSX for all?Michael S2021/04/10 11:13 AM
                                                TSX for all?Brendan2021/04/10 11:05 PM
                                          No conflict between theory and practiceanonymouse2021/04/09 03:02 PM
                            No conflict between theory and practiceLinus Torvalds2021/04/07 05:12 PM
                              No conflict between theory and practiceAndrey2021/04/07 05:33 PM
                                No conflict between theory and practiceanon22021/04/07 08:12 PM
                                  No conflict between theory and practiceAndrey2021/04/08 12:29 AM
                                    No conflict between theory and practiceAnon2021/04/08 12:50 AM
                                    No conflict between theory and practiceanon22021/04/08 12:52 AM
                                      No conflict between theory and practiceAndrey2021/04/08 02:41 AM
                                        No conflict between theory and practiceAdrian2021/04/08 03:09 AM
                                          No conflict between theory and practiceAndrey2021/04/08 03:50 AM
                                            No conflict between theory and practiceAdrian2021/04/08 05:07 AM
                                            No conflict between theory and practiceanon22021/04/08 05:18 AM
                                              No conflict between theory and practiceAndrey2021/04/08 08:18 AM
                                                No conflict between theory and practiceanon22021/04/08 09:11 AM
                                                  No conflict between theory and practiceAndrey2021/04/08 09:48 AM
                                                    No conflict between theory and practiceanon22021/04/08 04:10 PM
                                            No conflict between theory and practice---2021/04/08 08:30 PM
                                              No conflict between theory and practicedmcq2021/04/09 02:25 AM
                                                No conflict between theory and practiceLinus Torvalds2021/04/09 09:44 AM
                                        No conflict between theory and practiceanon22021/04/08 04:09 AM
                                          No conflict between theory and practicesr2021/04/10 01:22 AM
                                            No conflict between theory and practiceAnon2021/04/10 04:00 AM
                                              No conflict between theory and practiceEtienne Lorrain2021/04/12 12:56 AM
                                                No conflict between theory and practiceAnon2021/04/12 01:54 AM
                                                  No conflict between theory and practicedmcq2021/04/12 01:44 PM
                              No conflict between theory and practiceGabriele Svelto2021/04/08 01:03 AM
                                No conflict between theory and practicedmcq2021/04/12 01:53 PM
                                  No conflict between theory and practicedmcq2021/04/14 04:50 AM
                      transactional memory = memory lock/unlocksr2021/04/10 12:56 AM
                        transactional memory = memory lock/unlockAnon2021/04/10 04:05 AM
                    No conflict between theory and practiceanon22021/04/07 05:19 PM
                No conflict between theory and practicedmcq2021/04/07 01:16 PM
            No conflict between theory and practiceAnon2021/04/06 10:46 AM
            No conflict between theory and practiceAspect of Anonimity2021/04/06 02:16 PM
              No conflict between theory and practiceNoSpammer2021/04/10 12:02 AM
                No conflict between theory and practicesr2021/04/10 01:47 AM
                No conflict between theory and practiceAspect of Anonimity2021/04/10 11:30 PM
                  No conflict between theory and practiceAndrey2021/04/11 05:05 AM
                    HmAspect of Anonimity2021/04/12 07:29 PM
                      Special internal SRAM to store Mutex?Etienne Lorrain2021/04/13 01:01 AM
                        Special internal SRAM to store Mutex?Anon2021/04/13 01:26 AM
                        Special internal SRAM to store Mutex?Linus Torvalds2021/04/13 09:53 AM
                        Special internal SRAM to store Mutex?Dan Fay2021/04/13 12:03 PM
                          Special internal SRAM to store Mutex?Ben LaHaise2021/04/13 03:32 PM
                          Special internal SRAM to store Mutex?Gabriele Svelto2021/04/13 11:43 PM
                        Special internal SRAM to store Mutex?Carson2021/04/13 10:19 PM
          No conflict between theory and practicesr2021/04/06 07:12 AM
            No conflict between theory and practiceAnon2021/04/06 10:43 AM
            No conflict between theory and practiceAspect of Anonimity2021/04/06 03:20 PM
              No conflict between theory and practicesr2021/04/07 10:09 AM
                No conflict between theory and practiceanon22021/04/07 08:53 PM
  Armv9 officially announceddmcq2021/03/30 03:28 PM
    Totally backwads logic on compatibilityHeikki Kultala2021/03/30 03:44 PM
      Totally backwads logic on compatibilityDoug S2021/03/31 12:09 PM
        Totally backwads logic on compatibilitydmcq2021/03/31 03:15 PM
  Armv9 officially announcedv92021/04/12 03:57 PM
    Armv9 officially announcedj2021/04/13 05:07 AM
      Armv9 officially announcedDoug S2021/04/13 10:21 AM
        Armv9 officially announcedanonymou52021/04/13 11:06 AM
          Armv9 officially announcedDoug S2021/04/13 01:01 PM
        Armv9 officially announceddmcq2021/04/13 03:20 PM
Reply to this Topic
Name:
Email:
Topic:
Body: No Text
How do you spell avocado?