EricP wrote:
>
> The sum and trigger have enough bit to not overflow.
> For 1024 8-bit integer synapse weights the parallel adder looks
> like it requires 2048 adders varying in size from 8 to 8+10 bits
> producing an 18 bit total. Does that sound correct?

Its only 1023 adders.

In this example each neuron must sum 1024 signed weights,
implemented as a tree of adders for operand pairs,
probaby pipelined because of the number of layers.

512 9-bit adders
256 10-bit adders
....
2 17-bit adders
1 18-bit adder

I was curious whether there was a better way to do this than
a tree of adders. A bit of poking about finds these are called
"multi-operand adders" and there has been a fair amount of
research on these since NN became a thing.

There are a few approaches that have different power, area, delay
properties, e.g. Array tree adder, Wallace tree adder,
Balanced delay tree adder and Overturned-stairs tree adder.

But I can't find anything significantly better than a tree of adders.

On Thursday, November 18, 2021 at 11:30:01 AM UTC-6, EricP wrote:
> EricP wrote:
> >
> > The sum and trigger have enough bit to not overflow.
> > For 1024 8-bit integer synapse weights the parallel adder looks
> > like it requires 2048 adders varying in size from 8 to 8+10 bits
> > producing an 18 bit total. Does that sound correct?
> Its only 1023 adders.
>
> In this example each neuron must sum 1024 signed weights,
> implemented as a tree of adders for operand pairs,
> probaby pipelined because of the number of layers.
>
> 512 9-bit adders
> 256 10-bit adders
> ...
> 2 17-bit adders
> 1 18-bit adder
>
> I was curious whether there was a better way to do this than
> a tree of adders. A bit of poking about finds these are called
> "multi-operand adders" and there has been a fair amount of
> research on these since NN became a thing.
>
> There are a few approaches that have different power, area, delay
> properties, e.g. Array tree adder, Wallace tree adder,
> Balanced delay tree adder and Overturned-stairs tree adder.
>
> But I can't find anything significantly better than a tree of adders.
<
Tree of carry save adders ?? !!

EricP <ThatWouldBeTelling@thevillage.com> schrieb:
> EricP wrote:
>>
>> The sum and trigger have enough bit to not overflow.
>> For 1024 8-bit integer synapse weights the parallel adder looks
>> like it requires 2048 adders varying in size from 8 to 8+10 bits
>> producing an 18 bit total. Does that sound correct?
>
> Its only 1023 adders.
>
> In this example each neuron must sum 1024 signed weights,
> implemented as a tree of adders for operand pairs,
> probaby pipelined because of the number of layers.
>
> 512 9-bit adders
> 256 10-bit adders
> ...
> 2 17-bit adders
> 1 18-bit adder
>
> I was curious whether there was a better way to do this than
> a tree of adders. A bit of poking about finds these are called
> "multi-operand adders" and there has been a fair amount of
> research on these since NN became a thing.

You can do it as a carry-save adder until there are only two 17-bit
numbers left. Think Wallace (or Dadda) tree.

Using 4:2 compressors will reduce the number of bits by a factor of
(roughly) two for each level, without having to worry about carry
propagation until the last two numbers are added.

MitchAlsup wrote:
> On Thursday, November 18, 2021 at 11:30:01 AM UTC-6, EricP wrote:
>> EricP wrote:
>>>
>>> The sum and trigger have enough bit to not overflow.
>>> For 1024 8-bit integer synapse weights the parallel adder looks
>>> like it requires 2048 adders varying in size from 8 to 8+10 bits
>>> producing an 18 bit total. Does that sound correct?
>> Its only 1023 adders.
>>
>> In this example each neuron must sum 1024 signed weights,
>> implemented as a tree of adders for operand pairs,
>> probaby pipelined because of the number of layers.
>>
>> 512 9-bit adders
>> 256 10-bit adders
>> ...
>> 2 17-bit adders
>> 1 18-bit adder
>>
>> I was curious whether there was a better way to do this than
>> a tree of adders. A bit of poking about finds these are called
>> "multi-operand adders" and there has been a fair amount of
>> research on these since NN became a thing.
>>
>> There are a few approaches that have different power, area, delay
>> properties, e.g. Array tree adder, Wallace tree adder,
>> Balanced delay tree adder and Overturned-stairs tree adder.
>>
>> But I can't find anything significantly better than a tree of adders.
> <
> Tree of carry save adders ?? !!
>
Indeed!

That should be the first option for any structure like this,
particularly when/if you only need to extract the final result quite rarely.

No need to suffer the final carry propagation delay more than once, right?

Terje

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

On Thursday, November 18, 2021 at 1:49:58 PM UTC-6, Terje Mathisen wrote:
> MitchAlsup wrote:
> > On Thursday, November 18, 2021 at 11:30:01 AM UTC-6, EricP wrote:
> >> EricP wrote:
> >>>
> >>> The sum and trigger have enough bit to not overflow.
> >>> For 1024 8-bit integer synapse weights the parallel adder looks
> >>> like it requires 2048 adders varying in size from 8 to 8+10 bits
> >>> producing an 18 bit total. Does that sound correct?
> >> Its only 1023 adders.
> >>
> >> In this example each neuron must sum 1024 signed weights,
> >> implemented as a tree of adders for operand pairs,
> >> probaby pipelined because of the number of layers.
> >>
> >> 512 9-bit adders
> >> 256 10-bit adders
> >> ...
> >> 2 17-bit adders
> >> 1 18-bit adder
> >>
> >> I was curious whether there was a better way to do this than
> >> a tree of adders. A bit of poking about finds these are called
> >> "multi-operand adders" and there has been a fair amount of
> >> research on these since NN became a thing.
> >>
> >> There are a few approaches that have different power, area, delay
> >> properties, e.g. Array tree adder, Wallace tree adder,
> >> Balanced delay tree adder and Overturned-stairs tree adder.
> >>
> >> But I can't find anything significantly better than a tree of adders.
> > <
> > Tree of carry save adders ?? !!
> >
> Indeed!
>
> That should be the first option for any structure like this,
> particularly when/if you only need to extract the final result quite rarely.
>
> No need to suffer the final carry propagation delay more than once, right?
<
The rule of thumb for large sums is that you use one (1, uno, a single) carry chain
and as many 3-2 counters or 4-2-compressors as you need to reduce the sums
and carries to 2. All accumulations can be doin in carry save--in fact the entire
integer unit of the NEC-S/X (forgot model) was carry save so that adds would
always be 1 cycle. The only time the sums and carries were integerized was
when they were used in address arithmetic.
<
This was also how the Goldschmidt FDIV algorithm worked on the 360/91.
<
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

MitchAlsup wrote:
> On Thursday, November 18, 2021 at 11:30:01 AM UTC-6, EricP wrote:
>> EricP wrote:
>>> The sum and trigger have enough bit to not overflow.
>>> For 1024 8-bit integer synapse weights the parallel adder looks
>>> like it requires 2048 adders varying in size from 8 to 8+10 bits
>>> producing an 18 bit total. Does that sound correct?
>> Its only 1023 adders.
>>
>> In this example each neuron must sum 1024 signed weights,
>> implemented as a tree of adders for operand pairs,
>> probaby pipelined because of the number of layers.
>>
>> 512 9-bit adders
>> 256 10-bit adders
>> ...
>> 2 17-bit adders
>> 1 18-bit adder
>>
>> I was curious whether there was a better way to do this than
>> a tree of adders. A bit of poking about finds these are called
>> "multi-operand adders" and there has been a fair amount of
>> research on these since NN became a thing.
>>
>> There are a few approaches that have different power, area, delay
>> properties, e.g. Array tree adder, Wallace tree adder,
>> Balanced delay tree adder and Overturned-stairs tree adder.
>>
>> But I can't find anything significantly better than a tree of adders.
> <
> Tree of carry save adders ?? !!

Right. My brain fart there. Apologies.
I read that on FPGA's, for adders less than 32 bits Ripple Carry Adder
(RCA) is faster than Carry Save Adder due to routing delays,
and then interpreted everything as an RCA tree.
Had I looked a little further I would have seen they were
actually making a case for using 4:2 compressors.

On Thursday, November 18, 2021 at 4:01:06 PM UTC-6, EricP wrote:
> MitchAlsup wrote:
> > On Thursday, November 18, 2021 at 11:30:01 AM UTC-6, EricP wrote:
> >> EricP wrote:
> >>> The sum and trigger have enough bit to not overflow.
> >>> For 1024 8-bit integer synapse weights the parallel adder looks
> >>> like it requires 2048 adders varying in size from 8 to 8+10 bits
> >>> producing an 18 bit total. Does that sound correct?
> >> Its only 1023 adders.
> >>
> >> In this example each neuron must sum 1024 signed weights,
> >> implemented as a tree of adders for operand pairs,
> >> probaby pipelined because of the number of layers.
> >>
> >> 512 9-bit adders
> >> 256 10-bit adders
> >> ...
> >> 2 17-bit adders
> >> 1 18-bit adder
> >>
> >> I was curious whether there was a better way to do this than
> >> a tree of adders. A bit of poking about finds these are called
> >> "multi-operand adders" and there has been a fair amount of
> >> research on these since NN became a thing.
> >>
> >> There are a few approaches that have different power, area, delay
> >> properties, e.g. Array tree adder, Wallace tree adder,
> >> Balanced delay tree adder and Overturned-stairs tree adder.
> >>
> >> But I can't find anything significantly better than a tree of adders.
> > <
> > Tree of carry save adders ?? !!
<
> Right. My brain fart there. Apologies.
> I read that on FPGA's, for adders less than 32 bits Ripple Carry Adder
> (RCA) is faster than Carry Save Adder due to routing delays,
> and then interpreted everything as an RCA tree.
> Had I looked a little further I would have seen they were
> actually making a case for using 4:2 compressors.
<
Every person who wants to call themselves a computer architect should
understand the "math" behind the delay of an Adder:: whether it be a
ripple carry adder (4+bits), a carry-propogate adder (5+ln4(bits)), a
carry select adder (6+ln8(bits)), and also understand that there are
special adders to better deal with the delay characteristics of multiplier
trees (Baugh Wooley) and adders designed for "other purposes" like
Kooge-Stone adders.
<
Apparently we have a NG filled with people who don't really want to be
known of as computer architects..............sigh......................

For Thor the neuron is based on a weighted sum, using a multiplier and adder.
A clocked circuit is used and values are multiplied and added in sequence, the
operation iterates through a table using a counter. This has an advantage that
the values used may be partitioned allowing the same neuron to emulate more
than one neuron. I am not sure but a cascaded tree of 1024 adders with multipliers
in an FPGA is bound to use a lot of resources and be slow. A faster clock can be
used for a sequenced adder. I am curious what the difference in propagation delay
between input to output would be for a sequenced approach versus a direct
approach. I expect the adder tree approach to be many times faster, but it is
possible to fit many more neurons operating in parallel with a sequenced approach
because it uses fewer resources.
1 Thor Neuron uses: 2132 LUTs, 9 DSP blocks, 220 FF’s and 1.5 BRAMs..
Thor currently has 8 neurons operating in parallel, but it may be possible to increase
the count to 16.
Software is going to be relied on to map a virtual neural net to the available neurons.

On Sunday, November 21, 2021 at 4:33:26 PM UTC-6, robf...@gmail.com wrote:
> For Thor the neuron is based on a weighted sum, using a multiplier and adder.
> A clocked circuit is used and values are multiplied and added in sequence, the
> operation iterates through a table using a counter. This has an advantage that
> the values used may be partitioned allowing the same neuron to emulate more
> than one neuron. I am not sure but a cascaded tree of 1024 adders with multipliers
> in an FPGA is bound to use a lot of resources and be slow. A faster clock can be
> used for a sequenced adder. I am curious what the difference in propagation delay
> between input to output would be for a sequenced approach versus a direct
> approach. I expect the adder tree approach to be many times faster, but it is
> possible to fit many more neurons operating in parallel with a sequenced approach
> because it uses fewer resources.
> 1 Thor Neuron uses: 2132 LUTs, 9 DSP blocks, 220 FF’s and 1.5 BRAMs.
> Thor currently has 8 neurons operating in parallel, but it may be possible to increase
> the count to 16.
> Software is going to be relied on to map a virtual neural net to the available neurons.

Barrel processors would seem to be a natural for problems with NN timing on FPGAs?
Decent Wikipedia page on barrel processors in general (with several examples).
Charles LaForest has a summary of his thesis work: http://fpgacpu.ca/octavo/
He utilizes the DSP blocks at their maximum frequency.
Another barrel processor: https://opencores.org/projects/avr_hp, probably others
And other vector and multiple issue designs.

On 11/21/2021 4:27 PM, JimBrakefield wrote:
> On Sunday, November 21, 2021 at 4:33:26 PM UTC-6, robf...@gmail.com wrote:
>> For Thor the neuron is based on a weighted sum, using a multiplier and adder.
>> A clocked circuit is used and values are multiplied and added in sequence, the
>> operation iterates through a table using a counter. This has an advantage that
>> the values used may be partitioned allowing the same neuron to emulate more
>> than one neuron. I am not sure but a cascaded tree of 1024 adders with multipliers
>> in an FPGA is bound to use a lot of resources and be slow. A faster clock can be
>> used for a sequenced adder. I am curious what the difference in propagation delay
>> between input to output would be for a sequenced approach versus a direct
>> approach. I expect the adder tree approach to be many times faster, but it is
>> possible to fit many more neurons operating in parallel with a sequenced approach
>> because it uses fewer resources.
>> 1 Thor Neuron uses: 2132 LUTs, 9 DSP blocks, 220 FF’s and 1.5 BRAMs.
>> Thor currently has 8 neurons operating in parallel, but it may be possible to increase
>> the count to 16.
>> Software is going to be relied on to map a virtual neural net to the available neurons.
>
> Barrel processors would seem to be a natural for problems with NN timing on FPGAs?
> Decent Wikipedia page on barrel processors in general (with several examples).
> Charles LaForest has a summary of his thesis work: http://fpgacpu.ca/octavo/
> He utilizes the DSP blocks at their maximum frequency.
> Another barrel processor: https://opencores.org/projects/avr_hp, probably others
> And other vector and multiple issue designs.
>

CDC6600 Peripheral Processor.

On Sunday, November 21, 2021 at 7:04:30 PM UTC-6, Ivan Godard wrote:
> On 11/21/2021 4:27 PM, JimBrakefield wrote:
> > On Sunday, November 21, 2021 at 4:33:26 PM UTC-6, robf...@gmail.com wrote:
> >> For Thor the neuron is based on a weighted sum, using a multiplier and adder.
> >> A clocked circuit is used and values are multiplied and added in sequence, the
> >> operation iterates through a table using a counter. This has an advantage that
> >> the values used may be partitioned allowing the same neuron to emulate more
> >> than one neuron. I am not sure but a cascaded tree of 1024 adders with multipliers
> >> in an FPGA is bound to use a lot of resources and be slow. A faster clock can be
> >> used for a sequenced adder. I am curious what the difference in propagation delay
> >> between input to output would be for a sequenced approach versus a direct
> >> approach. I expect the adder tree approach to be many times faster, but it is
> >> possible to fit many more neurons operating in parallel with a sequenced approach
> >> because it uses fewer resources.
> >> 1 Thor Neuron uses: 2132 LUTs, 9 DSP blocks, 220 FF’s and 1.5 BRAMs.
> >> Thor currently has 8 neurons operating in parallel, but it may be possible to increase
> >> the count to 16.
> >> Software is going to be relied on to map a virtual neural net to the available neurons.
> >
> > Barrel processors would seem to be a natural for problems with NN timing on FPGAs?
> > Decent Wikipedia page on barrel processors in general (with several examples).
> > Charles LaForest has a summary of his thesis work: http://fpgacpu.ca/octavo/
> > He utilizes the DSP blocks at their maximum frequency.
> > Another barrel processor: https://opencores.org/projects/avr_hp, probably others
> > And other vector and multiple issue designs.
> >
> CDC6600 Peripheral Processor.
<
Qualcom micro-CPU.

On Sunday, November 21, 2021 at 7:04:30 PM UTC-6, Ivan Godard wrote:
> On 11/21/2021 4:27 PM, JimBrakefield wrote:
> > On Sunday, November 21, 2021 at 4:33:26 PM UTC-6, robf...@gmail.com wrote:
> >> For Thor the neuron is based on a weighted sum, using a multiplier and adder.
> >> A clocked circuit is used and values are multiplied and added in sequence, the
> >> operation iterates through a table using a counter. This has an advantage that
> >> the values used may be partitioned allowing the same neuron to emulate more
> >> than one neuron. I am not sure but a cascaded tree of 1024 adders with multipliers
> >> in an FPGA is bound to use a lot of resources and be slow. A faster clock can be
> >> used for a sequenced adder. I am curious what the difference in propagation delay
> >> between input to output would be for a sequenced approach versus a direct
> >> approach. I expect the adder tree approach to be many times faster, but it is
> >> possible to fit many more neurons operating in parallel with a sequenced approach
> >> because it uses fewer resources.
> >> 1 Thor Neuron uses: 2132 LUTs, 9 DSP blocks, 220 FF’s and 1.5 BRAMs.
> >> Thor currently has 8 neurons operating in parallel, but it may be possible to increase
> >> the count to 16.
> >> Software is going to be relied on to map a virtual neural net to the available neurons.
> >
> > Barrel processors would seem to be a natural for problems with NN timing on FPGAs?
> > Decent Wikipedia page on barrel processors in general (with several examples).
> > Charles LaForest has a summary of his thesis work: http://fpgacpu.ca/octavo/
> > He utilizes the DSP blocks at their maximum frequency.
> > Another barrel processor: https://opencores.org/projects/avr_hp, probably others
> > And other vector and multiple issue designs.
> >
> CDC6600 Peripheral Processor.

|> CDC6600 Peripheral Processor.
Have some experience, could read/write five 12-bit "bytes" to/from 6600 main memory at a time.
Perhaps the best (with documentation) example of a barrel processor.

JCB humor:
Lincoln said God must have loved the poor, he made so many of them.
Cray liked the CDC160 cause he made a lot of them (10 on each 6600).

The ten "160" uP took one of the 16 frames on a 6600. The CPU took eight?
The in-order slow 6400 CPU took one frame. Various combinations were sold.

On Sunday, November 21, 2021 at 7:45:03 PM UTC-6, JimBrakefield wrote:
> On Sunday, November 21, 2021 at 7:04:30 PM UTC-6, Ivan Godard wrote:
> > On 11/21/2021 4:27 PM, JimBrakefield wrote:
> > > On Sunday, November 21, 2021 at 4:33:26 PM UTC-6, robf...@gmail.com wrote:
> > >> For Thor the neuron is based on a weighted sum, using a multiplier and adder.
> > >> A clocked circuit is used and values are multiplied and added in sequence, the
> > >> operation iterates through a table using a counter. This has an advantage that
> > >> the values used may be partitioned allowing the same neuron to emulate more
> > >> than one neuron. I am not sure but a cascaded tree of 1024 adders with multipliers
> > >> in an FPGA is bound to use a lot of resources and be slow. A faster clock can be
> > >> used for a sequenced adder. I am curious what the difference in propagation delay
> > >> between input to output would be for a sequenced approach versus a direct
> > >> approach. I expect the adder tree approach to be many times faster, but it is
> > >> possible to fit many more neurons operating in parallel with a sequenced approach
> > >> because it uses fewer resources.
> > >> 1 Thor Neuron uses: 2132 LUTs, 9 DSP blocks, 220 FF’s and 1.5 BRAMs.
> > >> Thor currently has 8 neurons operating in parallel, but it may be possible to increase
> > >> the count to 16.
> > >> Software is going to be relied on to map a virtual neural net to the available neurons.
> > >
> > > Barrel processors would seem to be a natural for problems with NN timing on FPGAs?
> > > Decent Wikipedia page on barrel processors in general (with several examples).
> > > Charles LaForest has a summary of his thesis work: http://fpgacpu.ca/octavo/
> > > He utilizes the DSP blocks at their maximum frequency.
> > > Another barrel processor: https://opencores.org/projects/avr_hp, probably others
> > > And other vector and multiple issue designs.
> > >
> > CDC6600 Peripheral Processor.
> |> CDC6600 Peripheral Processor.
> Have some experience, could read/write five 12-bit "bytes" to/from 6600 main memory at a time.
> Perhaps the best (with documentation) example of a barrel processor.
>
> JCB humor:
> Lincoln said God must have loved the poor, he made so many of them.
> Cray liked the CDC160 cause he made a lot of them (10 on each 6600).
>
> The ten "160" uP took one of the 16 frames on a 6600. The CPU took eight?
> The in-order slow 6400 CPU took one frame. Various combinations were sold..
<
In a barrel processor there is one execution pipeline and n× fetch-writeback
pipeline-stages.
<
When a PP Read main memory, it had to do so using 5 LD instructions in a row
each LD getting 12-bits. Should such a LD not be fetched, that slot of the R-W
pryamid would simply be skipped. So if PP knew it was reading an address
(18 bits) it could use 2 LDs.
<
The PPs were not as complicated as a DG-NOVA.

Also note: although not claimed as a barrel processor::

reading the B6700 processor patents circa 1970-1985 one could
easily imaging that the B6700 was a 3-deep barrel; especilly those
at a circuit design and pipeline design levels.

On Sunday, November 21, 2021 at 6:27:54 PM UTC-6, JimBrakefield wrote:
> On Sunday, November 21, 2021 at 4:33:26 PM UTC-6, robf...@gmail.com wrote:
> > For Thor the neuron is based on a weighted sum, using a multiplier and adder.
> > A clocked circuit is used and values are multiplied and added in sequence, the
> > operation iterates through a table using a counter. This has an advantage that
> > the values used may be partitioned allowing the same neuron to emulate more
> > than one neuron. I am not sure but a cascaded tree of 1024 adders with multipliers
> > in an FPGA is bound to use a lot of resources and be slow. A faster clock can be
> > used for a sequenced adder. I am curious what the difference in propagation delay
> > between input to output would be for a sequenced approach versus a direct
> > approach. I expect the adder tree approach to be many times faster, but it is
> > possible to fit many more neurons operating in parallel with a sequenced approach
> > because it uses fewer resources.
> > 1 Thor Neuron uses: 2132 LUTs, 9 DSP blocks, 220 FF’s and 1.5 BRAMs.
> > Thor currently has 8 neurons operating in parallel, but it may be possible to increase
> > the count to 16.
> > Software is going to be relied on to map a virtual neural net to the available neurons.
> Barrel processors would seem to be a natural for problems with NN timing on FPGAs?
> Decent Wikipedia page on barrel processors in general (with several examples).
> Charles LaForest has a summary of his thesis work: http://fpgacpu.ca/octavo/
> He utilizes the DSP blocks at their maximum frequency.
> Another barrel processor: https://opencores.org/projects/avr_hp, probably others
> And other vector and multiple issue designs.

Uncle: Deep NN is too big and moving too fast for me to keep up.
https://xilinx.github.io/finn/about looks like my entry point into hacking FPGA NNs

The fast Walsh Hadamard transform needs only add and subtract operations. It is easy to turn into a neural network. I have a booklet for $25 US. Side-channel browser attacks are making typing very slow. Lol.