An AI bot has figured out some faster sorting algorithms.

https://www.nature.com/articles/s41586-023-06004-9

Looking at the C++* code output from the paper::

void variable_sort_2( int length, int *a )
{ switch( length )
{
case 0:
case 1:
return;
case 2:
int temp = a[0];
a[0] = (a[1] < a[0] ) ? a[1] : a[0];
a[1] = (a[1] < temp ) ? temp : a[1];
}
}

There is x86 asm code in the article, consisting of 11 instructions.

My 66000 ASM

variable_sort_2:
CMP R3,R1,#2
PLT R3,TTTTTT
LD R4,[R2,0]
LD R5,[R2,4]
MAX R6,R4,R5
MIN R7,R4,R5
ST R7,[R2,0]
ST R5,[R2,4]
RET

For a count of 9 instructions.

(*) it looks like C code to me instead of C++ code........

On 6/7/2023 4:40 PM, MitchAlsup wrote:
> An AI bot has figured out some faster sorting algorithms.
>
> https://www.nature.com/articles/s41586-023-06004-9
>
> Looking at the C++* code output from the paper::
>
> void variable_sort_2( int length, int *a )
> {
> switch( length )
> {
> case 0:
> case 1:
> return;
> case 2:
> int temp = a[0];
> a[0] = (a[1] < a[0] ) ? a[1] : a[0];
> a[1] = (a[1] < temp ) ? temp : a[1];
> }
> }
>
> There is x86 asm code in the article, consisting of 11 instructions.
>
> My 66000 ASM
>
> variable_sort_2:
> CMP R3,R1,#2
> PLT R3,TTTTTT
> LD R4,[R2,0]
> LD R5,[R2,4]
> MAX R6,R4,R5
> MIN R7,R4,R5
> ST R7,[R2,0]
> ST R5,[R2,4]
> RET
>
> For a count of 9 instructions.
>

Hmm, if "hand compiling" (very loose translation):
CMPGT 1, R4 //1c
BF .L0 //2c (*)
MOV.L (R5, 0), R6 //2c
MOV.L (R5, 4), R7 //3c
CMPGT R7, R6 //1c
MOV.L?T R7, (R5, 0) //1c
MOV.L?T R6, (R5, 4) //1c
.L0: RTS //2c

Length: 8 ops.
Latency: around 13 clock cycles (best case).

*: Depending on branch predictor (2c | 8c).
"RTS?F" could have been used, but this would have ended up with a higher
total latency.

> (*) it looks like C code to me instead of C++ code........

Yeah.

If I were to write similar in C:
void variable_sort_2(int length, int *arr)
{ int t0, t1;
if(length>1)
{
t0=arr[0]; t1=arr[1];
if(t0>t1)
{ arr[0]=t1; arr[1]=t0; }
}
}

Could generalize it further (to larger N), but decided to leave it out
(starts getting pretty hairy pretty quick).

In other news, generalized the:
long long x, y;
y=x*10;
Transform to handle all patterns up to:
y=(x<<S0)+(x<<S1)+(x<<S2)+(x<<S3);
Which can cover "most" of the values between 3 and 64 (but drops off
pretty quickly for larger values).

Despite its limitations, it seems to have an unexpectedly high hit rate
for long-long multiply.
Granted, the most common numbers in this case seem to be:
35, 10, 3, 5, 2097, ...

Excluding powers of 2 which are turned into shifts.

I guess leaving an open question of how many more "obvious cases" I may
have missed...

....

MitchAlsup wrote:
> An AI bot has figured out some faster sorting algorithms.
>
> https://www.nature.com/articles/s41586-023-06004-9
>
> Looking at the C++* code output from the paper::
>
> void variable_sort_2( int length, int *a )
> {
> switch( length )
> {
> case 0:
> case 1:
> return;
> case 2:
> int temp = a[0];
> a[0] = (a[1] < a[0] ) ? a[1] : a[0];
> a[1] = (a[1] < temp ) ? temp : a[1];
> }
> }

This is branchless sorting, something I started to investigate decades
ago: Every time I've done so I've found that since I force write
operations to store back the sorted pair, even when it was already in
order, the cost of those stores outweigh the advantage I got from being
branchless.

Things might be different now, but I did start with the assumption that
stores back to an already $L1 resident cache line would be very close to
free.

I have seen similar effects from branchless compressed token extraction,
where I keep reloading the source words even when the source
byte/word/dword index is the same, and here I also have big problems
beating naive code based on branch prediction working well.

> There is x86 asm code in the article, consisting of 11 instructions.
>
> My 66000 ASM
>
> variable_sort_2:
> CMP R3,R1,#2
> PLT R3,TTTTTT
> LD R4,[R2,0]
> LD R5,[R2,4]
> MAX R6,R4,R5
> MIN R7,R4,R5
> ST R7,[R2,0]
> ST R5,[R2,4]
> RET
>
> For a count of 9 instructions.

That's nice, but see my caveat about the actual cost of "free" stores.

Terje

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

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
> MitchAlsup wrote:
>> An AI bot has figured out some faster sorting algorithms.
>>
>> https://www.nature.com/articles/s41586-023-06004-9
>>
>> Looking at the C++* code output from the paper::
>>
>> void variable_sort_2( int length, int *a )
>> {
>> switch( length )
>> {
>> case 0:
>> case 1:
>> return;
>> case 2:
>> int temp = a[0];
>> a[0] = (a[1] < a[0] ) ? a[1] : a[0];
>> a[1] = (a[1] < temp ) ? temp : a[1];
>> }
>> }
>
> This is branchless sorting, something I started to investigate decades
> ago: Every time I've done so I've found that since I force write
> operations to store back the sorted pair, even when it was already in
> order, the cost of those stores outweigh the advantage I got from being
> branchless.
>
> Things might be different now, but I did start with the assumption that
> stores back to an already $L1 resident cache line would be very close to
> free.
>
> I have seen similar effects from branchless compressed token extraction,
> where I keep reloading the source words even when the source
> byte/word/dword index is the same, and here I also have big problems
> beating naive code based on branch prediction working well.
>
>
>> There is x86 asm code in the article, consisting of 11 instructions.
>>
>> My 66000 ASM
>>
>> variable_sort_2:
>> CMP R3,R1,#2
>> PLT R3,TTTTTT
>> LD R4,[R2,0]
>> LD R5,[R2,4]
>> MAX R6,R4,R5
>> MIN R7,R4,R5
>> ST R7,[R2,0]
>> ST R5,[R2,4]
>> RET
>>
>> For a count of 9 instructions.
>
> That's nice, but see my caveat about the actual cost of "free" stores.

Hmm... so better code could then be

cmp r1,r1,#2
pne r1,0,FFFFFF
ldsw r1,[r2]
ldsw r3,[r2,4]
cmp r4,r1,r3
ple r4,0,FF
stw r3,[r2]
stw r1,[r2,4]
ret

? Also branchless, and does not do the store if the condition is
not fulfilled.

MitchAlsup wrote:
> An AI bot has figured out some faster sorting algorithms.
>
> https://www.nature.com/articles/s41586-023-06004-9

Ummm... in fig 3.b they show the original sort3 result as

A = mem[0]
B = mem[1]
C = mem[2]

mem[0] = min(A,B,C)
mem[1] = max(min(A,C),B)
mem[2] = max(A,C)

and in fig 3.c they show the AI optimized sort3 result as

mem[0] = min(A,B)
mem[1] = max(min(A,C),B)
mem[2] = max(A,C)

If initially A=2, B=3, C=1 then the original produces

mem[0] = min(1,2,3) = 1
mem[1] = max(min(2,1),3) = 3
mem[2] = max(2,1) = 2

and the AI optimized produces

mem[0] = min(2,3) = 2
mem[1] = max(min(2,1),3) = 3
mem[2] = max(2,1) = 2

neither of them is the correct ascending sort order.

On 2023-06-07 kl. 23:40, MitchAlsup wrote:
> An AI bot has figured out some faster sorting algorithms.
>
> https://www.nature.com/articles/s41586-023-06004-9
>
> Looking at the C++* code output from the paper::
>
> void variable_sort_2( int length, int *a )
> {
> switch( length )
> {
> case 0:
> case 1:
> return;
> case 2:
> int temp = a[0];
> a[0] = (a[1] < a[0] ) ? a[1] : a[0];
> a[1] = (a[1] < temp ) ? temp : a[1];
> }
> }
>
> There is x86 asm code in the article, consisting of 11 instructions.
>
> My 66000 ASM
>
> variable_sort_2:
> CMP R3,R1,#2
> PLT R3,TTTTTT
> LD R4,[R2,0]
> LD R5,[R2,4]
> MAX R6,R4,R5
> MIN R7,R4,R5
> ST R7,[R2,0]
> ST R5,[R2,4]
> RET
>
> For a count of 9 instructions.
>
> (*) it looks like C code to me instead of C++ code........

For MRISC32 I get one branch:

variable_sort_2:
sne r1, r1, #2
bs r1, 1f
ldw r3, [r2]
ldw r1, [r2, #4]
min r4, r1, r3
max r1, r1, r3
stw r4, [r2]
stw r1, [r2, #4]
1: ret

/Marcus

On 6/8/2023 12:26 AM, Terje Mathisen wrote:
> MitchAlsup wrote:
>> An AI bot has figured out some faster sorting algorithms.
>>
>> https://www.nature.com/articles/s41586-023-06004-9
>>
>> Looking at the C++* code output from the paper::
>>
>> void variable_sort_2( int length, int *a )
>> {
>>       switch( length )
>>       {
>>        case 0:
>>        case 1:
>>                      return;
>>        case 2:
>>                      int temp = a[0];
>>                      a[0] = (a[1] < a[0] ) ? a[1] : a[0];
>>                      a[1] = (a[1] < temp ) ? temp : a[1];
>>       }
>> }
>
> This is branchless sorting, something I started to investigate decades
> ago: Every time I've done so I've found that since I force write
> operations to store back the sorted pair, even when it was already in
> order, the cost of those stores outweigh the advantage I got from being
> branchless.
>
> Things might be different now, but I did start with the assumption that
> stores back to an already $L1 resident cache line would be very close to
> free.

Note that the paper did give actual, experimental results. They showed
a not necessarily huge, but statistically significant improvement.

https://www.nature.com/articles/s41586-023-06004-9#Sec6

and the data given in table 1 linked to in that section.

There is some more discussion of the results in the news release related
to the article at

https://www.nature.com/articles/d41586-023-01883-4

together with a comment in the last paragraph that they would like to
apply the same methods to hardware design!

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

Stephen Fuld wrote:
> On 6/8/2023 12:26 AM, Terje Mathisen wrote:
>> MitchAlsup wrote:
>>> An AI bot has figured out some faster sorting algorithms.
>>>
>>> https://www.nature.com/articles/s41586-023-06004-9
>>>
>>> Looking at the C++* code output from the paper::
>>>
>>> void variable_sort_2( int length, int *a )
>>> {
>>>       switch( length )
>>>       {
>>>        case 0:
>>>        case 1:
>>>                      return;
>>>        case 2:
>>>                      int temp = a[0];
>>>                      a[0] = (a[1] < a[0] ) ? a[1]
>>> : a[0];
>>>                      a[1] = (a[1] < temp ) ? temp
>>> : a[1];
>>>       }
>>> }
>>
>> This is branchless sorting, something I started to investigate decades
>> ago: Every time I've done so I've found that since I force write
>> operations to store back the sorted pair, even when it was already in
>> order, the cost of those stores outweigh the advantage I got from
>> being branchless.
>>
>> Things might be different now, but I did start with the assumption
>> that stores back to an already $L1 resident cache line would be very
>> close to free.
>
> Note that the paper did give actual, experimental results.  They showed
> a not necessarily huge, but statistically significant improvement.

That's great, I'm reading the article now!
>
> https://www.nature.com/articles/s41586-023-06004-9#Sec6
>
> and the data given in table 1 linked to in that section.
>
> There is some more discussion of the results in the news release related
> to the article at
>
> https://www.nature.com/articles/d41586-023-01883-4

I'll have to check that more closely, but my immediate reaction for the
first part (better latency for VarSortN than human code) is that (a)
their assumption that human code doesn't take advantage of previous
compares is at least flawed, but more importantly, branchless x86 code
that uses CMOVs to get rid of the branches are almost always beaten by
less sophisticated code which does use branching to skip alread-sorted
parts.

I.e. I have had to work hard to generate random or even pessimal inputs
to get consistent speedups.

More importantly, their comparisons are always against human branchless
code, not also againsts hybrid/branchy code where the actual input data
strongly impacts the results. If they can use this approach to beat the
big iron sorting benchmarks, then they have something really worthwhile!

They emphasize how VarSort4 works by sorting the first 3 elements, then
adding in the last element in the length=4 case, but this is afaik just
a final insertion sort. Not at all surprisingly, this saves a lot of
instructions vs having to write and branch to three totally separate
Sort2, Sort3, Sort4 sections.

I'm in fact more optimistic about sorting lengths that fit inside a SIMD
register, using MIN/MAX operations or parallel compares and shuffles.

>
> together with a comment in the last paragraph that they would like to
> apply the same methods to hardware design!

This is probably more relevant: When you (i.e Mitch) can apply hw
resources in parallel, finding shorter paths to the final results looks
to me a lot like network optimizations that VLSI tools have employed for
decades.

Terje

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

I finally got to the part where they got a measured 1.7% speedup for
large sorts done with LLVM libc++ sort, with their patch accepted.

Well done, even if less amazing than the huge initial claims.

Re the final part about VarInt codeing/decoding, this was recently done
with some quite clever SIMD code, so that large parts could be handled
without branches or additiona loads.

Terje

Terje Mathisen wrote:
> Stephen Fuld wrote:
>> On 6/8/2023 12:26 AM, Terje Mathisen wrote:
>>> MitchAlsup wrote:
>>>> An AI bot has figured out some faster sorting algorithms.
>>>>
>>>> https://www.nature.com/articles/s41586-023-06004-9
>>>>
>>>> Looking at the C++* code output from the paper::
>>>>
>>>> void variable_sort_2( int length, int *a )
>>>> {
>>>>       switch( length )
>>>>       {
>>>>        case 0:
>>>>        case 1:
>>>>                      return;
>>>>        case 2:
>>>>                      int temp = a[0];
>>>>                      a[0] = (a[1] < a[0] ) ?
>>>> a[1] : a[0];
>>>>                      a[1] = (a[1] < temp ) ?
>>>> temp : a[1];
>>>>       }
>>>> }
>>>
>>> This is branchless sorting, something I started to investigate
>>> decades ago: Every time I've done so I've found that since I force
>>> write operations to store back the sorted pair, even when it was
>>> already in order, the cost of those stores outweigh the advantage I
>>> got from being branchless.
>>>
>>> Things might be different now, but I did start with the assumption
>>> that stores back to an already $L1 resident cache line would be very
>>> close to free.
>>
>> Note that the paper did give actual, experimental results.  They
>> showed a not necessarily huge, but statistically significant improvement.
>
> That's great, I'm reading the article now!
>>
>> https://www.nature.com/articles/s41586-023-06004-9#Sec6
>>
>> and the data given in table 1 linked to in that section.
>>
>> There is some more discussion of the results in the news release
>> related to the article at
>>
>> https://www.nature.com/articles/d41586-023-01883-4
>
> I'll have to check that more closely, but my immediate reaction for the
> first part (better latency for VarSortN than human code) is that (a)
> their assumption that human code doesn't take advantage of previous
> compares is at least flawed, but more importantly, branchless x86 code
> that uses CMOVs to get rid of the branches are almost always beaten by
> less sophisticated code which does use branching to skip alread-sorted
> parts.
>
> I.e. I have had to work hard to generate random or even pessimal inputs
> to get consistent speedups.
>
> More importantly, their comparisons are always against human branchless
> code, not also againsts hybrid/branchy code where the actual input data
> strongly impacts the results. If they can use this approach to beat the
> big iron sorting benchmarks, then they have something really worthwhile!
>
> They emphasize how VarSort4 works by sorting the first 3 elements, then
> adding in the last element in the length=4 case, but this is afaik just
> a final insertion sort. Not at all surprisingly, this saves a lot of
> instructions vs having to write and branch to three totally separate
> Sort2, Sort3, Sort4 sections.
>
> I'm in fact more optimistic about sorting lengths that fit inside a SIMD
> register, using MIN/MAX operations or parallel compares and shuffles.
>
>>
>> together with a comment in the last paragraph that they would like to
>> apply the same methods to hardware design!
>
> This is probably more relevant: When you (i.e Mitch) can apply hw
> resources in parallel, finding shorter paths to the final results looks
> to me a lot like network optimizations that VLSI tools have employed for
> decades.
>
> Terje
>

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

On Thursday, June 8, 2023 at 12:40:22 AM UTC+3, MitchAlsup wrote:
> An AI bot has figured out some faster sorting algorithms.
>
> https://www.nature.com/articles/s41586-023-06004-9
>
> Looking at the C++* code output from the paper::
>
> void variable_sort_2( int length, int *a )
> {
> switch( length )
> {
> case 0:
> case 1:
> return;
> case 2:
> int temp = a[0];
> a[0] = (a[1] < a[0] ) ? a[1] : a[0];
> a[1] = (a[1] < temp ) ? temp : a[1];
> }
> }
>
> There is x86 asm code in the article, consisting of 11 instructions.
>
> My 66000 ASM
>
> variable_sort_2:
> CMP R3,R1,#2
> PLT R3,TTTTTT
> LD R4,[R2,0]
> LD R5,[R2,4]
> MAX R6,R4,R5
> MIN R7,R4,R5
> ST R7,[R2,0]
> ST R5,[R2,4]
> RET
>
> For a count of 9 instructions.
>

Your asm can be literally translated into 9 x86 (AVX) instructions.
https://godbolt.org/z/Gbz1Kh56f
However I suspect that on majority of real-word x86 cores 11 original
instructions are faster.

> (*) it looks like C code to me instead of C++ code........

To me it looks legal in both languages.

On Friday, June 9, 2023 at 9:22:34 AM UTC+3, Terje Mathisen wrote:
> I finally got to the part where they got a measured 1.7% speedup for
> large sorts done with LLVM libc++ sort, with their patch accepted.
>

I would think that for large sorts you can find 1-2 or may be even 3%
of speed by playing with "small segment" threshold that decides where
to switch from quicksort to insertion sort. But this gain will be very target
and size dependent.

> Well done, even if less amazing than the huge initial claims.

Still, to me acceptance of the patch looks like a mistake on the part
of libc++ maintainers. The gain by itself is not worth the hassle of change..
May be, there were other factors, like the new code is less messy
than the one replaced?

>
> Re the final part about VarInt codeing/decoding, this was recently done
> with some quite clever SIMD code, so that large parts could be handled
> without branches or additiona loads.
>

IMHO, for practical purposes, sorting short segment is too small part of
bigger sorts to bother with heavy optimizations.
Which does not mean that it couldn't be done for enjoyment.

On Friday, June 9, 2023 at 5:15:31 AM UTC-5, Michael S wrote:
> On Thursday, June 8, 2023 at 12:40:22 AM UTC+3, MitchAlsup wrote:
> > An AI bot has figured out some faster sorting algorithms.
> >
> > https://www.nature.com/articles/s41586-023-06004-9
> >
> > Looking at the C++* code output from the paper::
> >
> > void variable_sort_2( int length, int *a )
> > {
> > switch( length )
> > {
> > case 0:
> > case 1:
> > return;
> > case 2:
> > int temp = a[0];
> > a[0] = (a[1] < a[0] ) ? a[1] : a[0];
> > a[1] = (a[1] < temp ) ? temp : a[1];
> > }
> > }
> >
> > There is x86 asm code in the article, consisting of 11 instructions.
> >
> > My 66000 ASM
> >
> > variable_sort_2:
> > CMP R3,R1,#2
> > PLT R3,TTTTTT
> > LD R4,[R2,0]
> > LD R5,[R2,4]
> > MAX R6,R4,R5
> > MIN R7,R4,R5
> > ST R7,[R2,0]
> > ST R5,[R2,4]
> > RET
> >
> > For a count of 9 instructions.
> >
> Your asm can be literally translated into 9 x86 (AVX) instructions.
> https://godbolt.org/z/Gbz1Kh56f
> However I suspect that on majority of real-word x86 cores 11 original
> instructions are faster.
> > (*) it looks like C code to me instead of C++ code........
> To me it looks legal in both languages.
<
Which is why it is not C++ -- it uses none of the C++ features which are above C.

On 9 Jun 2023, MitchAlsup wrote
(in article<fd0b5dc1-6328-4a88-b951-98ed59bd3207n@googlegroups.com>):

> On Friday, June 9, 2023 at 5:15:31???AM UTC-5, Michael S wrote:
> > On Thursday, June 8, 2023 at 12:40:22???AM UTC+3, MitchAlsup wrote:
> > > An AI bot has figured out some faster sorting algorithms.
> > >
> > > https://www.nature.com/articles/s41586-023-06004-9
> > >
> > > Looking at the C++* code output from the paper::
> > >
> > > void variable_sort_2( int length, int *a )
> > > {
> > > switch( length )
> > > {
> > > case 0:
> > > case 1:
> > > return;
> > > case 2:
> > > int temp = a[0];
> > > a[0] = (a[1] < a[0] ) ? a[1] : a[0];
> > > a[1] = (a[1] < temp ) ? temp : a[1];
> > > }
> > > }
> > >
> > > There is x86 asm code in the article, consisting of 11 instructions.
> > >
> > > My 66000 ASM
> > >
> > > variable_sort_2:
> > > CMP R3,R1,#2
> > > PLT R3,TTTTTT
> > > LD R4,[R2,0]
> > > LD R5,[R2,4]
> > > MAX R6,R4,R5
> > > MIN R7,R4,R5
> > > ST R7,[R2,0]
> > > ST R5,[R2,4]
> > > RET
> > >
> > > For a count of 9 instructions.
> > Your asm can be literally translated into 9 x86 (AVX) instructions.
> > https://godbolt.org/z/Gbz1Kh56f
> > However I suspect that on majority of real-word x86 cores 11 original
> > instructions are faster.

KDF9, designed ca. 1960:

YA0; YA1; MAX; =YA1; =YA0; {VR;}

It sets the V flipflop if the values had to be reversed in the NEST,
"VR;" clears V if you don't care about that.
--
Bill Findlay

MitchAlsup <MitchAlsup@aol.com> writes:
>On Friday, June 9, 2023 at 5:15:31=E2=80=AFAM UTC-5, Michael S wrote:
>> On Thursday, June 8, 2023 at 12:40:22=E2=80=AFAM UTC+3, MitchAlsup wrote:=
>=20
>> > An AI bot has figured out some faster sorting algorithms.=20
>> >=20
>> > https://www.nature.com/articles/s41586-023-06004-9=20
>> >=20
>> > Looking at the C++* code output from the paper::=20
>> >=20
>> > void variable_sort_2( int length, int *a )=20
>> > {=20
>> > switch( length )=20
>> > {=20
>> > case 0:=20
>> > case 1:=20
>> > return;=20
>> > case 2:=20
>> > int temp =3D a[0];=20
>> > a[0] =3D (a[1] < a[0] ) ? a[1] : a[0];=20
>> > a[1] =3D (a[1] < temp ) ? temp : a[1];=20
>> > }=20
>> > }=20
>> >=20
>> > There is x86 asm code in the article, consisting of 11 instructions.=20
>> >=20
>> > My 66000 ASM=20
>> >=20
>> > variable_sort_2:=20
>> > CMP R3,R1,#2=20
>> > PLT R3,TTTTTT=20
>> > LD R4,[R2,0]=20
>> > LD R5,[R2,4]=20
>> > MAX R6,R4,R5=20
>> > MIN R7,R4,R5=20
>> > ST R7,[R2,0]=20
>> > ST R5,[R2,4]=20
>> > RET=20
>> >=20
>> > For a count of 9 instructions.=20
>> >
>> Your asm can be literally translated into 9 x86 (AVX) instructions.=20
>> https://godbolt.org/z/Gbz1Kh56f=20
>> However I suspect that on majority of real-word x86 cores 11 original=20
>> instructions are faster.
>> > (*) it looks like C code to me instead of C++ code........
>> To me it looks legal in both languages.
><
>Which is why it is not C++ -- it uses none of the C++ features which are ab=
>ove C.

That doesn't mean that it isn't C++. Many of the soi disant "C++ features"
are syntactic sugar. The good parts (object orientation and data encapsulation)
can be used without using all the cruft.

On Friday, June 9, 2023 at 10:45:05 AM UTC-5, Scott Lurndal wrote:
> MitchAlsup <Mitch...@aol.com> writes:
> >On Friday, June 9, 2023 at 5:15:31=E2=80=AFAM UTC-5, Michael S wrote:
> >> On Thursday, June 8, 2023 at 12:40:22=E2=80=AFAM UTC+3, MitchAlsup wrote:=
> >=20
> >> > An AI bot has figured out some faster sorting algorithms.=20
> >> >=20
> >> > https://www.nature.com/articles/s41586-023-06004-9=20
> >> >=20
> >> > Looking at the C++* code output from the paper::=20
> >> >=20
> >> > void variable_sort_2( int length, int *a )=20
> >> > {=20
> >> > switch( length )=20
> >> > {=20
> >> > case 0:=20
> >> > case 1:=20
> >> > return;=20
> >> > case 2:=20
> >> > int temp =3D a[0];=20
> >> > a[0] =3D (a[1] < a[0] ) ? a[1] : a[0];=20
> >> > a[1] =3D (a[1] < temp ) ? temp : a[1];=20
> >> > }=20
> >> > }=20
> >> >=20
> >> > There is x86 asm code in the article, consisting of 11 instructions.=20
> >> >=20
> >> > My 66000 ASM=20
> >> >=20
> >> > variable_sort_2:=20
> >> > CMP R3,R1,#2=20
> >> > PLT R3,TTTTTT=20
> >> > LD R4,[R2,0]=20
> >> > LD R5,[R2,4]=20
> >> > MAX R6,R4,R5=20
> >> > MIN R7,R4,R5=20
> >> > ST R7,[R2,0]=20
> >> > ST R5,[R2,4]=20
> >> > RET=20
> >> >=20
> >> > For a count of 9 instructions.=20
> >> >
> >> Your asm can be literally translated into 9 x86 (AVX) instructions.=20
> >> https://godbolt.org/z/Gbz1Kh56f=20
> >> However I suspect that on majority of real-word x86 cores 11 original=20
> >> instructions are faster.
> >> > (*) it looks like C code to me instead of C++ code........
> >> To me it looks legal in both languages.
> ><
> >Which is why it is not C++ -- it uses none of the C++ features which are ab=
> >ove C.
>
> That doesn't mean that it isn't C++. Many of the soi disant "C++ features"
> are syntactic sugar. The good parts (object orientation and data encapsulation)
> can be used without using all the cruft.
<
I remember a program written for the C obfuscation event many years ago
which was compliable in C, compliable in Fortran, and compliable in Pascal.
<
Does that make that program any of them ??

EricP wrote:
> MitchAlsup wrote:
>> An AI bot has figured out some faster sorting algorithms.
>>
>> https://www.nature.com/articles/s41586-023-06004-9
>
> Ummm... in fig 3.b they show the original sort3 result as
> and in fig 3.c they show the AI optimized sort3 result as
>
> neither of them is the correct ascending sort order.

I think see what they were talking about. Those figures were examples of
arbitrary sort networks of 3 and 4 variables, and nothing to do with
the sort3 and sort4 routines.

Anyway, the code AlphaDev produced is here:

https://github.com/deepmind/alphadev/blob/main/sort_functions_test.cc

and is almost the same code I would have written as it results from
doing conditional swaps. For Sort3AlphaDev my only difference is I would
put the "mov (%0), %%r8d" at the front to get the load going ASAP.
Same for the other SortN's.

So I don't see what optimization AlphaDev could have done.

Remember that CMOV is often implemented as two uOps, one to move the
source if condition True, the other to copy the original dest if False.
That creates a dependency between the original dest register and
subsequent users of that same register that is not apparent in the code.
While register MOV can sometimes be optimized away by HW,
CMOV for both the True and False paths cannot.

The actual performance issues are obscured by the assembler.
Using CSWAP as a conditional register swap macro highlights the differences.

Sort3 is uninteresting because it is just
Sort3 (a, b, c)
CSWAP_GT (a,b)
CSWAP_GT (b,c)
CSWAP_GT (a,b)

Sort4 and others are interesting because some operations can be done
in parallel if a cpu can launch multiple ALU instructions per clock.

Sort4 (a, b, c, d)
CSWAP_GT (a,b)
CSWAP_GT (c,d)
CSWAP_GT (b,c)
CSWAP_GT (a,b)
CSWAP_GT (c,d)

For ISA design, compare and swap CSWAP_cc rd,rs could probably be an
instruction along with SWAP rd,rs.

I also have Load Immediate Conditional LIC , Load Conditional LDC and
Store Conditional STC. LDC and STC have nothing to do with atomics.

LIC and LDC allow you to conditionally overwrite a register value.
STC allows you to optimize away the store if you didn't change a value.

For LDC and STC one idea I had was that rather than add a condition register
because that would mean STC had 4 source register, was to test whether
the base address register was zero/non-zero as the disable/enable.

Applied to the above register sort routines, using CSWAP replaces a MOV
and 2 CMOV. One could set register bit flags to 1 if any swap occurs.
Then later test that flag and a STC skip the write back if unchanged.
In this SortN case that's probably more trouble than its worth.

On Friday, June 9, 2023 at 11:54:51 AM UTC-5, EricP wrote:
> EricP wrote:
> > MitchAlsup wrote:
> >> An AI bot has figured out some faster sorting algorithms.
> >>
> >> https://www.nature.com/articles/s41586-023-06004-9
> >
> > Ummm... in fig 3.b they show the original sort3 result as
> > and in fig 3.c they show the AI optimized sort3 result as
> >
> > neither of them is the correct ascending sort order.
> I think see what they were talking about. Those figures were examples of
> arbitrary sort networks of 3 and 4 variables, and nothing to do with
> the sort3 and sort4 routines.
>
> Anyway, the code AlphaDev produced is here:
>
> https://github.com/deepmind/alphadev/blob/main/sort_functions_test.cc
>
> and is almost the same code I would have written as it results from
> doing conditional swaps. For Sort3AlphaDev my only difference is I would
> put the "mov (%0), %%r8d" at the front to get the load going ASAP.
> Same for the other SortN's.
>
> So I don't see what optimization AlphaDev could have done.
>
> Remember that CMOV is often implemented as two uOps, one to move the
> source if condition True, the other to copy the original dest if False.
<
This is why MAX and MIN instructions are simply better, fewer operands
just as easy a choice.
<
> That creates a dependency between the original dest register and
> subsequent users of that same register that is not apparent in the code.
> While register MOV can sometimes be optimized away by HW,
> CMOV for both the True and False paths cannot.
>
> The actual performance issues are obscured by the assembler.
<
Errrrrrr........ISA is the problem, ASM is simply how ISA is spelled using ASCII.
<
> Using CSWAP as a conditional register swap macro highlights the differences.
>
> Sort3 is uninteresting because it is just
> Sort3 (a, b, c)
> CSWAP_GT (a,b)
> CSWAP_GT (b,c)
> CSWAP_GT (a,b)
<
// All single result instructions
MAX TA,A,B
MIN TB,A,B
MAX TB,TB,C
MIN C,TB,C
MAX A,TA,TB
MIN B,TA,TB
<
I see no particular reason that MAX and MIN cannot be issued together
(in parallel) so we have 3 cycles of 2 instruction each.
>
> Sort4 and others are interesting because some operations can be done
> in parallel if a cpu can launch multiple ALU instructions per clock.
>
> Sort4 (a, b, c, d)
> CSWAP_GT (a,b)
> CSWAP_GT (c,d)
> CSWAP_GT (b,c)
> CSWAP_GT (a,b)
> CSWAP_GT (c,d)
>
> For ISA design, compare and swap CSWAP_cc rd,rs could probably be an
> instruction along with SWAP rd,rs.
<
2 results per instruction is contrary to the tenets of RISC.
And most/many of us thing condition codes are contrary to tenets of RISC.
>
> I also have Load Immediate Conditional LIC , Load Conditional LDC and
> Store Conditional STC. LDC and STC have nothing to do with atomics.
>
> LIC and LDC allow you to conditionally overwrite a register value.
> STC allows you to optimize away the store if you didn't change a value.
>
> For LDC and STC one idea I had was that rather than add a condition register
> because that would mean STC had 4 source register, was to test whether
> the base address register was zero/non-zero as the disable/enable.
>
> Applied to the above register sort routines, using CSWAP replaces a MOV
> and 2 CMOV. One could set register bit flags to 1 if any swap occurs.
> Then later test that flag and a STC skip the write back if unchanged.
> In this SortN case that's probably more trouble than its worth.

Re our recent sort thread:

https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md

cpp_vqsort_new() seems like the current winner in the generic sort
library race, with gains almost certainly well above the quoted 1.7% for
the AI-derived micro-optimizations that got into clang libc

Terje

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

MitchAlsup wrote:
> On Friday, June 9, 2023 at 11:54:51 AM UTC-5, EricP wrote:
>>
>> For ISA design, compare and swap CSWAP_cc rd,rs could probably be an
>> instruction along with SWAP rd,rs.
> <
> 2 results per instruction is contrary to the tenets of RISC.
> And most/many of us thing condition codes are contrary to tenets of RISC.

I was driven to instructions with 2-dest results by my desire to
(a) not have condition codes and (b) wanting to handle add with carry
in a straight forward way. That leads to many new wide result instructions.

I see the RISC tenets as guidelines advising designers to
consider the benefits and costs rather than hidebound dogma.
And that cost/benefit consideration is made in the context of the
logic budgets of the current day, not locked to a date mid 1980's.

Variable length instructions opens the ISA to much useful functionality
like full size immediate operands but requires a more complicated fetch
unit than fixed size. This cost is generally accepted today.

I found your arguments for the utility of store immediate instructions
convincing but that requires allowing for up to two immediates,
one for the addressing mode and one for data. The cost of that internally
is it requires extra decode logic, extra flip-flops in the front end to
hold the second immediate and extra muxes to route it, and that puts
pressure on the budget designs.

Having up to two dest registers open an ISA to a whole host of new and
useful instructions. Mostly these are double-wide results for ADD, MUL,
various shifts and bit fields. It also allows integer DIV to return
both the results and remainder, and SWAP or CSWAP, plus many others.

As to the cost of 2 dest registers, at the low end for an in-order,
single issue pipeline with 1 register write port, taking an extra clock
to write a second result does not add any complexity.

For a multi-lane OoO uArch my concern was for Rename to NOT require
two register allocation units for each lane, adding greatly to the cost
and complexity, and which would mostly sit unused burning power.

My solution is for Decode to spit out 2-dest instructions as two 1-dest uOps
split across two consecutive lanes. Rename allocates the 1-dest registers
to uOps as normal, then fuses the two pieces and outputs a single uOp to
one output lane to Dispatch.

The OoO writeback of multiple dests is no more expensive because it
already requires multiple result and forwarding buses and write ports
so that it can catch up after bubbles.

With plausable solutions for each problem area, and the costs for 2-dest
registers under control, I green lighted it for general use by new
instructions.

So "CSWAP rdX, rdY, rsA, rsB, rsCC" slides right into the ISA:
IF (rsCC) rdX = rsA, rdY = rsB ELSE rdX = rsB, rdY = rsA END IF
It needs 3 source registers, but FMA and ADD-wide already need that,
and 2 dest registers, and could be implemented as a single ALU uOp.

EricP <ThatWouldBeTelling@thevillage.com> writes:
>I was driven to instructions with 2-dest results by my desire to
>(a) not have condition codes and (b) wanting to handle add with carry
>in a straight forward way.

I have expanded my answer to that problem into a paper:
<http://www.complang.tuwien.ac.at/anton/tmp/carry.pdf>.

Of course, the question is whether you consider this answer
straightforward.

>Variable length instructions opens the ISA to much useful functionality
>like full size immediate operands but requires a more complicated fetch
>unit than fixed size. This cost is generally accepted today.

Counterexample: ARM A64 (and ARM has ample experience with
variable-size instructions).

>As to the cost of 2 dest registers, at the low end for an in-order,
>single issue pipeline with 1 register write port, taking an extra clock
>to write a second result does not add any complexity.

At least not much.

But what's the difference from

add s0 = a, b
sltu carry0 = s0,a

which also takes two cycles? Or do you have a three-input
add-with-carry? That would certainly solve the major problem that
MIPS, Alpha, and RISC-V have for this stuff, which is dealing with the
carry-in.

>For a multi-lane OoO uArch my concern was for Rename to NOT require
>two register allocation units for each lane, adding greatly to the cost
>and complexity, and which would mostly sit unused burning power.
>
>My solution is for Decode to spit out 2-dest instructions as two 1-dest uOps
>split across two consecutive lanes. Rename allocates the 1-dest registers
>to uOps as normal, then fuses the two pieces and outputs a single uOp to
>one output lane to Dispatch.

I wonder if that's what ARM are doing for their multi-result
instructions (load-pair with pre/post-indexed addressing mode consumes
three write ports).

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

On Sunday, June 11, 2023 at 10:57:39 AM UTC-4, Anton Ertl wrote:
> EricP <ThatWould...@thevillage.com> writes:
> >I was driven to instructions with 2-dest results by my desire to
> >(a) not have condition codes and (b) wanting to handle add with carry
> >in a straight forward way.
> I have expanded my answer to that problem into a paper:
> <http://www.complang.tuwien.ac.at/anton/tmp/carry.pdf>.
>
> Of course, the question is whether you consider this answer
> straightforward.
> >Variable length instructions opens the ISA to much useful functionality
> >like full size immediate operands but requires a more complicated fetch
> >unit than fixed size. This cost is generally accepted today.
> Counterexample: ARM A64 (and ARM has ample experience with
> variable-size instructions).

I just decided not to long ago to go with a fixed sized instruction because
variable length calculations became on the critical timing path for an FPGA
design. Postfixes can effectively extend the instruction with constants.

> >As to the cost of 2 dest registers, at the low end for an in-order,
> >single issue pipeline with 1 register write port, taking an extra clock
> >to write a second result does not add any complexity.
> At least not much.
>
> But what's the difference from
>
>
> add s0 = a, b
> sltu carry0 = s0,a
>
> which also takes two cycles? Or do you have a three-input
> add-with-carry? That would certainly solve the major problem that
> MIPS, Alpha, and RISC-V have for this stuff, which is dealing with the
> carry-in.
> >For a multi-lane OoO uArch my concern was for Rename to NOT require
> >two register allocation units for each lane, adding greatly to the cost
> >and complexity, and which would mostly sit unused burning power.
> >
> >My solution is for Decode to spit out 2-dest instructions as two 1-dest uOps
> >split across two consecutive lanes. Rename allocates the 1-dest registers
> >to uOps as normal, then fuses the two pieces and outputs a single uOp to
> >one output lane to Dispatch.
> I wonder if that's what ARM are doing for their multi-result
> instructions (load-pair with pre/post-indexed addressing mode consumes
> three write ports).
>
An idea I have been toying with is for some operations caching the operands
and results. So, if a divide is done the remainder is available immediately
without having to do a full divide. Works for multiply high too. I think it should
work well with reciprocal calculations too, where the same reciprocal is used
in a loop for instance.

To deal with extended precision ADD in the past I have used a three operand
ADD, combined with a carry generate instruction. The carry generate
instruction takes the same operands as the add instruction but returns the
carry out instead of the sum. It can then be added in the next instruction. It
is a bit ugly but if one really wants to do multi-word arithmetic it is possible.
I think the ADD and the carry-generate can be done in the same clock cycle
in a superscalar CPU.

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

On 6/11/2023 11:59 AM, robf...@gmail.com wrote:
> On Sunday, June 11, 2023 at 10:57:39 AM UTC-4, Anton Ertl wrote:
>> EricP <ThatWould...@thevillage.com> writes:
>>> I was driven to instructions with 2-dest results by my desire to
>>> (a) not have condition codes and (b) wanting to handle add with carry
>>> in a straight forward way.
>> I have expanded my answer to that problem into a paper:
>> <http://www.complang.tuwien.ac.at/anton/tmp/carry.pdf>.
>>
>> Of course, the question is whether you consider this answer
>> straightforward.
>>> Variable length instructions opens the ISA to much useful functionality
>>> like full size immediate operands but requires a more complicated fetch
>>> unit than fixed size. This cost is generally accepted today.
>> Counterexample: ARM A64 (and ARM has ample experience with
>> variable-size instructions).
>
> I just decided not to long ago to go with a fixed sized instruction because
> variable length calculations became on the critical timing path for an FPGA
> design. Postfixes can effectively extend the instruction with constants.
>

I went with prefixes.

If I designed another (new) variable-length ISA, it is probable I would
still go with prefixes.

Though, I would likely start (this time) with the assumption of the
32-bit instructions as baseline, and the 16-bit as a shorthand. My
encoding is currently a little messy in that (in its original form) the
32-bit instructions were themselves a prefix encoding (of two 16-bit parts).

Granted, prefixes have the downside of turning the immediate values into
confetti... But, then again, there is RISC-V with fixed-length
instructions and the immediate fields are still confetti...

Doesn't really effect the CPU too much, but admittedly is kind of a pain
for the assembler and linker (linker needing a larger number of reloc
types). Though, one can reduce the annoyance, say, by making all PC-rel
offsets either Byte or Word (depending on the op), and all GBR-Rel ops
Byte based, ... At least cutting down on the needed number of reloc types.

Well, except when the encoding rules change from one instruction to
another, which is admittedly thus far why I haven't bothered with
RISC-V's 'C' extension.

Like, RVC is sort of like someone looked at Thumb and was then like
"Hold my beer!".

One other option would be, say, to have variable length ops with a
size/form bucket, say:
000: 32-bit op, 3R Forms
001: 32-bit op, 3RI Forms
010: 64-bit op, 3R/4R/etc forms
011: 64-bit op, 3RI Forms, Imm32
100: 96-bit op, -
101: 96-bit op, 3RI Forms, Imm64

Where, say:
000z-zzzz-zzdd-dddd ssss-sstt-tttt-zzzz //3R
001z-zzzz-zzdd-dddd ssss-ssii-iiii-iiii //3RI (Imm10)

011z-zzzz-zzdd-dddd ssss-sszz-zzzz-zzzz //3RI (Imm32)
iiii-iiii-iiii-iiii iiii-iiii-iiii-iiii //Imm

101z-zzzz-zzdd-dddd ssss-sszz-zzzz-zzzz //3RI (Imm64)
iiii-iiii-iiii-iiii iiii-iiii-iiii-iiii //Imm
iiii-iiii-iiii-iiii iiii-iiii-iiii-iiii //Imm

Where, say, the Imm32 and Imm64 encodings operate in (mostly) the same
space as the 3R encodings, but will normally suppress the Rt field in
favor of an immediate. The Imm10 encodings would represent a slightly
different encoding space (likely exclusively Load/Store ops and ALU
Immediate instructions).

This would be nicer for an assembler and linker, but would implicitly
mean that the instruction stream would no longer be "self-aligning".

Say, with a self-aligning stream, if one starts decoding/disassembling
instructions from an arbitrary location in the "text" sections, then the
decoding will realign with the instruction stream within a few
instruction words (this property is useful for tools like debuggers).

>>> As to the cost of 2 dest registers, at the low end for an in-order,
>>> single issue pipeline with 1 register write port, taking an extra clock
>>> to write a second result does not add any complexity.
>> At least not much.
>>
>> But what's the difference from
>>
>>
>> add s0 = a, b
>> sltu carry0 = s0,a
>>
>> which also takes two cycles? Or do you have a three-input
>> add-with-carry? That would certainly solve the major problem that
>> MIPS, Alpha, and RISC-V have for this stuff, which is dealing with the
>> carry-in.
>>> For a multi-lane OoO uArch my concern was for Rename to NOT require
>>> two register allocation units for each lane, adding greatly to the cost
>>> and complexity, and which would mostly sit unused burning power.
>>>
>>> My solution is for Decode to spit out 2-dest instructions as two 1-dest uOps
>>> split across two consecutive lanes. Rename allocates the 1-dest registers
>>> to uOps as normal, then fuses the two pieces and outputs a single uOp to
>>> one output lane to Dispatch.
>> I wonder if that's what ARM are doing for their multi-result
>> instructions (load-pair with pre/post-indexed addressing mode consumes
>> three write ports).
>>
> An idea I have been toying with is for some operations caching the operands
> and results. So, if a divide is done the remainder is available immediately
> without having to do a full divide. Works for multiply high too. I think it should
> work well with reciprocal calculations too, where the same reciprocal is used
> in a loop for instance.
>
> To deal with extended precision ADD in the past I have used a three operand
> ADD, combined with a carry generate instruction. The carry generate
> instruction takes the same operands as the add instruction but returns the
> carry out instead of the sum. It can then be added in the next instruction. It
> is a bit ugly but if one really wants to do multi-word arithmetic it is possible.
> I think the ADD and the carry-generate can be done in the same clock cycle
> in a superscalar CPU.
>

Possible, but likely to get rather annoying, rather fast.

One almost may as well have some designated architectural scratchpad
registers in this case.

Say:
DMULU R4, R5 //MACH:MACL = R4*R5
STS MACL, R2 // R2 = MACL

But, yeah, I know of an ISA that did the multiplier this way (cough, SH).

Though, to be fair, it is less bad than doing the multiplier via MMIO
(cough, MSP430).

In my case, the 32-bit widening multiply ops generate a 64-bit result:
MULU.L R4, R5, R2 //Zero-Extended
DMULU.L R4, R5, R2 //Widening

The 64-bit ops are only available in low/high variants, and slow. Had
considered a widening variant (with a 128-bit result), but given these
were only really added for sake of the RISC-V 'M' extension, and 'M'
doesn't have widening ops, I didn't bother in this case.

Though, a widening version would at least (in theory) make it more
useful for implementing 128-bit multiply, nevermind if it would still
currently be faster to build 128-bit multiply using the 32-bit multiply
ops (but, this part could be streamlined slightly if I added helper ops
to do the high/low and high-high multiplies without needing to use a
bunch of shift instructions...).

Well, and the (slow) 64-bit multiplier was still left out to try to
shoe-horn a 3-wide version of the BJX2 core into an XC7S50 (along with a
bunch of other features).

But, I still need to find a way to shave off some more LUTs, as I want
to be able to have a CPI based camera-interface module, and I still
don't currently have the LUT budget for this.

.... decided to leave out going into the specifics of the CPI camera
interface or how the module would work (or my annoyances trying to fit
all this into the XC7S50 on the Arty S7...).

But, also annoyingly: I can't use my Nexys A7 board either, as it
doesn't have enough unassigned IO (all those
LEDs/switches/7-segment-display/VGA-port/... eating up much of the
FPGA's total IO pins). Its "sibling" (the Arty A7) mostly just leaving a
lot more of this to PMODs and similar.

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

On Sunday, June 11, 2023 at 11:59:33 AM UTC-5, robf...@gmail.com wrote:
> On Sunday, June 11, 2023 at 10:57:39 AM UTC-4, Anton Ertl wrote:

> > >Variable length instructions opens the ISA to much useful functionality
> > >like full size immediate operands but requires a more complicated fetch
> > >unit than fixed size. This cost is generally accepted today.
> > Counterexample: ARM A64 (and ARM has ample experience with
> > variable-size instructions).
<
> I just decided not to long ago to go with a fixed sized instruction because
> variable length calculations became on the critical timing path for an FPGA
> design. Postfixes can effectively extend the instruction with constants.
<
I found an encoding scheme whereby determining the length of an
instruction is 4 gates of delay covering 1-5 word instructions. It is
entirely parallel and can be treeified at 1 gate per doubling of the
number of instructions decoded. Thus, in 1 stage of logic one can
parse 16-instructions out of 32-words.
<
Now, of course, all this takes place in unary form, which is the natural
form of hardware parsing of bit strings into useful containers. Why unary ?
Unary becomes the inputs to multiplexers--obviating the need for binary
to unary decoding.
<
Perhaps your variable length decoding mechanism was not very refined.
<
> > >As to the cost of 2 dest registers, at the low end for an in-order,
> > >single issue pipeline with 1 register write port, taking an extra clock
> > >to write a second result does not add any complexity.
<
For My 66000 CARRY, I get rid of the complexity of 2 result registers
by having a recirculating bus, aptly called the Carry-Bus, that recirculates
results to operands until the end of the CARRY shadow. And if the last
calculation does not produce a carry-out, the result does not get written.
Much of the time the carry result is never "written" into the register file..
<
> > At least not much.
> >
> > But what's the difference from
> >
> >
> > add s0 = a, b
> > sltu carry0 = s0,a
> >
> > which also takes two cycles? Or do you have a three-input
> > add-with-carry? That would certainly solve the major problem that
> > MIPS, Alpha, and RISC-V have for this stuff, which is dealing with the
> > carry-in.
> > >For a multi-lane OoO uArch my concern was for Rename to NOT require
> > >two register allocation units for each lane, adding greatly to the cost
> > >and complexity, and which would mostly sit unused burning power.
> > >
> > >My solution is for Decode to spit out 2-dest instructions as two 1-dest uOps
> > >split across two consecutive lanes. Rename allocates the 1-dest registers
> > >to uOps as normal, then fuses the two pieces and outputs a single uOp to
> > >one output lane to Dispatch.
> > I wonder if that's what ARM are doing for their multi-result
> > instructions (load-pair with pre/post-indexed addressing mode consumes
> > three write ports).
> >
> An idea I have been toying with is for some operations caching the operands
> and results. So, if a divide is done the remainder is available immediately
> without having to do a full divide. Works for multiply high too. I think it should
> work well with reciprocal calculations too, where the same reciprocal is used
> in a loop for instance.
<
My VEC instruction informs the hardware which registers hold live results when
the LOOP terminates. This means a majority of results produced inside a loop
never need to actually get written into the register file, the result just has to be
passed on as an operand. This saves power.
<
>
> To deal with extended precision ADD in the past I have used a three operand
> ADD, combined with a carry generate instruction. The carry generate
> instruction takes the same operands as the add instruction but returns the
> carry out instead of the sum. It can then be added in the next instruction. It
> is a bit ugly but if one really wants to do multi-word arithmetic it is possible.
> I think the ADD and the carry-generate can be done in the same clock cycle
> in a superscalar CPU.
<
My 66000 - 256-bit integer add::
<
CARRY R16,{{I}{IO}{IO}{O}}
ADD R12,R4,R8 // carry Out only
ADD R13,R5,R9 // Carry In and Out
ADD R14,R6,R10 // Carry In and Out
ADD R15,R7,R11 // Carry In only
<
Here, in typical use, the carry register does not have to be read from the
register file nor does it have to get written at the end, either.
<
> > - anton
> > --
> > 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> > Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On Sunday, June 11, 2023 at 2:47:51 PM UTC-5, BGB wrote:
> On 6/11/2023 11:59 AM, robf...@gmail.com wrote:
> > On Sunday, June 11, 2023 at 10:57:39 AM UTC-4, Anton Ertl wrote:
> >> EricP <ThatWould...@thevillage.com> writes:
> >>> I was driven to instructions with 2-dest results by my desire to
> >>> (a) not have condition codes and (b) wanting to handle add with carry
> >>> in a straight forward way.
> >> I have expanded my answer to that problem into a paper:
> >> <http://www.complang.tuwien.ac.at/anton/tmp/carry.pdf>.
> >>
> >> Of course, the question is whether you consider this answer
> >> straightforward.
> >>> Variable length instructions opens the ISA to much useful functionality
> >>> like full size immediate operands but requires a more complicated fetch
> >>> unit than fixed size. This cost is generally accepted today.
> >> Counterexample: ARM A64 (and ARM has ample experience with
> >> variable-size instructions).
> >
> > I just decided not to long ago to go with a fixed sized instruction because
> > variable length calculations became on the critical timing path for an FPGA
> > design. Postfixes can effectively extend the instruction with constants..
> >
> I went with prefixes.
>
> If I designed another (new) variable-length ISA, it is probable I would
> still go with prefixes.
>
> Though, I would likely start (this time) with the assumption of the
> 32-bit instructions as baseline, and the 16-bit as a shorthand. My
> encoding is currently a little messy in that (in its original form) the
> 32-bit instructions were themselves a prefix encoding (of two 16-bit parts).
>
>
>
> Granted, prefixes have the downside of turning the immediate values into
> confetti... But, then again, there is RISC-V with fixed-length
> instructions and the immediate fields are still confetti...
>
There is no particular reason to use RISC-V ISA as anything but a
stick in the sand......
>
> Doesn't really effect the CPU too much, but admittedly is kind of a pain
> for the assembler and linker (linker needing a larger number of reloc
> types). Though, one can reduce the annoyance, say, by making all PC-rel
> offsets either Byte or Word (depending on the op), and all GBR-Rel ops
> Byte based, ... At least cutting down on the needed number of reloc types..
>
I did not end up having to need any of that.
>
> Well, except when the encoding rules change from one instruction to
> another, which is admittedly thus far why I haven't bothered with
> RISC-V's 'C' extension.
>
> Like, RVC is sort of like someone looked at Thumb and was then like
> "Hold my beer!".
>
>
> One other option would be, say, to have variable length ops with a
> size/form bucket, say:
> 000: 32-bit op, 3R Forms
> 001: 32-bit op, 3RI Forms
> 010: 64-bit op, 3R/4R/etc forms
> 011: 64-bit op, 3RI Forms, Imm32
> 100: 96-bit op, -
> 101: 96-bit op, 3RI Forms, Imm64
<
For my part, every instruction gets 1 immediate and/or 1 displacement.
Calculation instructions get 1 immediate
Loads get 1 displacement
Stores get 1 displacement and 1 immediate
<
Also note: everything needed to determine the length of an instruction
is available in the first 32-bits of the instruction.
<
My rational was that the compiler would be "pretty good" at simplifying
the instructions such that when it ran into a DAG where a node needed
2 constants, a vast majority of the time it could perform the calculation
at compile time. Evidence has born this out.
>
>
> Where, say:
> 000z-zzzz-zzdd-dddd ssss-sstt-tttt-zzzz //3R
> 001z-zzzz-zzdd-dddd ssss-ssii-iiii-iiii //3RI (Imm10)
>
> 011z-zzzz-zzdd-dddd ssss-sszz-zzzz-zzzz //3RI (Imm32)
> iiii-iiii-iiii-iiii iiii-iiii-iiii-iiii //Imm
>
> 101z-zzzz-zzdd-dddd ssss-sszz-zzzz-zzzz //3RI (Imm64)
> iiii-iiii-iiii-iiii iiii-iiii-iiii-iiii //Imm
> iiii-iiii-iiii-iiii iiii-iiii-iiii-iiii //Imm
>
> Where, say, the Imm32 and Imm64 encodings operate in (mostly) the same
> space as the 3R encodings, but will normally suppress the Rt field in
> favor of an immediate. The Imm10 encodings would represent a slightly
> different encoding space (likely exclusively Load/Store ops and ALU
> Immediate instructions).
>
>
>
> This would be nicer for an assembler and linker, but would implicitly
> mean that the instruction stream would no longer be "self-aligning".
>
> Say, with a self-aligning stream, if one starts decoding/disassembling
> instructions from an arbitrary location in the "text" sections, then the
> decoding will realign with the instruction stream within a few
> instruction words (this property is useful for tools like debuggers).
> >>> As to the cost of 2 dest registers, at the low end for an in-order,
> >>> single issue pipeline with 1 register write port, taking an extra clock
> >>> to write a second result does not add any complexity.
> >> At least not much.
> >>
> >> But what's the difference from
> >>
> >>
> >> add s0 = a, b
> >> sltu carry0 = s0,a
> >>
> >> which also takes two cycles? Or do you have a three-input
> >> add-with-carry? That would certainly solve the major problem that
> >> MIPS, Alpha, and RISC-V have for this stuff, which is dealing with the
> >> carry-in.
> >>> For a multi-lane OoO uArch my concern was for Rename to NOT require
> >>> two register allocation units for each lane, adding greatly to the cost
> >>> and complexity, and which would mostly sit unused burning power.
> >>>
> >>> My solution is for Decode to spit out 2-dest instructions as two 1-dest uOps
> >>> split across two consecutive lanes. Rename allocates the 1-dest registers
> >>> to uOps as normal, then fuses the two pieces and outputs a single uOp to
> >>> one output lane to Dispatch.
> >> I wonder if that's what ARM are doing for their multi-result
> >> instructions (load-pair with pre/post-indexed addressing mode consumes
> >> three write ports).
> >>
> > An idea I have been toying with is for some operations caching the operands
> > and results. So, if a divide is done the remainder is available immediately
> > without having to do a full divide. Works for multiply high too. I think it should
> > work well with reciprocal calculations too, where the same reciprocal is used
> > in a loop for instance.
> >
> > To deal with extended precision ADD in the past I have used a three operand
> > ADD, combined with a carry generate instruction. The carry generate
> > instruction takes the same operands as the add instruction but returns the
> > carry out instead of the sum. It can then be added in the next instruction. It
> > is a bit ugly but if one really wants to do multi-word arithmetic it is possible.
> > I think the ADD and the carry-generate can be done in the same clock cycle
> > in a superscalar CPU.
> >
> Possible, but likely to get rather annoying, rather fast.
>
> One almost may as well have some designated architectural scratchpad
> registers in this case.
>
> Say:
> DMULU R4, R5 //MACH:MACL = R4*R5
> STS MACL, R2 // R2 = MACL
>
> But, yeah, I know of an ISA that did the multiplier this way (cough, SH).
>
> Though, to be fair, it is less bad than doing the multiplier via MMIO
> (cough, MSP430).
>
Once you bite off on the fact you need to support (double) FMACs
all of the calculation resources are present to do integer multiply
fast........and it is used often enough to justify smelling like an integer
ADD in format and operand routing.

MitchAlsup wrote:
> On Sunday, June 11, 2023 at 11:59:33 AM UTC-5, robf...@gmail.com wrote:
> <
>> To deal with extended precision ADD in the past I have used a three operand
>> ADD, combined with a carry generate instruction. The carry generate
>> instruction takes the same operands as the add instruction but returns the
>> carry out instead of the sum. It can then be added in the next instruction. It
>> is a bit ugly but if one really wants to do multi-word arithmetic it is possible.
>> I think the ADD and the carry-generate can be done in the same clock cycle
>> in a superscalar CPU.
> <
> My 66000 - 256-bit integer add::
> <
> CARRY R16,{{I}{IO}{IO}{O}}
> ADD R12,R4,R8 // carry Out only
> ADD R13,R5,R9 // Carry In and Out
> ADD R14,R6,R10 // Carry In and Out
> ADD R15,R7,R11 // Carry In only
> <
> Here, in typical use, the carry register does not have to be read from the
> register file nor does it have to get written at the end, either.

The various integer ADDs formats I came up with
(single and wide means one or two integer register specifiers)

#1 ADD single = single + single (3 registers)
ADDTS trap signed overflow
ADDTU trap unsigned carry
#2 ADDW2 wide = single + single (4 registers)
#3 ADDW3 wide = single + single + single (5 registers)
#4 ADDWW wide = wide + single (5 registers)

#2 and #3 are for propagating a carry horizontally along a chain.
#4 is for the equivalent of a carry-save add on a column.
The My 66000 CARRY prefix can do an arbitrary long horizontal
carry propagate but didn't seem to have a way to specify #4.