On 2/15/2022 8:22 AM, Stefan Monnier wrote:
>> I am not suggesting that isn't true, but I do question why it is true. That
>> is, if it is beneficial, I presume a compiler could do its scheduling across
>> a window at least as big as HW. The compiler can use more memory and time
>> than is available to the HW. As a minimum, it could emulate what the HW
>> does so should be equal (excepting for variable length delays).
>
> To make good use of a 1000-instruction window, you need extremely good
> branch prediction. We know how to build such predictors for CPUs
> (i.e. where they have access to the actual run-time behavior) but we
> have no clue how to do that in a compiler (which works on the static
> code without knowledge of the actual run time values manipulated).

Thank you. That makes perfect sense. BTW, does that present an
opportunity for some sort of profile driven optimization where the run
time branch history is fed back to a future compilation for better
optimization? Probably not as useful for an OoO machine.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

"Scott Smader" wrote in message
news:70f6512f-243d-4492-80e6-299b40361ea5n@googlegroups.com...

> Disclosure: I am so smitten by Mill, that I have made an investment
> in Mill Computing. I hope that isn't swaying my analysis. If I'm wildly
> wrong, I'd really like to know. Please be the friend who breaks it to me.

I'm really cheering for Mill but I worry about the Magic Compiler
issue and perhaps not offering enough support for pizza-faced
kids in their parents' garages trying to implement the a fun
IoT device on a no-income budget and no formal training or
oscilloscope or the like.

> Thank you. That makes perfect sense. BTW, does that present an opportunity
> for some sort of profile driven optimization where the run time branch
> history is fed back to a future compilation for better optimization?
> Probably not as useful for an OoO machine.

Profile-driven optimization is used, of course, but the problem remains:
the compiler needs to generate code that works for all possible
situations and it can't freely duplicate code all over the place.
A bit of code duplication (to specialize a code path to a few different
scenarios) can be done, but only within fairly strict limits otherwise
code size will explode and performance goes down the drain again.

In contrast, an OoO is free to use a different schedule each time
a chunk of code is run (and similarly the branch predictor is free to
provide wildly different predictions each time that chunk of code is
run) without any downside.

The OoO works on the trace of the actual execution, where the main limit
is the size of the window it can consider (linked to the accuracy of the
branch predictor), whereas the compiler is not limited to such a window
but instead it's limited to work on the non-unrolled code.

Stefan

According to Thomas Koenig <tkoenig@netcologne.de>:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>
>> * Before people make assumptions about what I mean with "software
>> crisis": When the software cost is higher than the hardware cost,
>> the software crisis reigns. This has been the case for much of the
>> software for several decades.
>
>Two reasonable dates for that: 1957 (the first Fortran compiler) or
>1964, when the /360 demonstrated for all to see that software (especially
>compatibility) was more important than any particular hardware.

It was earlier than that. IBM introduced the transistorized 7070
announced in 1958 and shipped in 1960, intended to replace the vacuum
tube 650 and 705. But it was a flop because it couldn't run 705
programs. IBM rushed out the 7080, which was essentially a
transistorized 705 built out of 7090 parts.

The 360 was a huge gamble since they knew customers would not be happy
to have to reprogram. That's why every 360 up to the /65 had optional
emulation microcode so customers could run their 70xx and 14xx software.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

On 2/15/2022 8:58 AM, Stefan Monnier wrote:
>> Thank you. That makes perfect sense. BTW, does that present an opportunity
>> for some sort of profile driven optimization where the run time branch
>> history is fed back to a future compilation for better optimization?
>> Probably not as useful for an OoO machine.
>
> Profile-driven optimization is used, of course, but the problem remains:
> the compiler needs to generate code that works for all possible
> situations and it can't freely duplicate code all over the place.
> A bit of code duplication (to specialize a code path to a few different
> scenarios) can be done, but only within fairly strict limits otherwise
> code size will explode and performance goes down the drain again.
>
> In contrast, an OoO is free to use a different schedule each time
> a chunk of code is run (and similarly the branch predictor is free to
> provide wildly different predictions each time that chunk of code is
> run) without any downside.
>
> The OoO works on the trace of the actual execution, where the main limit
> is the size of the window it can consider (linked to the accuracy of the
> branch predictor), whereas the compiler is not limited to such a window
> but instead it's limited to work on the non-unrolled code.

That all makes sense. Thank you again.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On Tuesday, February 15, 2022 at 10:22:17 AM UTC-6, Stefan Monnier wrote:
> > I am not suggesting that isn't true, but I do question why it is true. That
> > is, if it is beneficial, I presume a compiler could do its scheduling across
> > a window at least as big as HW. The compiler can use more memory and time
> > than is available to the HW. As a minimum, it could emulate what the HW
> > does so should be equal (excepting for variable length delays).
<
> To make good use of a 1000-instruction window, you need extremely good
> branch prediction. We know how to build such predictors for CPUs
> (i.e. where they have access to the actual run-time behavior) but we
> have no clue how to do that in a compiler (which works on the static
> code without knowledge of the actual run time values manipulated).
<
Back in the days of Opteron: up to 50%* of the work inserted into execution
never made it to retirement. This was an execution window of depth ~64
3-wide issue, and 16Kbytes of branch predictor. On average Opteron
would perform 1 x86-64 instructions per clock, ranging in bursts of 3 IPC
down to 0 IPC averaging just over 1 IPC. A lot of this was window full
waiting for memory.
<
So, we lost ~50% to BP 3.0->1.5; then we lost another ~33% to execution widow
size (latency)
<
A 1000 instruction sized window cannot be done "flat"* one would have to
have a layered window with 100-ish using FUs, 600 waiting to get in, 200
waiting to retire--or something on those orders. Notice that modern IBM
z-Series have 10-ish stage pipeline of retirement.
<
(*) where flat means every instruction is in reservation stations from issue
to retirement.
>
>
> Stefan

Thomas Koenig <tkoenig@netcologne.de> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>
>> * Before people make assumptions about what I mean with "software
>> crisis": When the software cost is higher than the hardware cost,
>> the software crisis reigns. This has been the case for much of the
>> software for several decades.
>
>Two reasonable dates for that: 1957 (the first Fortran compiler) or
>1964, when the /360 demonstrated for all to see that software (especially
>compatibility) was more important than any particular hardware.

Yes, the term "software crisis" is from 1968, but programming language
implementations demonstrated already before Fortran (and actually more
so, because pre-Fortran languages had less implementation investment
and did not utilize the hardware as well) that there is a world where
software cost is more relevant than hardware cost. But of course at
the time, that software segment was considered to be a negligible
niche. Actually similar sentiments survive until today, as
demonstrated by some recent comments about JITs.

And likewise, the building of a family of compatible machines
demonstrates that software cost played an important role for hardware
design (and trumped the clean-slate approach that hardware designers
would prefer) already in the IBM 7094 and certainly in the S/360.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> Concerning speculation, yes, it does waste power, but rarely, because
>> branch mispredictions are rare.
>
>Of course in-order cores also speculate, so this is only
>tangentially related. But as a side-note I'll point out that statically
>scheduled processors encourage the compiler to move long-latency
>instructions such as loads to "as soon as it's safe to do it" rather
>than "as soon as we know we will need it", and that sometimes
>requires adding yet more "compensation code" in other branches.

Loads are a bad example, because you typically don't move the above a
branch they control-depend on, because loads can trap. Instead one
tends to use prefetches. IA-64 had a mechanism that allowed moving
loads up, however. Non-trapping instructions such as multiplications
can be moved up speculatively by the compiler. And because compiler
branch prediction (~10% miss rate) is much worse than dynamic branch
prediction (~1% miss rate, both numbers vary strongly with the
application, so take them with a grain of salt), a static scheduling
speculating compiler will tend to waste more energy for the same
degree of speculation.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 2/15/2022 10:21 AM, Scott Smader wrote:
> On Tuesday, February 15, 2022 at 3:47:39 AM UTC-8, Anton Ertl wrote:
>> Scott Smader <yogam...@yahoo.com> writes:
>>> On Monday, February 14, 2022 at 2:26:46 PM UTC-8, Anton Ertl wrote:
>>>> Why? If OoO is superior now at the current transistor budget, why=20
>>>> would it stop being superior if the transistor budget does not=20
>>>> increase?
>>>
>>> Not sure if the assumption of OoO superiority is justified at current trans=
>>> istor budget,
>>
>> Definitely. Here are two benchmarks, all numbers are times in
>> seconds:
>>
>> LaTeX:
>>
>> - Intel Atom 330, 1.6GHz, 512K L2 Zotac ION A, Debian 9 64bit 2.368
>> - AMD E-450 1650MHz (Lenovo Thinkpad X121e), Ubuntu 11.10 64-bit 1.216
>> - Odroid N2 (1896MHz Cortex A53) Ubuntu 18.04 2.488
>> - Odroid N2 (1800MHz Cortex A73) Ubuntu 18.04 1.224
>>
>> Gforth:
>>
>> sieve bubble matrix fib fft
>> 0.492 0.556 0.424 0.700 0.396 Intel Atom 330 (Bonnell) 1.6GHz; gcc-4.9
>> 0.321 0.479 0.219 0.594 0.229 AMD E-350 1.6GHz; gcc version 4.7.1
>> 0.350 0.390 0.240 0.470 0.280 Odroid C2 (1536MHz Cortex-A53), gcc-6.3.0
>> 0.180 0.224 0.108 0.208 0.100 Odroid N2 (1800MHz Cortex-A73), gcc-6.3.0
>>
>> All these cores are 2-wide. The Atom 330 is in-order, the E-450 is
>> OoO (both AMD64); the Cortex-A53 is in-order, the Cortex-A73 is OoO
>> (both ARM A64).
>>
>
> Fine results. Thank you. But at least the A53/A73 numbers don't prove your claim. The A73 cores are twice as big as the A53 cores, according to https://www.anandtech.com/show/10347/arm-cortex-a73-artemis-unveiled/3. So a 2x performance improvement indicates equal efficiency per unit area, not superior.
>

Also the thing I was getting at:
Assume a future which is transistor-budget limited.

Unless the OoO cores deliver superior performance relative to their
transistor budget, they have a problem in this case.

OoO has tended to be faster, but at the cost of a higher transistor budget.

>> Intel switched from in-order to OoO for it's little/efficiency cores
>> with Silvermont, Apple uses OoO cores for their efficiency cores as
>> well as their performance cores. Intel even switched from in-order to
>> OoO for the Xeon Phi, which targets HPC, the area where in-order is
>> strongest.
>>
>>> but for the same transistor budget at the same clock rate, st=
>>> atically scheduled should win because it more efficiently uses the availabl=
>>> e transistors to do useful work.
>> That's the fallacy that caused Intel and HP to waste billions on
>> IA-64, and Transmeta investors to invest $969M, most of which was
>> lost.
>
> Agreed that Transmeta and IA-64 failed. Disagree that two failures prove static scheduling's efficiency to be a fallacy.
>

Likewise.

Though, one can't ignore one big drawback of in-order designs:
They do not deal well with cache misses.

One can use prefetching to good effect, but this may require involvement
from the programmer, and C doesn't really have a "good" way to express a
prefetch operation.

Also, the prefetch has to be timed correctly as well, far enough back to
absorb the cache miss, but recent enough that the prefetched data
doesn't end up evicted in the time between the prefetch and the time the
data is used.

If one could potentially put another (watered down) sat of fetch/decode
stages just ahead of the current position, it could be possible to use
them as a prefetcher. Less clear is how to do this "effectively".

One option would be to partly duplicate and delay the execute stages, say:
IF ID1 (V_ID2 V_EX1 V_EX2 V_EX3) ID2 EX1 EX2 EX3 WB

With the V_* stages mostly serving as "what if" stages, their results
not being saved to the register file, but any loads/stores resulting in
an L1 prefetch (stores are not written, and the L1 does not stall on a
miss).

But, this would pay some in terms of resource budget, and would increase
branch latency.

Though, the alternative is figuring out how to make the compiler insert
prefetches without needing this sort of trickery. Granted, this is
assuming that (ideally) the L1 can perform prefetches without them
resulting in a pipeline stall (which would mostly defeat the point).

One could also possibly try to work around some things if the compiler
were able to figure out when and where cache misses will occur (vs
current compilers which have no real way of knowing this).

This doesn't mean that in-order is basically dead in the water, but one
can't expect it to be at a performance parity with an OoO core within
similar constraints (issue width, number of cores, ...).

But, rather, "Could the core one could fit in the same transistor budget
as an OoO core deliver better performance?".

Or, even if each core performs a little worse, but you can fit enough of
them into the same area that performance relative to area works out as a
net-win.

Thus far, it hasn't really come to this mostly because the transistor
budget has been steadily increasing, but will not necessarily hold true
once it stops.

It is like the issue of all the ridiculously inefficient coding
practices during the "MHz keeps getting bigger" era, and then single
threaded performance hits a wall, and suddenly people are finding that
writing efficient code matters again.

We have had around a decade without much improvement in single-thread
performance.

If one is in a world where it has been over a decade past the last "die
shrink", with no more "die shrinks" in the foreseeable future, they may
start thinking about things differently.

People will also have a lot more time to try to work out the "magic
compiler" issues, ...

>>
>>> Every time a program runs on an OoO machine, it wastes power to speculate a=
>>> bout un-taken paths that can be avoided when source code compiles to a stat=
>>> ically scheduled target instruction set.
>>
>> OoO is superior in both performance and in efficiency at competetive
>> performance for smartphones, desktops and servers, as evidenced by the
>> use of OoO cores as efficiency cores by Apple, Intel and AMD. The
>> only ones who still stick with in-order efficiency cores are ARM, but
>> their efficiency does not look great compared to their own efficient
>> OoO cores, and compared to Apple's efficiency cores.
>>
>> Concerning speculation, yes, it does waste power, but rarely, because
>> branch mispredictions are rare.
>>
>>> Once the speculation transistors are removed, a statically scheduled chip c=
>>> an replace them with additional FUs to get more done each clock cycle.
>> "Speculation transistors"? Ok, you can remove the branch predictor
>> and spend the transistors for an additional FU. The result for much
>> of the software will be that there will be done much less in each
>> cycle, because there are far fewer instructions ready for execution on
>> average without speculative execution, and therefore less work will be
>> done each cycle. If you also remove OoO execution, even fewer
>> instructions will be executed each cycle. So you have more FUs
>> available, but they will be idle.
>
> I've said statically scheduled needs VLIW which you've ignored by comparing equal issue width cores.
>
> Whether fewer instructions are executed per cycle is less important than the number of results produced by the FUs per cycle. VLIW lets more FUs be active per cycle. And VLIW doesn't necessarily see execution delays for NOP placeholders. OoO complexity goes up approximately O(n^2) with the number of FUs, right?
>
> I've agreed that dynamic branch prediction deserves a place in a statically scheduled architecture, so the correct instruction will be available just as soon as in an OoO. OoO execution unavoidably consumes power and chip area that static scheduling avoids.
>

Yeah.

I am also not thinking of "OoO core vs in-order core running same ISA",
but rather, OoO core vs a VLIW core at a similar transistor budget.

If the latter runs the same machine code as the former, it would likely
be via an emulation layer.

> But I'm repeating myself.
>
> Let's build a Mill and see what happens.
>
>> - anton
>> --
>> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
>> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:

[...]

> In any case, I expect no problems when moving virtual
> machines from one microarchitecture to another, as long as the second
> microarchitecture supports the same instruction set extensions as the
> first one.

I remember reading that ARM has a problem with SVE when moving
between microarchitectures with different lengths of execution
units, in effect restricting the vector length to the minimum,
128 bits.

Duh.

On 2/15/2022 12:43 PM, Anton Ertl wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>> Concerning speculation, yes, it does waste power, but rarely, because
>>> branch mispredictions are rare.
>>
>> Of course in-order cores also speculate, so this is only
>> tangentially related. But as a side-note I'll point out that statically
>> scheduled processors encourage the compiler to move long-latency
>> instructions such as loads to "as soon as it's safe to do it" rather
>> than "as soon as we know we will need it", and that sometimes
>> requires adding yet more "compensation code" in other branches.
>
> Loads are a bad example, because you typically don't move the above a
> branch they control-depend on, because loads can trap. Instead one
> tends to use prefetches. IA-64 had a mechanism that allowed moving
> loads up, however. Non-trapping instructions such as multiplications
> can be moved up speculatively by the compiler. And because compiler
> branch prediction (~10% miss rate) is much worse than dynamic branch
> prediction (~1% miss rate, both numbers vary strongly with the
> application, so take them with a grain of salt), a static scheduling
> speculating compiler will tend to waste more energy for the same
> degree of speculation.
>

Whether to rely on predicted branches, or on the compiler (such as in a
modulo loop), would ideally need some what for the compiler to know
which branches are predictable.

Similar goes for things like predicated instructions:
Branch is highly predictable, better to branch.
Branch is highly unpredictable, may be better to predicate.

In a traditional compiler, one has no knowledge of the run-time state.

One could potentially have a compiler which incorporates profile
information from profile runs of the program (sometimes done).

Another option could be if the compiler were integrated with an
emulator, and so could "dummy profile" a lot of the code it is running.
Though, this would also require a bit of cooperation from the programmer
to make this work (such as some way to get mock-up data to use to
emulate/benchmark various parts of the program).

Say for example, for code for encoding and decoding JPEGs, one would
need a "runs at build time" function which proceeds to load and decode a
bunch of JPEGs, then re-encodes them with various options, ... But, this
is not emitted in the final program (and serves mostly to give the
compiler some idea how the code is likely to behave at run-time).

On Tuesday, February 15, 2022 at 11:15:38 AM UTC-8, BGB wrote:

<snip>

> Also the thing I was getting at:
> Assume a future which is transistor-budget limited.
>
> Unless the OoO cores deliver superior performance relative to their
> transistor budget, they have a problem in this case.
>
> OoO has tended to be faster, but at the cost of a higher transistor budget.

<snip>

> This doesn't mean that in-order is basically dead in the water, but one
> can't expect it to be at a performance parity with an OoO core within
> similar constraints (issue width, number of cores, ...).
>
> But, rather, "Could the core one could fit in the same transistor budget
> as an OoO core deliver better performance?".
>
> Or, even if each core performs a little worse, but you can fit enough of
> them into the same area that performance relative to area works out as a
> net-win.
>
> Thus far, it hasn't really come to this mostly because the transistor
> budget has been steadily increasing, but will not necessarily hold true
> once it stops.
>
> It is like the issue of all the ridiculously inefficient coding
> practices during the "MHz keeps getting bigger" era, and then single
> threaded performance hits a wall, and suddenly people are finding that
> writing efficient code matters again.
>
> We have had around a decade without much improvement in single-thread
> performance.
>
>
> If one is in a world where it has been over a decade past the last "die
> shrink", with no more "die shrinks" in the foreseeable future, they may
> start thinking about things differently.
>
> People will also have a lot more time to try to work out the "magic
> compiler" issues, ...

> I am also not thinking of "OoO core vs in-order core running same ISA",
> but rather, OoO core vs a VLIW core at a similar transistor budget.
>
> If the latter runs the same machine code as the former, it would likely
> be via an emulation layer.

Right. If you've built as large a DBP window as gives significant BP improvement, and if your FU issue width per instruction is as wide as you can figure out how to make it do useful work, then if you still have idle FUs across too many of your target applications, it's time to prune back a little bit and use the freed silicon area for the next core.

For the actual OoO v. Statically Scheduled Super Bowl, we can argue about what architecture the emulated ISA should assume, too.

> > Let's build a Mill and see what happens.
> >
> >> - anton
> >> --
> >> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> >> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
> And because compiler
> branch prediction (~10% miss rate)

That seems optimistic.

>is much worse than dynamic branch
> prediction (~1% miss rate, both numbers vary strongly with the
> application, so take them with a grain of salt),

What is the branch miss rate on a binary search, or a sort?
Should be close to 50%, correct?

EricP <ThatWouldBeTelling@thevillage.com> schrieb:

> The gate voltage affects leakage but also delay,
> lower voltage lowers leakage but increases delay ,
> and gate delay interacts with stage delay, which interacts with frequency.
> If the frequency of the mem stage is faster than cache then it can wind up
> wasting a partial extra cycle to round the access up to a whole cycle,
> which waste power by leaking while sitting idle.
>
> There is probably some great whacking differential equation
> that tells up where the optimum of all the parameters lies.

Unfortunately, designing a CPU has both integer variables (number of
gates) and real variables (length of wires, diameters, transistor
sizes), and mixed optimization problems are generally much harder
than purely continuous ones.

Oh, and just mix in a few stochastic variables as well, for all
the tolerances :-)

Ivan Godard <ivan@millcomputing.com> schrieb:
> On 2/15/2022 1:46 AM, Anton Ertl wrote:
>> Ivan Godard <ivan@millcomputing.com> writes:
>>> The
>>> specializer does quite extensive optimization - bundle-packing,
>>> scheduling, CFG collapse, software pipelining, in- and out-lining, etc.
>>> - which is too expensive for a JIT, but the passes that do the
>>> optimizations are optionally bypassed.
>>
>> By contrast, an OoO microarchitecture does not care whether the native
>> code has been generated by a JIT compiler or not, it will
>> branch-predict and schedule the instructions all the same.
>
> So will a Mill.
>
> The specializer passes that a JIT would skip are target independent, and
> give better code for any target: OOO, IO, or sideways.

If it is target independent, why is it in the specializer?

On Tuesday, February 15, 2022 at 1:15:38 PM UTC-6, BGB wrote:
> On 2/15/2022 10:21 AM, Scott Smader wrote:
> > On Tuesday, February 15, 2022 at 3:47:39 AM UTC-8, Anton Ertl wrote:
> >> Scott Smader <yogam...@yahoo.com> writes:
> >>> On Monday, February 14, 2022 at 2:26:46 PM UTC-8, Anton Ertl wrote:
> >>>> Why? If OoO is superior now at the current transistor budget, why=20
> >>>> would it stop being superior if the transistor budget does not=20
> >>>> increase?
> >>>
> >>> Not sure if the assumption of OoO superiority is justified at current trans=
> >>> istor budget,
> >>
> >> Definitely. Here are two benchmarks, all numbers are times in
> >> seconds:
> >>
> >> LaTeX:
> >>
> >> - Intel Atom 330, 1.6GHz, 512K L2 Zotac ION A, Debian 9 64bit 2.368
> >> - AMD E-450 1650MHz (Lenovo Thinkpad X121e), Ubuntu 11.10 64-bit 1.216
> >> - Odroid N2 (1896MHz Cortex A53) Ubuntu 18.04 2.488
> >> - Odroid N2 (1800MHz Cortex A73) Ubuntu 18.04 1.224
> >>
> >> Gforth:
> >>
> >> sieve bubble matrix fib fft
> >> 0.492 0.556 0.424 0.700 0.396 Intel Atom 330 (Bonnell) 1.6GHz; gcc-4.9
> >> 0.321 0.479 0.219 0.594 0.229 AMD E-350 1.6GHz; gcc version 4.7.1
> >> 0.350 0.390 0.240 0.470 0.280 Odroid C2 (1536MHz Cortex-A53), gcc-6.3.0
> >> 0.180 0.224 0.108 0.208 0.100 Odroid N2 (1800MHz Cortex-A73), gcc-6.3.0
> >>
> >> All these cores are 2-wide. The Atom 330 is in-order, the E-450 is
> >> OoO (both AMD64); the Cortex-A53 is in-order, the Cortex-A73 is OoO
> >> (both ARM A64).
> >>
> >
> > Fine results. Thank you. But at least the A53/A73 numbers don't prove your claim. The A73 cores are twice as big as the A53 cores, according to https://www.anandtech.com/show/10347/arm-cortex-a73-artemis-unveiled/3. So a 2x performance improvement indicates equal efficiency per unit area, not superior.
> >
> Also the thing I was getting at:
> Assume a future which is transistor-budget limited.
>
> Unless the OoO cores deliver superior performance relative to their
> transistor budget, they have a problem in this case.
>
> OoO has tended to be faster, but at the cost of a higher transistor budget.
<
Late in my AMD career, I did a study design of a 1-wide in order x86-64
to see how much the OoO-ness was costing.
<
We discussed this back when Nick McLaren was still posting.
<
The bottom line is that the GBOoO design is 12× bigger than the 1-wide
I-O design (including L1 cache and predictors but excluding L2 cache).
The GBOoO core ran 2× faster than LBIO core from the same L2 outwards.
The LBIO cores also operated at 1/12 the power--logic power scales with
area, [SD]RAM and pin power scales with utilization.
<
Until SW figures out how to utilize "craploads" of cores, the market will
continue to demand GBOoO--------it really is that simple.
<
> >> Intel switched from in-order to OoO for it's little/efficiency cores
> >> with Silvermont, Apple uses OoO cores for their efficiency cores as
> >> well as their performance cores. Intel even switched from in-order to
> >> OoO for the Xeon Phi, which targets HPC, the area where in-order is
> >> strongest.
> >>
> >>> but for the same transistor budget at the same clock rate, st=
> >>> atically scheduled should win because it more efficiently uses the availabl=
> >>> e transistors to do useful work.
> >> That's the fallacy that caused Intel and HP to waste billions on
> >> IA-64, and Transmeta investors to invest $969M, most of which was
> >> lost.
> >
> > Agreed that Transmeta and IA-64 failed. Disagree that two failures prove static scheduling's efficiency to be a fallacy.
> >
> Likewise.
>
> Though, one can't ignore one big drawback of in-order designs:
> They do not deal well with cache misses.
<
But cores are enough smaller, that for equal die size, you can double the biggest cache.
>
> One can use prefetching to good effect, but this may require involvement
> from the programmer, and C doesn't really have a "good" way to express a
> prefetch operation.
<
Still have not seen a prefetcher that performs well on linked list codes........
>
> Also, the prefetch has to be timed correctly as well, far enough back to
> absorb the cache miss, but recent enough that the prefetched data
> doesn't end up evicted in the time between the prefetch and the time the
> data is used.
>
>
> If one could potentially put another (watered down) sat of fetch/decode
> stages just ahead of the current position, it could be possible to use
> them as a prefetcher. Less clear is how to do this "effectively".
>
> One option would be to partly duplicate and delay the execute stages, say:
> IF ID1 (V_ID2 V_EX1 V_EX2 V_EX3) ID2 EX1 EX2 EX3 WB
>
> With the V_* stages mostly serving as "what if" stages, their results
> not being saved to the register file, but any loads/stores resulting in
> an L1 prefetch (stores are not written, and the L1 does not stall on a
> miss).
>
>
> But, this would pay some in terms of resource budget, and would increase
> branch latency.
>
> Though, the alternative is figuring out how to make the compiler insert
> prefetches without needing this sort of trickery. Granted, this is
> assuming that (ideally) the L1 can perform prefetches without them
> resulting in a pipeline stall (which would mostly defeat the point).
>
> One could also possibly try to work around some things if the compiler
> were able to figure out when and where cache misses will occur (vs
> current compilers which have no real way of knowing this).
>
>
>
> This doesn't mean that in-order is basically dead in the water, but one
> can't expect it to be at a performance parity with an OoO core within
> similar constraints (issue width, number of cores, ...).
<
BTW the intent of my study was to make an x86-64 so small that we could
put a core on each HT far end and handle MMIO accesses in a few nanoseconds
rather than hundreds of nanoseconds. Such an x86-64 would be vanilla verilog
compiled logic--but it would run the same binary as the OS. Interrupts were
handled topologically adjacent to the device. Like a channel but using the same ISA.
>
> But, rather, "Could the core one could fit in the same transistor budget
> as an OoO core deliver better performance?".
>
> Or, even if each core performs a little worse, but you can fit enough of
> them into the same area that performance relative to area works out as a
> net-win.
<
12× is the number you want. 2.6× is the number SW can use.
>
> Thus far, it hasn't really come to this mostly because the transistor
> budget has been steadily increasing, but will not necessarily hold true
> once it stops.
>
It gets hard, at a fundamental level, once gate oxide becomes 1 atom.
>
> It is like the issue of all the ridiculously inefficient coding
> practices during the "MHz keeps getting bigger" era, and then single
> threaded performance hits a wall, and suddenly people are finding that
> writing efficient code matters again.
>
> We have had around a decade without much improvement in single-thread
> performance.
>
IPC-wise : yes, frequency wise we are growing at 1/3rd what we were growing
in the 19890s.
>
> If one is in a world where it has been over a decade past the last "die
> shrink", with no more "die shrinks" in the foreseeable future, they may
> start thinking about things differently.
>
> People will also have a lot more time to try to work out the "magic
> compiler" issues, ...
> >>
> >>> Every time a program runs on an OoO machine, it wastes power to speculate a=
> >>> bout un-taken paths that can be avoided when source code compiles to a stat=
> >>> ically scheduled target instruction set.
> >>
> >> OoO is superior in both performance and in efficiency at competetive
> >> performance for smartphones, desktops and servers, as evidenced by the
> >> use of OoO cores as efficiency cores by Apple, Intel and AMD. The
> >> only ones who still stick with in-order efficiency cores are ARM, but
> >> their efficiency does not look great compared to their own efficient
> >> OoO cores, and compared to Apple's efficiency cores.
> >>
> >> Concerning speculation, yes, it does waste power, but rarely, because
> >> branch mispredictions are rare.
> >>
> >>> Once the speculation transistors are removed, a statically scheduled chip c=
> >>> an replace them with additional FUs to get more done each clock cycle..
> >> "Speculation transistors"? Ok, you can remove the branch predictor
> >> and spend the transistors for an additional FU. The result for much
> >> of the software will be that there will be done much less in each
> >> cycle, because there are far fewer instructions ready for execution on
> >> average without speculative execution, and therefore less work will be
> >> done each cycle. If you also remove OoO execution, even fewer
> >> instructions will be executed each cycle. So you have more FUs
> >> available, but they will be idle.
> >
> > I've said statically scheduled needs VLIW which you've ignored by comparing equal issue width cores.
> >
> > Whether fewer instructions are executed per cycle is less important than the number of results produced by the FUs per cycle. VLIW lets more FUs be active per cycle. And VLIW doesn't necessarily see execution delays for NOP placeholders. OoO complexity goes up approximately O(n^2) with the number of FUs, right?
> >
> > I've agreed that dynamic branch prediction deserves a place in a statically scheduled architecture, so the correct instruction will be available just as soon as in an OoO. OoO execution unavoidably consumes power and chip area that static scheduling avoids.
> >
> Yeah.
>
> I am also not thinking of "OoO core vs in-order core running same ISA",
> but rather, OoO core vs a VLIW core at a similar transistor budget.
>
> If the latter runs the same machine code as the former, it would likely
> be via an emulation layer.
> > But I'm repeating myself.
> >
> > Let's build a Mill and see what happens.
> >
> >> - anton
> >> --
> >> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> >> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On 2/15/2022 12:49 PM, Thomas Koenig wrote:
> Ivan Godard <ivan@millcomputing.com> schrieb:
>> On 2/15/2022 1:46 AM, Anton Ertl wrote:
>>> Ivan Godard <ivan@millcomputing.com> writes:
>>>> The
>>>> specializer does quite extensive optimization - bundle-packing,
>>>> scheduling, CFG collapse, software pipelining, in- and out-lining, etc.
>>>> - which is too expensive for a JIT, but the passes that do the
>>>> optimizations are optionally bypassed.
>>>
>>> By contrast, an OoO microarchitecture does not care whether the native
>>> code has been generated by a JIT compiler or not, it will
>>> branch-predict and schedule the instructions all the same.
>>
>> So will a Mill.
>>
>> The specializer passes that a JIT would skip are target independent, and
>> give better code for any target: OOO, IO, or sideways.
>
> If it is target independent, why is it in the specializer?

The specializer is the back-end of the compiler, and does back-end stuff
in addition to member-targeting stuff. The functionality could be split,
but that would require a communication format across the split.

Actually there are three kinds of work done: family independent (done in
both Mill and x86, like inlining); member independent (done in all Mill
members but not other ISAs, like ganging op/compare instructions, or
injecting pseudo-ops for load retires), and member dependent (done
uniquely for each member, like bit stuffing into the binary).

On 2/15/2022 5:28 AM, Thomas Koenig wrote:
> MitchAlsup <MitchAlsup@aol.com> schrieb:
>
>> L1s are stable because if the get bigger than 64 KB they take more than
>> one cycle to "access", where SRAM and wire routing are both considered.
>
> One cycle latency or throughput?

Probably latency.

It could be argued, I have an FPGA, it wouldn't be hard to throw 64K
L1's at the problem and then skip an L2.

However, timing doesn't really like big L1s...

For the L2, one may need to do things like:
tBlkDataA1 <= tBlkArrDataA[tReqIdx];
tBlkAddrA1 <= tBlkArrAddrA[tReqIdx];
tBlkDataB1 <= tBlkArrDataB[tReqIdx];
tBlkAddrB1 <= tBlkArrAddrB[tReqIdx];
//forward to next cycle
tBlkDataA <= tBlkDataA1;
tBlkAddrA <= tBlkDataA1;
tBlkDataB <= tBlkDataB1;
tBlkAddrB <= tBlkDataB1;
//the above represent what we check.

This would not be so ideal for L1.

For L2, I can have an ~ 4 cycle latency between the request arriving on
the ring-bus, and the time the request exits the L2 via the ring-bus (we
need to act on whether or not it was a hit or miss before it leaves).
The latency could be made longer if needed.

Multiple requests can arrive and be handled one-after-another if there
is no miss (with any missed L2 requests needing to circle around the bus
until they can be handled).

For L1, I have EX1/EX2/EX3. It gets the address in EX1, needs to do its
work in EX2, and have a result by EX3. One can't really stick an extra
clock cycle in there.

For L1's, I can get away with 16K or 32K at 50MHz. These fit OK in
BRAMs, and pass timing. They also have upwards of a 95% hit rate.

More so, much past 16K or 32K, the L1 hit-rate seems to mostly hit a
plateau (hits ~ 95 or 96% and then seemingly stops improving).
Increasing associativity helps slightly here, but only by ~ 1.5%.

Seems to work out better in this case to throw any additional memory at
the L2, which sees more benefit from the larger size (also L2 seems to
benefit more from associative caching when using the ringbus design,
hence the 2-way L2).

The L2 can offer around a 70% or so chance of hitting, which is a lot
better than needing to go to DRAM.

However, timing is a lot harder at 100MHz, so one may need to drop the
L1's to 2K or similar (allowing the use of LUTRAM).

However, if one has an L1 that only hits around 60% of the time or
similar, performance is not happy. Similarly, associative caching does
not fix this issue, so a 2K L1 cache still sucks.

It may work out faster overall to run at half the clock speed, but with
a better L1 cache, and also a wider execute pipeline (3-wide vs 1-wide),
even if the code is mostly limited to ~ 1.5 lanes or so on-average
(average case ILP being relatively weak).

The actual LUT cost difference between a 1-wide and 3-wide core is
smaller than one might expect, mostly because non-duplicated features
(L1 caches, FPU, TLB, ...) tend to eat up the majority of the budget
(the extra decoders, ALUs, ... don't effect cost all that much).

There is a cost due to the larger number of ports in the register file,
but this cost is shared by the ability to use it for sake of things like
SIMD operations and 128-bit Load/Store, ... which might not be possible
otherwise.

However, 3 wide seems to be the local optima. Going much wider than 3,
and "the crap hits the fan"...

So, partly in effect, it is 3-wide for 64-bit operations, but 1-wide for
128-bit operations.

The extra width is also being used for things like being able to load a
64-bit immediate within a single clock cycle, ... (Internally, the
immediate is spread across multiple lanes and then glued together when
the value is fetched, with the immediate fields in the pipeline not
actually being wide enough to pass the value directly).

Similar sort of issue for what I am still (mostly) stuck at a
double-precision FPU (64 to 96 bits is a bigger cost jump than it may
seem on the surface). Can enable it experimentally, but then usually end
up disabling it again due to having to keep fight with timing and
similar about it. And, at present, it doesn't offer much advantage over
software-emulated Binary128, which can be helped out some by the
(relatively cheaper) 128-bit ALUX instructions.

....

One could almost make a strong case for doing a 32-bit machine and being
able to run it at twice the clock-speed, but then one still has the L1
cache size issue. Code written to make effective use of a 64-bit machine
also benefits more from the 64b nature, than optimizing for (or being
limited to) a 32-bit machine.

I have also noted that "better numbers in Dhystone but worse at pretty
much everything else" isn't really a win...

Despite it also seeming like Doom would prefer a high-clocked 32-bit
machine, Doom's performance tends to be more effected by the performance
of the memory subsystem. On a 50MHz core with a 100% L2 hit rate, it
would also run pegged at the 32 fps frame-rate limiter.

Doom also remains surprisingly playable at 16 or 25 MHz, if one assumes
that DRAM access remains fast.

But, one other thing Doom does also notice with a fairly obvious effect,
is a high L1 miss rate (this having a bigger impact on performance than
the actual clock speed).

....

jgd@cix.co.uk (John Dallman) writes:
>Itanium had fixed-size bundles that sometimes needed to be padded with
>no-ops, and stop bits for indicating inter-bundle dependencies.

On IA-64 bundles are encoding. Groups (separated by stop bits)
comprise a set of instructions that can be executed in parallel as far
as register dependencies are concerned; you can have memory
dependencies within a group, and I don't know how the hardware handles
that.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 2/15/2022 8:59 AM, John Dallman wrote:
>> Itanium was not a VLIW, it was an EPIC architecture; granted, both
>> were wide issue, which is commonly confused with VLIW.
>>
>> The Mill is not a VLIW (or EPIC) either, although it is closer than
>> the Itanium.
>
> Can you enlarge on the differences? The basic concept of presenting
> several instructions to the processor at once, with the compiler ensuring
> that there are no data hazards between those instructions, seems to be
> much the same.
>
> Itanium had fixed-size bundles that sometimes needed to be padded with
> no-ops, and stop bits for indicating inter-bundle dependencies. I know
> Mill has variable-size bundles. What else is different in this aspect?
>
>> You probably have a VLIW in your pocket: Qualcomm Hexagon.
>
> On the table, but yes. Not that I use it very hard.
>
> John

These differ in which hazards are shifted from the hardware to the
compiler when dealing with a wide bundle.

EPIC hardware assumed that there are no intra-bundle hazards, so the
issue queue and its associated hazard check can be omitted. However,
there were no such guarantees for inter-bundle hazards, so either the
entire bundle had to run to completion, or, in later Itaniums, the
hardware did OOO-like retire hazard checking to deal with varying
instruction latency.

A classic VLIW assumes that there are neither issue nor retire hazards
in the schedule, and hence the latency of everything is statically
known. Neither issue nor retire hardware checking is needed. These days
the fixed latency requirement restricts VLIWs to applications which do
not present variable instruction latencies: DSPs, mini-engines like
crypto blocks, and the like. Usually there is no latency variability
physically possible, but if the core is connected to external devices
with unpredictable latency (such as DRAM) the hardware stalls if
external data is not available.

Mill is VLIW-like for all instructions but loads: everything has static
fixed latency, and neither issue nor retire hazards need hardware hazard
checking or scheduling queues. Like a VLIW, it does not check for or
take advantage of early-out such as multiply-by-one. For loads, which
are the only source of significant latency variability, Mill splits the
issue and retire into two different instructions which are independently
static scheduled (patented). A load-retire instruction stalls the core
if it has no data yet.

The distinction among these categories is not a matter of encoding - all
are wide issue, and each has its own scheme. The Itanium used fixed size
bundles; classic VLIW uses variable-size bundles; and Mill uses a
bundle-of-six-bundles encoding. However, any of the categories could use
any of the encoding schemes. It's a matter of what is done by the
compiler vs. hardware, not a matter of the bitsy representation.

This makes the Mill suitable for general-purpose work that would cause a
classic VLIW to spend too much time in stall, yet still take advantage
of any schedule variability to do other work while (possibly) waiting
for external data, and without needing OOO retire hazard hardware.

The gain from Mill's split load is limited by the maximal gap (in time)
between the load-issue and load-retire instructions, which is in turn
determined by how much work is available to do that neither depends on
the load result nor is depended on by the load issue. That's easily
determined by conventional dataflow analysis in the compiler, and is
exactly the same as the amount of work that an OOO can do while waiting
for a load to retire.

Ivan Godard <ivan@millcomputing.com> schrieb:
> On 2/15/2022 12:49 PM, Thomas Koenig wrote:
>> Ivan Godard <ivan@millcomputing.com> schrieb:
>>> On 2/15/2022 1:46 AM, Anton Ertl wrote:
>>>> Ivan Godard <ivan@millcomputing.com> writes:
>>>>> The
>>>>> specializer does quite extensive optimization - bundle-packing,
>>>>> scheduling, CFG collapse, software pipelining, in- and out-lining, etc.
>>>>> - which is too expensive for a JIT, but the passes that do the
>>>>> optimizations are optionally bypassed.
>>>>
>>>> By contrast, an OoO microarchitecture does not care whether the native
>>>> code has been generated by a JIT compiler or not, it will
>>>> branch-predict and schedule the instructions all the same.
>>>
>>> So will a Mill.
>>>
>>> The specializer passes that a JIT would skip are target independent, and
>>> give better code for any target: OOO, IO, or sideways.
>>
>> If it is target independent, why is it in the specializer?
>
> The specializer is the back-end of the compiler, and does back-end stuff
> in addition to member-targeting stuff. The functionality could be split,
> but that would require a communication format across the split.

That really depends on how you defined your model-independent
language, GenAsm. I would have expected this to be defined
in such a way that the specializer really only had to do the
target-dependent stuff, so most of the heavy lifting is done in
the normal compilation step.

You must have had your reasons, I just don't understand them.

>
> Actually there are three kinds of work done: family independent (done in
> both Mill and x86, like inlining);

In the specializer? That sounds a lot of what a compiler middle end
should do (maybe guided by some information abut the back end,
like number of registers - a thorny issue).

>member independent (done in all Mill
> members but not other ISAs,

That sounds like the task of a more or less traditional back
end to me (like the nvptx "back end", which also generates
intermediate code.

>like ganging op/compare instructions, or
> injecting pseudo-ops for load retires), and member dependent (done
> uniquely for each member, like bit stuffing into the binary).

This is the part that I would probably like to keep as small
as possible, if it were my project, which it isn't :-)

On 2/15/2022 10:58 AM, Stefan Monnier wrote:
>> Thank you. That makes perfect sense. BTW, does that present an opportunity
>> for some sort of profile driven optimization where the run time branch
>> history is fed back to a future compilation for better optimization?
>> Probably not as useful for an OoO machine.
>
> Profile-driven optimization is used, of course, but the problem remains:
> the compiler needs to generate code that works for all possible
> situations and it can't freely duplicate code all over the place.
> A bit of code duplication (to specialize a code path to a few different
> scenarios) can be done, but only within fairly strict limits otherwise
> code size will explode and performance goes down the drain again.
>

But, with a profiler, you can know *where* it likely matters, so it
could be done without exploding the code-size. The compiler would
realize a rarely-used path is rarely used, and this not bother unrolling
or modulo-scheduling it's loops, ...

Partial issue is pulling off profile driven optimization in a way that
is not sufficiently annoying that the programmers don't bother with it.

Most ideas I can imagine ATM would likely require running an emulator
inside the compiler with some amount of programmer-supplied test data.

Say:
[[auto_profile_hint]] void SomeBenchmarkFunction()
{ ... run some simulated benchmarks ...
}

Compiler sees the attribute, and tries running the function in an
emulator to see what it does and where its "hot-spots" are located.

> In contrast, an OoO is free to use a different schedule each time
> a chunk of code is run (and similarly the branch predictor is free to
> provide wildly different predictions each time that chunk of code is
> run) without any downside.
>
> The OoO works on the trace of the actual execution, where the main limit
> is the size of the window it can consider (linked to the accuracy of the
> branch predictor), whereas the compiler is not limited to such a window
> but instead it's limited to work on the non-unrolled code.
>

While this is true, I suspect it is a case of "best" vs "good enough".
If one can get the in-order scheduling to a "good enough" stage, it may
be possible to work around this deficiency by being able to throw
(slightly) more cores at the problem.

Though, I will note that I am assuming that core counts remain within
the limits of plausible memory bandwidth, but consider this to be a weak
argument because, if additional cores would be limited by bandwidth, a
single faster core would also be limited by bandwidth.

One is more limited by how effectively one can parallelize the codebase,
but if one is assuming an extended timeframe where no other
hardware-level performance improvements are viable, programmers will
"make it work" (IOW: if one assumes that the only other option is
multiple decades of stagnation).

Also I can note that some people have done things like sticking a whole
bunch of RV32I cores or similar onto an FPGA. I don't exactly consider
this sort of thing to be a viable approach either, this is not really
what I am talking about here...

On 2/15/2022 10:43 AM, Anton Ertl wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>> Concerning speculation, yes, it does waste power, but rarely, because
>>> branch mispredictions are rare.
>>
>> Of course in-order cores also speculate, so this is only
>> tangentially related. But as a side-note I'll point out that statically
>> scheduled processors encourage the compiler to move long-latency
>> instructions such as loads to "as soon as it's safe to do it" rather
>> than "as soon as we know we will need it", and that sometimes
>> requires adding yet more "compensation code" in other branches.
>
> Loads are a bad example, because you typically don't move the above a
> branch they control-depend on, because loads can trap. Instead one
> tends to use prefetches. IA-64 had a mechanism that allowed moving
> loads up, however. Non-trapping instructions such as multiplications
> can be moved up speculatively by the compiler. And because compiler
> branch prediction (~10% miss rate) is much worse than dynamic branch
> prediction (~1% miss rate, both numbers vary strongly with the
> application, so take them with a grain of salt), a static scheduling
> speculating compiler will tend to waste more energy for the same
> degree of speculation.

Not in modern processes, or so I'm told by the hardware guys. Leakage is
of the same order of cost as execution these days, so an idle ALU might
as well do something potentially useful. Consequently it is worth while
for the compiler to if-convert everything until it runs out of FUs.

Incidentally, in-order != static-prediction. No in-order core much above
a Z80 will use static branch prediction, for the reason you give. Well,
no competent core, anyway.

On 2/15/2022 11:15 AM, BGB wrote:
> On 2/15/2022 10:21 AM, Scott Smader wrote:
>> On Tuesday, February 15, 2022 at 3:47:39 AM UTC-8, Anton Ertl wrote:
>>> Scott Smader <yogam...@yahoo.com> writes:
>>>> On Monday, February 14, 2022 at 2:26:46 PM UTC-8, Anton Ertl wrote:
>>>>> Why? If OoO is superior now at the current transistor budget, why=20
>>>>> would it stop being superior if the transistor budget does not=20
>>>>> increase?
>>>>
>>>> Not sure if the assumption of OoO superiority is justified at
>>>> current trans=
>>>> istor budget,
>>>
>>> Definitely. Here are two benchmarks, all numbers are times in
>>> seconds:
>>>
>>> LaTeX:
>>>
>>> - Intel Atom 330, 1.6GHz, 512K L2 Zotac ION A, Debian 9 64bit 2.368
>>> - AMD E-450 1650MHz (Lenovo Thinkpad X121e), Ubuntu 11.10 64-bit 1.216
>>> - Odroid N2 (1896MHz Cortex A53) Ubuntu 18.04 2.488
>>> - Odroid N2 (1800MHz Cortex A73) Ubuntu 18.04 1.224
>>>
>>> Gforth:
>>>
>>> sieve bubble matrix fib fft
>>> 0.492 0.556 0.424 0.700 0.396 Intel Atom 330 (Bonnell) 1.6GHz; gcc-4.9
>>> 0.321 0.479 0.219 0.594 0.229 AMD E-350 1.6GHz; gcc version 4.7.1
>>> 0.350 0.390 0.240 0.470 0.280 Odroid C2 (1536MHz Cortex-A53), gcc-6.3.0
>>> 0.180 0.224 0.108 0.208 0.100 Odroid N2 (1800MHz Cortex-A73), gcc-6.3.0
>>>
>>> All these cores are 2-wide. The Atom 330 is in-order, the E-450 is
>>> OoO (both AMD64); the Cortex-A53 is in-order, the Cortex-A73 is OoO
>>> (both ARM A64).
>>>
>>
>> Fine results. Thank you. But at least the A53/A73 numbers don't prove
>> your claim. The A73 cores are twice as big as the A53 cores, according
>> to
>> https://www.anandtech.com/show/10347/arm-cortex-a73-artemis-unveiled/3. So
>> a 2x performance improvement indicates equal efficiency per unit area,
>> not superior.
>>
>
> Also the thing I was getting at:
>   Assume a future which is transistor-budget limited.
>
> Unless the OoO cores deliver superior performance relative to their
> transistor budget, they have a problem in this case.
>
> OoO has tended to be faster, but at the cost of a higher transistor budget.
>
>
>>> Intel switched from in-order to OoO for it's little/efficiency cores
>>> with Silvermont, Apple uses OoO cores for their efficiency cores as
>>> well as their performance cores. Intel even switched from in-order to
>>> OoO for the Xeon Phi, which targets HPC, the area where in-order is
>>> strongest.
>>>
>>>> but for the same transistor budget at the same clock rate, st=
>>>> atically scheduled should win because it more efficiently uses the
>>>> availabl=
>>>> e transistors to do useful work.
>>> That's the fallacy that caused Intel and HP to waste billions on
>>> IA-64, and Transmeta investors to invest $969M, most of which was
>>> lost.
>>
>> Agreed that Transmeta and IA-64 failed. Disagree that two failures
>> prove static scheduling's efficiency to be a fallacy.
>>
>
> Likewise.
>
> Though, one can't ignore one big drawback of in-order designs:
>   They do not deal well with cache misses.
>
> One can use prefetching to good effect, but this may require involvement
> from the programmer, and C doesn't really have a "good" way to express a
> prefetch operation.
>
> Also, the prefetch has to be timed correctly as well, far enough back to
> absorb the cache miss, but recent enough that the prefetched data
> doesn't end up evicted in the time between the prefetch and the time the
> data is used.
>
>
> If one could potentially put another (watered down) sat of fetch/decode
> stages just ahead of the current position, it could be possible to use
> them as a prefetcher. Less clear is how to do this "effectively".
>
> One option would be to partly duplicate and delay the execute stages, say:
>   IF ID1 (V_ID2 V_EX1 V_EX2 V_EX3) ID2 EX1 EX2 EX3 WB
>
> With the V_* stages mostly serving as "what if" stages, their results
> not being saved to the register file, but any loads/stores resulting in
> an L1 prefetch (stores are not written, and the L1 does not stall on a
> miss).
>
>
> But, this would pay some in terms of resource budget, and would increase
> branch latency.
>
> Though, the alternative is figuring out how to make the compiler insert
> prefetches without needing this sort of trickery. Granted, this is
> assuming that (ideally) the L1 can perform prefetches without them
> resulting in a pipeline stall (which would mostly defeat the point).
>
> One could also possibly try to work around some things if the compiler
> were able to figure out when and where cache misses will occur (vs
> current compilers which have no real way of knowing this).

Congratulations: you have invented the Mill load instruction, which is
really a "prefetch this if it doesn't get in trouble" instruction.

On 2/15/2022 8:58 AM, Stefan Monnier wrote:
>> Thank you. That makes perfect sense. BTW, does that present an opportunity
>> for some sort of profile driven optimization where the run time branch
>> history is fed back to a future compilation for better optimization?
>> Probably not as useful for an OoO machine.
>
> Profile-driven optimization is used, of course, but the problem remains:
> the compiler needs to generate code that works for all possible
> situations and it can't freely duplicate code all over the place.
> A bit of code duplication (to specialize a code path to a few different
> scenarios) can be done, but only within fairly strict limits otherwise
> code size will explode and performance goes down the drain again.
>
> In contrast, an OoO is free to use a different schedule each time
> a chunk of code is run (and similarly the branch predictor is free to
> provide wildly different predictions each time that chunk of code is
> run) without any downside.
>
> The OoO works on the trace of the actual execution, where the main limit
> is the size of the window it can consider (linked to the accuracy of the
> branch predictor), whereas the compiler is not limited to such a window
> but instead it's limited to work on the non-unrolled code.

Actually the limit to useful window size in GP code is dataflow
dependencies. All the fancy numbers bandied about for big windows are
for embarrassingly parallel apps - walk a huge array doing the same
thing for every element for example. Those (typically HPC) are
important, but engender a supercomputer bias in design.

GP code - the classic payroll app, or the great bulk of real work once
the embarrassingly parallel code has been moved off to special purpose
engines - hits a dataflow dependence within a few tends of instructions.
The rest of the window can be filled with instructions awaiting issue
resolution - but you might as well have left them in the icache.

"The dirty little secret about OOO is how little OOO there really is."
- Andy Glue