And a hardware predicttor needs access to fallback timing

By: Linus Torvalds (torvalds.delete@this.linux-foundation.org), April 3, 2021 10:41 am
Room: Moderated Discussions
Carson (carson.delete@this.example.edu) on April 1, 2021 11:13 pm wrote:
> I agree that a hardware predictor is probably required for a quality implementation,
> but there are two things that make it unlike other predictors:
>
>
  • It only gets unidirectional error information; if it predicts "don't try HTM", there's no indication that HTM would have worked. (So occasional re-tests of the HTM path are necessary.)

  • >
  • The costs are very unbalanced and variable. It's not like a branch where you want to pick the &gt50% prediction. Even more expensive things like prefetchers have cost ratios close enough to fixed to bake into the hardware. (You don't need a cost ratio more exact than your fuzzy prediction probability.)

>
> The only way to make a useful prediction is to combine the predicted probability of
> HTM succeeding with the (hopefully easily measurable) costs of the various paths.

I agree that both of the issues you mention are real, but I think your "solution" to them is a classic case of "perfect is the enemy of good".

The thing is, absolutely nobody has the kind of perfect information that your solution requires. Not the hardware, but most certainly not software either.

And hardware at least has a better notion of what the costs are than software does. In particular, hardware can estimate the abort costs fairly well, in ways software has no idea.

And the other cost you mention is not actually all that hard to at least give a fairly good approximation for. That factor of "C(fallback) - C(success)" is not some kind of very complex cost - in fact it should be pretty much a constant for a particular microarchitecture. It's basically "how much does transactional memory win", and it's basically the cost of locking.

Sure, that cost of locking will depend on the amount of contention on the lock that would have been elided, but considering that you had a transaction failure, you already should have a reasonable idea of the level of contention. And again, even if you don't have a great estimate, there's no question that the hardware has a better estimate than software would have.

And the unidirectional error handling really isn't some fundamental problem either.

Look here: if you know your abort cost, and you have some rough idea of how much you expect to win from doing the operation as a transaction, you should now have a rough idea how hard you should avoid aborts. Maybe you don't stop doing transactions after the first abort, but after you get a second abort (with some aging logic), you stop doing that transaction as a transaction for a longish while (again, some aging logic).

You know after two failures (again: "some aging logic", so "two failures" means basically "at least somewhat common") that you already lost a lot more than you would have won, so it's time to cut your losses, and stop doing that transaction entirely. At least for a good while - you can try again later to see if maybe things have changed. That "later" may be something really simple like "clear all transaction failure counters every million cycles" or whatever.

And you can obviously tune this - if you have a capacity failure, stop that transaction immediately, there's no point in failing multiple times at all.

But fundamentally, you don't need to be "perfect". You need to be better than what you are without the predictor. And honestly, that's not a very high bar to meet.

In the extreme case, you can approximate that cost/win thing as almost a constant (probably per-microarchitecture), and argue that the bigger the sequence you aborted, potentially the bigger the win was. It's pretty much what a software solution would have had to do anyway, but a software solution would have been prohibitively expensive, because updating some per-transaction counters for every transaction would pretty much entirely eat up any advantage you got from doing it as a transaction in the first place.

So the could be as simple as something like "age the failure counter by some factor every time you encounter a transaction start, and then try it again when the failure has aged away".

End result: sure, your counting logic is different from a conditional branch, but everything else (ie how to actually associate the code flow that has the transaction with the counting logic) is still largely the same.

And yes, I'm handwaving wildly. You obviously need to actually do a very good microarchitectural simulator and modeling with real-life problems (which implies that your simulator is fast enough to run real-life problems) to really tune the thing. But that's no different from what any competent CPU architecture group already has to do anyway.

If you tell me that your CPU architecture group doesn't have a good high-performance simulator for your architecture that can run real loads, then you're telling me that your architecture group is incompetent and shouldn't have implemented a new feature like TSX in the first place.

And no, none of this is needed if you can statically prove that your transactions will succeed sufficiently often to make up for the failure cases. That's how all those "look how nice transactional memory" benchmarks work.

Linus
< 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?