Anton Ertl wrote:
> EricP <ThatWouldBeTelling@thevillage.com> writes:
>> Anton Ertl wrote:
> [..]
>> But trying to come up with a circuit that can choose the optimum
>> crossbar configuration in 1 clock proved too difficult at that time.
>
> How about taking >1 cycle? What would suffer in that case?

Continued from prior msg...

To rename 4 or more lanes I needed was a faster way to allocate
resources in parallel with some log_N gate delay growth.

One part of the mechanism I came up with I call a "running popcount'.
It takes a vector of input bits, and outputs for each bit position
the sum the number number of 1's at that position and before.

e.g. from left to right

Pos: 0 1 2 3 4 5 6 7
Bit: 0 0 1 1 0 1 0 1
Sum: 0 0 1 2 2 3 3 4

At position 5 the sum is 3 1-bits there and to the left.

A running popcount circuit can be built from a multiple layer
summation tree, requiring log_2(number of input bits) layers.
I start by separating the inputs into groups of 3 because
a single full adder can sum 3 input bits.
Then the 3-groups are joined together into 6-groups, 12-groups, ...
with each layer doubling in size until all the input bits are counted.
So 255 inputs can be running-popcount'ed with 8 layers of
7-bit or less carry-lookahead adders.

The running popcount circuit can be used to select resources.
Each free resource indicates with a 1 input.
A compare-EQ (nxor) on the output of each position compares
that position sum to a fixed number. If the input is a 1 AND
the output sum == 3 then this is the third free resource.
The position number is converted to binary and output as the
resource number of the third available free resource.

I had planned on using that for choosing free physical registers
for multiple lanes.

A running popcount could also be used to allocate register read ports
to uOp lanes. Each uOp outputs a 1 for each source register that it reads,
the running sum is the port number to be used for reading that operand.
If a uOp gets a port for all its register operands then it can dispatch.
The number of resources to choose from is of course smaller than
what I was choosing from. For 4 lanes, with uOps usually having 2 source
registers, plus a couple of extras, so maybe 10 read ports.

On Thursday, May 11, 2023 at 2:50:55 PM UTC-5, EricP wrote:
> Anton Ertl wrote:
> > EricP <ThatWould...@thevillage.com> writes:
> >> Anton Ertl wrote:
> > [..]
> >> But trying to come up with a circuit that can choose the optimum
> >> crossbar configuration in 1 clock proved too difficult at that time.
> >
> > How about taking >1 cycle? What would suffer in that case?
> Continued from prior msg...
> To rename 4 or more lanes I needed was a faster way to allocate
> resources in parallel with some log_N gate delay growth.
> One part of the mechanism I came up with I call a "running popcount'.
> It takes a vector of input bits, and outputs for each bit position
> the sum the number number of 1's at that position and before.
>
> e.g. from left to right
>
> Pos: 0 1 2 3 4 5 6 7
> Bit: 0 0 1 1 0 1 0 1
> Sum: 0 0 1 2 2 3 3 4
>
> At position 5 the sum is 3 1-bits there and to the left.
<
An admirable invention.
>
> A running popcount circuit can be built from a multiple layer
> summation tree, requiring log_2(number of input bits) layers.
> I start by separating the inputs into groups of 3 because
> a single full adder can sum 3 input bits.
<
At this point, you have a multiplier summation tree, an odd
multiplication width and an even odder multiplication height.
<
> Then the 3-groups are joined together into 6-groups, 12-groups, ...
> with each layer doubling in size until all the input bits are counted.
> So 255 inputs can be running-popcount'ed with 8 layers of
> 7-bit or less carry-lookahead adders.
<
One can implement Popcount as multiplication by altering the
Boothe recoder so that only the center column of the tree has
bit-product terms.
>
> The running popcount circuit can be used to select resources.
> Each free resource indicates with a 1 input.
> A compare-EQ (nxor) on the output of each position compares
> that position sum to a fixed number. If the input is a 1 AND
> the output sum == 3 then this is the third free resource.
> The position number is converted to binary and output as the
> resource number of the third available free resource.
>
> I had planned on using that for choosing free physical registers
> for multiple lanes.
>
> A running popcount could also be used to allocate register read ports
> to uOp lanes. Each uOp outputs a 1 for each source register that it reads,
> the running sum is the port number to be used for reading that operand.
> If a uOp gets a port for all its register operands then it can dispatch.
> The number of resources to choose from is of course smaller than
> what I was choosing from. For 4 lanes, with uOps usually having 2 source
> registers, plus a couple of extras, so maybe 10 read ports.

MitchAlsup wrote:
> On Thursday, May 11, 2023 at 2:50:55 PM UTC-5, EricP wrote:
>> Anton Ertl wrote:
>>> EricP <ThatWould...@thevillage.com> writes:
>>>> Anton Ertl wrote:
>>> [..]
>>>> But trying to come up with a circuit that can choose the optimum
>>>> crossbar configuration in 1 clock proved too difficult at that time.
>>> How about taking >1 cycle? What would suffer in that case?
>> Continued from prior msg...
>> To rename 4 or more lanes I needed was a faster way to allocate
>> resources in parallel with some log_N gate delay growth.
>> One part of the mechanism I came up with I call a "running popcount'.
>> It takes a vector of input bits, and outputs for each bit position
>> the sum the number number of 1's at that position and before.
>>
>> e.g. from left to right
>>
>> Pos: 0 1 2 3 4 5 6 7
>> Bit: 0 0 1 1 0 1 0 1
>> Sum: 0 0 1 2 2 3 3 4
>>
>> At position 5 the sum is 3 1-bits there and to the left.
> <
> An admirable invention.

I'm not the first one to think of a running popcount
but I did have the same idea independently.

It sums up a series of inputs to count resources requests
which is something people have done for a long time,
such as I was doing for allocating read ports to uOp lanes.

I had thought of this serially which limits its applicability.
Later I realized that counting requests is a kind of popcount so the
sums can be done log_2 allowing it to be applied to larger resource pools.

I see the key idea as having each positions' sum drive a binary decoder
in parallel allowing all the IF-ELSE decisions to run concurrent,
such as output a selected resource id or controlling a mux.
That is where all the selection work is done.

It would take a shit load of gates and having a large number
of positions OR'ing their outputs together in giant trees
will limit how much can actually be done.

>> A running popcount circuit can be built from a multiple layer
>> summation tree, requiring log_2(number of input bits) layers.
>> I start by separating the inputs into groups of 3 because
>> a single full adder can sum 3 input bits.
> <
> At this point, you have a multiplier summation tree, an odd
> multiplication width and an even odder multiplication height.
> <

Yes I knew my summing approach is odd.
My feeling is that I just need to show that there is at least one
feasible implementation of a proposed solution that meets the
requirements of producing a running sum and scales log_2 or better.

>> Then the 3-groups are joined together into 6-groups, 12-groups, ...
>> with each layer doubling in size until all the input bits are counted.
>> So 255 inputs can be running-popcount'ed with 8 layers of
>> 7-bit or less carry-lookahead adders.
> <
> One can implement Popcount as multiplication by altering the
> Boothe recoder so that only the center column of the tree has
> bit-product terms.

Yes but that is for a single popcount value.
This produces a vector of running popcount values.
For N input bits it generates a vector of N sums.

Here I was thinking back to your log_2 decoder that takes tokens
and joins them in pairs, then quads, then octets, etc.
That gave me the idea to do similar but with runs of sums.
The number 3 comes from a full adder summing 3 inputs,
then the group of 3 joins to 6, then 12, 24, 48, ... in a tree of adders.

As you point out there are better way to do this.

On Thursday, May 11, 2023 at 8:50:55 PM UTC+1, EricP wrote:
>
> Pos: 0 1 2 3 4 5 6 7
> Bit: 0 0 1 1 0 1 0 1
> Sum: 0 0 1 2 2 3 3 4
>

there is a vector isa instruction for this, RVV i believe.
nice to see popping up. and impl. discussion.
popcount trees. parallel prefix sum normal way.
1st sum 1st bit, 2nd sum 1st&2nd ...
merge identical tree snippets avoid duplication
should not be mad gates.

l.

On Saturday, May 13, 2023 at 5:44:44 PM UTC+1, EricP wrote:

> It sums up a series of inputs to count resources requests
> which is something people have done for a long time,
> such as I was doing for allocating read ports to uOp lanes.

num ports != max popcount suggests alternative.
num ports <<< max popcount use chained PriorityPickers?
PPs are flat, big AND gates. output from 1st INVERT and mask
out 2nd. repeat.

thoughts? (sorry brief, extreme pain)
l.

On Saturday, May 13, 2023 at 6:18:45 PM UTC+1, luke.l...@gmail.com wrote:
> On Saturday, May 13, 2023 at 5:44:44 PM UTC+1, EricP wrote:
>
> > It sums up a series of inputs to count resources requests
> > which is something people have done for a long time,
> > such as I was doing for allocating read ports to uOp lanes.
> num ports != max popcount suggests alternative.

one of our team created undocumented extra idea. saturated-adders
on prefix-sums. implementation looks incomplete, like idea.

https://git.libre-soc.org/?p=nmutil.git;a=blob;f=src/nmutil/picker.py;h=7aab175d8d60c031020b7b208727156123b8c09f;hb=4bf2f20bddc057df1597d14e0b990c0b9bdeb10e#l244

luke.l...@gmail.com wrote:
> On Saturday, May 13, 2023 at 5:44:44 PM UTC+1, EricP wrote:
>
>> It sums up a series of inputs to count resources requests
>> which is something people have done for a long time,
>> such as I was doing for allocating read ports to uOp lanes.
>
> num ports != max popcount suggests alternative.
> num ports <<< max popcount use chained PriorityPickers?
> PPs are flat, big AND gates. output from 1st INVERT and mask
> out 2nd. repeat.
>
> thoughts? (sorry brief, extreme pain)
> l.

The goal is to dynamically assign source register read ports based
on what each uOp in each lane actually requires so we don't need to
have the worst case number of ports for all uOp lanes.

The problem is that performing conditional resource allocation serially
does not allow many allocations within the stage gate delay width.

Sequentially assigning ports to uOp source registers can be done with
a chain of conditional increments (CI). Say each CI is 3 gate delays.

If each uOp needs 0..3 source ports, and if a stage is 20 gates wide,
then we can afford a chain of 6 CI or just 2 lanes within a stage window,
and we still haven't accounted for other logic overhead.

To get more than 2 lanes we have to either assign ports in parallel,
or do it serially but across multiple pipeline stages (assuming it can).
But to do this across multiple stages requires fixing
the uOps to their lanes early, which means that any front end
pipeline bubbles are fixed in place and those lanes remain empty
(it precludes a compacting front end pipeline optimization).

This is what I was trying to point out earlier,
that it is a bit like trying to pick up Jello with your hands.

On Sunday, May 14, 2023 at 11:30:45 AM UTC-5, EricP wrote:
> luke.l...@gmail.com wrote:
> > On Saturday, May 13, 2023 at 5:44:44 PM UTC+1, EricP wrote:
> >
> >> It sums up a series of inputs to count resources requests
> >> which is something people have done for a long time,
> >> such as I was doing for allocating read ports to uOp lanes.
> >
> > num ports != max popcount suggests alternative.
> > num ports <<< max popcount use chained PriorityPickers?
> > PPs are flat, big AND gates. output from 1st INVERT and mask
> > out 2nd. repeat.
> >
> > thoughts? (sorry brief, extreme pain)
> > l.
> The goal is to dynamically assign source register read ports based
> on what each uOp in each lane actually requires so we don't need to
> have the worst case number of ports for all uOp lanes.
>
> The problem is that performing conditional resource allocation serially
> does not allow many allocations within the stage gate delay width.
>
> Sequentially assigning ports to uOp source registers can be done with
> a chain of conditional increments (CI). Say each CI is 3 gate delays.
>
> If each uOp needs 0..3 source ports, and if a stage is 20 gates wide,
<
That is what you get if you look at it from the instruction point of view.
<
Instead, if you look at it from the function unit point of view, there is
only 1 FU that services 3-rename ports (FMAC), so, while AGEN appears
to service 3-operands, only 2 of them can be registers, and the rest
are known to be 2-ports or 1-port.
<
I am working on a 6-Wide GBOoO design that only has 12-rename
ports, with one 3-register FU (FMAC and INSert and CMOV) and can
dish out new PRNs 6 per cycle.
<
> then we can afford a chain of 6 CI or just 2 lanes within a stage window,
> and we still haven't accounted for other logic overhead.
>
> To get more than 2 lanes we have to either assign ports in parallel,
> or do it serially but across multiple pipeline stages (assuming it can).
<
Route instructions to FUs THEN rename their ports. This eliminates
the 3-rename ports for all instructions; only the FUs that service
3-registers need 3-rename ports.
<
> But to do this across multiple stages requires fixing == routing
> the uOps to their lanes early, which means that any front end
> pipeline bubbles are fixed in place and those lanes remain empty
> (it precludes a compacting front end pipeline optimization).
<
I thought that way too in 1991........ there are solutions......
>
> This is what I was trying to point out earlier,
> that it is a bit like trying to pick up Jello with your hands.

luke.l...@gmail.com wrote:
> On Saturday, May 13, 2023 at 6:18:45 PM UTC+1, luke.l...@gmail.com wrote:
>> On Saturday, May 13, 2023 at 5:44:44 PM UTC+1, EricP wrote:
>>
>>> It sums up a series of inputs to count resources requests
>>> which is something people have done for a long time,
>>> such as I was doing for allocating read ports to uOp lanes.
>> num ports != max popcount suggests alternative.
>
> one of our team created undocumented extra idea. saturated-adders
> on prefix-sums. implementation looks incomplete, like idea.
>
> https://git.libre-soc.org/?p=nmutil.git;a=blob;f=src/nmutil/picker.py;h=7aab175d8d60c031020b7b208727156123b8c09f;hb=4bf2f20bddc057df1597d14e0b990c0b9bdeb10e#l244

I don't know python or your design but if I understand correctly,
yes the BetterMultiPriorityPicker is the same parallel multi-picker
I was referring to. The saturation adder could save propagating carries
unnecessarily (if you only need to pick K items then you only
need to sum to K).

For hardware the other part of the problem is how to get
each of the one-hot picks routed to a separate output port.
In other words a black box that takes N input bits and routes
each successive N-bit wide one-hot pick to successive outputs.

N item bits
|
v
Multi-Picker
---> pick[0] (one-hot, N-bits wide),(item number)
---> pick[1] (one-hot, N-bits wide),(item number)
---> pick[2] (one-hot, N-bits wide),(item number)

A decoder attached to each partial sum can drive the output
for each pick[n] plus generate a binary encoding of the bit position
(saving a one-hot to binary converter for each pick).

Used as a free register allocator, for each pick I get a
one-hot register selector plus a binary register number.

In my case the register number goes to Rename, and the one-hot value
is routed back to select the register status to change and remove it
from the free list if the register is taken by Rename.

MitchAlsup wrote:
> On Sunday, May 14, 2023 at 11:30:45 AM UTC-5, EricP wrote:
>> But to do this across multiple stages requires fixing == routing
>> the uOps to their lanes early, which means that any front end
>> pipeline bubbles are fixed in place and those lanes remain empty
>> (it precludes a compacting front end pipeline optimization).
> <
> I thought that way too in 1991........ there are solutions......

I have a thing for elastic pipelines.