[libre-riscv-dev] outstanding commit pending counters (for multi issue)

Luke Kenneth Casson Leighton lkcl at lkcl.net
Wed Jun 5 02:58:41 BST 2019

Mitch, hi,

Your question earlier "what happens to the instruction commit counter per
FU when a branch or ST operation occurs" was a good one that allowed me to
refine the concept. Documented hereafter.

The issue is that when using bitmatrices as a linked list to preserve
instruction order, whilst this works transitively (cumulatively) in a multi
issue context, when it comes to *dropping* multiple dependencies at once
(multi-commit) it is inadequate...

... on its own.

The solution I came up with is for each FU to have a *count* - as an
integer - of the exact same number of bits that were transitively raised to
cast the shadows which preserve instruction order.

Thus, if the resource that is to be committed to (regfile) has 4 write
ports, we *know* for a fact that any FU with a "count" of 1 thru 4 are the
last 4 FUs with the oldest instructions ready to retire (commit inorder).

It is quite simple and elegant.

The mistake that I made - the assumption that you caught Mitch - was that
the count is on the number of instructions *issued*, it is not, it is a
binary count of the bitmatrix transitive shadows cast over a given FU...
*per contended resource*

In other words, a separate bitmatrix shadow and associated binary count is
required for the regfile write ports... and a *separate* count is similarly
needed for the LD/ST resource.

Thus, for a Branch instruction, the binary count would NOT be increased for
the regfile, nor would it be increased for the MemRef DMs either.

When it came to instruction retire time, both the regcount *and*
memrefcount would be found to be below the appropriate per-cycle retire
thresholds and the branch allowed to retire (its transitive commit bits
dropped) without actually having anything to commit.

Similarly, a ST would, whilst the regfile write port commit count would be
within the commit threshold, the MemRef commit count could potentially NOT
be, and such an instruction would need other MemRef Dependencies to be
retired first, bringing its count similarly below the threshold.

LD is slightly odd in that it has *two* countrefs that it has to respect.
BOTH counts need to drop below the threshold in order to have the
instruction be eligible for in-order retirement.

This all just to ensure that no instruction may ever be retired out of

With such guarantees however, other things becone much safer, such as we
know that WaW is taken care of, that multi issue WaW is likewise safe, that
single and multi issue ST WaW is also safe.

Also, I feel much more comfortable with exceptions (the unwind stack),
branch prediction and speculation, with the Vectorisation of LDs and STs,
one major issue is what to do if an element LD or ST throws an exception,
where do you "unwind" to?

If the commit order has not been perfectly preserved, the question is moot
because it is too late, the damage may have been done (even by a LD) on an
element that was successful but out of order.

With a preserved order, the current "element index" can be unwound to just
before the element-LD that threw the exception, a page miss can be handled,
and execution of the Vectorisation loop continued where it was formerly

*this is not possible without perfect in-order preservation*.

So, thank you for asking the simple but critical question, Mitch.


crowd-funded eco-conscious hardware: https://www.crowdsupply.com/eoma68

More information about the libre-riscv-dev mailing list