requires registers to have extra hidden bits: register
x30 is now "x30:0+x30.1+x30.2+x30.3". have to discuss.
+See [[requirements_specification]]
+
# Conversation Notes
----
+http://lists.libre-riscv.org/pipermail/libre-riscv-dev/2019-January/000310.html
+
+> We will need fast f32 <-> i16 at least since that is used for 16-bit
+> z-buffers. Since we don't have indexed load/store and need to manually
+> construct pointer vectors we will need fast i32 -> i64. We will also need
+> fast i32 <-> f32.
+
+----
+
'm thinking about using tilelink (or something similar) internally as
having a cache-coherent protocol is required for implementing Vulkan
(unless you want to turn off the cache for the GPU memory, which I
Advantages of Speculation, Load and Store hazards:
-* A store updates memoryy only when it reached the head of the ROB
+* A store updates memory only when it reached the head of the ROB
* WAW and WAR type of hazards are eliminated with speculation
(actual updating of memory occurs in order)
* RAW hazards through memory are maintained by not allowing a load
the cache until the instruction retires. VVM uses this to avoid having
a vector strip mine the data cache.
+----
+
+> I meant the renaming done as part of the SV extension, not the
+> microarchitectural renaming.
+
+ah ok, yes. right. ok, so i don't know what to name that, and i'd
+been thinking of it in terms of "post-renaming", as in my mind, it's
+not really renaming, at all, it's... remapping. or, vector
+"elements".
+
+as in: architecturally we already have a name (vector "elements").
+physically we already have a name: register file.
+
+i was initially thinking that the issue stage would take care of it,
+by producing:
+
+* post-remapped elements which are basically post-remapped register indices
+* a byte-mask indicating which *bytes* of the register are to be
+ modified and which left alone
+* an element-width that is effectively an augmentation of (part of) the opcode
+
+the element width goes into the ALU as an augmentation of the opcode
+because the 64-bit "register" now contains e.g. 16-bit "elements"
+indexed 0-3, or 8-bit "elements" indexed 0-7, and we now want a
+SIMD-style (predicated) operation to take place.
+
+now that i think about it, i think we may need to have the three
+phases be part of a pipeline, in a single dependency matrix.
+
+----
+
+I had a state machine in one chip that could come up out of power on in a
+state it could not get out of. Since this experience, I have a rule with
+state machines, A state machine must be able to go from any state to idle
+when the reset line is asserted.
+
+You have to prove that the logic can never create a circular dependency,
+not a proof with test vectors, a logical proof like what we do with FP
+arithmetic these days.
+
+----
+
+
+> however... we don't mind that, as the vectorisation engine will
+> be, for the most part, generating sequentially-increasing index
+> dest *and* src registers, so we kinda get away with it.
+
+In this case:: you could simply design a 1R or 1W file (A.K.A. SRAM)
+and read 4 registers at a time or write 4 registers at a time. Timing
+looks like:
+
+<pre>
+ |RdS1|RdS2|RdS3|WtRd|RdS1|RdS2|RdS3|WtRd|RdS1|RdS2|RdS3|WtRd|
+ |F123|F123|F123|F123|
+ |Esk1|EsK2|EsK3|EsK4|
+ |EfK1|EfK2|EfK3|EfK4|
+</pre>
+
+4 cycle FU shown. Read as much as you need in 4 cycles for one operand,
+Read as much as you need in 4 cycles for another operand, read as much
+as you need in 4 cycles for the last operand, then write as much as you
+can for the result. This simply requires flip-flops to capture the width
+and then deliver operands in parallel (serial to parallel converter) and
+similarly for writing.
+
+----
+
+* <https://groups.google.com/d/msg/comp.arch/gedwgWzCK4A/32aNXIzeDQAJ>
+
+discussion of how to do dest-latches rather than src-latches.
+
+also includes need for forwarding to achieve it (synonymous with
+Tomasulo CDB).
+
+also, assigning a result number at issue time allows multiple results
+to be stored-and-forwarded, meaning that multiplying up the FUs is
+not needed.
+
+also, discussion of how to have multiple instructions issued even with
+the same dest reg: drop the reg-store and effectively rename them
+to "R.FU#". exceptions under discussion.
+
+----
+
+Speculation
+
+<https://groups.google.com/forum/#!topic/comp.arch/mzXXTU2GUSo>
+
+There is a minimal partial order that is immune to Spetré amd friends,
+You have the dependence matrix that imposes a minimal partial order on
+executing instructions (at least in the architecture you have been
+discussing herein) You just have to prove that your matrix provides
+that minimal partial order for instructions.
+
+Then you have to prove that no cache/tlb state can be updated prior to the
+causing instruction being made retirable (not retired retirable).
+
+As to cache updates, all "reasonable" interfaces that service cache misses
+will have line buffers to deal with the inbound and outbound memory traffic.
+These buffers will provide the appropriate data to the execution stream,
+but not update the cache until the causing instruction becomes transitively
+retirable. This will put "a little" extra pressure on these buffers.
+
+As to the TLB it is easy enough on a TLB miss to fetch the mapping tables
+transitively and arrive at a PTE. This PTE cannot be installed until the
+causing instruction becomes retirable. The miss buffers are probably the
+right place, and if a second TLB miss occurs, you might just as well walk
+the tables again and if it hits the line in the buffer use the data from
+there. When we looked at this a long time ago, there was little benefit
+for being able to walk more than one TLB miss at a time.
+
+----
+
+Register Prefixes <a name="prefixes" />
+
+<pre>
+| 3 | 2 | 1 | 0 |
+| ---------------- | ---------------- | ---------------- | ---------------- |
+| | xxxxxxxxxxxxxxaa | xxxxxxxxxxxxxxaa | XXXXXXXXXX011111 |
+| | xxxxxxxxxxxxxxxx | xxxxxxxxxxxbbb11 | XXXXXXXXXX011111 |
+| | xxxxxxxxxxxxxxaa | XXXXXXXXXX011111 | XXXXXXXXXX011111 |
+| xxxxxxxxxxxxxxaa | xxxxxxxxxxxxxxaa | XXXXXXXXXXXXXXXX | XXXXXXXXX0111111 |
+| xxxxxxxxxxxxxxxx | xxxxxxxxxxxbbb11 | XXXXXXXXXXXXXXXX | XXXXXXXXX0111111 |
+</pre>
+
+<pre>
+2x16-bit / 32-bit:
+
+| 9 8 | 7 6 5 | 4 3 | 2 1 | 0 |
+| ----- | ----- | ------- | ------- | - |
+| elwid | VL | rs[6:5] | rd[6:5] | 0 |
+
+| 9 8 7 6 5 | 4 3 | 2 | 1 | 0 |
+| --------- | -------- | --- | --- | - |
+| predicate | predtarg | end | inv | 1 |
+
+
+| | xxxxxxxxxxxxxxxx | xxxxxxxxxxxbbb11 | XXXXXXXXXX011111 |
+| | xxxxxxxxxxxxxxaa | XXXXXXXXXX011111 | XXXXXXXXXX011111 |
+| xxxxxxxxxxxxxxaa | xxxxxxxxxxxxxxaa | XXXXXXXXXXXXXXXX | XXXXXXXXX0111111 |
+| xxxxxxxxxxxxxxxx | xxxxxxxxxxxbbb11 | XXXXXXXXXXXXXXXX | XXXXXXXXX0111111 |
+</pre>
+
+# MVX and other reg-shuffling
+
+<pre>
+> Crucial strategic op missing is MVX:
+> regs[rd]= regs[regs[rs1]]
+>
+we could modify the definition slightly:
+for i in 0..VL {
+ let offset = regs[rs1 + i];
+ // we could also limit on out-of-range
+ assert!(offset < VL); // trap on fail
+ regs[rd + i] = regs[rs2 + offset];
+}
+
+The dependency matrix would have the instruction depend on everything from
+rs2 to rs2 + VL and we let the execution unit figure it out. for
+simplicity, we could extend the dependencies to a power of 2 or something.
+
+We should add some constrained swizzle instructions for the more
+pipeline-friendly cases. One that will be important is:
+for i in (0..VL) {
+ let i = i * 4;
+ let s1: [0; 4];
+ for j in 0..4 {
+ s1[j] = regs[rs1 + i + j];
+ }
+ for j in 0..4 {
+ regs[rd + i + j] = s1[(imm >> j * 2) & 0x3];
+ }
+}
+Another is matrix transpose for (2-4)x(2-4) matrices which we can implement
+as similar to a strided ld/st except for registers.
+</pre>
+
+# TLBs / Virtual Memory <a name="tlb" />
+
+----
+
+We were specifically looking for ways to not need large CAMs since they are
+power-hungry when designing the instruction scheduling logic, so it may be
+a good idea to have a smaller L1 TLB and a larger, slower, more
+power-efficient, L2 TLB. I would have the L1 be 4-32 entries and the L2 can
+be 32-128 as long as the L2 cam isn't being activated every clock cycle. We
+can also share the L2 between the instruction and data caches.
+
+# Register File having same-cycle "forwarding"
+
+discussion about CDC 6600 Register File: it was capable of forwarding
+operands being written out to "reads", *in the same cycle*. this
+effectively turns the Reg File *into* a "Forwarding Bus".
+
+we aim to only have (4 banks of) 2R1W ported register files,
+with *additional* Forwarding Multiplexers (which look exactly
+like multi-port regfile gate logic).
+
+suggestion by Mitch is to have a "demon" on the front of the regfile,
+<https://groups.google.com/d/msg/comp.arch/gedwgWzCK4A/qY2SYjd2DgAJ>,
+which:
+
+ basically, you are going to end up with a "demon" at the RF and when
+ all read reservations have been satisfied the demon determines if the
+ result needs to be written to the RF or discarded. The demon sees
+ the instruction issue process, the branch resolutions, and the FU
+ exceptions, and keeps track of whether the result needs to be written.
+ It then forwards the result from the FU and clears the slot, then writes
+ the result to the RF if needed.
+
# Design Layout
ok,so continuing some thoughts-in-order notes:
-* scoreboards are not just scoreboards, they are dependency matrices,
- and there are several of them:
- - one for LOAD/STORE-to-LOAD/STORE:
- + most recent LOADs prevent later STOREs
- + most recent STOREs prevent later LOADs.
- - one for Function-Unit to Function-Unit.
- + it exxpresses both RAW and WAW hazards through "Go_Write"
- and "Go_Read" signals, which are stopped from proceeding by
- dependent 1-bit CAM latches
- + exceptions may ALSO be made "precise" by holding a "Write prevention"
- signal. only when the Function Unit knows that an exception is
- not going to occur (memory has been fetched, for example), does
- it release the signal
- + speculative branch execution likewise may hold a "Write prevention",
- however it also needs a "Go die" signal, to clear out the
- incorrectly-taken branch.
- + LOADs/STOREs *also* must be considered as "Functional Units" and thus
- must also have corresponding entries (plural) in the FU-to-FU Matrix
- + it is permitted for ALUs to *BEGIN* execution (read operands are
- valid) without being permitted to *COMMIT*. thus, each FU must
- store (buffer) results, until such time as a "commit" signal is
- received
- + we may need to express an inter-dependence on the instruction order
- (raising the WAW hazard line to do so) as a way to preserve execution
- order. only the oldest instructions will have this flag dropped,
- permitting execution that has *begun* to also reach "commit" phase.
- - one for Function-Unit to Registers.
- + it expresses the read and write requirements: the source
- and destination registers on which the operation depends. source
- registers are marked "need read", dest registers marked
- "need write".
- + by having *more than one* Functional Unit matrix row per ALU
- it becomes possible to effectively achieve "Reservation Stations"
- orthogonality with the Tomasulo Algorithm. the FU row must, like
- RS's, take and store a copy of the src register values.
-* we may potentially have 2-issue (or 4-issue) and a simpler issue and
- detection by "striping" the register file according to modulo 2 (or 4)
- on the destination register number
- - the Function Unit rows are multiplied up by 2 (or 4) however they are
- actually connected to the same ALUs (pipelined and with both src and
- dest register buffers/latches).
- - the Register Read and Write signals are then "striped" such that read/write
- requests for every 2nd (or 4th) register are "grouped" and will have to
- fight for access to a multiplexer in order to access registers that do not
- have the same modulo 2 (or 4) match.
- - we MAY potentially be able to drop the destination (write) multiplexer(s)
- by only permitting FU rows with the same modulo to write to that destination
- bank. FUs with indices 0,4,8,12 may only write to registers similarly
- numbered.
- - there will therefore be FOUR separate register-data buses, with (at least)
- the Read buses multiplexed so that all FU banks may read all src registers
- (even if there is contention for the multiplexers)
-* an oddity / artefact of the FU-to-Registers Dependency Matrix is that the
- write/read enable signals already exist as single-bits. "normal" processors
- store the src/dest registers as an index (5 bits == 0-31), where in this
- design, that has been expanded out to 32 individual Read/Write wires,
- already.
- - the register file verilog implementation therefore must take in an
- array of 128-bit write-enable and 128-bit read-enable signals.
- - however the data buses will be multiplexed modulo 2 (or 4) according
- to the lower bits of the register number, in order to cross "lanes".
-* with so many Function Units in RISC-V (dozens of instructions, times 2
- to provide Reservation Stations, times 2 OR 4 for dual (or quad) issue),
- we almost certainly are going to have to deploy a "grouping" scheme:
- - rather than dedicate 2x4 FUs to ADD, 2x4 FUs to SUB, 2x4 FUs
- to MUL etc., instead we group the FUs by how many src and dest
- registers are required, and *pass the opcode down to them*
- - only FUs with the exact same number (and type) of register profile
- will receive like-minded opcodes.
- - when src and dest are free for a particular op (and an ALU pipeline is
- not stalled) the FU is at liberty to push the operands into the
- appropriate free ALU.
- - FUs therefore only really express the register, memory, and execution
- dependencies: they don't actually do the execution.
+## Scoreboards
+
+scoreboards are not just scoreboards, they are dependency matrices,
+and there are several of them:
+
+* one for LOAD/STORE-to-LOAD/STORE
+ - most recent LOADs prevent later STOREs
+ - most recent STOREs prevent later LOADs.
+ - a separate process analyses LOAD-STORE addresses for
+ conflicts, based on sufficient bits to assess uniqueness
+ as opposed to precise and exact matches
+* one for Function-Unit to Function-Unit.
+ - it expresses both RAW and WAW hazards through "Go_Write"
+ and "Go_Read" signals, which are stopped from proceeding by
+ dependent 1-bit CAM latches
+ - exceptions may ALSO be made "precise" by holding a "Write prevention"
+ signal. only when the Function Unit knows that an exception is
+ not going to occur (memory has been fetched, for example), does
+ it release the signal
+ - speculative branch execution likewise may hold a "Write prevention",
+ however it also needs a "Go die" signal, to clear out the
+ incorrectly-taken branch.
+ - LOADs/STOREs *also* must be considered as "Functional Units" and thus
+ must also have corresponding entries (plural) in the FU-to-FU Matrix
+ - it is permitted for ALUs to *BEGIN* execution (read operands are
+ valid) without being permitted to *COMMIT*. thus, each FU must
+ store (buffer) results, until such time as a "commit" signal is
+ received
+ - we may need to express an inter-dependence on the instruction order
+ (raising the WAW hazard line to do so) as a way to preserve execution
+ order. only the oldest instructions will have this flag dropped,
+ permitting execution that has *begun* to also reach "commit" phase.
+* one for Function-Unit to Registers.
+ - it expresses the read and write requirements: the source
+ and destination registers on which the operation depends. source
+ registers are marked "need read", dest registers marked
+ "need write".
+ - by having *more than one* Functional Unit matrix row per ALU
+ it becomes possible to effectively achieve "Reservation Stations"
+ orthogonality with the Tomasulo Algorithm. the FU row must, like
+ RS's, take and store a copy of the src register values.
+
+## Register Renaming
+
+There are several potential well-known schemes for register-renaming:
+*none of them will be used here*. The scheme below is a new form of
+renaming that is a topologically and functionally **direct** equivalent
+of the Tomasulo Algorithm with a Reorder Buffer, that came from the
+"Register Alias Table" concept that is better suited to Scoreboards.
+It works by flattening out Reservation Stations to one per FU (requiring
+more FUs as a result). On top of this the function normally carried
+out by "tags" of the RAT table may be merged-morphed into the role
+carried out by the ROB Destination Register CAM which may be merged-morphed
+into a single vector (per register) of 1-bit mutually-exclusive "CAMs"
+that are added, very simply, to the FU-Register Dependency Matrix.
+
+In this way, exactly as in the Tomasulo Algorithm, there is absolutely no
+need whatsoever for a separate PRF-ARF scheme. The PRF *is* the ARF.
+
+Register-renaming will be done with a single extra mutually-exclusive bit
+in the FUxReg Dependency Matrix, which may be set on only one FU (per register).
+This bit indicates which of the FUs has the **most recent** destination
+register value pending. It is **directly** functionally equivalent to
+the Reorder Buffer Dest Reg# CAM value, except that now it is a
+string of 1-bit "CAMs".
+
+When an FU needs a src reg and finds that it needs to create a
+dependency waiting for a result to be created, it must use this
+bit to determine which FU it creates a dependency on.
+
+If there is a destination register that already has a bit set
+(anywhere in the column), it is **cleared** and **replaced**
+with a bit in the FU's row and the destination register's column.
+
+See https://groups.google.com/d/msg/comp.arch/w5fUBkrcw-s/c80jRn4PCQAJ
+
+MUL r1, r2, r3
+
+ FU name Reg name
+ 12345678
+ add-0 ........
+ add-1 ........
+ mul-0 X.......
+ mul-1 ........
+
+ADD r4, r1, r3
+
+ FU name Reg name
+ 12345678
+ add-0 ...X....
+ add-1 ........
+ mul-0 X.......
+ mul-1 ........
+
+ADD r1, r5, r6
+
+ FU name Reg name
+ 12345678
+ add-0 ...X....
+ add-1 X.......
+ mul-0 ........
+ mul-1 ........
+
+note how on the 3rd instruction, the (mul-0,R1) entry is **cleared**
+and **replaced** with an (add-1,R1) entry. future instructions now
+know that if their src operands require R1, they are to place a
+RaW dependency on **add-1**, not mul-0
+
+## Multi-issue
+
+we may potentially have 2-issue (or 4-issue) and a simpler issue and
+detection by "striping" the register file according to modulo 2 (or 4)
+on the destination register number
+
+* the Function Unit rows are multiplied up by 2 (or 4) however they are
+ actually connected to the same ALUs (pipelined and with both src and
+ dest register buffers/latches).
+* the Register Read and Write signals are then "striped" such that
+ read/write requests for every 2nd (or 4th) register are "grouped" and
+ will have to fight for access to a multiplexer in order to access
+ registers that do not have the same modulo 2 (or 4) match.
+* we MAY potentially be able to drop the destination (write) multiplexer(s)
+ by only permitting FU rows with the same modulo to write to that
+ destination bank. FUs with indices 0,4,8,12 may only write to registers
+ similarly numbered.
+* there will therefore be FOUR separate register-data buses, with (at least)
+ the Read buses multiplexed so that all FU banks may read all src registers
+ (even if there is contention for the multiplexers)
+
+## FU-to-Register address de-muxed already
+
+an oddity / artefact of the FU-to-Registers Dependency Matrix is that the
+write/read enable signals already exist as single-bits. "normal" processors
+store the src/dest registers as an index (5 bits == 0-31), where in this
+design, that has been expanded out to 32 individual Read/Write wires,
+already.
+
+* the register file verilog implementation therefore must take in an
+ array of 128-bit write-enable and 128-bit read-enable signals.
+* however the data buses will be multiplexed modulo 2 (or 4) according
+ to the lower bits of the register number, in order to cross "lanes".
+
+## FU "Grouping"
+
+with so many Function Units in RISC-V (dozens of instructions, times 2
+to provide Reservation Stations, times 2 OR 4 for dual (or quad) issue),
+we almost certainly are going to have to deploy a "grouping" scheme:
+
+* rather than dedicate 2x4 FUs to ADD, 2x4 FUs to SUB, 2x4 FUs
+ to MUL etc., instead we group the FUs by how many src and dest
+ registers are required, and *pass the opcode down to them*
+* only FUs with the exact same number (and type) of register profile
+ will receive like-minded opcodes.
+* when src and dest are free for a particular op (and an ALU pipeline is
+ not stalled) the FU is at liberty to push the operands into the
+ appropriate free ALU.
+* FUs therefore only really express the register, memory, and execution
+ dependencies: they don't actually do the execution.
+
+## Recommendations
+
+* Include a merged address-generator in the INT ALU
+* Have simple ALU units duplicated and allow more than one FU to
+ receive (and process) the src operands.
+
+## Register file workloads
+
+Note: Vectorisation also includes predication, which is one extra integer read
+
+Integer workloads:
+
+* 43% Integer
+* 21% Load
+* 12% store
+* 24% branch
+
+* 100% of the instruction stream can be integer instructions
+* 75% utilize two source operand registers.
+* 50% of the instruction stream can be Load instructions
+* 25% can be store instructions,
+* 25% can be branch instructions
+
+FP workloads:
+
+* 30% Integer
+* 25% Load
+* 10% Store
+* 13% Multiplication
+* 17% Addition
+* 5% branch
+
+----
+
+> in particular i found it fascinating that analysis of INT
+> instructions found a 50% LD, 25% ST and 25% branch, and that
+> 70% were 2-src ops. therefore you made sure that the number
+> of read and write ports matched these, to ensure no bottlenecks,
+> bearing in mind that ST requires reading an address *and*
+> a data register.
+
+I never had a problem in "reading the write slot" in any of my pipelines.
+That is, take a pipeline where LD (cache hit) has a latency of 3 cycles
+(AGEN, Cache, Align). Align would be in the cycle where the data was being
+forwarded, and the subsequent cycle, data could be written into the RF.
+
+|dec|AGN|$$$|ALN|LDW|
+
+For stores I would read the LDs write slot Align the store data and merge
+into the cache as::
+
+|dec|AGEN|tag|---|STR|ALN|$$$|
+
+You know 4 cycles in advance that a store is coming, 2 cycles after hit
+so there is easy logic to decide to read the write slot (or not), and it
+costs 2 address comparators to disambiguate this short shadow in the pipeline.
+
+This is a lower expense than building another read port into the RF, in
+both area and power, and uses the pipeline efficiently.
+# Explicit Vector Length (EVL) extension to LLVM <a name="llvm_evl" />
+* <https://reviews.llvm.org/D57504>
+* <http://lists.libre-riscv.org/pipermail/libre-riscv-dev/2019-January/000433.html>
+* <http://lists.llvm.org/pipermail/llvm-dev/2019-January/129822.html>
# References
projects / libreriscv.git / blobdiff