Re: Stealing a Great Idea from the 6600

On 6/13/2024 3:40 PM, MitchAlsup1 wrote:

BGB wrote:
 

On 6/13/2024 11:52 AM, Stefan Monnier wrote:

This is a late reply, but optimal static ordering for N-wide may be
very non-optimal for N-1 (or N-2, etc.).  As an example, assume a
perfectly

>
AFAICT Terje was talking about scheduling for OoO CPUs, and wasn't
talking about the possible worst case situations, but about how things
usually turn out in practice.
>
For statically-scheduled or in-order CPUs, it can be indeed more
difficult to generate code that will run (almost) optimally on a
variety
of CPUs.
>

 

Yeah, you need to know the specifics of the pipeline for either optimal
>
machine code (in-order superscalar) or potentially to be able to run at
>
all (LIW / VLIW).

 

That said, on some OoO CPU's, such as when I was running a Piledriver based core, it did seem as if things were scheduled to assume an in-order CPU (such as putting other instructions between memory loads and the instructions using the results, etc), it did perform better (seemingly implying there are limits to the OoO magic).

 When doing both Mc 88120 and K9 we found lots of sequences if code
where
the scheduling to more orderly or narrower implementations were
impeding
performance on the GBOoO core.
 

In this case, scheduling as-if it were an in-order core was leading to better performance than a more naive ordering (such as directly using the results of previous instructions or memory loads, vs shuffling other instructions in between them).
Either way, seemed to be different behavior than seen on either the Ryzen or on Intel Core based CPUs (where, seemingly, the CPU does not care about the relative order).

Though, OTOH, a lot of the sorts of optimization tricks I found for the
>
Piledriver were ineffective on the Ryzen, albeit mostly because the
more
generic stuff caught up.

 

For example, I had an LZ compressor that was faster than LZ4 on that
CPU
(it was based around doing everything in terms of aligned 32-bit
dwords,
gaining speed at the cost of worse compression), but then when going over to the Ryzen, LZ4 got faster...

 It is the continuous nature of having to reschedule code every
generation
that lead to my wanting the compiler to just spit out correct code and
in the fewest number of instructions that lead to a lot of My 66000
architecture and microarchitectures.
 

Mostly works for x86-64 as well.
Though, I had noted that the optimization strategies that worked well on MSVC + Piledriver, continue to work effectively on my custom ISA / core.

Like, seemingly all my efforts in "aggressively optimizing" some things
>
became moot simply by upgrading my PC.

 I want to compile once and then use forever (in a dynamic library).
 

Some of it was optimizing the design tradeoffs, rather than ASM code.
One example was an LZ compressor:
   Encoded stream was expressed entirely as 32-bit DWORDs;
   Decoded data existed as DWORDs;
   Decoding was basically copying DWORDs around.
For some types of data, it worked well enough (but, for ASCII text, it was dismal...).
It would pull off around 3GB/sec on the AMD FX I was running at the time, whereas LZ4 was generally only around 1GB/s.
On the Ryzen, both jump to around 3.4 GB/s for similar data (for larger decompression, this also seems to be the limit). For most cases, LZ compressors seem to max out at a point near that of memcpy speed, though highly repetitive data can exceed memcpy speed and start to approach "memset()" speed (around 7GB/s or so).
Had also had a video codec that operated in this area (gigapixel/second on the FX). Also decrowned in a similar way.
Still turned out to not be all that usable on the BJX2 core though, mostly because it used a Rice coder for command and color endpoint data, and the Rice coder wasn't fast enough. Technically it was a more advanced form of color-cell encoder.
I had also investigated CRAM and LZ compressed CRAM. While CRAM is fast to decode, it isn't so great for IO bandwidth, which also became a limiting factor.
Had OK results with a format that was kinda like:
   pppppp00  //4x4 pattern from fixed pattern table, reused endpoints
   pppppp10  aaaaaaaa bbbbbbbb //4x4 pattern, 2 color endpoints.
   ...
Where, the endpoint colors were pulled from a 256-color color-palette; and the codec would treat 4x4x1 blocks as special (rather than the default). There were also "flat run of color A" and "flat run of color B", along with delta/skip blocks (the handling of delta is to double-buffer the image and copy blocks from one to another; unlike CRAM which merely copies new blocks on top of the prior frame with the option to skip over blocks).
Well, along with runs of 2x2x1 blocks (4 bits per 4x4 pixel block, each selecting one of the color endpoints for each 2x2 sub-block); etc.
The resulting image was then also LZ compressed, generally with my byte-oriented RP2 compressor (LZ4 also works, but gives worse compression).
The pattern table was generally based on using an X and Y frequency and X/Y polarity, along similar lines to single-point IDCT coefficients; which would unpack (via a table lookup) into the corresponding 4x4x1 patterns.
This was able to beat LZ+CRAM in terms of Q/bpp while having a similar computational cost in the decoder (and was fast enough to consistently pull off 320x200@16Hz video playback on my BJX2 core).
One minor issue at the time was that the encoder would attempt to dynamically optimize the color palette which could lead to ugliness when the scene changed and the color-palette no longer matched very well (the palette was updated only on I-Frames). A potentially better option might have been to use a global palette, or select between one of several generic palettes (allowing some optimization, while limiting the "badness" when it doesn't match up well).
...

....