3 ms·

> The safest bet now for the best security is probably to stick to in-order CPUs out-of-order execution != speculative execution. It is possible to have OoO w

by tomxor 7y ago

> The safest bet now for the best security is probably to stick to in-order CPUs out-of-order execution != speculative execution. It is possible to have OoO without speculative execution. On the other hand they do tend to come as a pair since they both utilise multiple execution units, for instance the Intel Pentium in 1993 was the first x86 to have OoO or branch prediction (486 and those before were scalar CPUs).

gpderetta 7y ago
OoO without speculation is completely pointless: the tipical reorder window is orders of magnitude larger than the average number of instructions between conditional jumps. I don't think there have ever been an OoO CPU without speculation. OTOH speculation without OoO Is not only possible but in fact very common. For example the majority of non ancient in-order CPUs. In fact the original pentium, contrary to your statement, was an in-order design (the pentium pro was the first Intel OoO design). Also I believe that 486 already had branch prediction. Pentium claim to fame was being superscalar (i.e it could execute, in some cases two instructions per cycle), a better FPU and better pipelined ALU (I think it had a fully pipelined multiply for example).
- dfrage 7y ago
  > I don't think there have ever been an OoO CPU without speculation. To the extent I've looked at it, without reading original documents, the original OoO design that current systems are based on, the IBM System 360/Models 91 and 95's floating point unit using Tomasulo's algorithm https://en.wikipedia.org/wiki/Tomasulo_algorithm https://en.wikipedia.org/wiki/Tomasulo_algorithm didn't extend to speculative execution. No doubt because gates were dear, implemented with discrete transistors, and that processor was a vanity project of Tom Watson Jr's. And memory was slow, core except for NASA's two 95's with 2 MiB of thin film memory at the bottom, and cache was still a couple of years out, introduced with the 360/Model 85. OoO becomes compelling when you have a fast and unpredictable memory hierarchy, as we started to have in a big way in the 1990s when we returned to this technique.
  - gpderetta 7y ago
    Interesting. It seems that the machine did have some limited form of branch prediction, but probably the expectation was that FP kernels would be optimized to be mostly branch free, and, as you say, transistors were a premium.
- tomxor 7y ago
  > Also I believe that 486 already had branch prediction I can't find any evidence to support that [1] I suppose it's technically possible to have branch prediction on a scalar processor, but I imagine it would not be hugely beneficial. https://books.google.com.sg/books?id=QzsEAAAAMBAJ&pg=PA59&lpg=PA59&dq=486+branch+prediction&source=bl&ots=LCXnhUpS83&sig=g59BBBuiCx-qM6bOjRW5mkq1Nug&hl=en&sa=X&ved=0ahUKEwi7k5aCucXYAhUHQY8KHcgACkUQ6AEIPDAD#v=onepage&q=486%20branch%20prediction&f=false https://books.google.com.sg/books?id=QzsEAAAAMBAJ&pg=PA59&lp...
  - gpderetta 7y ago
    So it seems that the 486 had a trivial not-taken predictor; but that's still different from stalling on each conditional branch and does require checkpointing and rollback on misprediction (although with a pipeline only 5 deep that's probably also not very complex). Edit: pentium did have a significantly more sophisticated predictor of course, although not without flaws.
cfallin 7y ago
> It is possible to have OoO without speculative execution That's technically correct (the best type of correct!), but without speculation, the CPU can't see beyond a branch, so the window in which the machine can reorder instructions is very small. (For x86 code, the usual rule of thumb is that branches occur once per 5 instructions.) So in practical terms, an OoO design (in the restricted-dataflow paradigm, i.e., all modern general-purpose OoO cores) always at least does branch prediction, to keep the machine adequately full of ops. An interesting question, though, given that we're going to do speculation, is what types of speculation the core can do. The practical minimum is just branch prediction, but modern cores do all sorts of other speculation in memory disambiguation, instruction scheduling, and the like, some of which has enabled real side-channel attacks (e.g., Meltdown). Also, FWIW, Pentium was 2-way superscalar, but not OoO in the fully general dataflow-driven sense; the Pentium Pro (aka P6), in 1995, was the first OoO. (Superscalar can technically be seen as OoO, I suppose, in that the machine checks dependencies and can execute independent instructions simultaneously, but it's not usually considered as such, as the "reordering" window is just 2 instructions.)

by tomxor 7y ago

gpderetta 7y ago

OoO without speculation is completely pointless: the tipical reorder window is orders of magnitude larger than the average number of instructions between conditional jumps. I don't think there have ever been an OoO CPU without speculation. OTOH speculation without OoO Is not only possible but in fact very common. For example the majority of non ancient in-order CPUs. In fact the original pentium, contrary to your statement, was an in-order design (the pentium pro was the first Intel OoO design). Also I believe that 486 already had branch prediction. Pentium claim to fame was being superscalar (i.e it could execute, in some cases two instructions per cycle), a better FPU and better pipelined ALU (I think it had a fully pipelined multiply for example).

dfrage 7y ago
> I don't think there have ever been an OoO CPU without speculation. To the extent I've looked at it, without reading original documents, the original OoO design that current systems are based on, the IBM System 360/Models 91 and 95's floating point unit using Tomasulo's algorithm https://en.wikipedia.org/wiki/Tomasulo_algorithm https://en.wikipedia.org/wiki/Tomasulo_algorithm didn't extend to speculative execution. No doubt because gates were dear, implemented with discrete transistors, and that processor was a vanity project of Tom Watson Jr's. And memory was slow, core except for NASA's two 95's with 2 MiB of thin film memory at the bottom, and cache was still a couple of years out, introduced with the 360/Model 85. OoO becomes compelling when you have a fast and unpredictable memory hierarchy, as we started to have in a big way in the 1990s when we returned to this technique.
- gpderetta 7y ago
  Interesting. It seems that the machine did have some limited form of branch prediction, but probably the expectation was that FP kernels would be optimized to be mostly branch free, and, as you say, transistors were a premium.
tomxor 7y ago
> Also I believe that 486 already had branch prediction I can't find any evidence to support that [1] I suppose it's technically possible to have branch prediction on a scalar processor, but I imagine it would not be hugely beneficial. https://books.google.com.sg/books?id=QzsEAAAAMBAJ&pg=PA59&lpg=PA59&dq=486+branch+prediction&source=bl&ots=LCXnhUpS83&sig=g59BBBuiCx-qM6bOjRW5mkq1Nug&hl=en&sa=X&ved=0ahUKEwi7k5aCucXYAhUHQY8KHcgACkUQ6AEIPDAD#v=onepage&q=486%20branch%20prediction&f=false https://books.google.com.sg/books?id=QzsEAAAAMBAJ&pg=PA59&lp...
- gpderetta 7y ago
  So it seems that the 486 had a trivial not-taken predictor; but that's still different from stalling on each conditional branch and does require checkpointing and rollback on misprediction (although with a pipeline only 5 deep that's probably also not very complex). Edit: pentium did have a significantly more sophisticated predictor of course, although not without flaws.

cfallin 7y ago

> It is possible to have OoO without speculative execution That's technically correct (the best type of correct!), but without speculation, the CPU can't see beyond a branch, so the window in which the machine can reorder instructions is very small. (For x86 code, the usual rule of thumb is that branches occur once per 5 instructions.) So in practical terms, an OoO design (in the restricted-dataflow paradigm, i.e., all modern general-purpose OoO cores) always at least does branch prediction, to keep the machine adequately full of ops. An interesting question, though, given that we're going to do speculation, is what types of speculation the core can do. The practical minimum is just branch prediction, but modern cores do all sorts of other speculation in memory disambiguation, instruction scheduling, and the like, some of which has enabled real side-channel attacks (e.g., Meltdown). Also, FWIW, Pentium was 2-way superscalar, but not OoO in the fully general dataflow-driven sense; the Pentium Pro (aka P6), in 1995, was the first OoO. (Superscalar can technically be seen as OoO, I suppose, in that the machine checks dependencies and can execute independent instructions simultaneously, but it's not usually considered as such, as the "reordering" window is just 2 instructions.)