# Conversion from Tomasulo to Scoreboards
-See [discussion](http://lists.libre-riscv.org/pipermail/libre-riscv-dev/2020-May/006747.html)
+See [discussion (1)](http://lists.libre-riscv.org/pipermail/libre-riscv-dev/2020-May/006747.html) and
+[discussion (2)](http://lists.libre-riscv.org/pipermail/libre-riscv-dev/2020-May/006904.html)
+
+This page aids and assists in understanding the full functional equivalence
+of a Scoreboard-based design when compared to a Tomasulo algorithm. However
+it is extremely important to note that the Academic literature, by focussing
+exclusively on the published patent covering Q-Tables, is hopelessly inaccurate,
+factually incorrect and completely misleading.
+
+By only comparing Q-Tables against the entirety of the Tomasulo algorithm,
+this is equivalent to narrowly focussing on the Reorder Buffer of
+Tomasulo, excluding all else, and concluding that a design that uses a
+ROB and therefore the entire Tomasulo algorithm itself is incapable of useful
+high-performance out-of-order execution.
+
+This article helps readers to understand that Q-Tables != Scoreboards,
+by describing a series of functionally-equivalent transformations that,
+when followed, *turn* the Tomasulo algorithm *into* a Scoreboard-based
+design. It also highlights that, following that transformation, multi-issue
+execution is near-trivial to add by comparison. Precise exception
+handling is also trivial to add (holding of write commits) and is
+described in the [[6600scoreboard]] page under "Shadowing"
-'''
On Saturday, May 16, 2020, Yehowshua <yimmanuel3@gatech.edu> wrote:
> This is a very intricate and complicated subject matter for sure.
start with this.
-1. Begin from Tomasulo. neither TS nor original 6600 have precise
- exceptions so we leave that out for now.
+1. Begin from Tomasulo.
2. Make sure to add an Operand Forwarding Bus. this is critical to
providing the functionality provided by the Tomasulo Common Data Bus.
4. Expand the number of RSes so that if you were to count the total
number of places operands are stored, they are the same.
-(another way to put this is, "flatten all 2D RSes into 1D")
+ (another way to put this is, "flatten all 2D RSes into 1D")
5. where pipelines were formerly connected exclusively to one RS,
*preserve* those connections even though the rows are now 1D flattened.
-(another way to put this is: we have a global 1D naming scheme to
-reference the *operand latches* rather than a 2D scheme involving RS
-number in 1 dimension and the row number in the 2nd)
+ (another way to put this is: we have a global 1D naming scheme to
+ reference the *operand latches* rather than a 2D scheme involving RS
+ number in 1 dimension and the row number in the 2nd)
6. give this 1D flattening an UNARY numbering scheme.
8. rename RSes to "Function Units" (actually in Thornton's book the phrase
"Computation Units" is used)
-thus, at this point in the transformation, the ROB row number *IS*
-the Function Unit Number, the need to actually store the ROB # in the
-Reservation Station Row is REMOVED, and consequently the Reservation
-Stations are NO LONGER A CAM.
+ thus, at this point in the transformation, the ROB row number *IS*
+ the Function Unit Number, the need to actually store the ROB # in the
+ Reservation Station Row is REMOVED, and consequently the Reservation
+ Stations are NO LONGER A CAM.
9. give all register file numbers (INT FP) an UNARY numbering.
-this means that in the ROB, updating of register numbers in a multi-issue
-scenario is a matter of raising one of any number of single bits.
-contrast this in the Tomasulo to having to multi-port the SRAM in the
-ROB, setting multiple bits *even for single-issue* (5-bits for 32-bit reg
-numbering).
+ this means that in the ROB, updating of register numbers in a multi-issue
+ scenario is a matter of raising one of any number of single bits.
+ contrast this in the Tomasulo to having to multi-port the SRAM in the
+ ROB, setting multiple bits *even for single-issue* (5-bits for 32-bit reg
+ numbering).
+
+10. add "Shadowing" capability to each Function Unit
+ and create a Shadow Matrix (appx 20 gates per Function Unit)
+
+ the "Shadow" capability hooks into the WRITE-COMMIT phase of every
+ Function Unit, permitting it to EXECUTE but prohibiting it from WRITING
+ the result of that execution until explicitly permitted to do so.
+
+11. Upgrade the CDB from a multi-fan-in, multi-fan-out, single resource
+ global choke-point to **separate** (multiple, if desired) read-fanout
+ broadcast and write-fan-in register data broadcast buses.
+
+# Post-transformation Analysis
with the ROB now having rows of bitvectors, it is now termed a "Matrix".
this we call the FU-FU Dependency Matrix.
+therefore, where previously, it was the ROB Row binary number that preserved
+instruction order (as an inherent DAG through sequential cyclically-incremented
+numbering), the 2-D bit-level FU-FU matrix preserves the same DAG by way of
+single-bit cells that express FU-to-FU dependencies, creating a hardware-form
+of a software "linked list".
+
the remainder of the "ROB" contains the register numbers in unary Matrix
form, and with each row being directly associated with a Function Unit,
we now have an association between FU and Regs which preserves the
parallelism at the pipelines would be kept fully occupied without an
overwhelming increase in gates or power consumption that would normally
be expected, and scalar performance would be similarly high as well.
-'''
+
+# Terminology notes
+
+These terms help understand that conceptually there is no difference
+in the capabilities of Tomasulo and Scoreboards.
+
+| Tomasulo name | Scoreboard name |
+| ----- | ---- |
+| Precise Exceptions | Precise-capable ("Shadowed") Scoreboard |
+| ROB index cycling order | FU-FU DAG that preserves instruction order |
+| Reorder Buffer | hybrid of Shadow, FU-FU and FU-Regs Matrices |
+| Reservation Station CAMs | RS Row = "Computation Unit latches" (no CAM) |
+| "register renaming" | "nameless" registers (Comp Unit latches) |
+| part-ROB, part-RS | Q-Tables |
+| blocking Common Data Bus | fan-out Read Reg, fan-in Write, OpFwd Bus(es)|
+| Centralised regfile(s) | Centralised regfile(s) |
projects / libreriscv.git / blobdiff