Comment by wtallis | Hacker News Reader

Comment by wtallis | Hacker News Reader

Parent Full thread

> 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.

The "wider" claim is one that I highly suspect.

Mill has very specific storage for arguments and results. For each operation you need 3 lines to that storage - two for arguments and one for result. The storage has O(num-of-wires^2) wiring overhead and you cannot get away from that in general. You can get away with less (Alpha AXP (OoO) has, for example, split register file where results migrated from one half to another behind the scenes) but it is very complex to implement. The VLIW architectures has some nice wideness and THEY ALL suffer from problem that register file of that width presents. You can see that in the clock speeds - Pentiums run around the Itanium in terms of clock speeds. It is precisely because Itanium has large register file (128 registers) and wide issue.

I keep coming to the discussion of the Mill and keep finding the argument that Mill will be wider. And no one bother to address my arguments that for wideness you need O(width^2) wires in the storage, which makes storage impractical or too complex to implement.

Mill has no register file, and is essentially a bypass network internally. That bypass network has a source X sink complexity (not N^2 because the number of sources need not match the number of sinks). You are right that the cross product is a limit on Mill scaling. Our internal work gives us some confidence that we can handle 30-wide issue with tolerable clock impact; beyond that is unclear, and indeed we may hit other constraints that preclude going further; memory bandwidth is a likely issue.

What makes you think you can extract that much instruction level parallelism in the first place?

One major one is speculation. Each Mill operand, or element in a vector operand, has a 'Not a Result' (NaR) flag.

You still have quadratic complexity of the network, the "need not match" argument can be reduced to a constant multiplier.

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.

> 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.

Read the next sections of the paper, it shows that the reason for that anguishing front end is due to the stalled instructions.

> it shows that the reason for that anguishing front end is due to the stalled instructions.

Stalled by what, though? Stalled waiting for memory (partially alleviated by the Mill's deferred loads), stalled waiting for dispatch from the queues that the Mill doesn't have, or stalled when at the head of the dispatch queue and ready to issue when the assigned execution unit is busy but some other execution unit is free?

The whole dispatch vs issue mismatch they're complaining about doesn't exist on the Mill or any other statically-scheduled machine (though there's a related problem in how many instruction slots end up as NOPs). There are at least three other features of the Mill that make the example in figure 6(a) inapplicable, and they didn't diagram the dependencies from the real code used to generate figure 6(b).

Stalled by scheduling constraints.

I don't think those scheduling constraints exist on the Mill. Certainly the ones illustrated in figure 6(a) don't. Add operation number 5 could issue during the empty slot on cycle number 5 instead of 6 thanks to deferred loads, or thanks to the fact that the Mill uses a multitude of specialized execution units rather than a handful of general-purpose execution units—a busy load unit could never stall an independent add operation to begin with.

It looks like add operation number 5 can't use the empty cycle on lane 2 because compare number 3 would already be queued in that lane. The time-reversed/consumers first scheduling heuristic that a Mill compiler uses wouldn't paint itself into this corner the way the this model's dispatcher does.

Figure 6(a) for a Mill would look like an ALU pipeline doing an add operation every cycle without stall, a load pipeline issuing a load operation every cycle without stall, another ALU pipeline doing compare operations every cycle but lagging behind by several cycles instead of just one, and a branch unit doing the conditional jump every cycle immediately after the corresponding compare. And on a mid-level or high-end Mill there would be plenty of execution units to spare for a non-trivial loop body without reducing throughput, and the whole thing would be vectorized too.

> FWIW, someone (disjoint from the Mill team!) has actually made a model of the Mill's phasing and found that it fails to deliver.

Citation is definitely needed, here.

Not really, publication quality. Just a Sunday-morning effort to understand the ceiling on the phased-execution model. All resources like decode, #pipes, cache and branch prediction are unmodeled, assumed infinite. I'm sure anyone can improve on it, but I lost interest with disappointing results.

https://pastebin.com/14E7X41j

I dump the instruction stream for coremark out of LLI interpreter, hacked a tiny bit. To save trouble, here's one iteration of coremark:

https://drive.google.com/open?id=0B0ygb7T_Ab3kM01DQnlvQi1teG...

gunzip the data, run it through the script and count the lines out vs lines in. (I get "IPC" ~2.12.) For a bit more insight, the number on the left of each output line is how many instructions fused. You can make a histogram like:

    cat tmp.out | cut -f 1 -d " " | sort -n|uniq -c

    76056 1
    95805 2
    32931 3
    4401 4
    1172 5
    970 6
    ...

Hi Michael,

To think I messed around with Valgrind ;) This is much easier.

I look at the particulars of the grouping and think 'no, that's not right', and 'that can't be with this', and 'that can be with that', and so on. The results are far too back-of-the-envelope to be right. But the approach is excellent, and that's the main thing :)

I'm going to crunch through the IR recording and work out the ILP with/without speculation etc. Will leave pipelining and auto-vectorization off the table. As this is all public stuff I reckon the results can be made public.

Wanna work with me on this? I'd like you back. This time it might work. Mail me :)

/Will

Reply on news.ycombinator.com