I am trying to find information on elastic pipeline processors but not having much luck.
Were there ever any built this way, or is it just theory? I am having difficulty
with the scoreboarding of registers and how it is handled on a branch miss.
If there is an instruction that tags a register as busy in the register fetch stage, I think that instruction should set the register as available in the commit stage regardless of whether or not the instruction is still valid. Otherwise, wouldn’t the pipeline lock up waiting for the register to become available? An issue is then that invalidated instructions cannot be removed from the pipeline or they wouldn’t make registers available. On a branch miss I was simply going to clear the fifos, but it looks like that won’t work because that will leave registers marked as busy that shouldn’t be. It seems like an elastic pipeline would be slow then as invalid instructions would have to percolate through the pipeline.
I have looked at some sample code of the handling of hazards but I think the code sample is too simple. In the commit stage the registers are flagged as available only if the instruction commits, I think this is too simple and will leave register flagged as busy that shouldn’t be.
I think there needs to be a register busy history correlated to branch instructions. IF there is a branch miss then the previous set of busy registers would be made active. It then gets complicated as busy counters would be used to avoid WAW hazards.

On Wednesday, May 19, 2021 at 7:36:44 PM UTC-5, robf...@gmail.com wrote:
> I am trying to find information on elastic pipeline processors but not having much luck.
> Were there ever any built this way, or is it just theory? I am having difficulty
> with the scoreboarding of registers and how it is handled on a branch miss.
<
A lot of the time we just use the pipeline to store the destination register and its
valid bit. If the valid bit is zero, that 5-bit field does not participate in the interlock.
If you keep track of the register in a storage structure, you end up having to maintain
a bit vector of outstanding results, and when a branch is recovered, these are used
to zap the valid bits.
<
> If there is an instruction that tags a register as busy in the register fetch stage, I think that instruction should set the register as available in the commit stage regardless of whether or not the instruction is still valid.
<
You are forgetting forwarding. You want to be able to use the result register as an operand
at the instant its result is known. You cannot afford to wait for retirement or even commit.
<
Otherwise, wouldn’t the pipeline lock up waiting for the register to become available?
<
You can drain the pipeline and not write the results, too.
<
>An issue is then that invalidated instructions cannot be removed from the pipeline or they wouldn’t make registers available.
<
Obviously, this would not fly.
<
>On a branch miss I was simply going to clear the fifos, but it looks like that won’t work because that will leave registers marked as busy that shouldn’t be.
<
Yep your work is not done.
<
On the other hand if you are using a real CDC 6600-like scoreboard, you can tag the FU valid bits
with which branch shadow this falls under (unary of course), and when a branch is recovered,
the branch broadcasts its failure tag, and all the instructions self destruct, making the register
available.
<
>It seems like an elastic pipeline would be slow then as invalid instructions would have to percolate through the pipeline.
<
Do not confuse the elasticity with record keeping. An elastic pipe would make this problem
only a LITTLE harder. Record keeping in mandatory, and you can never be in a position this
fails.
<
> I have looked at some sample code of the handling of hazards but I think the code sample is too simple. In the commit stage the registers are flagged as available only if the instruction commits, I think this is too simple and will leave register flagged as busy that shouldn’t be.
> I think there needs to be a register busy history correlated to branch instructions.
<
This is the tag I mentioned above, but it can also be done with bit vectors.. On one great Big
Out of Order machine I kept a history table of the valid bits of the physical register file, and
on a branch recovery simply read them all out overwriting the present data, and presto the
machine was back where it was before those 6-instructions were decoded.
<
>IF there is a branch miss then the previous set of busy registers would be made active. It then gets complicated as busy counters would be used to avoid WAW hazards.
<
It is complicated, but it is also very simple.
<
At decode (or issue) time you record the current state of the physical register file valid
bits. The PRF is read by a CAM and written by a decoder. The current valid bits and the
data of the CAM have everything you need to know about the accessibility of the registers.
>
If an instruction writes to a register, you allocate a new PRF entry and write the CAM and
set the valid bit.
<
At the end of decode you create a second bit vector of the registers that become free if
this set of instructions retires.
<
So now we have the bit vector to use if the set of instructions retires and we have the
bit vector to use if the set of instructions does not retire. If we retire, registers get
dumped on the free list, if recovered, the valid bits in the PRF are overwritten and the
PRF is back where it should have been
<
Each set of instruction is issued into the execution window with a modulo number.
If a set of instruction retires, this number can be reused. If the set of instructions
is recovered, this "tag" is used to clear instructions out of the reservation stations
(and calculation units) so they can't deliver calculated values.
<
so you can issue instruction into the execution window when there is modulo number
available, when properly resourced, the PRF is never over capacity when there is said
modulo number, and there are reservation station entries when the modulo number
is available. So if the modulo number is available you can issue instructions into the
window. Easy peezy.
<
You can get into BIG trouble if you under-resource the PRF, the Stations, or the history
table.

On Wednesday, May 19, 2021 at 10:08:19 PM UTC-4, MitchAlsup wrote:
> On Wednesday, May 19, 2021 at 7:36:44 PM UTC-5, robf...@gmail.com wrote:
> > I am trying to find information on elastic pipeline processors but not having much luck.
> > Were there ever any built this way, or is it just theory? I am having difficulty
> > with the scoreboarding of registers and how it is handled on a branch miss.
> <
> A lot of the time we just use the pipeline to store the destination register and its
> valid bit. If the valid bit is zero, that 5-bit field does not participate in the interlock.
> If you keep track of the register in a storage structure, you end up having to maintain
> a bit vector of outstanding results, and when a branch is recovered, these are used
> to zap the valid bits.
> <
> > If there is an instruction that tags a register as busy in the register fetch stage, I think that instruction should set the register as available in the commit stage regardless of whether or not the instruction is still valid.
> <
> You are forgetting forwarding. You want to be able to use the result register as an operand
> at the instant its result is known. You cannot afford to wait for retirement or even commit.
> <
> Otherwise, wouldn’t the pipeline lock up waiting for the register to become available?
> <
> You can drain the pipeline and not write the results, too.
> <
> >An issue is then that invalidated instructions cannot be removed from the pipeline or they wouldn’t make registers available.
> <
> Obviously, this would not fly.
> <
> >On a branch miss I was simply going to clear the fifos, but it looks like that won’t work because that will leave registers marked as busy that shouldn’t be.
> <
> Yep your work is not done.
> <
> On the other hand if you are using a real CDC 6600-like scoreboard, you can tag the FU valid bits
> with which branch shadow this falls under (unary of course), and when a branch is recovered,
> the branch broadcasts its failure tag, and all the instructions self destruct, making the register
> available.
> <
> >It seems like an elastic pipeline would be slow then as invalid instructions would have to percolate through the pipeline.
> <
> Do not confuse the elasticity with record keeping. An elastic pipe would make this problem
> only a LITTLE harder. Record keeping in mandatory, and you can never be in a position this
> fails.
> <
> > I have looked at some sample code of the handling of hazards but I think the code sample is too simple. In the commit stage the registers are flagged as available only if the instruction commits, I think this is too simple and will leave register flagged as busy that shouldn’t be.
> > I think there needs to be a register busy history correlated to branch instructions.
> <
> This is the tag I mentioned above, but it can also be done with bit vectors. On one great Big
> Out of Order machine I kept a history table of the valid bits of the physical register file, and
> on a branch recovery simply read them all out overwriting the present data, and presto the
> machine was back where it was before those 6-instructions were decoded.
> <
> >IF there is a branch miss then the previous set of busy registers would be made active. It then gets complicated as busy counters would be used to avoid WAW hazards.
> <
> It is complicated, but it is also very simple.
> <
> At decode (or issue) time you record the current state of the physical register file valid
> bits. The PRF is read by a CAM and written by a decoder. The current valid bits and the
> data of the CAM have everything you need to know about the accessibility of the registers.
> >
> If an instruction writes to a register, you allocate a new PRF entry and write the CAM and
> set the valid bit.
> <
> At the end of decode you create a second bit vector of the registers that become free if
> this set of instructions retires.
> <
> So now we have the bit vector to use if the set of instructions retires and we have the
> bit vector to use if the set of instructions does not retire. If we retire, registers get
> dumped on the free list, if recovered, the valid bits in the PRF are overwritten and the
> PRF is back where it should have been
> <
> Each set of instruction is issued into the execution window with a modulo number.
> If a set of instruction retires, this number can be reused. If the set of instructions
> is recovered, this "tag" is used to clear instructions out of the reservation stations
> (and calculation units) so they can't deliver calculated values.
> <
> so you can issue instruction into the execution window when there is modulo number
> available, when properly resourced, the PRF is never over capacity when there is said
> modulo number, and there are reservation station entries when the modulo number
> is available. So if the modulo number is available you can issue instructions into the
> window. Easy peezy.
> <
> You can get into BIG trouble if you under-resource the PRF, the Stations, or the history
> table.

Okay, it was a bit simpler than I thought. I was trying to follow sample code too closely.

The scoreboard now tracks which reorder buffer entry is the source for the register file data.
All the functional units write their results to the reorder buffer. So, the reorder buffer entry
can be tracked instead of the function unit. During decode the reorder id is written as the
register file source. During commit the register file is indicated as the register file source.

Fixed the operand bypassing I think. The operand, if coming from the reorder buffer, is now
loaded when the reorder buffer entry commit flag is set. The commit flag being set when the
functional unit is finished the instruction. So, as soon as the result is calculated it is usable
as an operand.

Functional units are fed by queues of the associated instructions so there is no need to wait
until the functional unit is not busy. The only stall is if the queue is full. All the queues are 64
entry as that is the number of entries that may be in a single LUT ram in the FPGA. Issuing
instructions is simple. If the queue is not full and there’s an available instruction with ready
operands, then it is queued. There is a state machine for the functional unit that deques the
next instruction when in the idle state.

Not sure branches will work properly. On a branch decode the register file source table is copied
to a history buffer indexed by the branch tag and the branch tag incremented. During execute
stage if there was a branch mis predict then the register file source table is restored from the
history buffer associated with the branch tag.