Rename design

[furuame]

Register Renaming

Olympia is going to adopt PowerPC E500's register renaming style (see differences in the last slide here) for the reason of simplicity. There is a set of physical registers held by rename unit and we classify them to two different sets:

• Architecture registers: A set of registers hold the architecture states updated by "retired" instructions.
• Rename registers: A set of registers hold values for temporal computation of "on-the-fly" instructions.

Rename Register Allocation

Rename unit holds the register map that tells which (architecture/rename) register holds the latest value for the renaming instruction to read. Rename unit then updates the register map after it allocates new rename register for the renaming instruction. Rename unit will be stalled when there is no available rename register, and waked up by ROB returning rename registers.

Life Time of Rename Register

ROB writes back the value of rename register to architecture register when ROB is retiring an instruction. However, ROB only frees the destination rename register of the retiring instruction when no younger instructions reference it, in case younger instructions read false values. In the model, Olympia will maintains a reference counter for every rename register to know when it is safe to be freed. The reference counter increments when the rename register is just allocated for writing instructions or referenced by reading instructions. As ROB retires reading instructions, the reference counter of source rename register decreases by one.

Rebuild in Pipeline Flush

No needs. Since architecture states are held by architecture registers, no register map update will be needed when an exception or branch mis-prediction happens.

[arupc]

Is freeing up the destination rename register being delayed beyond retirement of the instruction? Is that still needed, even though architectural registers (and rename table, too) are being updated on retirement?

[furuame]

I think so, because younger instructions can still reference the rename register before rename table is updated. For example:

Assuming instruction sequence that I2 and I3 depends on I1
I1: add x1, x2, x3
I2: add x4, x5, x1
I3: add x6, x7, x1

Cycle	What happens
T	I1 is at Rename. Destination x1 is renamed to, say, r33.
T+1	I2 is at Rename. Source x1 is renamed to r33.
T+5	I1 is retired. ROB writes r33's value back r1. r33 is not freed yet, because I2 will need to read it.
T+6	I3 is at Rename. Source x1 is renamed to r1.
T+8	I2 is at Execute, reading x1 value from r33.
T+9	I2 is retired. No instructions reference r33, ROB then frees up r33.

[arupc]

Can we parameterize register allocation to support both styles, i.e., PowerPC E500 style and MIPS style as described in those slides, with the MIPS style unimplemented for now?

[furuame]

Definitely a yes answer!

[arupc]

Thank you @aarongchan for driving this and @klingaard for continuing to advise. Sorry for not being able to review code earlier.

I was thinking if we can develop an API for rename in order to support both methods of rename and possibly fold Aaron's code into that API.

Thinking more about that API, this is what comes to my mind:

A class Rename with following public methods:

• renameInstruction (…)
  * renames dest by looking up freelist
  * renames sources by looking up rename table
  * input args: const STFInst & (or InstPtr ?)
  * returns: TBD (tuple of inst, renamed dest, renamed srcs)
  * may be this should renameInstGroup(...), based on recent comment from Knute
• retireInstruction()
  * write register values, if needed
  * free up physical reg
  * input args: TBD (ROB entry?)
  * returns: void (?)
  * this is only to manage rename part of the retirement
• handleException(…)
  * handle exception
  * input args: TBD
  * retuns: TBD

Then this API can be used to implement different flavors of rename. For example, for our current chosen flavor, handleException(...) would be passthrough.

[aarongchan]

Current Rename Structures:

• reference_counter_

  • counts the number of references for each PRF for each register file

• map_table_

  • holds the current mapping from ARF -> PRF value, so only 32 values
  • i.e if x1 -> PRF35 for RF_INTEGER then value read from map_table_[RF_INTEGER][1] would be 1
  • and if we assign PRF37 to x1, then the value read from map_table_[RF_INTEGER][1] would be 37

• Inst.hpp

  • RenameData
    • class in Inst that hold sources, destination, and original destination values
    • setDestination()
      • set new destination PRF
    • setOriginalDestination
      • set original destination PRF
    • setSource()
      • push source into vector
    • getSource()
      • returns vector of sources
    • getDestination()
      • returns new destination PRF
    • getoriginalDestination()
      • returns original destination PRF
    • dest_
      • uint32_t new PRF number
    • original_dest_
      • uint32_t old PRF number
    • src_
      • vector of the uint32_t source numbers

• rename_histogram_

  • histogram counter for number of renames each time scheduleRenaming_ is called

• scheduleRenaming_

  • this function is called to ensure we have enough freelist for all register files instructions in the uop_queue_

  • it uses the following data structure for keeping count

    • RegCountData
      • struct to hold cumulative count at each index in the uop_queue for each register file type
      • i.e we have 6 instructions: INT FLOAT INT FLOAT INT INT
      • the cumulative count would be:

idx	0	1	2	3	4	5
INT	1	1	2	2	3	4
FLOAT	0	1	1	2	2	2

• uop_queue_regcount_data_

  • a deque that holds a RegCountData object at each index to indicate how many freelist registers of each register file type are needed

  • The flow is to first get a cumulative count of each register file registers for each index of the uop_queue_ in uop_queue_regcount_data_, i.e at index 1 we need 1 INT register, index 2 we need 1 INT and 1 FLOAT register and so on

  • We start at the largest rename amount we can support and loop through until we have enough freelist registers to support the cumulative count at the index we're at in the uop_queue_regcount_

  • Once we find the rename count we can support, we pop all remaining entries in uop_queue_regcount_data_, update the cumulative counts for remaining entries, and schedule renameInstructions_ call

  • Diagram showing the flow:

• Register Renaming
  • we start with PRF0 -> PRF31 mapped to x0 -> x31
  • If we have 48 rename registers, we would start with PRF32 as the first free PRF, so we would only 16 PRFs in the freelist
  • we increment in the reference_counter_ the "valid" PRF for a certain mapping by 1 when we assign the PRF -> ARF for the destination
    • this then helps us know when to push a PRF to the freelist, when we retire the instruction, we decrement the reference_counter_ for the destination, and we decrement it on sources being retired, so once reference_counter_ for a PRF hits 0, we know we can retire it safety with no references and that PRF isn't the "valid" mapping
  • At this time, operand dependency isn't being checked, so we mark all registers as ready
  • Diagram below shows the flow of renaming:
    

[klingaard]

This is awesome! Very nice! Much appreciated too.