[libre-riscv-dev] Paper: Scoreboards can deadlock

[Luke Kenneth Casson Leighton]

On Fri, Jun 7, 2019 at 4:41 AM Samuel Falvo II <sam.falvo at gmail.com> wrote:
>
> I found this document while searching the Internet for a different
> text related to scoreboarding, and I thought this might be of some
> interest.
>
> Complexity and Correctness of Computer Architectures
>
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.6065&rep=rep1&type=pdf

 by page 10 the author talks about "inserting NOPs" into the pipeline,
which is valid (i.e. a side-effect of the cancellation).

 however the next statement is, "How that can be accomplished depends
on the type of the storage and on the stage in which it is updated."

 this statement indicates that the author of the paper is utterly
clueless on how precise exceptions - and shadowing - are implemented.

 exceptions (and interrupts if they are allowed to be made
high-priority exceptions) *require* that a shadow exists, to prevent
and prohibit any "damage".

 that shadow is not only cast across the instruction that could cause
"damage", it is cast TRANSITIVELY across ALL FUTURE instructions as
well.

 if that shadow does not exist, you *MUST* let the result commit to
whatever resource it is targetting, because the shadow holds ALL
future instructions from committing, allowing FULL and PRECISE
rollback.

at the bottom of the page the authors starts to go on about "backup of
memory" which is clearly completely the wrong solution.  no mention of
the above shadowing mechanism is even mentioned.

table 18, page 19, the author tries to create a "proof" that there
will be deadlock.

(1)R3=R1+R2
(2)R4=R4/R3
(3)R3=R1*42
(4)R5=R5+R5
(5)R3=...

however, i believe he has failed to take into account that there
exists *TWO* matrices in the 6600 design: the FU-Regs *and* the FU-FU
Matrices.

he says, "However, this restriction requires a nontrivial hardware
extension, because the scoreboard must store the order of the active
instructions."

without realising that the FU-FU Matrix provides the chain of inter-FU
dependencies that makes that moot, as we've discussed only just a
couple of weeks ago.

so from reading the paper, the authors appear to have a faulty
understanding of the internal workings of the 6600.  they also make no
mention of the Write-after-Write stalling that's built-in to the Issue
Unit.

overall then this is a flawed study.

l.