Predication and OoOE

Article: Why Apple Won’t ARM the MacBook
By: Wilco (Wilco.Dijkstra.delete@this.ntlworld.com), May 10, 2011 3:46 pm
Room: Moderated Discussions
Exophase (exophase@gmail.com) on 5/10/11 wrote:
---------------------------
>Wilco (Wilco.Dijkstra@ntlworld.com) on 5/10/11 wrote:
>---------------------------
>>Conditional execution does indeed pose a challenge to OoOE but not much more
>>than branches do (one possible implementation is to treat a conditional instruction
>>as a merged conditional branch + an unconditional instruction).
>
>This has been talked about a decent amount here lately and I'm not sure I follow
>all of the hazards and benefits. There's been a lot of talk in particular about
>the cost of mispredicting branches vs mispredicting predication.
>
>Let's say we're comparing an execution of a predicated instruction stream (both
>the true and false ends) vs a stream selected by a conditional branch. The direct
>implementation of predication wouldn't involve any kind of prediction; it'd include
>the destination as a source and mux the output somewhere down the pipe, accounting
>for the extra input David cited. Of course, some won't need 3 inputs (conditional
>register moves for instance) so even if things are cracked conditional instructions
>won't always need multiple stages to fit a 2-input register file.

This is basically the scheme used in Cortex-A8. Just execute the instruction and later on decide whether to use the original value or the newly computed value. It simplifies the forwarding as each conditionally executed instruction always produces its result. It has a cost though in that you always read the destination register (extra dependency) and you end up with a mux in all critical forwarding paths.

>Compared to the conditionally branched over instruction this introduces an additional
>register dependency in the instruction stream. But a dependency by itself doesn't
>necessarily have a penalty if there are enough independent instructions to fill
>the execution slots during its latency, and for a lot of instructions you'd predicate
>(ALU operations for instance) the latency will be low.

Correct.

>Surely there will be situations where you only want to predicate few or single
>instructions where there won't be dependency stalls due to it but the conditional
>will be random enough to branch mispredict much of the time otherwise (and the additional
>fetch/decode of the branch instruction itself).
>
>Trying to predict the predication and replay afterwards sounds unnecessarily complex;
>if the mispredicts here cost more than the non-predicting system then it won't save
>you much for unpredictable code which is the only place you really wanted predication
>over branches to begin with. Given that ARM code has the choice between the two
>you'd think the programmer/compiler/profiler would try to avoid the worse one for the situation.
>
>If I'm completely missing the real expenses of predication/OoOE here could someone please set me straight?

You're right. Predication is particularly good at removing otherwise unpredictable branches. However doing it that way adds an extra register operand which means you need to rename 3 registers rather than 2. I suppose the best option would be to crack them into 2 uops, one to execute the instruction unconditionally and one to merge the result. This avoids the extra mux like in the A8 as well. Loads/stores are obviously harder, as they need to be speculated and not affect state.

However using branch prediction may actually be simpler and even faster in some circumstances. You use the existing mechanisms in place to deal with branches, and avoid the extra rename operand or cracking. If the replay mechanism is fast then you could avoid the full branch mispredict penalty, which could result in better performance even if the prediction accuracy is low.

So which is best depends. For a simple OoO like the A9, it is no surprise it chooses the branch prediction option. For more advanced cores I suspect cracking is better.

Wilco
< Previous Post in ThreadNext Post in Thread >
TopicPosted ByDate
New Article: Why Apple Won’t ARM the MacBookDavid Kanter2011/05/10 12:19 AM
  New Article: Why Apple Won’t ARM the MacBookMark Christiansen2011/05/09 11:24 PM
  New Article: Why Apple Won’t ARM the MacBookLouis Gerbarg2011/05/09 11:54 PM
  New Article: Why Apple Won’t ARM the MacBooknone2011/05/10 12:57 AM
    New Article: Why Apple Won’t ARM the MacBookDavid Kanter2011/05/10 01:18 AM
      New Article: Why Apple Won’t ARM the MacBooknone2011/05/10 02:14 AM
        New Article: Why Apple Won’t ARM the MacBookDavid Kanter2011/05/10 02:19 AM
          New Article: Why Apple Won’t ARM the MacBookGoose2011/05/10 02:34 AM
          New Article: Why Apple Won’t ARM the MacBookRatherNotSay2011/05/10 06:25 AM
          ARM predication not so horriblePaul A. Clayton2011/05/10 08:05 AM
            ARM predication not so horriblenone2011/05/10 08:12 AM
              Partial update seems kind of oddPaul A. Clayton2011/05/10 08:29 AM
                Partial update seems kind of oddExophase2011/05/10 08:51 AM
                  Partial update seems kind of oddMichael S2011/05/10 12:56 PM
                    Partial update seems kind of oddMichael S2011/05/10 01:25 PM
                      Partial update seems kind of oddWilco2011/05/10 02:39 PM
                        Partial update seems kind of oddanonymous422011/05/10 07:09 PM
                          Partial update seems kind of oddrwessel2011/05/10 09:57 PM
                  Condition register usesPaul A. Clayton2011/05/10 05:56 PM
                  Partial update seems kind of oddMegol2011/05/11 01:06 AM
          New Article: Why Apple Won’t ARM the MacBookKevin G2011/05/11 01:21 AM
      New Article: Why Apple Won’t ARM the MacBookWilco2011/05/10 03:47 AM
        New Article: Why Apple Won’t ARM the MacBookMichael S2011/05/10 04:06 AM
          New Article: Why Apple Won’t ARM the MacBookWilco2011/05/10 04:25 AM
            New Article: Why Apple Won’t ARM the MacBookMichael S2011/05/10 05:13 AM
        Predication and OoOEExophase2011/05/10 08:34 AM
          Predication and OoOEWilco2011/05/10 03:46 PM
            Predication and OoOEExophase2011/05/11 07:51 AM
        ARM ISADavid Kanter2011/05/10 09:12 AM
          ARM ISAUngo2011/05/10 12:30 PM
  New Article: Why Apple Won’t ARM the MacBookThibs2011/05/10 02:45 AM
  New Article: Why Apple Won’t ARM the MacBookLlew2011/05/10 03:33 AM
    New Article: Why Apple Won’t ARM the MacBookDavid Kanter2011/05/10 09:34 AM
  New Article: Why Apple Won’t ARM the MacBookKevin G2011/05/10 03:55 AM
    New Article: Why Apple Won’t ARM the MacBookDavid Kanter2011/05/10 10:07 AM
      New Article: Why Apple Won’t ARM the MacBookKevin G2011/05/11 01:33 AM
        New Article: Why Apple Won’t ARM the MacBookDavid Kanter2011/05/11 02:00 AM
  New Article: Why Apple Won’t ARM the MacBook ... The FACTS say otherwise !fabrice2011/05/10 04:07 AM
    New Article: Why Apple Won’t ARM the MacBook ... The FACTS say otherwise !Rakesh Malik2011/05/11 03:03 PM
      New Article: Why Apple Won’t ARM the MacBook ... The FACTS say otherwise !Richard Cownie2011/05/12 08:50 AM
        New Article: Why Apple Won’t ARM the MacBook ... The FACTS say otherwise !Rakesh Malik2011/05/12 09:10 AM
    Hrmmmm...David Kanter2011/05/14 12:19 AM
  iPad-writer?Jouni Osmala2011/05/10 04:35 AM
    Laptops finally moving to touchscreen GUI?mpx2011/05/10 06:03 AM
  What about MS?Joe Kerr2011/05/10 06:26 AM
  New Article: Why Apple Won’t ARM the MacBookRichard Cownie2011/05/10 06:41 AM
    Dual CPU makes more sense than dropping x86Mark Roulo2011/05/10 07:54 AM
      Dual CPU makes more sense than dropping x86Richard Cownie2011/05/10 09:02 AM
        Dual CPU makes more sense than dropping x86Mark Roulo2011/05/10 09:28 AM
          Dual CPU makes more sense than dropping x86Richard Cownie2011/05/10 09:55 AM
            Dual CPU makes more sense than dropping x86Wes Felter2011/05/10 11:20 AM
      Dual CPU makes more sense than dropping x86rwessel2011/05/10 11:01 AM
        Dual CPU makes more sense than dropping x86fabrice2011/05/10 12:02 PM
    New Article: Why Apple Won’t ARM the MacBookDavid Kanter2011/05/10 10:18 AM
      New Article: Why Apple Won’t ARM the MacBookRichard Cownie2011/05/10 12:10 PM
        Form factors and performanceDavid Kanter2011/05/10 12:39 PM
          Form factors and performanceRichard Cownie2011/05/10 05:25 PM
            Form factors and performanceLinus Torvalds2011/05/10 06:24 PM
              Form factors and performanceRichard cownie2011/05/11 02:12 AM
                Form factors and performanceRichard Cownie2011/05/11 03:44 AM
              Form factors and performanceGabriele Svelto2011/05/11 09:03 AM
                Form factors and performanceLinus Torvalds2011/05/11 10:16 AM
                  Form factors and performanceMark Christiansen2011/05/11 11:06 AM
                  Form factors and performanceRichard Cownie2011/05/11 12:36 PM
              Form factors and performanceDoug Siebert2011/05/11 10:19 AM
                Form factors and performanceRakesh Malik2011/05/11 03:36 PM
            Form factors and performanceFoo_2011/05/11 04:33 AM
              Form factors and performanceRichard Cownie2011/05/11 05:35 AM
              Form factors and performanceJoe Kerr2011/05/11 09:05 PM
    New Article: Why Apple Won’t ARM the MacBookUngo2011/05/10 01:33 PM
      New Article: Why Apple Won’t ARM the MacBookRichard Cownie2011/05/10 04:54 PM
  Maybe after Cortex A15 ?Nicolas2011/05/10 07:07 AM
    Maybe after Cortex A15 ?anonymous422011/05/10 11:01 AM
      Maybe after Cortex A15 ? Nicolas2011/05/11 01:34 PM
  One way for ARM to beat Inteletienne2011/05/10 04:38 PM
  Perhaps ARMed apple netbooks?John H2011/05/16 08:14 PM
    Perhaps ARMed apple netbooks?blah2011/05/17 08:02 PM
      Perhaps ARMed apple netbooks?Brett2011/05/18 02:50 AM
        Perhaps ARMed apple netbooks?Llew2011/05/18 03:43 AM
        Perhaps ARMed apple netbooks?David Kanter2011/05/18 09:46 AM
          Perhaps ARMed apple netbooks?Brett2011/05/18 11:43 AM
            Perhaps ARMed apple netbooks?blah2011/05/18 08:01 PM
            Perhaps ARMed apple netbooks?David Kanter2011/05/18 11:47 PM
              Perhaps ARMed apple netbooks?Rob Thorpe2011/05/19 01:07 AM
                Perhaps ARMed apple netbooks?blah2011/05/19 11:01 AM
                  Perhaps ARMed apple netbooks?Richard Cownie2011/05/19 11:48 AM
              iOS changes from OSXBrett2011/05/21 12:18 PM
                iOS changes from OSXBrett Davis2011/08/26 04:46 PM
              iOS changes from OSX Brett2011/06/03 10:50 AM
  New Article: Why Apple Won’t ARM the MacBookRobi52011/05/20 11:55 PM
    New Article: Why Apple Won’t ARM the MacBookDavid Kanter2011/05/21 01:36 PM
Reply to this Topic
Name:
Email:
Topic:
Body: No Text
How do you spell avocado?