Thomas Koenig wrote:
> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> schrieb:
>> On 8/23/2021 2:29 PM, Thomas Koenig wrote:
>>> MitchAlsup <MitchAlsup@aol.com> schrieb:
>>>> Back to the posed question:
>>>> <
>>>> If the programmer unrolled the loop by hand (like DGEMM without transposes):
>>>> The LDs would need to be coded using offsets from the index register to be
>>>> recognized as dense::
>>>>
>>>> MOV Ri,#0
>>>> VEC R8,{}
>>>> LDD R4,[R2,Ri<<3]
>>>> LDD R5,[R2,Ri<<3+8]
>>>> LDD R6,[R2,Ri<<3+16]
>>>> LDD R7,[R2,Ri<<3+24]
>>>> ...
>>>> LOOP LT,Ri,#4,Rmax
>>>> <
>>>> The above code would be recognized as dense.
>>>> <
>>>> MOV Ri,#0
>>>> ADD R9,R2,#8
>>>> ADD R9,R2,#16
>>>> ADD R10,R2,#24
>>>> VEC R8,{}
>>>> LDD R4,[R2,Ri<<3]
>>>> LDD R5,[R8,Ri<<3+8]
>>>> LDD R6,[R9,Ri<<3+16]
>>>> LDD R7,[R10,Ri<<3+24]
>>>> ...
>>>> LOOP LT,Ri,#4,Rmax
>>>> <
>>>> This loop is harder to recognize as dense--even though the number of words
>>>> in the loop is less.
>>>
>>> Hm... all possible, but less elegant that it could be. All the
>>> manual unrolling and autovectorization and... rears its ugly
>>> head again.
>>>
>>> With all the mechanisms that VVM already offers, a way for the
>>> programmer or a programming language to specify that operations
>>> such as summation can be done in any order would be a very useful
>>> addition.
>>
>> I am probably missing something here.
>
> Or, equvalently, I have been explaining things badly :-)
>
>> To me the main advantage of
>> allowing out of order summations (using summations here as shorthand for
>> other similar type operations), was to allow the hardware to make use of
>> multiple functional units.
>
> Yes.
>
>> That is, a core with two adders could, if
>> allowed, complete the summation in about half the time.
>
> Yes.
>
>> Without that, I
>> don't see any advantage of out of order summations on VVM. If I am
>> wrong, please explain. If I am right, see below.
>
> Seeing below.
>
>>
>>
>>
>>> Suggestion:
>>>
>>> A variant of the VEC instruction, which does not specify a special
>>> register to keep the address in (which can be hardwired if there
>>> is no space in the thread header). This leaves five bits for
>>> "reduction" registters, which specify that operations on that
>>> register can be done in any order in the loop.
>>
>> Doing the operations in a different order isn't the problem.
>
> It's one half of the problem.
>
> The way VVM is currently specified, it's stricly in-order semantics
> you write down a C loop, and the hardware delivers the results
> exactly in the order you wrote down. This would have to be
> changed.
>
>
>> You need a
>> way to allow/specify the two partial sums to be added together in the
>> end.
>
> That as well.
>
>> I don't see your proposal as doing that.
>
> I thought I had implied it, but it was obviously not clear enough.
>
>
>> And, of course, it is
>> limited to five registers which must be specified in the hardware design.
>
> Five reductions in a loop would be plenty, it is usually one, or more
> rarely two.
>
>>> This would be a perfect match for OpenMP's reduction clause or
>>> for the planned REDUCTION addition to Fortran's DO CONCURRENT.
>>
>> I am not an OpenMP person, and my knowledge of Fortran is old, so could
>> you please give a brief explanation of what these two things do? Thanks.
>
> #pragma omp simd reduction(+:var)
>
> before a loop will tell the compiler that it can go wild
> with the sequence of loops but that "var" will be used
> in a summation reduction.
>
> DO CONCURRENT also runs loops in an unspecified order,
> the REDUCTION clause would then allow to, for example,
> sum up all elements.
>
> One problems with C and similar languages is that you have
> to specify an ordering of the loop explicitly, which shapes
> programmer's thinking and also shapes intermediate languages
> for compilers...
>
The eventual solution for all this will be similar to Mitch's FMAC
accumulator, i.e. a form of super-accumulator which allows one or more
elements to be added per cycle, while delaying all inexact/rounding to
the very end.

A carry-save exact accumulator with ~1100 paired bits would only use a
single full adder (2 or 3 gate delays?) to accept a new input, right?

I am not sure what is the best way for such a beast to handle both
additions and subtractions: Do you need to invert/negate the value to be
subtracted?

Terje

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

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
> Thomas Koenig wrote:
>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> schrieb:
>>> On 8/23/2021 2:29 PM, Thomas Koenig wrote:
[some snippage, hopefully context-preserving]

>>>> With all the mechanisms that VVM already offers, a way for the
>>>> programmer or a programming language to specify that operations
>>>> such as summation can be done in any order would be a very useful
>>>> addition.

[...]

>>>> Suggestion:
>>>>
>>>> A variant of the VEC instruction, which does not specify a special
>>>> register to keep the address in (which can be hardwired if there
>>>> is no space in the thread header). This leaves five bits for
>>>> "reduction" registters, which specify that operations on that
>>>> register can be done in any order in the loop.

[...]

>> The way VVM is currently specified, it's stricly in-order semantics
>> you write down a C loop, and the hardware delivers the results
>> exactly in the order you wrote down. This would have to be
>> changed.
>>
>>
>>> You need a
>>> way to allow/specify the two partial sums to be added together in the
>>> end.
>>
>> That as well.

[...]

> The eventual solution for all this will be similar to Mitch's FMAC
> accumulator, i.e. a form of super-accumulator which allows one or more
> elements to be added per cycle, while delaying all inexact/rounding to
> the very end.
>
> A carry-save exact accumulator with ~1100 paired bits would only use a
> single full adder (2 or 3 gate delays?) to accept a new input, right?

Depends on the number of functional units you have. If you have
eight, for a high-performance CPU, you would need four layers
of adders to reduce the number of numbers to be added to two.

It might make sense to go to a signed digit implementation for
the 1100-bit adder (even though that doubles the number of bits of
storage needed for the register) and only do the carry propagation
once, upon storing. Adding one binary number to a signed digit
number should be cheap enough to be done in half a cycle, so adding
one number per cycle throughput sounds feasible.

> I am not sure what is the best way for such a beast to handle both
> additions and subtractions: Do you need to invert/negate the value to be
> subtracted?

Probably easiest.

However, there are also other operations in reduction, multiplication
for example...

On 8/23/2021 11:27 PM, Thomas Koenig wrote:
> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> schrieb:
>> On 8/23/2021 2:29 PM, Thomas Koenig wrote:
>>> MitchAlsup <MitchAlsup@aol.com> schrieb:
>>>> Back to the posed question:
>>>> <
>>>> If the programmer unrolled the loop by hand (like DGEMM without transposes):
>>>> The LDs would need to be coded using offsets from the index register to be
>>>> recognized as dense::
>>>>
>>>> MOV Ri,#0
>>>> VEC R8,{}
>>>> LDD R4,[R2,Ri<<3]
>>>> LDD R5,[R2,Ri<<3+8]
>>>> LDD R6,[R2,Ri<<3+16]
>>>> LDD R7,[R2,Ri<<3+24]
>>>> ...
>>>> LOOP LT,Ri,#4,Rmax
>>>> <
>>>> The above code would be recognized as dense.
>>>> <
>>>> MOV Ri,#0
>>>> ADD R9,R2,#8
>>>> ADD R9,R2,#16
>>>> ADD R10,R2,#24
>>>> VEC R8,{}
>>>> LDD R4,[R2,Ri<<3]
>>>> LDD R5,[R8,Ri<<3+8]
>>>> LDD R6,[R9,Ri<<3+16]
>>>> LDD R7,[R10,Ri<<3+24]
>>>> ...
>>>> LOOP LT,Ri,#4,Rmax
>>>> <
>>>> This loop is harder to recognize as dense--even though the number of words
>>>> in the loop is less.
>>>
>>> Hm... all possible, but less elegant that it could be. All the
>>> manual unrolling and autovectorization and... rears its ugly
>>> head again.
>>>
>>> With all the mechanisms that VVM already offers, a way for the
>>> programmer or a programming language to specify that operations
>>> such as summation can be done in any order would be a very useful
>>> addition.
>>
>> I am probably missing something here.
>
> Or, equvalently, I have been explaining things badly :-)
>
>> To me the main advantage of
>> allowing out of order summations (using summations here as shorthand for
>> other similar type operations), was to allow the hardware to make use of
>> multiple functional units.
>
> Yes.
>
>> That is, a core with two adders could, if
>> allowed, complete the summation in about half the time.
>
> Yes.
>
>> Without that, I
>> don't see any advantage of out of order summations on VVM. If I am
>> wrong, please explain. If I am right, see below.
>
> Seeing below.
>
>>
>>
>>
>>> Suggestion:
>>>
>>> A variant of the VEC instruction, which does not specify a special
>>> register to keep the address in (which can be hardwired if there
>>> is no space in the thread header). This leaves five bits for
>>> "reduction" registters, which specify that operations on that
>>> register can be done in any order in the loop.
>>
>> Doing the operations in a different order isn't the problem.
>
> It's one half of the problem.
>
> The way VVM is currently specified, it's stricly in-order semantics
> you write down a C loop, and the hardware delivers the results
> exactly in the order you wrote down.

Sort of. If you code the two statements
C := A + B
D := E + F
it may be, say because of a cache miss on the load of B, that the second
addition occurs before the first. I think it is more accurate to say
that the hardware makes it appear with correct semantics, even if
internally, it takes some liberties with the ordering, as long as the
result is the same.

> This would have to be
> changed.

If it makes a difference, yes. That is why I keep going back to summing
a vector of unsigned integers, where it doesn't. But if it does, then
you need some syntax like you describe below to tell the hardware it is
OK. Then you need some mechanism in the hardware that the compiler can
generate to tell the hardware weather it matters or not.

>> You need a
>> way to allow/specify the two partial sums to be added together in the
>> end.
>
> That as well.
>
>> I don't see your proposal as doing that.
>
> I thought I had implied it, but it was obviously not clear enough.

The problem is, you can't use a single accumulator as the hardware can't
do two/four adds to the same accumulator in the same cycle. If you are
doing say 2/4 partial sums, you need 2/4 places to store them (e.g.
registers), say in the event of an interrupt, and you need to tell the
hardware that, at the end, it needs to add the partial sums. It is this
syntax in the VVM ISA that is not there.

>> And, of course, it is
>> limited to five registers which must be specified in the hardware design.
>
> Five reductions in a loop would be plenty, it is usually one, or more
> rarely two.

Sure. I was thinking more about the fact that the choice of five, say
R1-R5, limits the compiler's register allocation flexibility. Perhaps
this isn't a big deal, but it is something.

>>> This would be a perfect match for OpenMP's reduction clause or
>>> for the planned REDUCTION addition to Fortran's DO CONCURRENT.
>>
>> I am not an OpenMP person, and my knowledge of Fortran is old, so could
>> you please give a brief explanation of what these two things do? Thanks.
>
> #pragma omp simd reduction(+:var)
>
> before a loop will tell the compiler that it can go wild
> with the sequence of loops but that "var" will be used
> in a summation reduction.
>
> DO CONCURRENT also runs loops in an unspecified order,
> the REDUCTION clause would then allow to, for example,
> sum up all elements.

That makes excellent sense. Thank you.

> One problems with C and similar languages is that you have
> to specify an ordering of the loop explicitly,

So you need something like a pragma to perform similarly to the
Concurrrent Reduction clause in Fortran.

> which shapes
> programmer's thinking and also shapes intermediate languages
> for compilers...

Are you saying something about C programmers versus say Fortran
programmers? :-)

As for intermediate languages, if they can solve it for Fortran, I guess
they could do the same for C.

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

On Monday, August 23, 2021 at 9:51:45 PM UTC-5, Stephen Fuld wrote:
> On 8/23/2021 2:29 PM, Thomas Koenig wrote:
> > MitchAlsup <Mitch...@aol.com> schrieb:
> >> Back to the posed question:
> >> <
> >> If the programmer unrolled the loop by hand (like DGEMM without transposes):
> >> The LDs would need to be coded using offsets from the index register to be
> >> recognized as dense::
> >>
> >> MOV Ri,#0
> >> VEC R8,{}
> >> LDD R4,[R2,Ri<<3]
> >> LDD R5,[R2,Ri<<3+8]
> >> LDD R6,[R2,Ri<<3+16]
> >> LDD R7,[R2,Ri<<3+24]
> >> ...
> >> LOOP LT,Ri,#4,Rmax
> >> <
> >> The above code would be recognized as dense.
> >> <
> >> MOV Ri,#0
> >> ADD R9,R2,#8
> >> ADD R9,R2,#16
> >> ADD R10,R2,#24
> >> VEC R8,{}
> >> LDD R4,[R2,Ri<<3]
> >> LDD R5,[R8,Ri<<3+8]
> >> LDD R6,[R9,Ri<<3+16]
> >> LDD R7,[R10,Ri<<3+24]
> >> ...
> >> LOOP LT,Ri,#4,Rmax
> >> <
> >> This loop is harder to recognize as dense--even though the number of words
> >> in the loop is less.
> >
> > Hm... all possible, but less elegant that it could be. All the
> > manual unrolling and autovectorization and... rears its ugly
> > head again.
> >
> > With all the mechanisms that VVM already offers, a way for the
> > programmer or a programming language to specify that operations
> > such as summation can be done in any order would be a very useful
> > addition.
> I am probably missing something here. To me the main advantage of
> allowing out of order summations (using summations here as shorthand for
<
The word you are looking for is "reduce", or "reduction"
I want this series of calculations reduced to a single number.
<
> other similar type operations), was to allow the hardware to make use of
> multiple functional units. That is, a core with two adders could, if
> allowed, complete the summation in about half the time.
<
This comes with numeric "issues". As with such, I do not want compilers
creating code to use wide resources WITHOUT some word from the
programmer saying it is "OK this time". (#pragma or such)
<
> Without that, I
> don't see any advantage of out of order summations on VVM. If I am
> wrong, please explain. If I am right, see below.
> > Suggestion:
> >
> > A variant of the VEC instruction, which does not specify a special
> > register to keep the address in (which can be hardwired if there
> > is no space in the thread header). This leaves five bits for
> > "reduction" registters, which specify that operations on that
> > register can be done in any order in the loop.
<
> Doing the operations in a different order isn't the problem. You need a
> way to allow/specify the two partial sums to be added together in the
> end. I don't see your proposal as doing that. And, of course, it is
> limited to five registers which must be specified in the hardware design.
<
Done properly, you want each loop performing Kahan-Babuška summations
not lossy clumsy double FP.
<
Kahan-Babuška summation should be known to and embedded in the compiler.
<
> >
> > This would be a perfect match for OpenMP's reduction clause or
> > for the planned REDUCTION addition to Fortran's DO CONCURRENT.
> I am not an OpenMP person, and my knowledge of Fortran is old, so could
> you please give a brief explanation of what these two things do? Thanks.
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

On Tuesday, August 24, 2021 at 1:27:51 AM UTC-5, Thomas Koenig wrote:
> Stephen Fuld <sf...@alumni.cmu.edu.invalid> schrieb:
> > On 8/23/2021 2:29 PM, Thomas Koenig wrote:
> >> MitchAlsup <Mitch...@aol.com> schrieb:
> >>> Back to the posed question:
> >>> <
> >>> If the programmer unrolled the loop by hand (like DGEMM without transposes):
> >>> The LDs would need to be coded using offsets from the index register to be
> >>> recognized as dense::
> >>>
> >>> MOV Ri,#0
> >>> VEC R8,{}
> >>> LDD R4,[R2,Ri<<3]
> >>> LDD R5,[R2,Ri<<3+8]
> >>> LDD R6,[R2,Ri<<3+16]
> >>> LDD R7,[R2,Ri<<3+24]
> >>> ...
> >>> LOOP LT,Ri,#4,Rmax
> >>> <
> >>> The above code would be recognized as dense.
> >>> <
> >>> MOV Ri,#0
> >>> ADD R9,R2,#8
> >>> ADD R9,R2,#16
> >>> ADD R10,R2,#24
> >>> VEC R8,{}
> >>> LDD R4,[R2,Ri<<3]
> >>> LDD R5,[R8,Ri<<3+8]
> >>> LDD R6,[R9,Ri<<3+16]
> >>> LDD R7,[R10,Ri<<3+24]
> >>> ...
> >>> LOOP LT,Ri,#4,Rmax
> >>> <
> >>> This loop is harder to recognize as dense--even though the number of words
> >>> in the loop is less.
> >>
> >> Hm... all possible, but less elegant that it could be. All the
> >> manual unrolling and autovectorization and... rears its ugly
> >> head again.
> >>
> >> With all the mechanisms that VVM already offers, a way for the
> >> programmer or a programming language to specify that operations
> >> such as summation can be done in any order would be a very useful
> >> addition.
> >
> > I am probably missing something here.
> Or, equvalently, I have been explaining things badly :-)
> > To me the main advantage of
> > allowing out of order summations (using summations here as shorthand for
> > other similar type operations), was to allow the hardware to make use of
> > multiple functional units.
> Yes.
> > That is, a core with two adders could, if
> > allowed, complete the summation in about half the time.
> Yes.
<
Who chooses time versus numerical precision ? Human, of software.
IEEE 754-1985 took hardware off the list of who could choose.
<
Even in integer code, unrolled summation changes where exceptions
get thrown (if thrown at all).
<
> >Without that, I
> > don't see any advantage of out of order summations on VVM. If I am
> > wrong, please explain. If I am right, see below.
> Seeing below.
> >
> >
> >
> >> Suggestion:
> >>
> >> A variant of the VEC instruction, which does not specify a special
> >> register to keep the address in (which can be hardwired if there
> >> is no space in the thread header). This leaves five bits for
> >> "reduction" registters, which specify that operations on that
> >> register can be done in any order in the loop.
> >
> > Doing the operations in a different order isn't the problem.
> It's one half of the problem.
>
> The way VVM is currently specified, it's stricly in-order semantics
> you write down a C loop, and the hardware delivers the results
> exactly in the order you wrote down. This would have to be
> changed.
> > You need a
> > way to allow/specify the two partial sums to be added together in the
> > end.
> That as well.
> >I don't see your proposal as doing that.
> I thought I had implied it, but it was obviously not clear enough.
> > And, of course, it is
> > limited to five registers which must be specified in the hardware design.
> Five reductions in a loop would be plenty, it is usually one, or more
> rarely two.
> >> This would be a perfect match for OpenMP's reduction clause or
> >> for the planned REDUCTION addition to Fortran's DO CONCURRENT.
> >
> > I am not an OpenMP person, and my knowledge of Fortran is old, so could
> > you please give a brief explanation of what these two things do? Thanks.
> #pragma omp simd reduction(+:var)
>
> before a loop will tell the compiler that it can go wild
> with the sequence of loops but that "var" will be used
> in a summation reduction.
>
> DO CONCURRENT also runs loops in an unspecified order,
> the REDUCTION clause would then allow to, for example,
> sum up all elements.
>
> One problems with C and similar languages is that you have
> to specify an ordering of the loop explicitly, which shapes
> programmer's thinking and also shapes intermediate languages
> for compilers...

On Tuesday, August 24, 2021 at 3:10:39 AM UTC-5, Terje Mathisen wrote:
> Thomas Koenig wrote:
> > Stephen Fuld <sf...@alumni.cmu.edu.invalid> schrieb:
> >> On 8/23/2021 2:29 PM, Thomas Koenig wrote:
> >>> MitchAlsup <Mitch...@aol.com> schrieb:
> >>>> Back to the posed question:
> >>>> <
> >>>> If the programmer unrolled the loop by hand (like DGEMM without transposes):
> >>>> The LDs would need to be coded using offsets from the index register to be
> >>>> recognized as dense::
> >>>>
> >>>> MOV Ri,#0
> >>>> VEC R8,{}
> >>>> LDD R4,[R2,Ri<<3]
> >>>> LDD R5,[R2,Ri<<3+8]
> >>>> LDD R6,[R2,Ri<<3+16]
> >>>> LDD R7,[R2,Ri<<3+24]
> >>>> ...
> >>>> LOOP LT,Ri,#4,Rmax
> >>>> <
> >>>> The above code would be recognized as dense.
> >>>> <
> >>>> MOV Ri,#0
> >>>> ADD R9,R2,#8
> >>>> ADD R9,R2,#16
> >>>> ADD R10,R2,#24
> >>>> VEC R8,{}
> >>>> LDD R4,[R2,Ri<<3]
> >>>> LDD R5,[R8,Ri<<3+8]
> >>>> LDD R6,[R9,Ri<<3+16]
> >>>> LDD R7,[R10,Ri<<3+24]
> >>>> ...
> >>>> LOOP LT,Ri,#4,Rmax
> >>>> <
> >>>> This loop is harder to recognize as dense--even though the number of words
> >>>> in the loop is less.
> >>>
> >>> Hm... all possible, but less elegant that it could be. All the
> >>> manual unrolling and autovectorization and... rears its ugly
> >>> head again.
> >>>
> >>> With all the mechanisms that VVM already offers, a way for the
> >>> programmer or a programming language to specify that operations
> >>> such as summation can be done in any order would be a very useful
> >>> addition.
> >>
> >> I am probably missing something here.
> >
> > Or, equvalently, I have been explaining things badly :-)
> >
> >> To me the main advantage of
> >> allowing out of order summations (using summations here as shorthand for
> >> other similar type operations), was to allow the hardware to make use of
> >> multiple functional units.
> >
> > Yes.
> >
> >> That is, a core with two adders could, if
> >> allowed, complete the summation in about half the time.
> >
> > Yes.
> >
> >> Without that, I
> >> don't see any advantage of out of order summations on VVM. If I am
> >> wrong, please explain. If I am right, see below.
> >
> > Seeing below.
> >
> >>
> >>
> >>
> >>> Suggestion:
> >>>
> >>> A variant of the VEC instruction, which does not specify a special
> >>> register to keep the address in (which can be hardwired if there
> >>> is no space in the thread header). This leaves five bits for
> >>> "reduction" registters, which specify that operations on that
> >>> register can be done in any order in the loop.
> >>
> >> Doing the operations in a different order isn't the problem.
> >
> > It's one half of the problem.
> >
> > The way VVM is currently specified, it's stricly in-order semantics
> > you write down a C loop, and the hardware delivers the results
> > exactly in the order you wrote down. This would have to be
> > changed.
> >
> >
> >> You need a
> >> way to allow/specify the two partial sums to be added together in the
> >> end.
> >
> > That as well.
> >
> >> I don't see your proposal as doing that.
> >
> > I thought I had implied it, but it was obviously not clear enough.
> >
> >
> >> And, of course, it is
> >> limited to five registers which must be specified in the hardware design.
> >
> > Five reductions in a loop would be plenty, it is usually one, or more
> > rarely two.
> >
> >>> This would be a perfect match for OpenMP's reduction clause or
> >>> for the planned REDUCTION addition to Fortran's DO CONCURRENT.
> >>
> >> I am not an OpenMP person, and my knowledge of Fortran is old, so could
> >> you please give a brief explanation of what these two things do? Thanks.
> >
> > #pragma omp simd reduction(+:var)
> >
> > before a loop will tell the compiler that it can go wild
> > with the sequence of loops but that "var" will be used
> > in a summation reduction.
> >
> > DO CONCURRENT also runs loops in an unspecified order,
> > the REDUCTION clause would then allow to, for example,
> > sum up all elements.
> >
> > One problems with C and similar languages is that you have
> > to specify an ordering of the loop explicitly, which shapes
> > programmer's thinking and also shapes intermediate languages
> > for compilers...
> >
> The eventual solution for all this will be similar to Mitch's FMAC
> accumulator, i.e. a form of super-accumulator which allows one or more
> elements to be added per cycle, while delaying all inexact/rounding to
> the very end.
>
> A carry-save exact accumulator with ~1100 paired bits would only use a
> single full adder (2 or 3 gate delays?) to accept a new input, right?
<
A carry save accumulator uses a 4-input-2-output compressor. With
true complement signals, this is 2 gates of delay (3-input XOR is 1 gate
in TC form). Without TC signals it is 3 gates.
>
> I am not sure what is the best way for such a beast to handle both
> additions and subtractions: Do you need to invert/negate the value to be
> subtracted?
<
The key property is that the value spinning around in the accumulator
remains the polarity of when it started (+ or - but not both) while
the multiplier can produce + or - on a per calculation basis.
But in practice one can work in the negations at the cost of a
single additional gate of delay.
<
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

On 8/24/2021 8:25 AM, MitchAlsup wrote:
> On Monday, August 23, 2021 at 9:51:45 PM UTC-5, Stephen Fuld wrote:
>> On 8/23/2021 2:29 PM, Thomas Koenig wrote:

snip

>>> With all the mechanisms that VVM already offers, a way for the
>>> programmer or a programming language to specify that operations
>>> such as summation can be done in any order would be a very useful
>>> addition.
>> I am probably missing something here. To me the main advantage of
>> allowing out of order summations (using summations here as shorthand for
> <
> The word you are looking for is "reduce", or "reduction"
> I want this series of calculations reduced to a single number.

Yes, I worded that clumsily. I probably should have used the word
"operation" to indicate whatever is needed to perform the reduction.
But using simple summation as an example, makes saying things like
"partial sums" meaningful. Is there a generally accepted better term
for the intermediate results of a reduction?

>> other similar type operations), was to allow the hardware to make use of
>> multiple functional units. That is, a core with two adders could, if
>> allowed, complete the summation in about half the time.
> <
> This comes with numeric "issues". As with such, I do not want compilers
> creating code to use wide resources WITHOUT some word from the
> programmer saying it is "OK this time". (#pragma or such)

Absolutely agreed. But Thomas has said such things are coming, at least
for Fortran. But adding a pragma for C doesn't seem unreasonable, as it
potentially allows a huge performance improvement. But clearly it
shouldn't be the default.

> <
>> Without that, I
>> don't see any advantage of out of order summations on VVM. If I am
>> wrong, please explain. If I am right, see below.
>>> Suggestion:
>>>
>>> A variant of the VEC instruction, which does not specify a special
>>> register to keep the address in (which can be hardwired if there
>>> is no space in the thread header). This leaves five bits for
>>> "reduction" registters, which specify that operations on that
>>> register can be done in any order in the loop.
> <
>> Doing the operations in a different order isn't the problem. You need a
>> way to allow/specify the two partial sums to be added together in the
>> end. I don't see your proposal as doing that. And, of course, it is
>> limited to five registers which must be specified in the hardware design.
> <
> Done properly, you want each loop performing Kahan-Babuška summations
> not lossy clumsy double FP.
> <
> Kahan-Babuška summation should be known to and embedded in the compiler.

While I agree with that, it still doesn't address the issues of needing
multiple intermediate results "places"(to allow multiple partial
reductions (is that the right word?) to proceed in parallel, and how to
combine them at the end. You need some ISA syntax to specify such things.

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

On Tuesday, August 24, 2021 at 4:58:52 AM UTC-5, Thomas Koenig wrote:
> Terje Mathisen <terje.m...@tmsw.no> schrieb:
> > Thomas Koenig wrote:
> >> Stephen Fuld <sf...@alumni.cmu.edu.invalid> schrieb:
> >>> On 8/23/2021 2:29 PM, Thomas Koenig wrote:
> [some snippage, hopefully context-preserving]
> >>>> With all the mechanisms that VVM already offers, a way for the
> >>>> programmer or a programming language to specify that operations
> >>>> such as summation can be done in any order would be a very useful
> >>>> addition.
> [...]
> >>>> Suggestion:
> >>>>
> >>>> A variant of the VEC instruction, which does not specify a special
> >>>> register to keep the address in (which can be hardwired if there
> >>>> is no space in the thread header). This leaves five bits for
> >>>> "reduction" registters, which specify that operations on that
> >>>> register can be done in any order in the loop.
> [...]
> >> The way VVM is currently specified, it's stricly in-order semantics
> >> you write down a C loop, and the hardware delivers the results
> >> exactly in the order you wrote down. This would have to be
> >> changed.
> >>
> >>
> >>> You need a
> >>> way to allow/specify the two partial sums to be added together in the
> >>> end.
> >>
> >> That as well.
> [...]
> > The eventual solution for all this will be similar to Mitch's FMAC
> > accumulator, i.e. a form of super-accumulator which allows one or more
> > elements to be added per cycle, while delaying all inexact/rounding to
> > the very end.
> >
> > A carry-save exact accumulator with ~1100 paired bits would only use a
> > single full adder (2 or 3 gate delays?) to accept a new input, right?
<
> Depends on the number of functional units you have. If you have
> eight, for a high-performance CPU, you would need four layers
> of adders to reduce the number of numbers to be added to two.
<
Each layer of 4-2 compression costs 2 gates of delay. 8-2 4 gates
16-2 6 gates......
>
> It might make sense to go to a signed digit implementation for
> the 1100-bit adder (even though that doubles the number of bits of
> storage needed for the register) and only do the carry propagation
> once, upon storing.
<
Carry save is perfectly adequate for an accumulator as carries are
only moving forward ln2( #inputs ) per cycle. IT is easy to build
a Carry Save Find First circuit, so you know where in that 1076 bit
accumulator is the most likely highest bit of significance. {You
will only be off by 1 at most}
<
< Adding one binary number to a signed digit
> number should be cheap enough to be done in half a cycle, so adding
> one number per cycle throughput sounds feasible.
<
> > I am not sure what is the best way for such a beast to handle both
> > additions and subtractions: Do you need to invert/negate the value to be
> > subtracted?
<
New value into summation can be + or -
Current running sum cannot (or can at another couple of gate delays.)
<
> Probably easiest.
>
> However, there are also other operations in reduction, multiplication
> for example...

On Tuesday, August 24, 2021 at 10:42:32 AM UTC-5, Stephen Fuld wrote:
> On 8/24/2021 8:25 AM, MitchAlsup wrote:
> > On Monday, August 23, 2021 at 9:51:45 PM UTC-5, Stephen Fuld wrote:
> >> On 8/23/2021 2:29 PM, Thomas Koenig wrote:
> snip
> >>> With all the mechanisms that VVM already offers, a way for the
> >>> programmer or a programming language to specify that operations
> >>> such as summation can be done in any order would be a very useful
> >>> addition.
> >> I am probably missing something here. To me the main advantage of
> >> allowing out of order summations (using summations here as shorthand for
> > <
> > The word you are looking for is "reduce", or "reduction"
> > I want this series of calculations reduced to a single number.
> Yes, I worded that clumsily. I probably should have used the word
> "operation" to indicate whatever is needed to perform the reduction.
> But using simple summation as an example, makes saying things like
> "partial sums" meaningful. Is there a generally accepted better term
> for the intermediate results of a reduction?
<
As far as I know: accumulator is about as good as it gets.
<
> >> other similar type operations), was to allow the hardware to make use of
> >> multiple functional units. That is, a core with two adders could, if
> >> allowed, complete the summation in about half the time.
> > <
> > This comes with numeric "issues". As with such, I do not want compilers
> > creating code to use wide resources WITHOUT some word from the
> > programmer saying it is "OK this time". (#pragma or such)
<
> Absolutely agreed. But Thomas has said such things are coming, at least
> for Fortran. But adding a pragma for C doesn't seem unreasonable, as it
> potentially allows a huge performance improvement. But clearly it
> shouldn't be the default.
> > <
> >> Without that, I
> >> don't see any advantage of out of order summations on VVM. If I am
> >> wrong, please explain. If I am right, see below.
> >>> Suggestion:
> >>>
> >>> A variant of the VEC instruction, which does not specify a special
> >>> register to keep the address in (which can be hardwired if there
> >>> is no space in the thread header). This leaves five bits for
> >>> "reduction" registters, which specify that operations on that
> >>> register can be done in any order in the loop.
> > <
> >> Doing the operations in a different order isn't the problem. You need a
> >> way to allow/specify the two partial sums to be added together in the
> >> end. I don't see your proposal as doing that. And, of course, it is
> >> limited to five registers which must be specified in the hardware design.
> > <
> > Done properly, you want each loop performing Kahan-Babuška summations
> > not lossy clumsy double FP.
> > <
> > Kahan-Babuška summation should be known to and embedded in the compiler.
<
> While I agree with that, it still doesn't address the issues of needing
> multiple intermediate results "places"(to allow multiple partial
> reductions (is that the right word?) to proceed in parallel, and how to
> combine them at the end. You need some ISA syntax to specify such things.
<
A single "core" can work on a single reduction.
It takes multiple cores to work on multiple reductions simultaneously.
cores, by themselves, are multiple clock cycles apart, and so are not
in general, allowed to know anything about what the others are up to.
<
To properly sum multiple reductions one needs a way to ship the
multiple 1076-bit reductions to a common adder/normalizer/rounder.
One HAS to perform a single rounding to get the correct final result
in a Kahan sense (754 has not gone this far, yet).
<
unums (posits) use the word "quire" as the accumulator.
<
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

MitchAlsup wrote:
> On Tuesday, August 24, 2021 at 10:42:32 AM UTC-5, Stephen Fuld wrote:
>> On 8/24/2021 8:25 AM, MitchAlsup wrote:
>>> On Monday, August 23, 2021 at 9:51:45 PM UTC-5, Stephen Fuld wrote:
>>>> On 8/23/2021 2:29 PM, Thomas Koenig wrote:
>> snip
>>>>> With all the mechanisms that VVM already offers, a way for the
>>>>> programmer or a programming language to specify that operations
>>>>> such as summation can be done in any order would be a very useful
>>>>> addition.
>>>> I am probably missing something here. To me the main advantage of
>>>> allowing out of order summations (using summations here as shorthand for
>>> <
>>> The word you are looking for is "reduce", or "reduction"
>>> I want this series of calculations reduced to a single number.
>> Yes, I worded that clumsily. I probably should have used the word
>> "operation" to indicate whatever is needed to perform the reduction.
>> But using simple summation as an example, makes saying things like
>> "partial sums" meaningful. Is there a generally accepted better term
>> for the intermediate results of a reduction?
> <
> As far as I know: accumulator is about as good as it gets.
> <
>>>> other similar type operations), was to allow the hardware to make use of
>>>> multiple functional units. That is, a core with two adders could, if
>>>> allowed, complete the summation in about half the time.
>>> <
>>> This comes with numeric "issues". As with such, I do not want compilers
>>> creating code to use wide resources WITHOUT some word from the
>>> programmer saying it is "OK this time". (#pragma or such)
> <
>> Absolutely agreed. But Thomas has said such things are coming, at least
>> for Fortran. But adding a pragma for C doesn't seem unreasonable, as it
>> potentially allows a huge performance improvement. But clearly it
>> shouldn't be the default.
>>> <
>>>> Without that, I
>>>> don't see any advantage of out of order summations on VVM. If I am
>>>> wrong, please explain. If I am right, see below.
>>>>> Suggestion:
>>>>>
>>>>> A variant of the VEC instruction, which does not specify a special
>>>>> register to keep the address in (which can be hardwired if there
>>>>> is no space in the thread header). This leaves five bits for
>>>>> "reduction" registters, which specify that operations on that
>>>>> register can be done in any order in the loop.
>>> <
>>>> Doing the operations in a different order isn't the problem. You need a
>>>> way to allow/specify the two partial sums to be added together in the
>>>> end. I don't see your proposal as doing that. And, of course, it is
>>>> limited to five registers which must be specified in the hardware design.
>>> <
>>> Done properly, you want each loop performing Kahan-Babuška summations
>>> not lossy clumsy double FP.
>>> <
>>> Kahan-Babuška summation should be known to and embedded in the compiler.
> <
>> While I agree with that, it still doesn't address the issues of needing
>> multiple intermediate results "places"(to allow multiple partial
>> reductions (is that the right word?) to proceed in parallel, and how to
>> combine them at the end. You need some ISA syntax to specify such things.
> <
> A single "core" can work on a single reduction.
> It takes multiple cores to work on multiple reductions simultaneously.
> cores, by themselves, are multiple clock cycles apart, and so are not
> in general, allowed to know anything about what the others are up to.
> <
> To properly sum multiple reductions one needs a way to ship the
> multiple 1076-bit reductions to a common adder/normalizer/rounder.
> One HAS to perform a single rounding to get the correct final result
> in a Kahan sense (754 has not gone this far, yet).

You can round each super-acc result to 109 bits or more, at which point
you are guaranteed to get the same result when you add these two
together and then do a final round to double, as if you actually did the
full 1100-bit merge and then rounded, right?

....

No, it is easy to contruct a counter-example. :-(

OTOH, I expect that such a super-acc with redundant storage would have a
way to canonicalize it while storing, and at this point it is easy to
merge multiple accumulators as unsigned integer arrays.

If the hw also reports the position of the most significant bit, then
the merging can be handled more efficiently by starting at that position
and add all the accumulator results, then iterate over subsequent 64-bit
blocks until the end or until no change is possible at the rounding point.

Terje

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

On 8/24/2021 8:52 AM, MitchAlsup wrote:
> On Tuesday, August 24, 2021 at 10:42:32 AM UTC-5, Stephen Fuld wrote:
>> On 8/24/2021 8:25 AM, MitchAlsup wrote:
>>> On Monday, August 23, 2021 at 9:51:45 PM UTC-5, Stephen Fuld wrote:
>>>> On 8/23/2021 2:29 PM, Thomas Koenig wrote:
>> snip
>>>>> With all the mechanisms that VVM already offers, a way for the
>>>>> programmer or a programming language to specify that operations
>>>>> such as summation can be done in any order would be a very useful
>>>>> addition.
>>>> I am probably missing something here. To me the main advantage of
>>>> allowing out of order summations (using summations here as shorthand for
>>> <
>>> The word you are looking for is "reduce", or "reduction"
>>> I want this series of calculations reduced to a single number.
>> Yes, I worded that clumsily. I probably should have used the word
>> "operation" to indicate whatever is needed to perform the reduction.
>> But using simple summation as an example, makes saying things like
>> "partial sums" meaningful. Is there a generally accepted better term
>> for the intermediate results of a reduction?
> <
> As far as I know: accumulator is about as good as it gets.
> <
>>>> other similar type operations), was to allow the hardware to make use of
>>>> multiple functional units. That is, a core with two adders could, if
>>>> allowed, complete the summation in about half the time.
>>> <
>>> This comes with numeric "issues". As with such, I do not want compilers
>>> creating code to use wide resources WITHOUT some word from the
>>> programmer saying it is "OK this time". (#pragma or such)
> <
>> Absolutely agreed. But Thomas has said such things are coming, at least
>> for Fortran. But adding a pragma for C doesn't seem unreasonable, as it
>> potentially allows a huge performance improvement. But clearly it
>> shouldn't be the default.
>>> <
>>>> Without that, I
>>>> don't see any advantage of out of order summations on VVM. If I am
>>>> wrong, please explain. If I am right, see below.
>>>>> Suggestion:
>>>>>
>>>>> A variant of the VEC instruction, which does not specify a special
>>>>> register to keep the address in (which can be hardwired if there
>>>>> is no space in the thread header). This leaves five bits for
>>>>> "reduction" registters, which specify that operations on that
>>>>> register can be done in any order in the loop.
>>> <
>>>> Doing the operations in a different order isn't the problem. You need a
>>>> way to allow/specify the two partial sums to be added together in the
>>>> end. I don't see your proposal as doing that. And, of course, it is
>>>> limited to five registers which must be specified in the hardware design.
>>> <
>>> Done properly, you want each loop performing Kahan-Babuška summations
>>> not lossy clumsy double FP.
>>> <
>>> Kahan-Babuška summation should be known to and embedded in the compiler.
> <
>> While I agree with that, it still doesn't address the issues of needing
>> multiple intermediate results "places"(to allow multiple partial
>> reductions (is that the right word?) to proceed in parallel, and how to
>> combine them at the end. You need some ISA syntax to specify such things.
> <
> A single "core" can work on a single reduction.

Sure. Apparently, I am not making myself clear. I want to be able
*optionally* to take advantage of multiple functional units in a single
core to speed up a single reduction. As an example, if I want to sum
the elements of an array, and I have two FUs that can do the addition, I
want each to sum half the elements in parallel, then a final add to
combine the two partial sums.

As was pointed out earlier, you can certainly get this by unrolling the
loop, then doing the final add of the two partial sums outside of the
loop. But this makes the code "specify" the number of lanes (i.e. how
many times the loop is unrolled by), thus makes it hardware model
specific (i.e. it can't take advantage of a more powerful model with say
four appropriate FUs).

One of the beauties of VVM is that, for most loops, you code it for one
unit, but the hardware "automagically" and transparently invokes
multiple FUs to speed things up. I want to be able to extend this
capability (transparently taking advantage of multiple FUs if they are
available), to reductions, *where the programmer/compiler knows it will
be OK to do so*.

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

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Tuesday, August 24, 2021 at 4:58:52 AM UTC-5, Thomas Koenig wrote:

>> Depends on the number of functional units you have. If you have
>> eight, for a high-performance CPU, you would need four layers
>> of adders to reduce the number of numbers to be added to two.
><
> Each layer of 4-2 compression costs 2 gates of delay. 8-2 4 gates
> 16-2 6 gates......

So 4-2 compression is currently what people are now using, not
one of the (many) other possibilities, and not the full
adders that I assumed?

I didn't know that, thanks for the info.

>>

>> It might make sense to go to a signed digit implementation for
>> the 1100-bit adder (even though that doubles the number of bits of
>> storage needed for the register) and only do the carry propagation
>> once, upon storing.
><
> Carry save is perfectly adequate for an accumulator as carries are
> only moving forward ln2( #inputs ) per cycle. IT is easy to build
> a Carry Save Find First circuit, so you know where in that 1076 bit
> accumulator is the most likely highest bit of significance. {You
> will only be off by 1 at most}

Interesting.

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Monday, August 23, 2021 at 9:51:45 PM UTC-5, Stephen Fuld wrote:

>> other similar type operations), was to allow the hardware to make use of
>> multiple functional units. That is, a core with two adders could, if
>> allowed, complete the summation in about half the time.
><
> This comes with numeric "issues". As with such, I do not want compilers
> creating code to use wide resources WITHOUT some word from the
> programmer saying it is "OK this time". (#pragma or such)

Agreed - this should be specified in the language (and preferably
not with a #pragma, which are sort of an evil hack, but for things
that are standardized like OpenMP that is accepatble).

Unfortunately, it takes a big hammer to get code to be vectorized on
SIMD systems, such as ignoring all these niceties, so a big hammer
is what is supplied, with seductively named compiler options such
as -Ofast or -ffast-math.

(There's a double-langauge pun lurking here. "fast" means "almost"
in German, and one could vary an old saying about experiments to
"Fast programs, fast results, fast richtig" (where the last part
means "almost correct"). Maybe something for Anton's office wall?)

I appreciate what VVM can do here, by keeping the sequential
dependencies alive. There's simply a case where the language
does not specify this, as in DO CONCURRENT or #pragma simd,
when these semantics do not apply and where more speed would
help (which is the point you made above).

>> Doing the operations in a different order isn't the problem. You need a
>> way to allow/specify the two partial sums to be added together in the
>> end. I don't see your proposal as doing that. And, of course, it is
>> limited to five registers which must be specified in the hardware design.
><
> Done properly, you want each loop performing Kahan-Babuška summations
> not lossy clumsy double FP.
><
> Kahan-Babuška summation should be known to and embedded in the compiler.

Depends if you need it or not. It is a considerable overhead /
slowdown, and putting it in for all cases also would not be a
good thing.

On Tuesday, August 24, 2021 at 11:38:50 AM UTC-5, Thomas Koenig wrote:
> MitchAlsup <Mitch...@aol.com> schrieb:
> > On Monday, August 23, 2021 at 9:51:45 PM UTC-5, Stephen Fuld wrote:
>
> >> other similar type operations), was to allow the hardware to make use of
> >> multiple functional units. That is, a core with two adders could, if
> >> allowed, complete the summation in about half the time.
> ><
> > This comes with numeric "issues". As with such, I do not want compilers
> > creating code to use wide resources WITHOUT some word from the
> > programmer saying it is "OK this time". (#pragma or such)
> Agreed - this should be specified in the language (and preferably
> not with a #pragma, which are sort of an evil hack, but for things
> that are standardized like OpenMP that is accepatble).
>
> Unfortunately, it takes a big hammer to get code to be vectorized on
> SIMD systems, such as ignoring all these niceties, so a big hammer
> is what is supplied, with seductively named compiler options such
> as -Ofast or -ffast-math.
>
> (There's a double-langauge pun lurking here. "fast" means "almost"
> in German, and one could vary an old saying about experiments to
> "Fast programs, fast results, fast richtig" (where the last part
> means "almost correct"). Maybe something for Anton's office wall?)
>
> I appreciate what VVM can do here, by keeping the sequential
> dependencies alive. There's simply a case where the language
> does not specify this, as in DO CONCURRENT or #pragma simd,
> when these semantics do not apply and where more speed would
> help (which is the point you made above).
> >> Doing the operations in a different order isn't the problem. You need a
> >> way to allow/specify the two partial sums to be added together in the
> >> end. I don't see your proposal as doing that. And, of course, it is
> >> limited to five registers which must be specified in the hardware design.
> ><
> > Done properly, you want each loop performing Kahan-Babuška summations
> > not lossy clumsy double FP.
> ><
> > Kahan-Babuška summation should be known to and embedded in the compiler.
> Depends if you need it or not. It is a considerable overhead /
> slowdown, and putting it in for all cases also would not be a
> good thing.
<
On some implementations is may have considerable overhead (6 FP ops
mostly dependent, instead of 1) on others it cost no more than FMAC all by
itself. In my 66000 ISA it can be encoded in 2 instructions and performed
in 1 (CARRY is an instruction-modifier and does not necessarily execute)

MitchAlsup <MitchAlsup@aol.com> schrieb:

> Carry save is perfectly adequate for an accumulator as carries are
> only moving forward ln2( #inputs ) per cycle. IT is easy to build
> a Carry Save Find First circuit, so you know where in that 1076 bit
> accumulator is the most likely highest bit of significance. {You
> will only be off by 1 at most}

Having second thoughts here...

Assuming I calculate

01..111111111....111000
+ 00..000000000....001000
=========================
10..000000000....000000

with the 1076 bit accumulator, the carry would still have to be
propagated all the way, across more than 1024 bits if I am unlucky.
This is why I suggested signed digits, because carries only propagate
a single position there (if done correctly).

How would a carry-save adder deal with this situation?

On Tuesday, August 24, 2021 at 11:46:09 AM UTC-5, Thomas Koenig wrote:
> MitchAlsup <Mitch...@aol.com> schrieb:
> > Carry save is perfectly adequate for an accumulator as carries are
> > only moving forward ln2( #inputs ) per cycle. IT is easy to build
> > a Carry Save Find First circuit, so you know where in that 1076 bit
> > accumulator is the most likely highest bit of significance. {You
> > will only be off by 1 at most}
> Having second thoughts here...
>
> Assuming I calculate
>
> 01..111111111....111000
> + 00..000000000....001000
> =========================
> 10..000000000....000000
>
> with the 1076 bit accumulator, the carry would still have to be
> propagated all the way, across more than 1024 bits if I am unlucky.
<
But this propagation takes place in the adder not in the accumulator
which remains carry save during all the iterations. The adder is used
only after all of the reductions from all of the lanes arrive and are
compressed into a final carry save result. This adder will be of Kogee
Stone variety, where the middle order bits are the last to resolve,
allowing one to begin finding the point of greatest significance
early.
<
> This is why I suggested signed digits, because carries only propagate
> a single position there (if done correctly).
>
> How would a carry-save adder deal with this situation?
>
You are going to get carry save results out of the multiplier
every cycle. In carry save form, you use 2 signals for each bit.
We know fast multipliers perform their work in not just carry
save but also True-Complement (to make the XORs fast),
so I assume we have carry-save and true-complement out
of the multiplier.
<
Anytime one gets a value out of a latch (of flip-flop) one has
access to both true and compliment values. The accumulator
"runs" through this flip-flop, so we have both carry save and true
complement data from the 'flop.
<
Thus we have 2-bits from the multiplier and 2 bits from the
accumulator flop and we can add these 2 values in 2 gates
of delay producing carry save output, which we then flop.
<
Since this addition only costs 2 gates of delay, we could take
results from 3 lanes and 1 accumulator in 4 gates, 7 lanes
and 1 accumulator in 6 gates: the reduction can easily take
as many as 16 lanes, per cycle. I doubt anyone is going to
build a machine "that wide".

On Monday, August 23, 2021 at 6:44:45 AM UTC+1, Thomas Koenig wrote:
> MitchAlsup <Mitch...@aol.com> schrieb:

> Will it run several iterations in parallel without source code
> modification, or not?

yes, by running the exact same instructions in in-flight out-of-order multi-issue micro-architecture.

VVM took me 2 years to understand rhe concept, it was a lightbulb moment but only after i had a brainwave in SVP64. more of a 2x4 cluebat smack to the side of the head, but hey.

to conceptually understand VVM in full,.first take either Cray-style Vectors or "SIMD where it is implemented as a horizontal for-loop". doesn't matter which: the important part is:

you have a for-loop on the current instruction, it goes from 0 to LEN-1

thus, instruction1 you have a for-loop from element 0 to element LEN+1
instruction 2: for-loop from element 0 to element LEN+1

got that bit so far?

Vertical-First, of which VVM is a type, you do this:

START LOOP
instruction 1 element 0
instruction 2 element 0
instruction 3 element 0
LOOP BACK
instruction 1 element 1
instruction 2 element 1
.....
LOOP BACK
instruction 1 element LEN-1
Instruction 2 element LEN-1
instruction 3 element LEN-1
END LOOP

that's it.

that's all there is to it. if you understand this difference,
between Horizontal-First and Vertical-First element/instruction
processing order, you understand VVM.

thus you can see:

* a simple single issue may do this dead easy, exactly
as the scalar code is written
* a multi issue version may analyse the loop and shove multiple
overlapping elements into overlapping in-flight buffers.

there is no actual optimisation, it just turns out that
the LOOP instruction declares various things such
as the loop invariant, and which registers can be
considered "Vectorised".

[somebody please do check this:
the limitation as i understand it is that those registers
marked as "Vectorised" *cannot* have data passed in to
them. as best i have been able to tell you *must* use
LD to get data into a Vector element and you likewise
*must* ST that element towards the end of the loop]

if you do this then the HW is happy due to it detecting
that the elements are in fact loop independent, and need
only concern itself about Memory R/W Hazards.

SVP64's Vertical First Mode on the other hand has
*actual* mapping to *actual* registers one to one
with the conceptual element numbering illustrated
above, and consequently you *do not* have to rely
on LD/ST. SVP64 is however a 64bit ISA so not
especially compact.

l.

On Friday, August 27, 2021 at 4:36:28 PM UTC-5, luke.l...@gmail.com wrote:
> On Monday, August 23, 2021 at 6:44:45 AM UTC+1, Thomas Koenig wrote:
> > MitchAlsup <Mitch...@aol.com> schrieb:
> > Will it run several iterations in parallel without source code
> > modification, or not?
> yes, by running the exact same instructions in in-flight out-of-order multi-issue micro-architecture.
>
> VVM took me 2 years to understand rhe concept, it was a lightbulb moment but only after i had a brainwave in SVP64. more of a 2x4 cluebat smack to the side of the head, but hey.
>
> to conceptually understand VVM in full,.first take either Cray-style Vectors or "SIMD where it is implemented as a horizontal for-loop". doesn't matter which: the important part is:
>
> you have a for-loop on the current instruction, it goes from 0 to LEN-1
>
> thus, instruction1 you have a for-loop from element 0 to element LEN+1
> instruction 2: for-loop from element 0 to element LEN+1
>
> got that bit so far?
>
> Vertical-First, of which VVM is a type, you do this:
>
> START LOOP
> instruction 1 element 0
> instruction 2 element 0
> instruction 3 element 0
> LOOP BACK
> instruction 1 element 1
> instruction 2 element 1
> ....
> LOOP BACK
> instruction 1 element LEN-1
> Instruction 2 element LEN-1
> instruction 3 element LEN-1
> END LOOP
>
> that's it.
>
> that's all there is to it. if you understand this difference,
> between Horizontal-First and Vertical-First element/instruction
> processing order, you understand VVM.
>
> thus you can see:
>
> * a simple single issue may do this dead easy, exactly
> as the scalar code is written
> * a multi issue version may analyse the loop and shove multiple
> overlapping elements into overlapping in-flight buffers.
>
> there is no actual optimisation, it just turns out that
> the LOOP instruction declares various things such
> as the loop invariant, and which registers can be
> considered "Vectorised".
>
> [somebody please do check this:
> the limitation as i understand it is that those registers
> marked as "Vectorised" *cannot* have data passed in to
> them. as best i have been able to tell you *must* use
> LD to get data into a Vector element and you likewise
> *must* ST that element towards the end of the loop]
<
The difference between Scalar, Vector, and Loop Carried is::
a) Scalar registers are read once put into stations and then
.....just used to supply operands to instructions
b) Vector registers capture a result produced in this iteration
c) Loop Carried registers capture a result produced in a
.....previous iteration.
<
The distinction is used in the operand capture portion of
the stations.
>
> if you do this then the HW is happy due to it detecting
> that the elements are in fact loop independent, and need
> only concern itself about Memory R/W Hazards.
<
One of the things I learned when building wide OoO machines
is the stunning nature of how LITTLE OoOness is needed to
get within spitting distance of "all you can get" performance.
>
> SVP64's Vertical First Mode on the other hand has
> *actual* mapping to *actual* registers one to one
> with the conceptual element numbering illustrated
> above, and consequently you *do not* have to rely
> on LD/ST. SVP64 is however a 64bit ISA so not
> especially compact.
>
> l.

On Monday, August 23, 2021 at 10:55:26 PM UTC+1, MitchAlsup wrote:

> The major problem is where does one store the state on an interrupt
> taken inside of the loop. I am letting my subconscious dwell on it right
> now.

the answer is, without an actual register, you can't.

even if it was a Special Purpose register for storing
in-flight data, it's still a register.

if it was an actual GPR/FPR, actually named
in the instruction (and given as a src/dst into
the FMAC as the accumulator) *now* you
have a register to actually store in-flight
data during an interrupt. it can even be
contextswitched.

a lot of things in SVP64 look overly complex until precise interrupt
handling is thrown into the pot.

l.

On Monday, August 23, 2021 at 10:55:26 PM UTC+1, MitchAlsup wrote:
> My preferred means is to make a way to specify that a function unit is
> performing a reduction, and that it should not deliver its value at the
> end of its calculation, but hold on to it an use it in the next calculation.

in SVP64 we do not have explicit reduction or iteration instructions:
iteration is performed simply by issuing a Vector-Context on top
of a base instruction where OH LOOK! the difference between the
register number src snd dest happens to be exactly one, and OH LOOK!
on each time round the multi-issue-capable execution backend
you get spammed with ADD r1, r2 ADD r2, r3 ADD r3, r4 etc etc
which looks an awful lot like iteration / reduction and is inherently
precise exception interruptible.

we are however also working out an explicit (fixed, predictable)
paralleliseable reduction schedule, it is quite tricky. but, as a fixed
schedule, even non-commutative operations can be thrown at it.

l.

On Tuesday, August 24, 2021 at 5:24:16 PM UTC+1, Stephen Fuld wrote:

> As was pointed out earlier, you can certainly get this by unrolling the
> loop, then doing the final add of the two partial sums outside of the
> loop. But this makes the code "specify" the number of lanes (i.e. how
> many times the loop is unrolled by), thus makes it hardware model
> specific (i.e. it can't take advantage of a more powerful model with say
> four appropriate FUs).

we designed a reduction "schedule" which does exactly that and
is not tied to the microarchitectural width.

it is a recursive tree algorithm (butterfly-like) as part of the SVP64
Specification. hardware will be required to implement that
algorithm or one that produces the exact same result.

it is possible in other words if you are willing to make the decision
to make it part of the specification of the ISA. ARM did something
similar i believe

however i am not sure that a Vertical-First ISA such as VVM the
concept of Horizontal Reduction even makes sense. i have a strong
feeling they are mutually exclusively incompatible.

l.

On Friday, August 27, 2021 at 5:05:20 PM UTC-5, luke.l...@gmail.com wrote:
> On Monday, August 23, 2021 at 10:55:26 PM UTC+1, MitchAlsup wrote:
>
> > The major problem is where does one store the state on an interrupt
> > taken inside of the loop. I am letting my subconscious dwell on it right
> > now.
<
Reminding others that this state is 1076 bits long.
<
> the answer is, without an actual register, you can't.
>
> even if it was a Special Purpose register for storing
> in-flight data, it's still a register.
>
> if it was an actual GPR/FPR, actually named
> in the instruction (and given as a src/dst into
> the FMAC as the accumulator) *now* you
> have a register to actually store in-flight
> data during an interrupt. it can even be
> context switched.
<
OK, so what register do you have that is big enough to hold all 1076 bits ?
>
> a lot of things in SVP64 look overly complex until precise interrupt
> handling is thrown into the pot.
>
> l.

On Saturday, August 28, 2021 at 12:55:31 AM UTC+1, MitchAlsup wrote:

> OK, so what register do you have that is big enough to hold all 1076 bits ?

none, i'm limiting things to 64 bit, so that'd need to be
done across multiple registers (long arithmetic, big
integer math).

one option to explore: the iteration/reduction in SVP64, the
parallel schedule, *requires* a Vector src/dest for use as
an accumulator, because it is used to store partial parallel
results as part of the tree reduction. this has an advantage
in that it solves the precise exception problem.

the only reason this is possible is because SVP64 has explicit
not implicit Vector registers, mapped onto the (enlargened)
scalar regfile.

if VVM was similarly extended to have *actual* Vector registers
as opposed to its current design of only mapping elements onto
in-flight Reservation Stations, *then* there would be somewhere
to put large in-flight data (such as 1076 bits).

l

MitchAlsup wrote:
> On Friday, August 27, 2021 at 5:05:20 PM UTC-5, luke.l...@gmail.com wrote:
>> On Monday, August 23, 2021 at 10:55:26 PM UTC+1, MitchAlsup wrote:
>>
>>> The major problem is where does one store the state on an interrupt
>>> taken inside of the loop. I am letting my subconscious dwell on it right
>>> now.
> <
> Reminding others that this state is 1076 bits long.
> <
>> the answer is, without an actual register, you can't.
>>
>> even if it was a Special Purpose register for storing
>> in-flight data, it's still a register.
>>
>> if it was an actual GPR/FPR, actually named
>> in the instruction (and given as a src/dst into
>> the FMAC as the accumulator) *now* you
>> have a register to actually store in-flight
>> data during an interrupt. it can even be
>> context switched.
> <
> OK, so what register do you have that is big enough to hold all 1076 bits ?
>> a lot of things in SVP64 look overly complex until precise interrupt
>> handling is thrown into the pot.
>>
>> l.

Did you decide against the barf-buffer?

On Saturday, August 28, 2021 at 3:17:41 PM UTC+1, EricP wrote:
> Did you decide against the barf-buffer?

https://m.youtube.com/watch?v=KvzrguhmK0o&t=17