10 ms·

Well, I'd love to get some discussion here. One of the perennial questions that I've never received a satisfactory answer to is: Where's the ILP? Everytime I

Well, I'd love to get some discussion here. One of the perennial questions that I've never received a satisfactory answer to is: Where's the ILP? Everytime I get asked this, I get referred to the "Phasing" talk, but that isn't a satisfactory response either. I think quantitative analysis will prove to be far more nuanced and damning than expected. Take this paper (https://pdfs.semanticscholar.org/1002/50a822251d1302c146ab499635af2b3adb45.pdf https://pdfs.semanticscholar.org/1002/50a822251d1302c146ab49...). This paper analyzes a processor with much STRONGER characteristics than the Mill: It dynamically identifies these dependencies and then schedules them. The result? It gets smashed by a classic OoO.

mycall 9y ago
They are claiming up to 6 ILP: http://millcomputing.com/topic/introduction-to-the-mill-cpu-programming-model-2/ http://millcomputing.com/topic/introduction-to-the-mill-cpu-...
- m-j-fox 9y ago
  If true, that'd be a very high number. Intel can get 2 on some benchmarks, but system-average IPC tends towards 1. (In terms of instructions standardized for cross-platform comparison. I take data on ARM servers and I'm jellous of 1.) Are any Intel engineers on this thread saying, whelp if they can do 6 we may as well give up? Or does the lack of any data help you sleep soundly and skeptically?
  - deepnotderp 9y ago
    Sure. In theory Skylake can deliver ~8uOPs per cycle in parallel. Do they in real code? No. The Mill team claims (with no running general purpose code OR data of any sort) that they can. YMMV, but I bet Intel sleeps safe. Which sucks because I actually want innovation in computer architecture, which is a notoriously uninnovative industry, and the Mill has some genuinely good ideas, but I don't think they'll work here.
    - Veedrac 9y ago
      > In theory Skylake can deliver ~8uOPs per cycle in parallel. 4 µop/cycle after fusion. http://www.agner.org/optimize/blog/read.php?i=650 http://www.agner.org/optimize/blog/read.php?i=650
  - jimrandomh 9y ago
    ILP and IPC are not the same thing. ILP (instruction-level parallelism) is the number of instructions executed in a non-stalled clock cycle. IPC (instructions per clock) is the average number of instructions executed per clock, including clock cycles spent waiting for main memory and recovering from branch mis-prediction.
  - deleted 9y ago
    [deleted]
    - naasking 9y ago
      Decades of optimization on a crap architecture. The Mill has been able to learn from the mistakes made in every architecture to date. The kind of comparison you make doesn't mean anything as a result.
      - mozumder 9y ago
        Intel has also learned from each generation. CISC is very efficient. They do the most ops per transistor.
        naasking 9y ago
        But Intel is constrained by backwards compatibility. "CISC is very efficient" is a meaningless statement. The specific instruction set and its implementation is or is not efficient.
    - dbancajas 9y ago
      Disclaimer: Opinions are solely my own and do not reflect my employer's
  - phkahler 9y ago
    See slide 44: https://riscv.org/wp-content/uploads/2016/01/Wed1345-RISCV-Workshop-3-BOOM.pdf https://riscv.org/wp-content/uploads/2016/01/Wed1345-RISCV-W... It is very dependent on the workload.
kinghajj 9y ago
It doesn't look like the architecture in this paper supports pervasive speculation, which the Mill can via its "Not-a-Result" (NAR) bits on each data element. Vectors on the Mill have such a bit both for the entire vector, and for each element within the vector, which (along with other novelties) is supposed to help both with vectorizing and software pipelining code that can't be on conventional architectures. Ivan emphasizes in the videos that these features are what make the Mill capable of high ILP, which is why they go very wide (33 on "gold").
- deepnotderp 9y ago
  Short loops which have very few iterations and are not very long running comprise anywhere from 50-60% of the execution time on SpecINT type workloads (we'll extrapolate that to general purpose code). These are the types of things that kill software pipelining. Furthermore, sometimes these loops have dependencies between iterations. As a sidenote, the primary advantage of the Mill in software pipelining seems to be that they can software pipeline loops without a need for a prologue or epilogue and thus save a lot of cache space. Elbrus (https://www.google.ch/patents/US20020133813 https://www.google.ch/patents/US20020133813) had this too, didn't help them get good ILP.
  - jacobolus 9y ago
    Why don’t you come up with a concrete example of code that you think will perform poorly and post it on their forum and see what they say?
    - deepnotderp 9y ago
      Basically any piece of general purpose code. Oh, and someone (disjoint from the Mill team!) has actually made a model of the Mill's phasing and found that it fails to r.
      - overcyn 9y ago
        Do you have a link to that?
_chris_ 9y ago
"We postulate that the original study produced good results because it evaluated the new scheduler in a machine whose performance bottleneck lay outside the execution core. The problems introduced by the steering logic were, as a result, hidden." Any new microarchitecture needs to first answer that big question -- how is the core going to deal with memory?
- deepnotderp 9y ago
  Fun fact, the Mill's proposed method for hiding that latency, "deferred loads" has already been done by Duke's Architecture Group: http://people.duke.edu/~bcl15/documents/huang2016-nisc.pdf http://people.duke.edu/~bcl15/documents/huang2016-nisc.pdf (warning PDF link). The big gain? A measly ~8%.
  - cwzwarich 9y ago
    This doesn't decouple across function calls like the Mill claims to, right? Although doing that optimization on existing C/C++ programs will be difficult.
    - deepnotderp 9y ago
      I don't think that's enough of a difference, YMMV, but nothing indicates that it should.
cwzwarich 9y ago
It seems to me that the main fundamentally new idea of the Mill is the deferred load mechanism described in the Memory talk. They claim that it can complete with OoO execution with a much simpler implementation. It does require some of the other Mill mechanisms for full efficiency, e.g. it uses the belt to defer loads across calls. If this mechanism doesn't work as expected with real software, then there's no reason to think that the Mill will fare any better for general-purpose computation than any earlier VLIW/EPIC machine, for all the same reasons as before. And in that same talk they make some claims about OoO that seem a bit naive. The state-of-the-art has evolved a lot since the company was founded in 2003.
- deepnotderp 9y ago
  Copy paste: Fun fact, the Mill's proposed method for hiding that latency, "deferred loads" has already been done by Duke's Architecture Group: http://people.duke.edu/~bcl15/documents/huang2016-nisc.pdf http://people.duke.edu/~bcl15/documents/huang2016-nisc.pdf (warning PDF link). The big gain? A measly ~8%.
  - legulere 9y ago
    8% seems huge for an architectural change to me.
  - jimrandomh 9y ago
    IIRC the Mill's presentation about deferred loads predates this paper, though the paper is a lot more detailed and has simulations. It's not clear how the Mill's gain from deferred loads would compare (it differs in a lot of other ways that would interact).
  - mistercow 9y ago
    I'm pretty out of my depth here, but I thought the deferred loads latency was part of the 12% gained from dynamic scheduling, not the 88% that the Mill claims to tackle with its phasing thing. In that case, 8% doesn't sound measly at all. But like I said, I wouldn't be surprised if I'm just not understanding what I'm reading/watching.
  - 9y ago
wtallis 9y ago
> This paper analyzes a processor with much STRONGER characteristics than the Mill: It dynamically identifies these dependencies and then schedules them. I'm not really sure what this means, especially "stronger characteristics". The paper seems to have started with an idealized OoO processor, then subtracted from its capabilities and demonstrated that performance suffered. No surprise there, but that's not easy to translate into a comparison against the Mill. The Mill is not expected to ever compete against a full OoO processor of equivalent width; the Mill is expected to always be much wider. I haven't fully thought through the implications, but I think there might be a significant difference in the instruction scheduling algorithm between the paper's model and a Mill. The paper's model will queue an instruction as soon as at least one of its dependencies has been scheduled, or slot it into an empty queue (where it may cause head of line blocking). By contrast, the ahead-of-time scheduling done by a compiler for the Mill won't issue an instruction until all of its dependencies are in the pipeline and due to finish in time (or stall for memory fetches), and uses explicit NOPs instead of head of line blocking on an issue queue.
- deepnotderp 9y ago
  The reason I bring up the comparison is that both the Mill and this paper rely upon the existence of these sorts of dependency chains (I like to call them "picothreads" or "femtothreads") in general purpose code in order to get good performance. This paper shows that the existence of such chains are far too wide and shallow to be useful for their intended purpose. FWIW, someone (disjoint from the Mill team!) has actually made a model of the Mill's phasing and found that it fails to deliver. And "stronger characteristics" means that it dynamically identifies dependencies.
  - wtallis 9y ago
    > This paper shows that the existence of such chains are far too wide and shallow to be useful for their intended purpose. But doesn't this paper model a machine that is substantially narrower and deeper than a high-end Mill is expected to be? And what you judge to be the depth of a dependency chain depends on whether you're looking at a 128-instruction reorder buffer or if you're a compiler looking at the entire function. Figure 4 in the paper particularly seems to indicate that the failing of the dependence-based model is entirely in the front-end, which seems to be the least Mill-like part of the model.
m-j-fox 9y ago
It's good he recognizes that most code won't benefit from switch optimization. But certain tasks like pattern matching benefit greatly. For that, I suggest: http://www.micronautomata.com/ http://www.micronautomata.com/ Micron will eat 1000 nested switches 100 cases wide every cycle. This sort of TCAM tech was rare 5 years ago, but everywhere now.
- glangdale 9y ago
  I'm biased on this topic, as I work for Intel on regular expression matching, so I suppose I am 100% invested in the traditional Von Neumann architecture for this task. I'd say the Micron Automata processor (which never really shipped from Micron in performant form - there were some "too slow to provide real numbers" units out there) is very interesting. But many of the applications for it in pattern matching as elsewhere are contingent on doing useful parallel work if they are to outcompete an optimized software implementation. So if you have a giant NFA where you need to run 16384 states all the time, the Micron AP looks great. However, if you can manage to find sleazy optimization tricks that allow you to cheat and get down to running the occasional 256-bit NFA over a few bits of your input, the AP isn't competitive. More of the pattern matching task that we're familiar with (i.e. for network security) looks like the latter case (tricks being possible). I'm very interested in seeing the tech get out there, but its been spun out into a startup and I don't know what the future looks like for it.
cpleppert 9y ago
>> One of the perennial questions that I've never received a satisfactory answer to is: Where's the ILP? Anyone with any experience in the field can come up with an instruction encoding structure that produces more instruction level parallelism in theory. It's usually a simple mental exercise to determine that such a CPU isn't implementable in the "real world." That's exactly what is happening here with Mill except they have really dived off the deep end and do so much handwaving that it's hard to tell exactly how mill is supposed to work. Take branch prediction: Last time I checked they wanted the processor to load what they described as an "exit table" associated with a module of code that serves as a branch prediction unit. The problem is that this doesn't work at all. You can't have a CPU load a separate data structure that replaces its internal state like this. First off, this is way too complex as a piece of front end logic for the processor. Trying to access this as code is running is basically impossible. Secondly, A branch predictor has to produce a prediction immediately, you can't just handwave and say you will ask an internal data store structure to produce a result. Their description of this is that it is in some way a "hash table" (http://millcomputing.com/wiki/Prediction http://millcomputing.com/wiki/Prediction). That's really interesting because you would never ever want to implement a hash table in a CPU. Either a) they described it analogously as acting like a hash table; which doesn't make a lot of sense here in a technical description b) they really want to implement a hash table lookup as a branch predictor which be horrendously complex and would never work latency wise or c) they are are calling an associative cache a hash table. They also want to somehow update this "hash table" with a correct prediction on a mispredict. So somehow the processor will update a separate data structure (using a hash table lookup) every time there is a misprediction. Which again, doesn't work latency wise. By the way, all of this somehow has to be loaded and unloaded seamlessly into main memory. Notice that there is no description of any advanced logic that is used in modern processors to dramatically increase the accuracy of predictors. I don't even understand how they would possibly implement any of that advanced logic with the branch prediction unit so complex and decoupled from the front end of the processor. Of course, this kind of compiler driven prediction has been tried before and it doesn't work for obvious reasons. The compiler has a lot less information about the current state of the program than the processor does. So to recap: they described a feature that doesn't work as described, if it did work would be horrendously complex and wouldn't properly work as a branch predictor and finally doesn't actually provide better predictions at all. This is basically Mill in a nutshell.
randyrand 9y ago
Can the mill not execute instructions ahead of others? Maybe i dont understand what it means to be out of order, but the Mill can decode up to 30ops per cycle and issue many of the simultaneously.
- TazeTSchnitzel 9y ago
  The Mill isn't an “out-of-order” machine because it's not taking linear code and scheduling it to run out-of-order dynamically (i.e. when it executes). Instead, the compiler does the scheduling.
- wtallis 9y ago
  The Mill is pipelined and superscalar, which are the key features to having multiple operations in-flight, and it is also speculative in that it will start feeding stuff into the pipeline before it's known whether those are definitely the right instructions to be executing. Out-of-order execution means a CPU will re-order instructions on-chip to account for stalls due to cache misses or (on superscalar processors) due to a mismatch between the kinds of instructions and the kinds of execution units available. OoO execution require analyzing instruction dependency information pretty early in the pipeline and very quickly to keep up a steady stream of ready-to-execute operations. An in-order processor like the Mill only pays attention to instruction dependencies to determine whether a memory fetch has been completed, and if not to stall the pipeline until it has. The Mill compensates for that performance disadvantage by being statically scheduled: all the decisions about how to schedule the instructions are handled by the compiler toolchain, which has to know the exact instruction latencies and mix of available functional units on that model. An in-order processor that isn't statically scheduled could be superscalar but it would be hard to get several functional units in use simultaneously. For example, the original Pentium was in-order but could issue up to two instructions simultaneously, with restrictions on what instructions could be executed in what pipe and if the two instructions in a pair didn't take the same amount of time a third (and maybe fourth) instruction couldn't start until both had finished.
  - hvidgaard 9y ago
    > ... all the decisions about how to schedule the instructions are handled by the compiler toolchain, which has to know the exact instruction latencies and mix of available functional units on that model. That sounds pretty bad from a performance standpoint. You'd have to compile a binary for every single CPU to get the best performance. Maybe it could work with JIT languages running on JVM and CLR.
ghusbands 9y ago
That paper isn't particularly relevant, as the non-OoO CPU described therein is not much like the Mill at all. It would be interesting indeed, though, to see the Mill folks produce performance figures for some common software. Remember that a VLIW CPU has a lot of sub-ops in each instruction word, so it by design has more ILP, though only when the workload allows for many of those sub-ops to be filled, and how much work those sub-ops do can muddy the waters.
rbanffy 9y ago
> It gets smashed by a classic OoO. Keep in mind that if its implementation is much simpler, it'll be smashed by an OoO x86 single thread performance, but may still win on real world workloads.

mycall 9y ago

They are claiming up to 6 ILP: http://millcomputing.com/topic/introduction-to-the-mill-cpu-programming-model-2/ http://millcomputing.com/topic/introduction-to-the-mill-cpu-...

m-j-fox 9y ago
If true, that'd be a very high number. Intel can get 2 on some benchmarks, but system-average IPC tends towards 1. (In terms of instructions standardized for cross-platform comparison. I take data on ARM servers and I'm jellous of 1.) Are any Intel engineers on this thread saying, whelp if they can do 6 we may as well give up? Or does the lack of any data help you sleep soundly and skeptically?
- deepnotderp 9y ago
  Sure. In theory Skylake can deliver ~8uOPs per cycle in parallel. Do they in real code? No. The Mill team claims (with no running general purpose code OR data of any sort) that they can. YMMV, but I bet Intel sleeps safe. Which sucks because I actually want innovation in computer architecture, which is a notoriously uninnovative industry, and the Mill has some genuinely good ideas, but I don't think they'll work here.
  - Veedrac 9y ago
    > In theory Skylake can deliver ~8uOPs per cycle in parallel. 4 µop/cycle after fusion. http://www.agner.org/optimize/blog/read.php?i=650 http://www.agner.org/optimize/blog/read.php?i=650
- jimrandomh 9y ago
  ILP and IPC are not the same thing. ILP (instruction-level parallelism) is the number of instructions executed in a non-stalled clock cycle. IPC (instructions per clock) is the average number of instructions executed per clock, including clock cycles spent waiting for main memory and recovering from branch mis-prediction.
- deleted 9y ago
  [deleted]
  - naasking 9y ago
    Decades of optimization on a crap architecture. The Mill has been able to learn from the mistakes made in every architecture to date. The kind of comparison you make doesn't mean anything as a result.
    - mozumder 9y ago
      Intel has also learned from each generation. CISC is very efficient. They do the most ops per transistor.
      - naasking 9y ago
        But Intel is constrained by backwards compatibility. "CISC is very efficient" is a meaningless statement. The specific instruction set and its implementation is or is not efficient.
  - dbancajas 9y ago
    Disclaimer: Opinions are solely my own and do not reflect my employer's
- phkahler 9y ago
  See slide 44: https://riscv.org/wp-content/uploads/2016/01/Wed1345-RISCV-Workshop-3-BOOM.pdf https://riscv.org/wp-content/uploads/2016/01/Wed1345-RISCV-W... It is very dependent on the workload.

kinghajj 9y ago

It doesn't look like the architecture in this paper supports pervasive speculation, which the Mill can via its "Not-a-Result" (NAR) bits on each data element. Vectors on the Mill have such a bit both for the entire vector, and for each element within the vector, which (along with other novelties) is supposed to help both with vectorizing and software pipelining code that can't be on conventional architectures. Ivan emphasizes in the videos that these features are what make the Mill capable of high ILP, which is why they go very wide (33 on "gold").

deepnotderp 9y ago
Short loops which have very few iterations and are not very long running comprise anywhere from 50-60% of the execution time on SpecINT type workloads (we'll extrapolate that to general purpose code). These are the types of things that kill software pipelining. Furthermore, sometimes these loops have dependencies between iterations. As a sidenote, the primary advantage of the Mill in software pipelining seems to be that they can software pipeline loops without a need for a prologue or epilogue and thus save a lot of cache space. Elbrus (https://www.google.ch/patents/US20020133813 https://www.google.ch/patents/US20020133813) had this too, didn't help them get good ILP.
- jacobolus 9y ago
  Why don’t you come up with a concrete example of code that you think will perform poorly and post it on their forum and see what they say?
  - deepnotderp 9y ago
    Basically any piece of general purpose code. Oh, and someone (disjoint from the Mill team!) has actually made a model of the Mill's phasing and found that it fails to r.
    - overcyn 9y ago
      Do you have a link to that?

_chris_ 9y ago

"We postulate that the original study produced good results because it evaluated the new scheduler in a machine whose performance bottleneck lay outside the execution core. The problems introduced by the steering logic were, as a result, hidden." Any new microarchitecture needs to first answer that big question -- how is the core going to deal with memory?

deepnotderp 9y ago
Fun fact, the Mill's proposed method for hiding that latency, "deferred loads" has already been done by Duke's Architecture Group: http://people.duke.edu/~bcl15/documents/huang2016-nisc.pdf http://people.duke.edu/~bcl15/documents/huang2016-nisc.pdf (warning PDF link). The big gain? A measly ~8%.
- cwzwarich 9y ago
  This doesn't decouple across function calls like the Mill claims to, right? Although doing that optimization on existing C/C++ programs will be difficult.
  - deepnotderp 9y ago
    I don't think that's enough of a difference, YMMV, but nothing indicates that it should.

cwzwarich 9y ago

It seems to me that the main fundamentally new idea of the Mill is the deferred load mechanism described in the Memory talk. They claim that it can complete with OoO execution with a much simpler implementation. It does require some of the other Mill mechanisms for full efficiency, e.g. it uses the belt to defer loads across calls. If this mechanism doesn't work as expected with real software, then there's no reason to think that the Mill will fare any better for general-purpose computation than any earlier VLIW/EPIC machine, for all the same reasons as before. And in that same talk they make some claims about OoO that seem a bit naive. The state-of-the-art has evolved a lot since the company was founded in 2003.

deepnotderp 9y ago
Copy paste: Fun fact, the Mill's proposed method for hiding that latency, "deferred loads" has already been done by Duke's Architecture Group: http://people.duke.edu/~bcl15/documents/huang2016-nisc.pdf http://people.duke.edu/~bcl15/documents/huang2016-nisc.pdf (warning PDF link). The big gain? A measly ~8%.
- legulere 9y ago
  8% seems huge for an architectural change to me.
- jimrandomh 9y ago
  IIRC the Mill's presentation about deferred loads predates this paper, though the paper is a lot more detailed and has simulations. It's not clear how the Mill's gain from deferred loads would compare (it differs in a lot of other ways that would interact).
- mistercow 9y ago
  I'm pretty out of my depth here, but I thought the deferred loads latency was part of the 12% gained from dynamic scheduling, not the 88% that the Mill claims to tackle with its phasing thing. In that case, 8% doesn't sound measly at all. But like I said, I wouldn't be surprised if I'm just not understanding what I'm reading/watching.
- 9y ago

wtallis 9y ago

> This paper analyzes a processor with much STRONGER characteristics than the Mill: It dynamically identifies these dependencies and then schedules them. I'm not really sure what this means, especially "stronger characteristics". The paper seems to have started with an idealized OoO processor, then subtracted from its capabilities and demonstrated that performance suffered. No surprise there, but that's not easy to translate into a comparison against the Mill. The Mill is not expected to ever compete against a full OoO processor of equivalent width; the Mill is expected to always be much wider. I haven't fully thought through the implications, but I think there might be a significant difference in the instruction scheduling algorithm between the paper's model and a Mill. The paper's model will queue an instruction as soon as at least one of its dependencies has been scheduled, or slot it into an empty queue (where it may cause head of line blocking). By contrast, the ahead-of-time scheduling done by a compiler for the Mill won't issue an instruction until all of its dependencies are in the pipeline and due to finish in time (or stall for memory fetches), and uses explicit NOPs instead of head of line blocking on an issue queue.

deepnotderp 9y ago
The reason I bring up the comparison is that both the Mill and this paper rely upon the existence of these sorts of dependency chains (I like to call them "picothreads" or "femtothreads") in general purpose code in order to get good performance. This paper shows that the existence of such chains are far too wide and shallow to be useful for their intended purpose. FWIW, someone (disjoint from the Mill team!) has actually made a model of the Mill's phasing and found that it fails to deliver. And "stronger characteristics" means that it dynamically identifies dependencies.
- wtallis 9y ago
  > This paper shows that the existence of such chains are far too wide and shallow to be useful for their intended purpose. But doesn't this paper model a machine that is substantially narrower and deeper than a high-end Mill is expected to be? And what you judge to be the depth of a dependency chain depends on whether you're looking at a 128-instruction reorder buffer or if you're a compiler looking at the entire function. Figure 4 in the paper particularly seems to indicate that the failing of the dependence-based model is entirely in the front-end, which seems to be the least Mill-like part of the model.

m-j-fox 9y ago

It's good he recognizes that most code won't benefit from switch optimization. But certain tasks like pattern matching benefit greatly. For that, I suggest: http://www.micronautomata.com/ http://www.micronautomata.com/ Micron will eat 1000 nested switches 100 cases wide every cycle. This sort of TCAM tech was rare 5 years ago, but everywhere now.

glangdale 9y ago
I'm biased on this topic, as I work for Intel on regular expression matching, so I suppose I am 100% invested in the traditional Von Neumann architecture for this task. I'd say the Micron Automata processor (which never really shipped from Micron in performant form - there were some "too slow to provide real numbers" units out there) is very interesting. But many of the applications for it in pattern matching as elsewhere are contingent on doing useful parallel work if they are to outcompete an optimized software implementation. So if you have a giant NFA where you need to run 16384 states all the time, the Micron AP looks great. However, if you can manage to find sleazy optimization tricks that allow you to cheat and get down to running the occasional 256-bit NFA over a few bits of your input, the AP isn't competitive. More of the pattern matching task that we're familiar with (i.e. for network security) looks like the latter case (tricks being possible). I'm very interested in seeing the tech get out there, but its been spun out into a startup and I don't know what the future looks like for it.

cpleppert 9y ago

>> One of the perennial questions that I've never received a satisfactory answer to is: Where's the ILP? Anyone with any experience in the field can come up with an instruction encoding structure that produces more instruction level parallelism in theory. It's usually a simple mental exercise to determine that such a CPU isn't implementable in the "real world." That's exactly what is happening here with Mill except they have really dived off the deep end and do so much handwaving that it's hard to tell exactly how mill is supposed to work. Take branch prediction: Last time I checked they wanted the processor to load what they described as an "exit table" associated with a module of code that serves as a branch prediction unit. The problem is that this doesn't work at all. You can't have a CPU load a separate data structure that replaces its internal state like this. First off, this is way too complex as a piece of front end logic for the processor. Trying to access this as code is running is basically impossible. Secondly, A branch predictor has to produce a prediction immediately, you can't just handwave and say you will ask an internal data store structure to produce a result. Their description of this is that it is in some way a "hash table" (http://millcomputing.com/wiki/Prediction http://millcomputing.com/wiki/Prediction). That's really interesting because you would never ever want to implement a hash table in a CPU. Either a) they described it analogously as acting like a hash table; which doesn't make a lot of sense here in a technical description b) they really want to implement a hash table lookup as a branch predictor which be horrendously complex and would never work latency wise or c) they are are calling an associative cache a hash table. They also want to somehow update this "hash table" with a correct prediction on a mispredict. So somehow the processor will update a separate data structure (using a hash table lookup) every time there is a misprediction. Which again, doesn't work latency wise. By the way, all of this somehow has to be loaded and unloaded seamlessly into main memory. Notice that there is no description of any advanced logic that is used in modern processors to dramatically increase the accuracy of predictors. I don't even understand how they would possibly implement any of that advanced logic with the branch prediction unit so complex and decoupled from the front end of the processor. Of course, this kind of compiler driven prediction has been tried before and it doesn't work for obvious reasons. The compiler has a lot less information about the current state of the program than the processor does. So to recap: they described a feature that doesn't work as described, if it did work would be horrendously complex and wouldn't properly work as a branch predictor and finally doesn't actually provide better predictions at all. This is basically Mill in a nutshell.

randyrand 9y ago

Can the mill not execute instructions ahead of others? Maybe i dont understand what it means to be out of order, but the Mill can decode up to 30ops per cycle and issue many of the simultaneously.

TazeTSchnitzel 9y ago
The Mill isn't an “out-of-order” machine because it's not taking linear code and scheduling it to run out-of-order dynamically (i.e. when it executes). Instead, the compiler does the scheduling.
wtallis 9y ago
The Mill is pipelined and superscalar, which are the key features to having multiple operations in-flight, and it is also speculative in that it will start feeding stuff into the pipeline before it's known whether those are definitely the right instructions to be executing. Out-of-order execution means a CPU will re-order instructions on-chip to account for stalls due to cache misses or (on superscalar processors) due to a mismatch between the kinds of instructions and the kinds of execution units available. OoO execution require analyzing instruction dependency information pretty early in the pipeline and very quickly to keep up a steady stream of ready-to-execute operations. An in-order processor like the Mill only pays attention to instruction dependencies to determine whether a memory fetch has been completed, and if not to stall the pipeline until it has. The Mill compensates for that performance disadvantage by being statically scheduled: all the decisions about how to schedule the instructions are handled by the compiler toolchain, which has to know the exact instruction latencies and mix of available functional units on that model. An in-order processor that isn't statically scheduled could be superscalar but it would be hard to get several functional units in use simultaneously. For example, the original Pentium was in-order but could issue up to two instructions simultaneously, with restrictions on what instructions could be executed in what pipe and if the two instructions in a pair didn't take the same amount of time a third (and maybe fourth) instruction couldn't start until both had finished.
- hvidgaard 9y ago
  > ... all the decisions about how to schedule the instructions are handled by the compiler toolchain, which has to know the exact instruction latencies and mix of available functional units on that model. That sounds pretty bad from a performance standpoint. You'd have to compile a binary for every single CPU to get the best performance. Maybe it could work with JIT languages running on JVM and CLR.

ghusbands 9y ago

That paper isn't particularly relevant, as the non-OoO CPU described therein is not much like the Mill at all. It would be interesting indeed, though, to see the Mill folks produce performance figures for some common software. Remember that a VLIW CPU has a lot of sub-ops in each instruction word, so it by design has more ILP, though only when the workload allows for many of those sub-ops to be filled, and how much work those sub-ops do can muddy the waters.

rbanffy 9y ago

> It gets smashed by a classic OoO. Keep in mind that if its implementation is much simpler, it'll be smashed by an OoO x86 single thread performance, but may still win on real world workloads.