Anders Jensen (@.) on 9/29/09 wrote:
>
>Putting instructions in parallel however is probably
>cheaper in software and extremely expensive in hardware,
>sure you will miss out on the last 10% of optimization
>or so, but that is the healthy sign you should look for
>in complex optimization.

You're overcomplicating the thing.

You don't even need any complex parallel decoding (which
really is quite complex for something like x86): OoO can
be done (and has been done) on a much simpler scale.

For example, you might be much better off with a single
instruction per cycle decoder tied into an OoO core, than
with a two-instruction paidable "UV pipe" like Intel has
in the Pentium (and Atom?) that has some fairly strict
pairability rules.

Of course, I wouldn't actually expect Intel to ever do
anything like that. A more likely situation is the kind
of traditional Intel decoder, which does one complex
instruction per cycle, but can do several ones if they
are simple.

And whatever you do at the front-end, you certainly don't
need to do any complex and "extremely expensive"
parallelism anywhere else. Tomasulo is neither very complex
nor extremely expensive.

>Still I'm not sure it is worth doing Tomasulo just to get
>this last part. Doing multipass pipelining will probably
>get you some gains that runahead leaves behind in this
>respect, but it will definitively cost you some
>throughput/watt.

I doubt that a superscalar highly pipelined approach is
all that much more simpler than Tomasulo with just a
reservation station per unit. I also think your "corner
cases" are oddly chosen:

>Complex problems never has simple solutions and I have yet
>to find a complex question where the best solution is a
>corner case. For CPU uarch typical corner cases would be
>in-order and Out-of-order.

That's just total bullsh*t.

The corner cases aren't "in-order" vs "out-of-order" at all.

There's a lot of details you are skipping, and the
complexity of in-order easily overlaps with the complexity
of out-of-order when you start looking at those details.

What you trivially just call in-order is a whole spectrum
of possible complexities, with ranges of pipeline depth
(and the inevitable forwarding) and super-scalar. Add to
that blocking vs nonblocking cache accesses etc etc.

Similarly, what you just dismiss as the "corner case" of
being OoO is not a corner case at all, but another whole
spectrum of implementations, ranging from some fairly
simple Tomasulo with just one reservation per unit to having
some rather extreme instruction window depths of tens (or
hundreds) of instructions etc.

And then you have the whole "speculative execution" which
you can do in both cases, and the question is just how
far you push it (in OoO you can push it much further - but
you don't have to).

So while I agree with you that the solution is never the
extremes ("corner cases") I fundamentally think you then
totally went off the deep end by saying that "in-order" vs
"out-of-order" are some kind of corner cases. You can't
make that kind of insane simplifications.

And the thing is, in-order hits a huge complexity and
performance wall. I can't recall anybody ever having done
more than two-way superscalar, even on things that are
much easier to decode than x86. There's just not enough of
an upside to the complexity (you'd do WLIV to avoid the
complexity, but that has its own downsides, both in future
designs and in I$ costs).

I also suspect that things like SMT (which Atom supports)
are a whole lot more natural in an OoO environment. The
pipeline just isn't as rigid. So you can't just compare
some unnamed in-order implementation with some other OoO
one and say that the in-order one is simpler - you have to
state what the performance requirements are.

Is a single-scalar in-order CPU without HT much simpler than
even the simplest OoO core? Oh, sure. Nobody will claim
otherwise. But try to make it perform better, and you'll
start seeing huge complexities - to the point where you
simply have to either say "no more performance", or you'd
create a monster that is much more complex than the
equivalently performing out-of-order implementation.

See? Nobody makes those insane in-order ones, because at
some point it just becomes much simpler to do out-of-order,
and get better performance much more naturally than by
trying to push the in-order thing.

Sure, you can push in-order. You can try to push it with
run-ahead threads, you can do SMT, you can do a lot of
those things. But in the end, at some point you'll either
find that your chip is more complex than a simple OoO
implementation would have been at equivalent performance,
or you'll just say "I'll stop here, and suck".

Calling out-of-order some "corner case" is ludicrous.

Linus