Load Store Unit Design

[h0lyalg0rithm]

The load/store unit in the RISC-V Performance Model is a simple, single, in-order, pipeline with a fixed number of stages:

• MMU Lookup
• Cache lookup
• Completion

The current design has a few drawbacks:

• The MMU can only handle 1 outstanding miss
• The cache can only handle 1 outstanding miss
• There is only support for 1 load/store pipeline
• Load and Store requests share the same queue.
• Arbitration for load/store pipe is only based on priority

The goal of the redesign is to implement a fully functional LSU, similar to the one present in the BOOM.

Load Pipeline

1	2	3	4	5	6	7	8	9	10
Dispatch	Issue	Address calculation	MMU lookup	Cache Lookup	Cache Response	WriteBack stage			Instr Retire
Append to IssueQ	- wakeup by scoreboard and issue		- VA to PA translation - If hit, proceed to next stage- if miss, cancel load; make load dependent on completion of MMU miss handling; handle MMU miss	- tag lookup- if hit, proceed to next stage- if miss, cancel load; make load dependent on cache fill; and handle cache miss- parallely look up SQ :	- wakeup dependent instruction if cache hit	register writeback			- when instr reaches head of reorder buffer
				st-to-ld fwding enabled: if SB hit, wakeup dependent instruction
				st-to-ld fwding disabled: if SQ hit, cancel the load and make it dependent on the cache write of conficting older store

Store Pipeline

1	2	3	4	5	6	7	8	9	10	11
Dispatch	Issue	Address calculation	MMU lookup	Cache lookup	Cache Response		Instr Retire / Commit		Write to cache
Append to IssueQ; allocate SQ	- wakeup by scoreboard		- VA to PA translation - If hit, proceed to next stage- if miss, cancel store; make store dependent on completion of MMU miss handling; handle MMU miss	- update address & data in SQ- if hit, proceed to next stage- if miss, initiate miss handling (update SQ when the miss handling is completed)	- wakeup dependent instruction if cache hit		- when instr reaches head of reorder buffer- SQ/SB entry ready to written to cache		- Write instruction to Cache- Can incur cacheline miss
	- wakeup by cache			Page Table Walk	Page Table Walk	Page Table Walk	Page Table Walk Complete; wakeup dependent store
	- wakeup by MMU				cache miss handling	cache miss handling	cache miss handling	cache miss handling	Cache Fill return
	- wakeup by dependent instruction			Tag is looked up
				if hit - do nothing
				if miss - initiate cache line fill and wait

Live document with the timing diagram is available here

The behaviour I would like to model is as follows:

• Older instructions prioritized over younger instruction.
• Load/Store Instructions which resolve to the same address are dependent and executed in order(older instructions first)
• Instruction is removed from the store queue once instruction is committed and stored in the cache.
• Load to Store forwarding is configurable using a parameter.
• Ensure flushing of instructions works as expected.

Features/behaviours we could add in the future:

• Support synchronization instructions(fence).
• Support prefetching
• Support speculative actions
• Customize queue picking behaviour( age,priority)
• Prevent dependent instruction stalls

[arupc]

A few questions / comments:

• Is the IssueQ shared by Ld and St ops?
• Please list all the reasons by which a Ld/St op can be issued, such as dependent instruction, MMU miss, cache miss, etc.
• Is SQ and SB the same thing? If yes, let's use one term (either SQ or SB) for it.
• Since St-to-Ld forwarding is done using a SB, it is required that all older stores must be executed (at least their address calculation, VA-to-PA translation and allocating or updating in SB done) before any younger load can look into SB to search for potential forwarding case. Does that mean, in the IssueQ, an older store will always be picked before a younger load? In other words, if a St op is not ready to be issued (such as because, it is dependent on another instruction to generate its address), it will also block any younger load, even if it ready?

Please share the corresponding pipeline table for Store Ops. Please specify at what pipeline stage the SQ/SB gets allocated and deallocated; what the minimum required fields of SQ/SB for our example uarch and at pipeline stage(s) each of those fields get updated.

Thank you for putting this together.

[h0lyalg0rithm]

Here are my comments on the questions

• Is the IssueQ shared by Ld and St ops?
  -- Instructions are stored in to the Issue Queue and the Load and Store Queue in parallel.The reason to have a separate issue queue is to prevent the decode from stalling if the load and store queue is full.
• Please list all the reasons by which a Ld/St op can be issued, such as dependent instruction, MMU miss, cache miss, etc.
  -- I will update the original discussion with the information.
• Is SQ and SB the same thing? If yes, let's use one term (either SQ or SB) for it.
  -- Yes now the Store buffer (SB) is not longer required inorder to have a design similar to BOOM.
• Since St-to-Ld forwarding is done using a SB, it is required that all older stores must be executed (at least their address calculation, VA-to-PA translation and allocating or updating in SB done) before any younger load can look into SB to search for potential forwarding case. Does that mean, in the IssueQ, an older store will always be picked before a younger load? In other words, if a St op is not ready to be issued (such as because, it is dependent on another instruction to generate its address), it will also block any younger load, even if it ready?
  -- Yes instructions would be picked based on their age(Older first),After the MMU Lookup(VA-PA),Dependency check is performed based on the youngest instruction amongst the instructions which have the same address and its older than the current instruction is marked as dependent instruction.When that instruction commits it wakes up current instruction in-order to perform a store-to-load forward.
  This handles the following:
• Store x, Store x, Load x
• Load x, Store x, Load x
• Store x, load x, Store x

[arupc]

Is the IssueQ shared by Ld and St ops?
-- Instructions are stored in to the Issue Queue and the Load and Store Queue in parallel.The reason to have a separate issue queue is to prevent the decode from stalling if the load and store queue is full.

Why do we need loadQ at all? Is it not enough to have just the IssueQ?

Please specify at what pipeline stage the SQ/SB gets allocated and deallocated; what the minimum required fields of SQ/SB for our example uarch and at pipeline stage(s) each of those fields get updated.

What to do when a St gets canceled because of MMU miss (thus does not its VA)? Does that mean all younger loads must also be canceled (if already executing) or wait for cancelled St to wake up?

[arupc]

Another example of a simple LSU unit is described here:

• https://www.nxp.com/docs/en/application-note/AN2665.pdf (look at Sec 2, description of the overall processor pipeline and 8.4 LSU rules)
• https://www.nxp.com/docs/en/reference-manual/E500CORERM.pdf (sec 11, L1 cache, especially the role and use of buffers/queues such as Load Miss Q, L1 store Q, DLFB, DWB and replay buffer)

This uarch is different and simpler than Boom.

[arupc]

The pipeline for BOOM is shown here: https://github.com/riscv-boom/riscv-boom/blob/master/docs/figures/evolution.png A block diagram of the processor is shown here https://github.com/riscv-boom/riscv-boom/raw/master/docs/figures/uarch.png

There are following stages for Ld/St op:

1. Decode
2. Issue
3. Register Read (?)
4. TLB
5. D$
6. D$
7. WB

This pipeline is similar (but not same) to what we have discussed so far and to current pipeline in Olympia

There are references to following structures (the sizes, shown in paranthesis, are irrelevant in our discussion, provided as just examples):

• memory issue queue (32)
• load queue (32)
• store buffer, also referred to as store queue ? (32)
• MSHRs (8)
• Line fill buffers (10)

We need to document functions performed in each of those 7 steps, including how each of the structures are allocated/updated/freed.

From my reading of BOOM doc https://carrv.github.io/2020/papers/CARRV2020_paper_15_Zhao.pdf, here is my attempt. @h0lyalg0rithm can you please look through latest BOOM code and confirm/correct/update the following, as needed. Pending items are provided below.

• Decode:

  • Allocate Ld/St instr to memory issue queue
  • Allocate LdQ (https://docs.boom-core.org/en/latest/sections/load-store-unit.html#load-instructions)
  • Allocate StQ (https://docs.boom-core.org/en/latest/sections/load-store-unit.html#store-instructions)

• Issue

  • Issue Ld instr, when ready
  • Issue St instr, when (address & data) ready

• Register Read

  • calculate Ld/St instr virtual address

• TLB

  • if hit
    • look up physical addr
    • update Ld/StQ with physical addr
  • if miss
    • what happens to Ld/St instr

• D$

  • if hit, go to next stage
  • if miss,
    • if a unique miss, allocate MSHR
    • what happens to Ld/St instr

• D$

  • for Ld instr, read data

• WB

  • for Ld instr, write back to register and forward to dependent instructions

Pending questions:

• at which stage memory issue queue is deallocated?
• at which stage LdQ is deallocated ?
• at which stage StQ is deallocated ?
• at which stage MSHR is allocated and deallocated?
• at which stage Line fill buffer is allocated and deallocated?
• at which stage St data is updated in St buffer?
• at which stage how is St data written to the cache?
• at which stage, load to store forwarding check is performed and how?

[h0lyalg0rithm]

@arupc Here is what I understood from the code
After the decode stage, there is the dispatch stage which is missing the list you provided.From what I understood in the dispatch stage the micro-ops are issued to the different units.
https://github.com/riscv-boom/riscv-boom/blob/96409013ee7a1e0aebfb535d5ad40a8e9b53e97b/src/main/scala/exu/core.scala#L711

• at which stage memory issue queue is deallocated?

Not sure when it gets dellocated but I assume it is once once its commited
UPDATE: Based on the discussion last week, it seems like its deallocated immediately from the issue queue

• at which stage LdQ is deallocated ?

LDQ is deallocated once the instruction is committed(the committed field is not present in the load store entry). Valid bit set to false
https://github.com/riscv-boom/riscv-boom/blob/1e8c2a3c5804abe41f9c9b40842ea20eed31f02c/src/main/scala/lsu/lsu.scala#L1457
The commit signal comes from the ROB https://github.com/riscv-boom/riscv-boom/blob/1e8c2a3c5804abe41f9c9b40842ea20eed31f02c/src/main/scala/exu/rob.scala#L118

• at which stage StQ is deallocated ?

STQ is deallocated once its committed and sent to memory
https://github.com/riscv-boom/riscv-boom/blob/1e8c2a3c5804abe41f9c9b40842ea20eed31f02c/src/main/scala/lsu/lsu.scala#L1494
https://github.com/riscv-boom/riscv-boom/blob/1e8c2a3c5804abe41f9c9b40842ea20eed31f02c/src/main/scala/lsu/lsu.scala#L1504

• at which stage, load to store forwarding check is performed and how?

During the cache lookup stage,
https://github.com/riscv-boom/riscv-boom/blob/1e8c2a3c5804abe41f9c9b40842ea20eed31f02c/src/main/scala/lsu/lsu.scala#L886
Here the different forwarding logic is checked
https://github.com/riscv-boom/riscv-boom/blob/1e8c2a3c5804abe41f9c9b40842ea20eed31f02c/src/main/scala/lsu/lsu.scala#L1009
If there is an older load waiting before a newer store completes, the store is killed.
If a younger load finishes before an old store, order failure occurs and instruction is killed.

[h0lyalg0rithm]

@arupc Here are the answers from one of the developers of BOOM @jerryz123

• at which stage memory issue queue is deallocated?
  The memory issue queue is deallocated at the issue stage, the same cycle the MIQ issues an addr-gen or stdata-gen operation
• at which stage LdQ is deallocated ?
  The LdQ is deallocated the cycle after a ROB commits the instruction
• at which stage StQ is deallocated ?
  The StQ is deallocated 2 cycles after a the STQ issues the committed store to the DCache, assuming a store hit
• at which stage MSHR is allocated and deallocated?
  The MSHR is allocated 2 cycles after a uOp is issued to the DCache, if the op missed in the cache
• at which stage Line fill buffer is allocated and deallocated?
  The LineFillBuffers are statically allocated per MSHR, so allocation is the same cycle as MSHR allocate
• at which stage St data is updated in St buffer?
  The StData is written to the store buffer the cycle the LSU receives the issued stdata uop (2 cycles after issue, IIRC)
• at which stage how is St data written to the cache?
  StData is written to the cache 3 cycles after issue of a store op by the LSU
• at which stage, load to store forwarding check is performed and how?
  LdSt forwarding check is performed the cycle after each load is issued (for loads), and the cycle after store address is generated (for stores), same cycle as the L1D$ SRAM access. Ops check the contents of the LDQ/STQ for matching addresses

[arupc]

Thanks for following up for the answers.

[arupc]

Functional requirement of a load instruction:

• generate the address
• read data from the generated address, such that it reflects updates to memory by all store instructions before this load in program order
• forward the data read to dependent instructions

Functional requirement of a store instruction:

• generate the address
• generate the data
• only if the store instruction is non-speculative, change the state of memory permanently, such that any load instruction after the store in program order is certain to see the changed state of memory.

Keeping in mind the above functional requirements and based on previous discussions, we can create a generic LSU unit, with following parameters:

• stall_pipe_on_miss: stall pipeline on miss events:
  • If true, stalls the pipeline when there is TLB miss or Cache miss, until the miss events are completed.
    • TBD: what other miss events?
  • If false, allows other, potentially younger, load / store instructions to proceed while waiting for misses to be completed. Requires the affected instructions to re-enter the pipeline when the miss events are completed. This is referred to as replay.
• allow_speculative_load_exec: allow loads to proceed speculatively before all older store addresses are known:
  • if true, loads will proceed speculatively and if later, it is discovered that a load has gathered stale data, that load and all younger instructions are aborted (as in BOOM)
  • if false, loads will only issue after all older stores are issued, making sure addresses of all older stores are known when a load generates its address, allowing it to check for conflicts. (as in e500)
• latency in cycles of MMU lookup: 1 or higher
• latency in cycles of Cache lookup: 1 or higher
• latency in cycles of Cache data read: 0 or higher (if 0, cache data read is assumed to be done in same cycle as Cache lookup)

Following structures are needed:

• IssueQ
• Replay buffer
• LoadQ (only if allow_speculative_load_exec is true)
• StoreQ
• MSHR
• LineFillBuffer
• VictimBuffer

[arupc]

Pipeline of the generic LSU unit will have the following stages:

• Dispatch

  • Allocate StoreQ for store instruction
  • Allocate LoadQ for load instruction (only if allow_speculative_load_exec is true)
  • Allocate IssueQ for any load/store instruction

• Issue:

  • if stall_pipe_on_miss is false, Issue load or store instruction, if ready, from replay buffer
    • any load or store instruction issued will be in replay buffer until removed
    • any load or store instruction in replay buffer, when dropped from the pipeline, becomes ready for issue again after N cycles after being dropped, where N can be a parameter
    • an instruction may have to do multiple replay attempts, even for a single miss event cache as TLB miss.
  • If no instruction ready in replay buffer, issue oldest ready load or store instruction from IssueQ
    • If allow_spec_load_exec is false, a load instruction is only ready after its dependencies are met and physical addresses of all older stores are known.
    • If allow_spec_load_exec is true, a load instruction is ready after its dependencies are met irrespective of status of older stores
    • A store instruction is ready when both data and address are ready
    • if stall_pipe_on_miss_events is false, allocate instruction to replay buffer

• Address generation:

  • deallocate issue queue (Updated based on the discussion with Knute)
  • generate virtual address
  • update store queue with store data

• MMU lookup:

  • if hit:
    • get physical address
    • update load queue / store queue with generated address
    • for loads, check store queue for a match address using physical address
      • if there is a match, record the matching store queue entry
    • for stores, if allow_spec_load_exec is true, check load queue for an address match for all younger loads. If there is an address match, abort the matching load and all following instructions.
  • if miss or MMU busy (for example, because of updated by table walker):
    • if stall_pipe_on_miss_events is
      • true, stall the pipe and wait for the miss to be completed
      • false, drop instruction from pipeline
    • if miss, initiate page table walk to update MMU while making it busy for all future accesses until MMU is updated.

  (to be continued)

[arupc]

• Cache lookup:

  • for loads:
    • if has hit on store queue, bypass cache lookup
    • if cache busy, drop instruction
      • cache can be busy for cache refills or writes by committed store
    • if hit: proceed to next stage
    • if miss:
      • if stall_pipe_on_miss_events is
        • true, stall the pipe and wait for the miss to be completed
        • false:
          • drop instruction from pipeline
          • if address match with existing MSHR entries, do nothing
          • if no address match with existing MSHR entries:
            • if MSHR full: do nothing (instruction to be replayed later)
            • else: allocate a new MSHR entry and line fill buffer entry
  • for stores:
    • drop instruction from pipeline

• Cache data read:

  • must have been a cache hit; read data from cache
  • deallocate replay buffer for load hits as well stores that were dropped from pipeline in last cycle from cache lookup stage

• Writeback:

  • for loads, forward data to dependent instructions; write data to register

Retire:

• When a store is determined to be non-speculative, mark the corresponding store queue entry as non-speculative
• When a load instruction retires, deallocate load queue
• Deallocate from issue queue (Updated based on the discussion with Knute)

Data Cache Pipeline:

Data cache pipeline consists of following stages

• Stage0 (same as MMU stage of LSU):

  • arbitrate among three sources of cache accesses and select one, according to a policy TBD: a) non-speculative stores in store queue b) cache refills from line fill buffer c) load instruction currently in MMU stage

• Stage1

  • for non-speculative store, look up cache to determine hit or miss
  • if hit, proceed to next stage
  • if miss
    • if stall_pipe_on_miss_events is
      • true: stall the pipe and wait for the miss to be completed
      • false:
        • if address match with existing MSHR entry, update line fill buffer, drop store instruction from pipeline
        • else if no address match with existing MSHR entry and MSHR full, drop store instruction from pipeline (will be replayed from store queue later)
        • else allocate MSHR and line fill buffer, update line fill buffer and drop instruction from pipeline
  • for cache refill:
    • proceed to next stage
  • for load instruction from MMU, perform the actions listed in Cache lookup stage listed above.

• Stage2

  • for non-speculative stores that hit in cache, update replacement info, update appropriate cache line
  • for cache refills, update replacement info, read dirty victim line, if any, initiate a write to downstream cache and update appropriate cache line
  • for load instruction from MMU, update replacement info and perform the actions listed in Cache data read stage listed above.
  • for non-speculative stores that have either hit in cache or have updated line fill buffer entry, deallocate store queue
  • for any new MSHR allocated last cycle (in Stage1 / Cache lookup stage), initiate a read from downstream cache.

• Stage3

  • deallocate MSHR and line fill buffer for completed cache refills

[arupc]

Data Cache Pipeline:

• Stage0 (same as MMU stage of LSU):

  • arbitrate among three sources of cache accesses and select one, according to a policy TBD: a) non-speculative stores in store queue b) cache refills from line fill buffer c) load instruction currently in MMU stage

• Stage1

  • for non-speculative store, look up cache to determine hit or miss
  • if hit, proceed to next stage
  • if miss
    • if stall_pipe_on_miss_events is
      • true: stall the pipe and wait for the miss to be completed
      • false:
        • if address match with existing MSHR entry, update line fill buffer, drop store instruction from pipeline
        • else if no address match with existing MSHR entry and MSHR full, drop store instruction from pipeline (will be replayed from store queue later)
        • else allocate MSHR and line fill buffer, update line fill buffer and drop instruction from pipeline
  • for cache refill:
    • proceed to next stage
  • for load instruction from MMU, perform the actions listed in Cache lookup stage listed above.

• Stage2

  • for non-speculative stores that hit in cache, update replacement info, update appropriate cache line
  • for cache refills, update replacement info, read dirty victim line, if any, initiate a write to downstream cache and update appropriate cache line
  • for load instruction from MMU, update replacement info and perform the actions listed in Cache data read stage listed above.
  • for non-speculative stores that have either hit in cache or have updated line fill buffer entry, deallocate store queue
  • for any new MSHR allocated last cycle (in Stage1 / Cache lookup stage), initiate a read from downstream cache.

• Stage3

  • deallocate MSHR and line fill buffer for completed cache refills

[arupc]

Address generation:
deallocate issue queue (Updated based on the discussion with Knute)

@h0lyalg0rithm Can you please describe the rationale for not deallocating the issue queue at the address generation stage?

[h0lyalg0rithm]

Link to the cache documentation Link