which type of core requires high frequency of operation ,in-order or out-of-order?Is it good to have in-order and out-of-order core to share the same cache level(L2 or L3)?

On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
> which type of core requires high frequency of operation ,in-order or out-of-order?Is it good to have in-order and out-of-order core to share the same cache level(L2 or L3)?
<
Neither has an inherent frequency advantage or an "effective" length of pipeline advantage.
<
Pure In Order is immune to Spectré-like attacks.
<
Out of Order can be made immune to Spectré-like attacks.
<
Out of Order enables (not requires) more instructions "in flight" and can better utilize sparse resources thereby finding Instruction Level Parallelism.

On Tuesday, June 15, 2021 at 9:53:37 PM UTC+5:30, MitchAlsup wrote:
> On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
> > which type of core requires high frequency of operation ,in-order or out-of-order?Is it good to have in-order and out-of-order core to share the same cache level(L2 or L3)?
> <
> Neither has an inherent frequency advantage or an "effective" length of pipeline advantage.
> <
> Pure In Order is immune to Spectré-like attacks.
> <
> Out of Order can be made immune to Spectré-like attacks.
> <
> Out of Order enables (not requires) more instructions "in flight" and can better utilize sparse resources thereby finding Instruction Level Parallelism.
Are there any issues when in-order and out-of-order cores share same last level cache?like improper cache partitioning between cores etc.

On Tuesday, June 15, 2021 at 11:43:43 AM UTC-5, Chingu wrote:
> On Tuesday, June 15, 2021 at 9:53:37 PM UTC+5:30, MitchAlsup wrote:
> > On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
> > > which type of core requires high frequency of operation ,in-order or out-of-order?Is it good to have in-order and out-of-order core to share the same cache level(L2 or L3)?
> > <
> > Neither has an inherent frequency advantage or an "effective" length of pipeline advantage.
> > <
> > Pure In Order is immune to Spectré-like attacks.
> > <
> > Out of Order can be made immune to Spectré-like attacks.
> > <
> > Out of Order enables (not requires) more instructions "in flight" and can better utilize sparse resources thereby finding Instruction Level Parallelism.
> Are there any issues when in-order and out-of-order cores share same last level cache?like improper cache partitioning between cores etc.
<
Not if the cache coherence protocol is correct.

On 6/15/2021 11:23 AM, MitchAlsup wrote:
> On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
>> which type of core requires high frequency of operation ,in-order or out-of-order?Is it good to have in-order and out-of-order core to share the same cache level(L2 or L3)?
> <
> Neither has an inherent frequency advantage or an "effective" length of pipeline advantage.
> <
> Pure In Order is immune to Spectré-like attacks.
> <
> Out of Order can be made immune to Spectré-like attacks.
> <
> Out of Order enables (not requires) more instructions "in flight" and can better utilize sparse resources thereby finding Instruction Level Parallelism.
>

Yeah.

Some typical OoO features:
* Able to reorganize instructions around cache misses;
* Able to shuffle instructions around to increase effective ILP;
* ...

For an in-order, any shuffling needs to be done by the compiler, which
may in turn need to account for things like instruction latency, ...

Premise goes, for OoO one can avoid this (though, IME, one can still see
some benefit from reorganizing instructions to minimize dependencies).

For in-order, one can potentially divide things further:
* Scalar / Single-Issue: Only one instruction at a time.
* Multi-Issue: More than one instruction at a time.
** Superscalar: The CPU figures out what it can execute in parallel.
** VLIW: The encoding makes it explicit what it can execute in parallel.

Scalar:
* Non-pipelined:
** Every instruction takes multiple clock cycles;
** Basically, all stages complete for every instruction;
** The processor does not move on until an instruction completes.
* Pipelined: May approach 1 instruction per clock.
** The instructions overlap in terms of execution;
** After each stage, the instruction moves to the next stage;
** Each unit does one piece of work, and immediately moves to the next.

Pretty much everything of note is pipelined, excluding some very old or
very small processors (almost all are "8-bit" architectures), with a few
edge cases for people trying to do RV32E cores while also minimizing LUT
cost and similar.

In theory a pipelined CPU could run at a solid 1.0 IPC, however a few
factors may limit this:
* Things like memory may stall on a cache miss, forcing the CPU to wait;
* Some instructions may trigger an "interlock"
** One instruction may need the result of a prior instruction;
** However, the result isn't ready yet at the time it is requested;
** So, one part of the pipeline stalls while the rest continues;
** This allows the depended-on instruction to complete first;
** During this time, the pipeline may execute "Bubbles" / NOPs.

If one did not have an interlock mechanism in a processor, it would be
necessary for the compiler to insert NOPs anywhere where an unavoidable
dependency may occur. This is undesirable.

Things like pipeline length can also be a tradeoff (longer pipeline
makes it easier to go faster, but also increases potential for hazards
and increases the relative cost of unpredictable branch instructions).

Many examples present things in terms of a 5-stage pipeline, but
admittedly I am running an 8-stage pipeline and am still only typically
running at 50 MHz on an Artix-7 FPGA.

For a Multi-Issue CPU, things get a little wider:
* Instruction Fetch: Returns enough data for the maximum number of
instructions;
* Decode: Runs multiple decoders in parallel;
* Register file: has enough read and write ports for all the
instructions which may execute;
....
* Execute: One has multiple lanes, each with their own ALU, ...;
* ...

For a superscalar, one needs to figure out whether or not the fetched
and decoded instructions can be executed in parallel. The difficulty,
however, is that one doesn't really have the context to know this until
after Instruction Decode has finished, which means one has to get funky
with the decode-and-fecth logic.

For example, the fetch may move initially as if only a
single-instruction had executed, and the decoder may keep track of when
superscalar execution had happened (shifting everything over). This may
end up being added to PC after the fact.

The result of this is, say, for a maximum of 3 instructions, a
superscalar core using this approach may need to fetch enough data for 6
instructions, and then decode with an offset of 0-3 instructions for
every cycle.

Similarly, the decoded instructions may need to provide additional metadata:
Which lanes they are allowed to execute in;
Whether they depend on or modify status flags or other resources;
...

This metadata, along with checking register IDs, etc, would need to be
factored in towards the "can we do this as superscalar" decision.

Another option is VLIW, which can be further subdivided:
* Using a larger fixed-size bundle which is then subdivided into
multiple instructions;
* Using smaller instructions with a tagging scheme to combine them.

Large fixed-size bundles is conceptually simpler, but has a few obvious
drawbacks:
* You either get the maximum possible ILP, or else...;
** Failure to achieve max ILP means lots of wasted space;
** Any unused lanes need to be padded with NOPs.
* Not usually particularly flexible regarding instruction encodings.

The use of tagging makes things more flexible:
* The ISA can facilitate variable-length instructions and bundles;
* Can use less space when less ILP is available;
* ...

The tagging approach is more like superscalar in presentation, but
allows the bundle length to be determined earlier (such as during the
Instruction Fetch stage), meaning there is no ambiguity in terms of how
much can be executed. If we see a bundle, we execute a bundle.

Comparably, it also allows for a wider core to be done more cheaply than
a comparable superscalar.

However:
It does require the compiler to be aware of the specific properties of
the target machine, such as maximum bundle length, which instructions
are allowed in which lanes, ...

In some sense, this favors superscalar as a more "in general" solution.

With a tag-based VLIW, it may be possible for mismatched code for the
CPU core to fall back to executing it one instruction at a time
(provided the ISA makes the provision that all valid bundles are also
required to be valid if the instructions are executed sequentially).

This case also potentially allows a superscalar (or maybe even OoO)
implementation of the same ISA to ignore the VLIW tag bits and execute
the code as if it were a more conventional RISC style ISA.

Potentially, the compiler may need to be capable of some fancy
transformations to be able to utilize it effectively.

So, for 2 or 3 lanes, one may find that cases which can utilize it may
"fall out" of code without doing too much. However, trying to "saturate"
these lanes, or to make effective use of a wider core, would require a
fair bit more heavy lifting from the compiler.

For example, one could have a 5 or 6 lane core, but absent a
particularly smart compiler, these lanes would almost always end up
being "wasted".

Similarly, absent these sorts of optimizations, OoO is about the only
other way one could hope to use this potential ILP (where we basically
try to get the hardware to do a bunch of stuff which might have
otherwise been done by the compiler).

So, the "most bang for the buck" for an in-order machine seems to be for
a width of around 2 or 3 lanes.

There also tends to be a local optimum of around 32 registers, though
cases may still occur where 32 isn't enough. For small functions, there
might not be enough going on to justify more.

For example, something like "strcmp()" might fit entirely within 6 or so
scratch registers, and one may find they can do little to optimize it
significantly (within the realm of conventional optimizations).

If rewriting it in ASM, one can make it process 8 characters at a time.
It may be possible to get a little more ILP by processing 16 characters
at a time, but then one runs into another problem:
The 16-at-a-time version may actually end up being slower, the main
reason being that it only reaches peak efficiency for strings larger
than 32 or 48 characters, and this falls into "hardly ever happens"
territory (whereas, say, the 8 characters at a time version reaches its
peak at around 16 characters, which is a little more reasonable).

OoO gets a bit more complicated, but am not going to say as much here.

Now as for caches, these are their own issue.

Generally, the L2 or L3 cache need not care what is happening in the CPU
core. The L1 may care, since it is generally tied in with the pipeline
machinery. However, some "more generic" mechanisms are likely to be used
for the larger cache levels, which are typically more concerned with
moving blocks of data around than what exactly happens with them.

MitchAlsup [2021-06-15 09:23:35] wrote:
> On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
>> which type of core requires high frequency of operation ,in-order or
>> out-of-order?Is it good to have in-order and out-of-order core to share
>> the same cache level(L2 or L3)?
> [...]
> Pure In Order is immune to Spectré-like attacks.

Really? I mean, maybe it happens to be true in practice for existing
in-order designs, but is it true in theory?

I mean, given a deep enough in-order pipeline, it seems it should be
possible to get the branch predictor to cause speculative execution of
a load followed by speculative execution of another load that depends on
the value of the first load before the mispredicted branch reaches the
retire stage. It does require a "large" number of stages between the
load execution and the "branch retire", tho.

Or am I missing something?

Stefan

On 6/15/2021 8:17 PM, Stefan Monnier wrote:
> MitchAlsup [2021-06-15 09:23:35] wrote:
>> On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
>>> which type of core requires high frequency of operation ,in-order or
>>> out-of-order?Is it good to have in-order and out-of-order core to share
>>> the same cache level(L2 or L3)?
>> [...]
>> Pure In Order is immune to Spectré-like attacks.
>
> Really? I mean, maybe it happens to be true in practice for existing
> in-order designs, but is it true in theory?
>
> I mean, given a deep enough in-order pipeline, it seems it should be
> possible to get the branch predictor to cause speculative execution of
> a load followed by speculative execution of another load that depends on
> the value of the first load before the mispredicted branch reaches the
> retire stage. It does require a "large" number of stages between the
> load execution and the "branch retire", tho.
>
> Or am I missing something?
>

This only seems like it could be true if the branch doesn't initiate
(and thus trigger a pipeline flush) until the WB stage or some other
late-stage in a very long pipeline.

If one has a branch mechanism which, say:
Starts branch initiation in EX1;
Branch takes effect in EX2 (thus triggering a flush).

Then, the ability to perform a load during this time is effectively
impossible no matter how many stages there are in total.

And, you wouldn't necessarily want to wait until WB or similar to
initiate a branch (while also allowing things like memory access), since
then it would be much harder to avoid visible state changes due to the
branch misprediction.

To allow for the state of memory to be rolled back during a flush, one
would also effectively need to keep in-flight memory loads and stores in
a queue, ..., which is already starting to go down the OoO path.

Then again, there are apparently some large in-order VLIW machines, such
as the Elbrus, so I guess the question is whether something like this
could be subject to such an exploit.

Though, what I can gather implies they are still using an 8-stage
pipeline (with 2 extra stages for FPU ops).

It also appears they are using variable-length bundles, but accomplish
this via an explicit bundle-length field rather than via a daisy-chain
encoding.

....

>
> Stefan
>

On Tuesday, June 15, 2021 at 8:17:45 PM UTC-5, Stefan Monnier wrote:
> MitchAlsup [2021-06-15 09:23:35] wrote:
> > On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
> >> which type of core requires high frequency of operation ,in-order or
> >> out-of-order?Is it good to have in-order and out-of-order core to share
> >> the same cache level(L2 or L3)?
> > [...]
> > Pure In Order is immune to Spectré-like attacks.
> Really? I mean, maybe it happens to be true in practice for existing
> in-order designs, but is it true in theory?
<
Well, let's see:: the vast majority of IO architectures do not have various
predictors that Spectré and Metldown exploit, leaving only the cache
footprint, and seldom does one architect a IO machine to start a subsequent
memory ref before one verifies via TLB that the access is supposed to
transpire. So while not inconceivable, the probabilities are low and
easily suppressed (assuming one has Spectré and Meltdown on their
hit list.
>
> I mean, given a deep enough in-order pipeline, it seems it should be
> possible to get the branch predictor to cause speculative execution of
> a load followed by speculative execution of another load that depends on
> the value of the first load before the mispredicted branch reaches the
> retire stage. It does require a "large" number of stages between the
> load execution and the "branch retire", tho.
>
> Or am I missing something?
>
>
> Stefan

On Tuesday, June 15, 2021 at 9:12:11 PM UTC-5, BGB wrote:
> On 6/15/2021 8:17 PM, Stefan Monnier wrote:
> > MitchAlsup [2021-06-15 09:23:35] wrote:
> >> On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
> >>> which type of core requires high frequency of operation ,in-order or
> >>> out-of-order?Is it good to have in-order and out-of-order core to share
> >>> the same cache level(L2 or L3)?
> >> [...]
> >> Pure In Order is immune to Spectré-like attacks.
> >
> > Really? I mean, maybe it happens to be true in practice for existing
> > in-order designs, but is it true in theory?
> >
> > I mean, given a deep enough in-order pipeline, it seems it should be
> > possible to get the branch predictor to cause speculative execution of
> > a load followed by speculative execution of another load that depends on
> > the value of the first load before the mispredicted branch reaches the
> > retire stage. It does require a "large" number of stages between the
> > load execution and the "branch retire", tho.
> >
> > Or am I missing something?
> >
> This only seems like it could be true if the branch doesn't initiate
> (and thus trigger a pipeline flush) until the WB stage or some other
> late-stage in a very long pipeline.
>
> If one has a branch mechanism which, say:
> Starts branch initiation in EX1;
> Branch takes effect in EX2 (thus triggering a flush).
>
> Then, the ability to perform a load during this time is effectively
> impossible no matter how many stages there are in total.
<
The only hole is whether the LD under the branch can cause a cache
miss which alters cache state after the branch got flushed.
>
>
> And, you wouldn't necessarily want to wait until WB or similar to
> initiate a branch (while also allowing things like memory access), since
> then it would be much harder to avoid visible state changes due to the
> branch misprediction.
>
> To allow for the state of memory to be rolled back during a flush, one
> would also effectively need to keep in-flight memory loads and stores in
> a queue, ..., which is already starting to go down the OoO path.
>
>
>
> Then again, there are apparently some large in-order VLIW machines, such
> as the Elbrus, so I guess the question is whether something like this
> could be subject to such an exploit.
>
> Though, what I can gather implies they are still using an 8-stage
> pipeline (with 2 extra stages for FPU ops).
>
> It also appears they are using variable-length bundles, but accomplish
> this via an explicit bundle-length field rather than via a daisy-chain
> encoding.
>
> ...
>
>
> >
> > Stefan
> >

On Wednesday, June 16, 2021 at 6:56:29 PM UTC+3, MitchAlsup wrote:
> On Tuesday, June 15, 2021 at 9:12:11 PM UTC-5, BGB wrote:
> > On 6/15/2021 8:17 PM, Stefan Monnier wrote:
> > > MitchAlsup [2021-06-15 09:23:35] wrote:
> > >> On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
> > >>> which type of core requires high frequency of operation ,in-order or
> > >>> out-of-order?Is it good to have in-order and out-of-order core to share
> > >>> the same cache level(L2 or L3)?
> > >> [...]
> > >> Pure In Order is immune to Spectré-like attacks.
> > >
> > > Really? I mean, maybe it happens to be true in practice for existing
> > > in-order designs, but is it true in theory?
> > >
> > > I mean, given a deep enough in-order pipeline, it seems it should be
> > > possible to get the branch predictor to cause speculative execution of
> > > a load followed by speculative execution of another load that depends on
> > > the value of the first load before the mispredicted branch reaches the
> > > retire stage. It does require a "large" number of stages between the
> > > load execution and the "branch retire", tho.
> > >
> > > Or am I missing something?
> > >
> > This only seems like it could be true if the branch doesn't initiate
> > (and thus trigger a pipeline flush) until the WB stage or some other
> > late-stage in a very long pipeline.
> >
> > If one has a branch mechanism which, say:
> > Starts branch initiation in EX1;
> > Branch takes effect in EX2 (thus triggering a flush).
> >
> > Then, the ability to perform a load during this time is effectively
> > impossible no matter how many stages there are in total.
> <
> The only hole is whether the LD under the branch can cause a cache
> miss which alters cache state after the branch got flushed.

And that's exactly what they call Spectre Variant 1.

> >
> >
> > And, you wouldn't necessarily want to wait until WB or similar to
> > initiate a branch (while also allowing things like memory access), since
> > then it would be much harder to avoid visible state changes due to the
> > branch misprediction.
> >
> > To allow for the state of memory to be rolled back during a flush, one
> > would also effectively need to keep in-flight memory loads and stores in
> > a queue, ..., which is already starting to go down the OoO path.
> >
> >
> >
> > Then again, there are apparently some large in-order VLIW machines, such
> > as the Elbrus, so I guess the question is whether something like this
> > could be subject to such an exploit.
> >
> > Though, what I can gather implies they are still using an 8-stage
> > pipeline (with 2 extra stages for FPU ops).
> >
> > It also appears they are using variable-length bundles, but accomplish
> > this via an explicit bundle-length field rather than via a daisy-chain
> > encoding.
> >
> > ...
> >
> >
> > >
> > > Stefan
> > >

On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
> which type of core requires high frequency of operation ,in-order or out-of-order?Is it good to have in-order and out-of-order core to share the same cache level(L2 or L3)?

One of the interesting results of our research was that out-of-order machines are easier to ramp to high frequency. This is because an in-order machine suffers more as L1D latency increases (you need to get the compiler to extract more and more ILP).

On 6/16/2021 10:56 AM, MitchAlsup wrote:
> On Tuesday, June 15, 2021 at 9:12:11 PM UTC-5, BGB wrote:
>> On 6/15/2021 8:17 PM, Stefan Monnier wrote:
>>> MitchAlsup [2021-06-15 09:23:35] wrote:
>>>> On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
>>>>> which type of core requires high frequency of operation ,in-order or
>>>>> out-of-order?Is it good to have in-order and out-of-order core to share
>>>>> the same cache level(L2 or L3)?
>>>> [...]
>>>> Pure In Order is immune to Spectré-like attacks.
>>>
>>> Really? I mean, maybe it happens to be true in practice for existing
>>> in-order designs, but is it true in theory?
>>>
>>> I mean, given a deep enough in-order pipeline, it seems it should be
>>> possible to get the branch predictor to cause speculative execution of
>>> a load followed by speculative execution of another load that depends on
>>> the value of the first load before the mispredicted branch reaches the
>>> retire stage. It does require a "large" number of stages between the
>>> load execution and the "branch retire", tho.
>>>
>>> Or am I missing something?
>>>
>> This only seems like it could be true if the branch doesn't initiate
>> (and thus trigger a pipeline flush) until the WB stage or some other
>> late-stage in a very long pipeline.
>>
>> If one has a branch mechanism which, say:
>> Starts branch initiation in EX1;
>> Branch takes effect in EX2 (thus triggering a flush).
>>
>> Then, the ability to perform a load during this time is effectively
>> impossible no matter how many stages there are in total.
> <
> The only hole is whether the LD under the branch can cause a cache
> miss which alters cache state after the branch got flushed.

It is possible, if this is the case.

In my case, with the branch mechanism initiating in EX2, it should also
flush EX1 (turning the load into a NOP) before it has a chance to send
the request to the L1 cache.

Though, if the load request does make it to the L1, it stands a chance
of triggering a cache miss.

In other news, recently have gotten a few speed boosts in my project:
Dhrystone (2.1) score went from ~ 37000 to ~ 49000 by rewriting
strcmp/strlen/strncmp/strcat in ASM, and using a few new helper ops (*);
Got another boost up to ~ 53000 (~ 30.2 DMIPS) by adding a compiler
feature to skip creating stack frames for small leaf functions (where it
can fit everything into scratch registers).

This latter change also resulted in an ~9% reduction in the size of the
generated binaries (for both Doom and Quake). Not much visible impact on
Doom performance though. GLQuake does now seem to be a little faster
(went from ~ 2-5 fps to ~ 3-8; in-game, GLQuake now seems to be a little
faster than Software Quake).

*1: In particular, added a "Packed Byte Search" op which can be used to
(quickly) detect the presence of a NUL byte (not really sure if
something like this counts as "cheating" though).

At the moment, it seems to be getting similar speeds to a 486DX2-66
according to this metric. Still a mystery how the 486 did so well given
how much x86 sucks, but then again for my compiler, much of the
benchmark seems to turn into a giant mess of memory loads and stores
(once one shaves off the big chunk of time that was previously going
into "strcmp()" and similar).

>>
>>
>> And, you wouldn't necessarily want to wait until WB or similar to
>> initiate a branch (while also allowing things like memory access), since
>> then it would be much harder to avoid visible state changes due to the
>> branch misprediction.
>>
>> To allow for the state of memory to be rolled back during a flush, one
>> would also effectively need to keep in-flight memory loads and stores in
>> a queue, ..., which is already starting to go down the OoO path.
>>
>>
>>
>> Then again, there are apparently some large in-order VLIW machines, such
>> as the Elbrus, so I guess the question is whether something like this
>> could be subject to such an exploit.
>>
>> Though, what I can gather implies they are still using an 8-stage
>> pipeline (with 2 extra stages for FPU ops).
>>
>> It also appears they are using variable-length bundles, but accomplish
>> this via an explicit bundle-length field rather than via a daisy-chain
>> encoding.
>>
>> ...
>>
>>
>>>
>>> Stefan
>>>

Michael S <already5chosen@yahoo.com> writes:
>On Wednesday, June 16, 2021 at 6:56:29 PM UTC+3, MitchAlsup wrote:
>> The only hole is whether the LD under the branch can cause a cache=20
>> miss which alters cache state after the branch got flushed.
>
>
>And that's exactly what they call Spectre Variant 1.

That's not any variant of Spectre, because it does not reveal any
speculatively accessed data.

Spectre consists of a spectlative load of the secret followed by some
mechanism that reveals the secret through a side channel. The first
Spectre variants used cache side channels.

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

On Wednesday, June 16, 2021 at 8:30:59 PM UTC-5, BGB wrote:
> On 6/16/2021 10:56 AM, MitchAlsup wrote:
> > On Tuesday, June 15, 2021 at 9:12:11 PM UTC-5, BGB wrote:
> >> On 6/15/2021 8:17 PM, Stefan Monnier wrote:
> >>> MitchAlsup [2021-06-15 09:23:35] wrote:
> >>>> On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
> >>>>> which type of core requires high frequency of operation ,in-order or
> >>>>> out-of-order?Is it good to have in-order and out-of-order core to share
> >>>>> the same cache level(L2 or L3)?
> >>>> [...]
> >>>> Pure In Order is immune to Spectré-like attacks.
> >>>
> >>> Really? I mean, maybe it happens to be true in practice for existing
> >>> in-order designs, but is it true in theory?
> >>>
> >>> I mean, given a deep enough in-order pipeline, it seems it should be
> >>> possible to get the branch predictor to cause speculative execution of
> >>> a load followed by speculative execution of another load that depends on
> >>> the value of the first load before the mispredicted branch reaches the
> >>> retire stage. It does require a "large" number of stages between the
> >>> load execution and the "branch retire", tho.
> >>>
> >>> Or am I missing something?
> >>>
> >> This only seems like it could be true if the branch doesn't initiate
> >> (and thus trigger a pipeline flush) until the WB stage or some other
> >> late-stage in a very long pipeline.
> >>
> >> If one has a branch mechanism which, say:
> >> Starts branch initiation in EX1;
> >> Branch takes effect in EX2 (thus triggering a flush).
> >>
> >> Then, the ability to perform a load during this time is effectively
> >> impossible no matter how many stages there are in total.
> > <
> > The only hole is whether the LD under the branch can cause a cache
> > miss which alters cache state after the branch got flushed.
> It is possible, if this is the case.
>
> In my case, with the branch mechanism initiating in EX2, it should also
> flush EX1 (turning the load into a NOP) before it has a chance to send
> the request to the L1 cache.
>
> Though, if the load request does make it to the L1, it stands a chance
> of triggering a cache miss.
>
>
>
> In other news, recently have gotten a few speed boosts in my project:
> Dhrystone (2.1) score went from ~ 37000 to ~ 49000 by rewriting
> strcmp/strlen/strncmp/strcat in ASM, and using a few new helper ops (*);
> Got another boost up to ~ 53000 (~ 30.2 DMIPS) by adding a compiler
> feature to skip creating stack frames for small leaf functions (where it
> can fit everything into scratch registers).
>
> This latter change also resulted in an ~9% reduction in the size of the
> generated binaries (for both Doom and Quake). Not much visible impact on
> Doom performance though. GLQuake does now seem to be a little faster
> (went from ~ 2-5 fps to ~ 3-8; in-game, GLQuake now seems to be a little
> faster than Software Quake).
>
>
> *1: In particular, added a "Packed Byte Search" op which can be used to
> (quickly) detect the presence of a NUL byte (not really sure if
> something like this counts as "cheating" though).
<
It is not cheating, it is borrowing. Mc 88110 had its CMP instruction set
bits for AnyByteZero and AnyHalfwordZero for identical purposes.
>
>
> At the moment, it seems to be getting similar speeds to a 486DX2-66
> according to this metric. Still a mystery how the 486 did so well given
> how much x86 sucks, but then again for my compiler, much of the
> benchmark seems to turn into a giant mess of memory loads and stores
> (once one shaves off the big chunk of time that was previously going
> into "strcmp()" and similar).
> >>
> >>
> >> And, you wouldn't necessarily want to wait until WB or similar to
> >> initiate a branch (while also allowing things like memory access), since
> >> then it would be much harder to avoid visible state changes due to the
> >> branch misprediction.
> >>
> >> To allow for the state of memory to be rolled back during a flush, one
> >> would also effectively need to keep in-flight memory loads and stores in
> >> a queue, ..., which is already starting to go down the OoO path.
> >>
> >>
> >>
> >> Then again, there are apparently some large in-order VLIW machines, such
> >> as the Elbrus, so I guess the question is whether something like this
> >> could be subject to such an exploit.
> >>
> >> Though, what I can gather implies they are still using an 8-stage
> >> pipeline (with 2 extra stages for FPU ops).
> >>
> >> It also appears they are using variable-length bundles, but accomplish
> >> this via an explicit bundle-length field rather than via a daisy-chain
> >> encoding.
> >>
> >> ...
> >>
> >>
> >>>
> >>> Stefan
> >>>

On 6/17/2021 10:08 AM, MitchAlsup wrote:
> On Wednesday, June 16, 2021 at 8:30:59 PM UTC-5, BGB wrote:
>> On 6/16/2021 10:56 AM, MitchAlsup wrote:
>>> On Tuesday, June 15, 2021 at 9:12:11 PM UTC-5, BGB wrote:
>>>> On 6/15/2021 8:17 PM, Stefan Monnier wrote:
>>>>> MitchAlsup [2021-06-15 09:23:35] wrote:
>>>>>> On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
>>>>>>> which type of core requires high frequency of operation ,in-order or
>>>>>>> out-of-order?Is it good to have in-order and out-of-order core to share
>>>>>>> the same cache level(L2 or L3)?
>>>>>> [...]
>>>>>> Pure In Order is immune to Spectré-like attacks.
>>>>>
>>>>> Really? I mean, maybe it happens to be true in practice for existing
>>>>> in-order designs, but is it true in theory?
>>>>>
>>>>> I mean, given a deep enough in-order pipeline, it seems it should be
>>>>> possible to get the branch predictor to cause speculative execution of
>>>>> a load followed by speculative execution of another load that depends on
>>>>> the value of the first load before the mispredicted branch reaches the
>>>>> retire stage. It does require a "large" number of stages between the
>>>>> load execution and the "branch retire", tho.
>>>>>
>>>>> Or am I missing something?
>>>>>
>>>> This only seems like it could be true if the branch doesn't initiate
>>>> (and thus trigger a pipeline flush) until the WB stage or some other
>>>> late-stage in a very long pipeline.
>>>>
>>>> If one has a branch mechanism which, say:
>>>> Starts branch initiation in EX1;
>>>> Branch takes effect in EX2 (thus triggering a flush).
>>>>
>>>> Then, the ability to perform a load during this time is effectively
>>>> impossible no matter how many stages there are in total.
>>> <
>>> The only hole is whether the LD under the branch can cause a cache
>>> miss which alters cache state after the branch got flushed.
>> It is possible, if this is the case.
>>
>> In my case, with the branch mechanism initiating in EX2, it should also
>> flush EX1 (turning the load into a NOP) before it has a chance to send
>> the request to the L1 cache.
>>
>> Though, if the load request does make it to the L1, it stands a chance
>> of triggering a cache miss.
>>
>>
>>
>> In other news, recently have gotten a few speed boosts in my project:
>> Dhrystone (2.1) score went from ~ 37000 to ~ 49000 by rewriting
>> strcmp/strlen/strncmp/strcat in ASM, and using a few new helper ops (*);
>> Got another boost up to ~ 53000 (~ 30.2 DMIPS) by adding a compiler
>> feature to skip creating stack frames for small leaf functions (where it
>> can fit everything into scratch registers).
>>
>> This latter change also resulted in an ~9% reduction in the size of the
>> generated binaries (for both Doom and Quake). Not much visible impact on
>> Doom performance though. GLQuake does now seem to be a little faster
>> (went from ~ 2-5 fps to ~ 3-8; in-game, GLQuake now seems to be a little
>> faster than Software Quake).
>>

Clarification:
Rather than demand-loading variables into registers and then spilling
them back to memory at the end of the basic block (with the top N
variables being statically assigned to registers), it uses a different
approach.

All the local variables/arguments/temporaries are statically assigned to
registers throughout the entire function, and no stack-frame is created
for them (and thus no stack spills will occur).

There are two sub-variants for different handling of constants and globals:
They may also be statically assigned to registers, loaded in at the
start of the function, and any "dirty" globals being written back when
the function returns (excluding 'volatile');
A hybrid mode is used, with constants and globals still being
demand-loaded (and stored-back / evicted at the end of the basic block).

The distinction between these is based on whether or not everything can
fit into registers using the direct approach. If there isn't sufficient
register space to fit everything in the second case, it falls back to
stack-frame creation and demand-loading as usual.

Similarly, it excludes leaf functions which access global variables
which are also referenced via a function pointer, since this is a
problem case for the C ABI (no way to make this work reliably absent
creating a stack frame).

This approach does seem to result in a notable improvement for the
performance of the functions it applies to, but seems to be being
limited by the size of the register space (with 32 registers), with most
of the potentially eligible leaf functions still running out of registers.

It looks like if I extend the C compilers' register allocator to be able
to deal with the XGPR space, then it will be possible to handle a lot
more functions with this approach.

....

The limited gains with Doom performance seems to be mostly due to leaf
functions being relatively uncommon (and generally not in
performance-sensitive areas).

Meanwhile, Quake seems to have a significantly higher number of leaf
functions relative to Doom.

An intermediate option, where it creates a stack-frame but just uses it
to save callee preserved registers, is another possibility (this could
then prefer scratch registers and then use the callee-preserved
registers as an overflow space; falling back to the more traditional
approach if it exceeds the limit of 27 or 59 usable GPRs).

Or potentially a similar sort of static assignment strategy could also
be applied to a subset of non-leaf functions?...

Granted, I don't really expect all this is particularly novel.

>>
>> *1: In particular, added a "Packed Byte Search" op which can be used to
>> (quickly) detect the presence of a NUL byte (not really sure if
>> something like this counts as "cheating" though).
> <
> It is not cheating, it is borrowing. Mc 88110 had its CMP instruction set
> bits for AnyByteZero and AnyHalfwordZero for identical purposes.

Yeah. This is at least slightly more generic:
* PSCHEQ.B Rm, Rt, Rn
Compare if bytes in Rm match Rt within a 64-bit QWord.
Sets Rn to the index of the first match and sets SR.T if a match is found.

* PSCHNE.B Rm, Rt, Rn
Compare if bytes in Rm differ from Rt.
Sets Rn to the index of the first mismatch and sets SR.T if a mismatch
is found.

These can be used to accelerate C string functions (detecting a NUL byte
or finding the first mismatch), but also potentially some other things
(eg: LZ77 compression).

Relatedly, there is also a Word variant:
* PSCHEQ.W Rm, Rt, Rn
* PSCHNE.W Rm, Rt, Rn

Which does similar, except using packed 16-bit words.

This is more useful for UCS2 / UTF16 strings, but was also intended for
things like dictionary objects (where, say, one looks up a value in an
array based on a 16-bit key index).

But, it is possible that some might try to argue that strcmp is necessarily:
while(*s1 && (*s1==*t1))
{ s1++; t1++; }
if(*s1>*t1)return(1);
if(*s1<*t1)return(-1);
return(0);
...

And that, potentially, using instructions that allow running the loop 64
bits at a time and using ASM is cheating.

Though. potentially similarly for implementing memcpy and memset using
QWord or XWord/OWord ops rather than byte ops, say:
while(n--)*t++=*s++;
Or:
while(n--)*t++=c;
....

Functions like strcpy/strcat need to fall back to byte-copying at the
end though, since AFAIK they aren't allowed to stomp memory past the end
of the destination string (even if this would be a little faster).

Similarly, trying to splice the destination (via bit-masking) wouldn't
necessarily be much (if any) faster than falling back to byte-copying
for the final bytes.

Similarly, I also replaced some amount of the "math.h" functions to be
"less terrible", mostly using things like unrolled Taylor-series
expansions and similar...

Namely, if one calculates the factorials, calls "pow()", does a
division, ..., for every loop iteration, this *sucks* in terms of
performance.

The malloc implementation effectively got replaced as well, with the C
library's "malloc()" effectively being a thin wrapper over a function
pointer, which is then redirected to the "tk_malloc()" implementation.

Then added a few extensions, like "_msize()" / "malloc_usable_size()"
and similar. The actual memory manager also supports a few extra
features (type tags and reference counts), but these are not terribly
relevant to normal C code.

On Thursday, June 17, 2021 at 1:41:29 PM UTC-5, BGB wrote:
> On 6/17/2021 10:08 AM, MitchAlsup wrote:

> >> *1: In particular, added a "Packed Byte Search" op which can be used to
> >> (quickly) detect the presence of a NUL byte (not really sure if
> >> something like this counts as "cheating" though).
> > <
> > It is not cheating, it is borrowing. Mc 88110 had its CMP instruction set
> > bits for AnyByteZero and AnyHalfwordZero for identical purposes.
<
> Yeah. This is at least slightly more generic:
<
> * PSCHEQ.B Rm, Rt, Rn
> Compare if bytes in Rm match Rt within a 64-bit QWord.
> Sets Rn to the index of the first match and sets SR.T if a match is found.
<
The Mc 88110 CMP instruction performed word, half, byte compares
along with the AnyByteZero and AnyHalfZero. All in one instruction.
>
> * PSCHNE.B Rm, Rt, Rn
> Compare if bytes in Rm differ from Rt.
> Sets Rn to the index of the first mismatch and sets SR.T if a mismatch
> is found.

>
> This is more useful for UCS2 / UTF16 strings, but was also intended for
> things like dictionary objects (where, say, one looks up a value in an
> array based on a 16-bit key index).
>
>
> But, it is possible that some might try to argue that strcmp is necessarily:
> while(*s1 && (*s1==*t1))
> { s1++; t1++; }
> if(*s1>*t1)return(1);
> if(*s1<*t1)return(-1);
> return(0);
<
int strcmp
{ while(*s1 && (*s1==*t1))
{ s1++; t1++; }
return s1-t1;
} <
It does not have to return +1 and -1 it can return positive or negative.
> ...

On Thursday, June 17, 2021 at 7:27:05 PM UTC-4, MitchAlsup wrote:
> On Thursday, June 17, 2021 at 1:41:29 PM UTC-5, BGB wrote:
> > On 6/17/2021 10:08 AM, MitchAlsup wrote:
>
> > >> *1: In particular, added a "Packed Byte Search" op which can be used to
> > >> (quickly) detect the presence of a NUL byte (not really sure if
> > >> something like this counts as "cheating" though).
> > > <
> > > It is not cheating, it is borrowing. Mc 88110 had its CMP instruction set
> > > bits for AnyByteZero and AnyHalfwordZero for identical purposes.
> <
> > Yeah. This is at least slightly more generic:
> <
> > * PSCHEQ.B Rm, Rt, Rn
> > Compare if bytes in Rm match Rt within a 64-bit QWord.
> > Sets Rn to the index of the first match and sets SR.T if a match is found.
> <
> The Mc 88110 CMP instruction performed word, half, byte compares
> along with the AnyByteZero and AnyHalfZero. All in one instruction.
> >
> > * PSCHNE.B Rm, Rt, Rn
> > Compare if bytes in Rm differ from Rt.
> > Sets Rn to the index of the first mismatch and sets SR.T if a mismatch
> > is found.
>
> >
> > This is more useful for UCS2 / UTF16 strings, but was also intended for
> > things like dictionary objects (where, say, one looks up a value in an
> > array based on a 16-bit key index).
> >
> >
> > But, it is possible that some might try to argue that strcmp is necessarily:
> > while(*s1 && (*s1==*t1))
> > { s1++; t1++; }
> > if(*s1>*t1)return(1);
> > if(*s1<*t1)return(-1);
> > return(0);
> <
> int strcmp
> {
> while(*s1 && (*s1==*t1))
> { s1++; t1++; }
> return s1-t1;
> }
> <
> It does not have to return +1 and -1 it can return positive or negative.
> > ...

>Yeah. This is at least slightly more generic:
>* PSCHEQ.B Rm, Rt, Rn
>Compare if bytes in Rm match Rt within a 64-bit QWord.
>Sets Rn to the index of the first match and sets SR.T if a match is found.

The same thing is available in ANY1 as the BYTNDX,WYDNDX, and U21NDX instructions.
UTF21 being used for unicode strings. The instructions have both register and immediate forms.
BYTNDX can also be applied to vector registers to search all the elements for the first occurrence
of a byte.

On 6/17/2021 6:27 PM, MitchAlsup wrote:
> On Thursday, June 17, 2021 at 1:41:29 PM UTC-5, BGB wrote:
>> On 6/17/2021 10:08 AM, MitchAlsup wrote:
>
>>>> *1: In particular, added a "Packed Byte Search" op which can be used to
>>>> (quickly) detect the presence of a NUL byte (not really sure if
>>>> something like this counts as "cheating" though).
>>> <
>>> It is not cheating, it is borrowing. Mc 88110 had its CMP instruction set
>>> bits for AnyByteZero and AnyHalfwordZero for identical purposes.
> <
>> Yeah. This is at least slightly more generic:
> <
>> * PSCHEQ.B Rm, Rt, Rn
>> Compare if bytes in Rm match Rt within a 64-bit QWord.
>> Sets Rn to the index of the first match and sets SR.T if a match is found.
> <
> The Mc 88110 CMP instruction performed word, half, byte compares
> along with the AnyByteZero and AnyHalfZero. All in one instruction.

OK. The instruction I have can do similar, except that one needs load
zero into a register, typically before entering the loop.

>>
>> * PSCHNE.B Rm, Rt, Rn
>> Compare if bytes in Rm differ from Rt.
>> Sets Rn to the index of the first mismatch and sets SR.T if a mismatch
>> is found.
>

This one is useful for strcmp in that it can also eliminate needing to
do a byte-compare loop for the last several characters of the string,
and a relative comparison of the first-mismatched-character vs the NUL
terminator location can indicate whether the string ended before it
mismatched.

>>
>> This is more useful for UCS2 / UTF16 strings, but was also intended for
>> things like dictionary objects (where, say, one looks up a value in an
>> array based on a 16-bit key index).
>>
>>
>> But, it is possible that some might try to argue that strcmp is necessarily:
>> while(*s1 && (*s1==*t1))
>> { s1++; t1++; }
>> if(*s1>*t1)return(1);
>> if(*s1<*t1)return(-1);
>> return(0);
> <
> int strcmp
> {
> while(*s1 && (*s1==*t1))
> { s1++; t1++; }
> return s1-t1;
> }
> <
> It does not have to return +1 and -1 it can return positive or negative.

Good to know I guess, could maybe save a few cycles...

The existing logic does something more like:
CMPGT R6, R7
MOV?T 1, R2 | MOV?F -1, R2
But, eg:
SUB R6, R7, R2
Is a little cheaper...

Otherwise...

A little more fiddling with the compiler (mostly more fiddling with the
register allocation logic), I am now up to ~55000 in Dhrystone (and
binaries also shrank a few more %).

The relative amount of clock cycles spent on memory load/store ops has
also shrank slightly, and some other operations (namely branches and ALU
ops) have become a bigger part of the total (to the point of starting to
become a little more relevant).

Those memory ops which remain though seem to have a higher rate of cache
misses, and are also seem more prone to getting caught up in interlock
penalties.

Did go and add logic so now RTS will do the branch-prediction thing as
long as no other ops have modified LR within the pipeline. This is
nearly always true, but is harder to verify statically within the
compiler (more so with the new leaf function logic). For a sufficiently
small leaf function, it is possible to hit the final RTS instruction
before the original BSR instruction has cleared the WB stage (due mostly
to the branch prediction mechanism).

The new logic allows getting a speed advantage similar to the RTSU op
(namely, the RTS will be branch-predicted), but with the relative safety
of RTS (albeit at a slight cost increase vs not doing the pipeline check).

MitchAlsup wrote:
> On Thursday, June 17, 2021 at 1:41:29 PM UTC-5, BGB wrote:
>> On 6/17/2021 10:08 AM, MitchAlsup wrote:
>
>>>> *1: In particular, added a "Packed Byte Search" op which can be used to
>>>> (quickly) detect the presence of a NUL byte (not really sure if
>>>> something like this counts as "cheating" though).
>>> <
>>> It is not cheating, it is borrowing. Mc 88110 had its CMP instruction set
>>> bits for AnyByteZero and AnyHalfwordZero for identical purposes.
> <
>> Yeah. This is at least slightly more generic:
> <
>> * PSCHEQ.B Rm, Rt, Rn
>> Compare if bytes in Rm match Rt within a 64-bit QWord.
>> Sets Rn to the index of the first match and sets SR.T if a match is found.
> <
> The Mc 88110 CMP instruction performed word, half, byte compares
> along with the AnyByteZero and AnyHalfZero. All in one instruction.
>>
>> * PSCHNE.B Rm, Rt, Rn
>> Compare if bytes in Rm differ from Rt.
>> Sets Rn to the index of the first mismatch and sets SR.T if a mismatch
>> is found.
>
>>
>> This is more useful for UCS2 / UTF16 strings, but was also intended for
>> things like dictionary objects (where, say, one looks up a value in an
>> array based on a 16-bit key index).
>>
>>
>> But, it is possible that some might try to argue that strcmp is necessarily:
>> while(*s1 && (*s1==*t1))
>> { s1++; t1++; }
>> if(*s1>*t1)return(1);
>> if(*s1<*t1)return(-1);
>> return(0);
> <
> int strcmp
> {
> while(*s1 && (*s1==*t1))
> { s1++; t1++; }
> return s1-t1;
> }
> <
> It does not have to return +1 and -1 it can return positive or negative.

I have used that pattern, it fails when you can have a string which is
larger than half your int range, but is otherwise OK.

For a 64-bit int I'd be prefectly OK using it, but 32-bit is iffy.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On 2021-06-17, nedbrek wrote:
> On Tuesday, June 15, 2021 at 5:10:42 AM UTC-5, Chingu wrote:
>> which type of core requires high frequency of operation ,in-order or out-of-order?Is it good to have in-order and out-of-order core to share the same cache level(L2 or L3)?
>
> One of the interesting results of our research was that out-of-order machines are easier to ramp to high frequency. This is because an in-order machine suffers more as L1D latency increases (you need to get the compiler to extract more and more ILP).
>

I've had this gut feeling for some time: In order to reach higher
frequencies you typically need to reduce the gate depth of each
pipeline stage, and hence introduce more pipeline stages. That
means that you increase the latency (in clock cycles) before a
result becomes ready to use (and this becomes especially noticeable
for data load operations, as well as for some long-pipeline floating-
point operations I'd suppose).

For an in-order machine this means that you get more pipeline stalls,
thus eating some of the benefits from the increased clock frequency,
but for an out-of-order machine it's possible to "hide" these stalls
by running other instructions in the mean time.

/Marcus

On 18.06.2021 08:14, Terje Mathisen wrote:
> MitchAlsup wrote:
>>
>> int strcmp
>> {
>> while(*s1 && (*s1==*t1))
>> { s1++; t1++; }
>> return s1-t1;
>> }
>> <
>> It does not have to return +1 and -1 it can return positive or negative.
>
> I have used that pattern, it fails when you can have a string which is larger than half your int range, but is otherwise OK.
>
> For a 64-bit int I'd be prefectly OK using it, but 32-bit is iffy.

In fact, this pattern is simply wrong. It returns the difference between
the two string pointers, not between the first differing characters. The
failure you observed is only based on this programming error.

Irrespective of the result of the comparison, the return value is the
distance between the start address of the first and the start address of
the second string (ptrdiff_t casted to int). The compiler is even
entitled to remove the the complete while loop, since it does not
contribute to the returned result at all.

A correct version would be (C99):

int strcmp(char const* s1, char const* t1)
{ while (*s1 && (*s1 == *t1)) ++s1, ++t1;
return *s1 - *t1; // [sic] dereference pointers before subtraction
}

This still lacks verification for non-null arguments, but we could rely
on GPFs and runtime environment. However, it'd be helpful for the
compiler to declare strcmp with GCC attribute nonnull, so it will
prevent any calls with NULL pointers where it can deduce their values.

--
Regards,
Bernd

On 6/18/2021 5:26 AM, Bernd Linsel wrote:
> On 18.06.2021 08:14, Terje Mathisen wrote:
>> MitchAlsup wrote:
>>>
>>> int strcmp
>>> {
>>>       while(*s1 && (*s1==*t1))
>>>       { s1++; t1++; }
>>>       return s1-t1;
>>> }
>>> <
>>> It does not have to return +1 and -1 it can return positive or negative.
>>
>> I have used that pattern, it fails when you can have a string which is
>> larger than half your int range, but is otherwise OK.
>>
>> For a 64-bit int I'd be prefectly OK using it, but 32-bit is iffy.
>
> In fact, this pattern is simply wrong. It returns the difference between
> the two string pointers, not between the first differing characters. The
> failure you observed is only based on this programming error.
>
> Irrespective of the result of the comparison, the return value is the
> distance between the start address of the first and the start address of
> the second string (ptrdiff_t casted to int). The compiler is even
> entitled to remove the the complete while loop, since it does not
> contribute to the returned result at all.
>
> A correct version would be (C99):
>
> int strcmp(char const* s1, char const* t1)
> {
>     while (*s1 && (*s1 == *t1)) ++s1, ++t1;
>     return *s1 - *t1;    // [sic] dereference pointers before subtraction
> }
>

In my case, I assumed this was what was meant...

> This still lacks verification for non-null arguments, but we could rely
> on GPFs and runtime environment. However, it'd be helpful for the
> compiler to declare strcmp with GCC attribute nonnull, so it will
> prevent any calls with NULL pointers where it can deduce their values.
>

In my case, I am using "BGBCC" for this, which is my own compiler for my
own ISA, though sadly kinda fails at generating good code for it (what
it does generate is primarily scalar code, with little ability to avoid
interlocks).

Meanwhile, an in-order superscalar wouldn't do much better with this
code, as the compiler can manage the "easy part" (putting independent
ops in parallel), but not really the harder parts. It has some logic to
try to shuffle ops around, but this is fairly constrained in that many
operations are immovable, and it can't change the relative order of
memory operations.

The reordering is also limited by false dependencies between registers
(eg, if the same register is immediately reused), but this is another issue.

Some recent tweaks though do greatly reduce the number of register
spills in leaf functions by tweaking the register allocation logic, so
this is something...

....

nedbrek <nedbrek@yahoo.com> writes:
>One of the interesting results of our research was that out-of-order machines are easier to ramp to high frequency. This is because an in-order machine suffers more as L1D latency increases (you need to get the compiler to extract more and more ILP).

The numbers I have seen posted here (in an IA-64 discussion) are that
one extra L1D cycles costs 10% on in-order and 5% on OoO. But I don't
see why this should make it hard to ramp up clock rates. Sure, you
don't see as much benefit from the higher clock rate because of that
effect, but you should still see a benefit, because ALU ops go faster
and because the compiler is able to fill some of the load latency with
useful work.

My impression is that in-order designs are harder to clock fast
because they have less localized control recurrences than OoO; and
last time I wrote that, the people in the know did not really
contradict me, but discussed some techniques to work around that, such
as having a backup of the pipeline state and rolling back to that.

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

On Saturday, June 19, 2021 at 11:57:56 AM UTC-5, Anton Ertl wrote:
> nedbrek <ned...@yahoo.com> writes:
> >One of the interesting results of our research was that out-of-order machines are easier to ramp to high frequency. This is because an in-order machine suffers more as L1D latency increases (you need to get the compiler to extract more and more ILP).
<
> The numbers I have seen posted here (in an IA-64 discussion) are that
> one extra L1D cycles costs 10% on in-order and 5% on OoO. But I don't
<
Back in the R2000 and Mc 88100 days it was measured around 13%.
So we are not in any real disagreement. But this was 2-cycle versus
3-cycle, both in order. It would have been significantly worse 2-cycle
versus 4-cycle.
<
Conversely, I don't see much degradation in GBOoO 3-cycle versus 4-cycle.
But we can both agree it is rather small,a nd that frequency gain can easily
outweigh the pipeline disadvantage.
<
> see why this should make it hard to ramp up clock rates. Sure, you
> don't see as much benefit from the higher clock rate because of that
> effect, but you should still see a benefit, because ALU ops go faster
> and because the compiler is able to fill some of the load latency with
> useful work.
<
Since IO is so dependent on actual latency, many IO designs are
built around direct mapped caches so one can be aligning cache data
into register format even while hit is being detected.
<
Conversely, OoO designs, being less sensitive in the first place, can
afford set associative L1 caches and take the hit rate advantage to
ameliorate any pipeline disadvantage--often getting more than break
even.
>
> My impression is that in-order designs are harder to clock fast
> because they have less localized control recurrences than OoO; and
> last time I wrote that, the people in the know did not really
> contradict me, but discussed some techniques to work around that, such
> as having a backup of the pipeline state and rolling back to that.
<
My impression is that it is time to jump over into OoO (reservation
stations and all that) about the time set associative L1 caches are
called for. With today's transistor counts, there is little to prevent this
jump.
<
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On Saturday, June 19, 2021 at 7:57:56 PM UTC+3, Anton Ertl wrote:
> nedbrek <ned...@yahoo.com> writes:
> >One of the interesting results of our research was that out-of-order machines are easier to ramp to high frequency. This is because an in-order machine suffers more as L1D latency increases (you need to get the compiler to extract more and more ILP).
> The numbers I have seen posted here (in an IA-64 discussion) are that
> one extra L1D cycles costs 10% on in-order and 5% on OoO. But I don't
> see why this should make it hard to ramp up clock rates. Sure, you
> don't see as much benefit from the higher clock rate because of that
> effect, but you should still see a benefit, because ALU ops go faster
> and because the compiler is able to fill some of the load latency with
> useful work.
>
> My impression is that in-order designs are harder to clock fast
> because they have less localized control recurrences than OoO; and
> last time I wrote that, the people in the know did not really
> contradict me, but discussed some techniques to work around that, such
> as having a backup of the pipeline state and rolling back to that.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

I never tried to think hard about it, but my uneducated impression always was that it applies to "normal" In-Order, the one that does interlocks in hardware.
I don't see why it should apply to in-order designs with exposed pipeline, especially to those that also expose to software a banked structure of register files.
Of course, even designs like those has to have a way to deal with variable-length latency of memory instructions... May be, if it's done by replay the control could remain distributed?

Please , don't think for a second, that I advocated that sort of designs. Just say that they are possible.