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?

Last week I was working on an allocator for my physical register file.
In my uArch physical registers are allocated by Rename from a
bit vector indicating which registers are free.

The problem is how to do this concurrently for multiple lanes.

Originally I used a priority selector doing a Find-First-1 to select
the first free bit. The physical register file has status bits for
each pReg, one of which is Free. The priority selector scans the free
vector producing a one-hot output, and a one-hot to binary encoder
converts that to a free phy reg number.
A FF1 can be built having log_4 gate delay of the number of scanned bits,
so selecting a free reg from a set of 255 physical registers should
take about 4-5 NAND/NOR gate delays.

Originally to rename multiple lanes I had planned that the priority
selectors would be serially chained: the one-hot output of the first
FF1 masks out that bit from the input of the second FF1, and so on.

free bit vector
|---------------
v | |
FF1 | |
| v |
|------>MASK |
| v |
| FF1 v
| |--->MASK
| | v
| | FF1
v v v
encode encode encode
v v v
lane-0 lane-1 lane-2
free free free
reg# reg# reg#

The problem is the propagation delay for multiple lanes uses
up much of the available time in the Rename stage.
Besides the free register selector there is other gate delay overhead
in Rename so it really didn't look like this FF1 chaining approach
would be usable beyond 2 or maybe 3 lanes.

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

Continued next msg...

On Thursday, May 11, 2023 at 2:48: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?
<
> Last week I was working on an allocator for my physical register file.
> In my uArch physical registers are allocated by Rename from a
> bit vector indicating which registers are free.
>
> The problem is how to do this concurrently for multiple lanes.
<
When I did this (1991 Mc88120), we had a 96 instruction execution
unit and with 32 architectural registers, this gave us a physical register
file of 128 entries; we had a 6-wide machine, so we divided the PRF
into 6 segments; 2 segments got 22 registers, and 4 segments got 21.
<
Now the allocation problem is if the instruction is routed to FU[slot]
then it gets the FF1(PRF[slot]). This was all done in unary, and the
destination register of that instruction is written into the PRF CAM
at the allocated register. Subsequent accesses will match the CAM
and read the proper register.
<
One can make a FF1 as wide as 72-bits taking no more than 4 gate delays
using 4-input NANDs and 3-input NORs. But since we are scanning only a
22-bit field, the delay is 3 gates.
>
> Originally I used a priority selector doing a Find-First-1 to select
> the first free bit. The physical register file has status bits for
> each pReg, one of which is Free. The priority selector scans the free
> vector producing a one-hot output, and a one-hot to binary encoder
> converts that to a free phy reg number.
<
Check,
<
> A FF1 can be built having log_4 gate delay of the number of scanned bits,
> so selecting a free reg from a set of 255 physical registers should
> take about 4-5 NAND/NOR gate delays.
>
> Originally to rename multiple lanes I had planned that the priority
> selectors would be serially chained: the one-hot output of the first
> FF1 masks out that bit from the input of the second FF1, and so on.
>
> free bit vector
> |---------------
> v | |
> FF1 | |
> | v |
> |------>MASK |
> | v |
> | FF1 v
> | |--->MASK
> | | v
> | | FF1
> v v v
> encode encode encode
> v v v
> lane-0 lane-1 lane-2
> free free free
> reg# reg# reg#
>
Segmentation works easier.
>
> The problem is the propagation delay for multiple lanes uses
> up much of the available time in the Rename stage.
> Besides the free register selector there is other gate delay overhead
> in Rename so it really didn't look like this FF1 chaining approach
> would be usable beyond 2 or maybe 3 lanes.
>
> To rename 4 or more lanes I needed was a faster way to
> allocate resources in parallel with some log_N gate delay growth.
>
> Continued next msg...