On 2021-05-19, Thomas Koenig wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>
>> Given that the compiler knows _exactly_ what sort of target it is
>> working towards,
>
> That assumption can certainly be true if people compile the software
> themselves, as they often do for scientific applications.
>
> It is not the case with pre-compiled software delivered by some
> vendor or other distributor. If you use new features (such
> as this new-fangled popcnt instructions), the software will
> not run on old hardware (unless somebody puts in a feature test
> and a runtime switch for different architectures).
>
> As an example, look at the binary distributions of Stockfish for
> different CPUs.
>

Another very real example is the distribution of "apps" for
mobile devices (phones & tablets). When I worked at Opera Software
two very important goals for the mobile browser applications were:

1) The binary must be really small (e.g. to support quick and cheap
downloads over a 3G connection, and to fit in limited storage on
cheap devices).

2) It must be as fast as possible on a wide range of CPU generations
(e.g. ARMv6 vs ARMv7 vs ARMv7+NEON).

This required quite innovative solutions to be able to ship code that
is optimized for several architectures (with different ABI:s) in a
single, compact binary package. (The situation may have improved since
then w.r.t support for multiple architectures etc. in the "app stores").

There are many situations where there is great value in having a single,
stable ISA+ABI, allowing the same binary to run on a wide range of
microarchitectures.

/Marcus

On 2021-05-19, Stephen Fuld wrote:
> On 5/19/2021 8:04 AM, MitchAlsup wrote:
>> On Wednesday, May 19, 2021 at 3:52:42 AM UTC-5, Anton Ertl wrote:
>
> snip
>
>>> The big problem for software scheduling is that compilers are much
>>> worse at branch prediction than hardware.
>> <
>> Precisely because the Branch prediction structures contain vastly
>> more correlated states than SW currently manages.
>
> I think that is part of it.  The compiler could keep such data
> structures.  After all, software simulators of CPUs do.
>
> But the inescapable part is that compilers don't have access to the
> input data that is only available at run time and that affects the
> accuracy of branch predictors.  There is profile guided optimization,
> but then you are back to the problem John Dallman pointed out about
> getting "correct" test data to guide the test runs.
>

Using the "correct data" is part of it, but it's worse. Static analysis
and even PGO can only find the statistical probabilities for each
branch, and at best optimize & schedule for one way or the other. On
the other hand the hardware branch predictor can make different
decisions for the same branch instruction at different points in time.
This is something that a compiler can not practically do (at least not
without spewing out a large number of different code sequences, that
would kill I$ performance, and probably be quite inaccurate anyway).

/Marcus

On 5/19/2021 11:38 AM, Marcus wrote:
> On 2021-05-19, Stephen Fuld wrote:
>> On 5/19/2021 8:04 AM, MitchAlsup wrote:
>>> On Wednesday, May 19, 2021 at 3:52:42 AM UTC-5, Anton Ertl wrote:
>>
>> snip
>>
>>>> The big problem for software scheduling is that compilers are much
>>>> worse at branch prediction than hardware.
>>> <
>>> Precisely because the Branch prediction structures contain vastly
>>> more correlated states than SW currently manages.
>>
>> I think that is part of it.  The compiler could keep such data
>> structures.  After all, software simulators of CPUs do.
>>
>> But the inescapable part is that compilers don't have access to the
>> input data that is only available at run time and that affects the
>> accuracy of branch predictors.  There is profile guided optimization,
>> but then you are back to the problem John Dallman pointed out about
>> getting "correct" test data to guide the test runs.
>>
>
> Using the "correct data" is part of it, but it's worse. Static analysis
> and even PGO can only find the statistical probabilities for each
> branch, and at best optimize & schedule for one way or the other. On
> the other hand the hardware branch predictor can make different
> decisions for the same branch instruction at different points in time.

True. I had missed the temporal aspect. Thanks.

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

According to MitchAlsup <MitchAlsup@aol.com>:
>I wonder what would Multiflow compiler do with your std garbage collector
>"application" ?

Give up, I expect. Since their customers were mostly doing scientific
computation and this was the 1980s, they had a C compiler but the main
language was Fortran and I get the impression that the more your C was
like Fortran, the faster it was likely to run.

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

MitchAlsup <MitchAlsup@aol.com> writes:
>On Wednesday, May 19, 2021 at 4:36:01 AM UTC-5, Anton Ertl wrote:
>> MitchAlsup <Mitch...@aol.com> writes:
>> >However, there are things that HW simply takes in stride
>> >that software scheduling can never get "correct", cache misses, for example;
>> >and in particular a cache miss that runs 1 miss followed by 7 hits. Does SW
>> >schedule for the hit case or for the miss case ?
><
>> Easy: This does not sound like pointer-chasing, so just schedule for
>> the miss case. If there is some reason not to, unroll by 8, and
>> schedule 1 miss followed by 7 hits. Alternatively, let the hardware
>> prefetcher do its work, and schedule for a hit.
><
>But then SW is not driving the whole process !!

Software is doing the fetches that inform the prefetcher. But if
that's too much hardware autonomy for some religious reason, the
hardware prefetcher could be set up by software: e.g., program it to
prefetch n cache lines ahead when the load/store unit sees a load
within a certain range. And then there are the prefetch instructions.

But note that EPIC does not have such religious rules. The register
stack engine of IA-64 has quite a bit of autonomy. And caches are
also autonomous (cache line length, organization, replacement policy).

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

MitchAlsup wrote:
> On Wednesday, May 19, 2021 at 2:11:47 AM UTC-5, Terje Mathisen wrote:
>> MitchAlsup wrote:
>>> On Tuesday, May 18, 2021 at 2:25:18 PM UTC-5, Marcus wrote:
>>>> On 2021-05-18, gree...@gmail.com wrote:
>>>>> On Thu, 13 May 2021 00:25:41 +0200, David Brown <david...@hesbynett.no> sprachen:
>>>>>
>>>>>> Thus processors
>>>>>> that made these decisions at run-time (super-scaler multi-issue cpus)
>>>>>> gave you more speed for a great deal less money and power.
>>>>>
>>>>> Well no, because if you want to decide what to parallel at run-time, write code that will do that at run-time. A mix of
>>>>> self-modding code, and a recompiler. It would just be doing in software, what is currently the job of a shitload of transistors
>>>>> doing all the prediction and hyper-threading and stuff.
>>>>>
>>>>> Admittedly those transistors can do all that in real-time, or even non-time, hidden away between and behind instruction ticks.
>>>>> They do a great job. But as ever, software is better than hardware. Scrap all that stuff, that exoskeleton that drags the poor old
>>>>> x86 along screaming in agony. Instead give the transistors to EPIC stuff. You know how many transistors you'd have spare? It'd be
>>>>> halfway to running an entire application in one clock cycle. Build an absolute fuckload of execution units, ALUs, registers. Then
>>>>> get software to figure out to run as much as possible explicitly parallel. Where it can't do that, other software tries to figure
>>>>> out what it can.
>>>>
>>>> Doesn't this reasoning fall apart when you need to take into account
>>>> the dynamic nature of program execution, such as instruction latency
>>>> variations due to cache hit/miss and and branch mispredictions (unless
>>>> you want to add dozens of delay slots) etc? How do you fill unused
>>>> execution units without dynamic scheduling?
>>> <
>>> It is in arguably true that software has a much larger horizon for scheduling
>>> that HW can manage. However, there are things that HW simply takes in stride
>>> that software scheduling can never get "correct", cache misses, for example;
>>> and in particular a cache miss that runs 1 miss followed by 7 hits. Does SW
>>> schedule for the hit case or for the miss case ? HW can schedule for both
>>> cases simultaneously !
> <
>> Given that the compiler knows _exactly_ what sort of target it is
>> working towards, it should unroll code like this by a factor of 8, then
>> it can target both the first miss and the next 7 hits (but only if it
>> also pre-aligns the source address.)
> <
> But what if the sequence is 4 hits 1 miss 3 hits ??

I did note in a follow-up msg that the compiler would have to pre-align
all loops, which would add both more code and significantly slower loop
startup.

I.e. I agree with you that only the HW is in the right position to
optimize at this level.

Terje

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