On Monday, July 12, 2021 at 8:34:58 PM UTC-5, luke.l...@gmail.com wrote:
> On Tuesday, July 13, 2021 at 2:01:34 AM UTC+1, MitchAlsup wrote:
> > On Monday, July 12, 2021 at 7:51:42 PM UTC-5, luke.l...@gmail.com wrote:
> .
> > > we'll be adding SIN and COS etc because 3D. although.. aren't these supposed to be expensive latency even in hardware (like divide?) and so best cached in tables anyway?
> > <
> > While they are FDIV-like in latency the FFTs can be arranged so that these are
> > initialized outside of the innermost loop, which considerably decreases the costs.
> ohh yehyehyeh, seen examples like that.
> > And if the FFT is a big data set, each inner loop will totally trash the L1 and most
> > of the L2 caches, so having these in tables can be significantly more expensive
> > than a cache hitting LD; and at this point the instructions are higher performing....
> interesting. would a 4 way set associative L1 cache not help?
<
Not "that" much. It is a capacity problem. A radix 2 FFT accesses 4 complex data points
performs "some" math and stores them back. Then it accesses the next 4 data points
in 4× strip-mine fashion. So that other than having 4 pointers into memory, it is a typical
strip mine type of FP memory access problem.
<
4-sets will help along the fringes, but not by a lot.
<
< i am keenly aware that the FFT hits the same power of 2 point, so if there are say 64 cache lines it is ABSOLUTELY guaranteed that for large FFTs the exact same cache line is going to get hammered.
<
you need to add the words "a lot" just after "hammered".
<
> > <
> > Also note: USPTO 10,761,806 has been issued which covers how to do these
> > at FDIV speeds. I am willing to sell licenses for less than it will cost you to
> > assign an engineer to develop noninfrigning implementation. We should take
> > this off line.......
<
> cando, this will be something the commercial operation would look into when established. Libre-SOC is NLnet Grant funded (charitable foundation) and a Libre/Open R&D group.
>
> l.

On Tuesday, July 13, 2021 at 2:55:16 AM UTC+1, MitchAlsup wrote:
> On Monday, July 12, 2021 at 8:34:58 PM UTC-5, luke.l...@gmail.com wrote:
> > On Tuesday, July 13, 2021 at 2:01:34 AM UTC+1, MitchAlsup wrote:

> > > And if the FFT is a big data set, each inner loop will totally trash the L1 and most
> > > of the L2 caches, so having these in tables can be significantly more expensive
> > > than a cache hitting LD; and at this point the instructions are higher performing....
> > interesting. would a 4 way set associative L1 cache not help?
> <
> Not "that" much. It is a capacity problem. A radix 2 FFT accesses 4 complex data points
> performs "some" math and stores them back. Then it accesses the next 4 data points
> in 4× strip-mine fashion. So that other than having 4 pointers into memory, it is a typical
> strip mine type of FP memory access problem.

arrrgh i remember now, i did the LDST analysi...^W guesswork based on DFT, not full complex FFT.

mmm... thinkthink...

ok the analysis for DFT went something like this:

* for RADIX16 data can be loaded contiguously in place.
* let us set the max inplace size at 16 based on register file size
* therefore to do RADIX32 you must use recursion:
- perform 2 RADIX16s
- perform a last layer (outer loop) butterfly
* the two inner RADIX16s have to be offset odd and even.

now, let us extend that to RADIX-1024. this requires (1024/16) leaf-node RADIX16s each one taking data *every 16th element*.

here therefore is where the cache lines get regular-spaced hammering (a lot). RADIX-16, by spacing out every 16th element, if there are 64 L1 cache lines, any one of those RADIX-16s will try to fit all 16 elements into only (say) 4 cache lines. if however you did RADIX-8 that tries to fit into double that number of cache lines.

this is dreadful.

does the situation improve if using a bitreversed LOAD sequence?

l.

On Tuesday, July 13, 2021 at 2:39:30 AM UTC+1, MitchAlsup wrote:

> As a point of comparison, My 66000 has exactly 61 instructions total.

Power ISA has popcount (glad i sootted the typo in that one from this dreadful peck peck phone), count leading zeros, count trailing zeros, bpermd, 12 variants of add/subtract because it has carry-in and carry-out, 3 BCD instructions, Condition Code logical operators, Indexed as well as immediate LDST *and* LD-with-update, it is... extensive.

Condition Codes and the Indexed and update LDSTs save an awful lot of instructions for the kinds of workloads it is put to.

is there a "summary card" around anywhere online with the 66000 ISA?

l.

On 7/12/2021 10:03 PM, luke.l...@gmail.com wrote:
> On Tuesday, July 13, 2021 at 2:39:30 AM UTC+1, MitchAlsup wrote:
>
>> As a point of comparison, My 66000 has exactly 61 instructions total.
>
> Power ISA has popcount (glad i sootted the typo in that one from this dreadful peck peck phone), count leading zeros, count trailing zeros, bpermd, 12 variants of add/subtract because it has carry-in and carry-out, 3 BCD instructions, Condition Code logical operators, Indexed as well as immediate LDST *and* LD-with-update, it is... extensive.
>
> Condition Codes and the Indexed and update LDSTs save an awful lot of instructions for the kinds of workloads it is put to.
>
> is there a "summary card" around anywhere online with the 66000 ISA?
>
> l.
>

apples vs. bananas. Is "instruction" a semantic notion, or an encoding one?

When My66 casts a CARRY over an ADD, is that still an ADD?
Well, yes, it still has the same binary encoding.
Well, no, it does a different job.

Mitch is counting it as an ADD, and so gets a lower "instruction count"
than an ISA that encodes the same job as an ADC.

Mill "load" functionality comes with independent semantic variants:
with or without predication
with a base register or a pointer from the belt
with or without an index from the belt
with one of byte/half/word/double/quad data width
with or without index scaling
with one of 0/1/2/4 byte offset

How many "instructions" does this comprise?

We call the cross-product of these semantic possibilities the "models".
There are well over a thousand different models in the Mill ISA. In all,
does Mill or My66 need more or less entropy to express a "load" operation?

Counts of ISA instructions don't tell you anything. Don't get sucked
into a meaningless pissing contest.

MitchAlsup <MitchAlsup@aol.com> schrieb:

> Also note: USPTO 10,761,806 has been issued which covers how to do these
> at FDIV speeds.

Congratulations!

People should now be beating a path to your door.

On Tuesday, July 13, 2021 at 6:43:18 AM UTC+1, Ivan Godard wrote:
> On 7/12/2021 10:03 PM, luke.l...@gmail.com wrote:

> Mill "load" functionality comes with independent semantic variants:
> with or without predication
> with a base register or a pointer from the belt
> with or without an index from the belt
> with one of byte/half/word/double/quad data width
> with or without index scaling
> with one of 0/1/2/4 byte offset
>
> How many "instructions" does this comprise?

a lot :)

> We call the cross-product of these semantic possibilities the "models".

in SVP64 it's well north of a quarter of a million: that's just what a 24-bit
prefix will do to a 32-bit (pre-existing, suffixed) scalar instruction set.
including REMAP, SWIZZLE and others it's probably more like several
million.

> There are well over a thousand different models in the Mill ISA. In all,
> does Mill or My66 need more or less entropy to express a "load" operation?
>
> Counts of ISA instructions don't tell you anything. Don't get sucked
> into a meaningless pissing contest.

i know where Mitch is coming from: simplicity of the ISA decoder.
Power ISA is a PIG to decode into Micro-Ops: 4,000 gates *and
we haven't added FP yet*.

l.

On Monday, July 12, 2021 at 11:52:41 PM UTC-5, luke.l...@gmail.com wrote:
> On Tuesday, July 13, 2021 at 2:55:16 AM UTC+1, MitchAlsup wrote:
> > On Monday, July 12, 2021 at 8:34:58 PM UTC-5, luke.l...@gmail.com wrote:
> > > On Tuesday, July 13, 2021 at 2:01:34 AM UTC+1, MitchAlsup wrote:
>
> > > > And if the FFT is a big data set, each inner loop will totally trash the L1 and most
> > > > of the L2 caches, so having these in tables can be significantly more expensive
> > > > than a cache hitting LD; and at this point the instructions are higher performing....
> > > interesting. would a 4 way set associative L1 cache not help?
> > <
> > Not "that" much. It is a capacity problem. A radix 2 FFT accesses 4 complex data points
> > performs "some" math and stores them back. Then it accesses the next 4 data points
> > in 4× strip-mine fashion. So that other than having 4 pointers into memory, it is a typical
> > strip mine type of FP memory access problem.
> arrrgh i remember now, i did the LDST analysi...^W guesswork based on DFT, not full complex FFT.
>
> mmm... thinkthink...
>
> ok the analysis for DFT went something like this:
>
> * for RADIX16 data can be loaded contiguously in place.
> * let us set the max inplace size at 16 based on register file size
> * therefore to do RADIX32 you must use recursion:
> - perform 2 RADIX16s
> - perform a last layer (outer loop) butterfly
> * the two inner RADIX16s have to be offset odd and even.
>
> now, let us extend that to RADIX-1024. this requires (1024/16) leaf-node RADIX16s each one taking data *every 16th element*.
>
> here therefore is where the cache lines get regular-spaced hammering (a lot). RADIX-16, by spacing out every 16th element, if there are 64 L1 cache lines, any one of those RADIX-16s will try to fit all 16 elements into only (say) 4 cache lines. if however you did RADIX-8 that tries to fit into double that number of cache lines.
>
> this is dreadful.
>
> does the situation improve if using a bitreversed LOAD sequence?
<
There is an in-place data manipulation that basically has to touch everything in the array
sooner (decimation in time) or later (decimation in frequency). So the only real difference
is WHEN you run into the complete strip mining of the cache footprint.
>
> l.

On Tuesday, July 13, 2021 at 12:03:53 AM UTC-5, luke.l...@gmail.com wrote:
> On Tuesday, July 13, 2021 at 2:39:30 AM UTC+1, MitchAlsup wrote:
>
> > As a point of comparison, My 66000 has exactly 61 instructions total.
> Power ISA has popcount (glad i sootted the typo in that one from this dreadful peck peck phone), count leading zeros, count trailing zeros, bpermd, 12 variants of add/subtract because it has carry-in and carry-out, 3 BCD instructions, Condition Code logical operators, Indexed as well as immediate LDST *and* LD-with-update, it is... extensive.
>
> Condition Codes and the Indexed and update LDSTs save an awful lot of instructions for the kinds of workloads it is put to.
>
> is there a "summary card" around anywhere online with the 66000 ISA?
<
No, but I have something more like "Principles of operation" (2 *.pdfs about 336 pages)
Chapter 4 is the summary card (18 pages)
>
> l.

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:

> I am certainly not an expert in this area, but isn't complex used
> much more frequently than Quaternions or Octonerions?

Quaternions are routinely used to represent orientation in
3-space, for example in spacecraft flight software.

On Friday, July 16, 2021 at 5:00:43 AM UTC-6, Tim Rentsch wrote:
> Stephen Fuld <sf...@alumni.cmu.edu.invalid> writes:

> > I am certainly not an expert in this area, but isn't complex used
> > much more frequently than Quaternions or Octonerions?

> Quaternions are routinely used to represent orientation in
> 3-space, for example in spacecraft flight software.

I do remember quaternions being mentioned in a book on
mathematics for writing video games.

However, quaternion multiplication produces the cross
product as the imaginary part, and the dot product as
the real part; they have to be separated out before a
second multplication, or things will become messed up.

So what really happens when using quaternions is that
vector calculus operations are being done which it would
probably make more sense to implement directly.

On the other hand, complex numbers are nearly ubiquitous,
being fundamental to calculus.

Caley's octaves - now often called octonions, although in
Caley's day, that name was taken for something else that
is completely forgotten nowadays - are indeed hardly used
at all, although they are noted as an example of a division
algebra.

John Savard

On Saturday, July 17, 2021 at 8:17:08 AM UTC-6, Quadibloc wrote:

> Caley's octaves

Oops, Cayley.

John Savard

Quadibloc <jsavard@ecn.ab.ca> writes:

> On Friday, July 16, 2021 at 5:00:43 AM UTC-6, Tim Rentsch wrote:
>
>> Stephen Fuld <sf...@alumni.cmu.edu.invalid> writes:
>>
>>> I am certainly not an expert in this area, but isn't complex used
>>> much more frequently than Quaternions or Octonerions?
>>
>> Quaternions are routinely used to represent orientation in
>> 3-space, for example in spacecraft flight software.
>
> I do remember quaternions being mentioned in a book on
> mathematics for writing video games.
>
> However, quaternion multiplication produces the cross
> product as the imaginary part, and the dot product as
> the real part; they have to be separated out before a
> second multplication, or things will become messed up.

This comment is something of a non sequitur. Quaternions are
values with four components. Quaternion multiplication takes two
four-component values in and produces a single four-component value
out; each of the four output components involves three additions
and four multiplications, and furthermore each output component
involves all eight components (in different combinations) of the
two input values. If someone wants to think of quaternion
multiplication as involving (in part) dot products and cross
products, that might be useful for a mental understanding, but it
is not necessary either for understanding or for implementing the
operation of quaternion multiplication.

> So what really happens when using quaternions is that
> vector calculus operations are being done which it would
> probably make more sense to implement directly.

I can tell you from first hand experience that implementing
quaternion multiplication does not involve any of the usual vector
operations. It's just straight adds and multiplies.

> On the other hand, complex numbers are nearly ubiquitous,
> being fundamental to calculus.

Complex numbers are often used in mathematics, but less so in
software. In the mathematical domain, complex numbers behave
perfectly. In the programming domain, complex numbers can easily
lead to problems of cancellation and numerical stability. It's a
dirty little secret that implementing complex multiplication and
division is a lot more difficult than it might appear at first
blush, because of cancellation and range problems. Using complex
numbers often simplifies mathematics, but can easily complicate
programming.

Note that quaternions do not have these numerical problems, as they
are typically used, because quaternion values are normalized to
have unit length. Multiplying two quaternions of unit length
produces an output that is also of unit length, so they tend to
be much better behaved than arbitrary complex values.

Besides which, all I said is that quaternions are routinely used to
represent orientation in 3-space, which is true in both video game
software and in spacecraft control software.