2 Introduction

In this project, you will implement a timing simulator for an Out-of-Order FOCO CPU using the PREGS/RAT approach. This CPU is equipped with a Branch Predictor, Instruction Cache, Data Cache, and Store Buffer. In order to enable correct behavior with memory operations in parallel, the CPU uses a memory disambiguation algorithm. Read the following sections carefully for simulator details.

Note: This project MUST be done individually. Please follow all the rules from Sec- tion 1 and review Appendix A.

3 Simulator Specifications

3.1 Basic Out of Order Architecture

Your simulator will implement the stages of an out-of-order (FOCO) processor using PREGs and a RAT, and functional support for cache misses and branch mispredictions. Your simulator will take in a handful of parameters that are used to define the processor configuration. The provided code will call your per-stage simulator functions in reverse order to emulate pipelined behavior. Figure 1 is a diagram of the general architecture of the model you will simulate. All edges passing through a dotted line will write to their relevant buffers/latches on the clock edge.

3.2 Simulator Parameters

The following command line parameters can be passed to the simulator:

• -A: The number of ALU units in the Execute stage

• -M: The number of Multiply (MUL) units in the Execute stage

• -L: The number of Load/Store (LSU) units in the Execute stage

• -S: The number of reservation stations per function unit. (You will model a unified scheduling queue with S * (A + M + L) reservation stations)

• -D: This flag has no argument; if it is passed, cache misses and mispredictions are disabled by the driver

• -F: The “Fetch Width” is the number of instructions fetched/added to the dispatch queue per cycle

• -P: The number of Physical registers. There are P + 32 ROB entries

• -I: The input trace file

• -H: Print the usage information

Queue>

while sched_q not full and room in ROB

Set src pregs, and search for free dest

if need a free preg and found one

or no destination

Remove

Scheduling Queue

Store Buffer

Re-Order Buffer (ROB)

<Tail>

Retire

Figure 1: Overview of the Out of Order Architecture. An arrow that crosses a dotted line indicates that the value is latched at the end of a cycle. An arrow that does not cross a dotted line indicates that the associated action occurs within the clock cycle.

3.3 Trace Format

Each line in a trace represents the following:

              

That is, the instructions are effectively already decoded for you.  Each register number is in the range [0, 31], except when a register is −1, which indicates (for example) there is no destination register. The Branch Misprediction, I-Cache Miss, and D-Cache Miss flags are set to 1 when these events occur. The opcodes map to the following operations and Function Units:

Opcode	Operation	Function Unit
2	Add	ALU unit
3	Multiply	MUL unit
4	Load	LSU unit
5	Store	LSU unit
6	Branch	ALU unit

3.4 The Memory Hierarchy

You will implement a Store Buffer that holds a store between the time it is completed and it is retired.  In the Execute Stage, when progressing the Load-Store Units, you will first progress all loads through the load store units, then you will progress all stores.  Loads can take a variable number of cycles to execute, more details will be discussed later in this section.   Stores always complete in the first cycle and in this cycle, they will add their load/store address to the store buffer.

3.4.1 The Cache

The traces have been annotated with I-Cache misses and D-Cache misses based on a 64 KiB 16-way set-associative cache with 64 byte cache blocks  (C=16,  B=6,  S=4 with a TLB that never misses. This cache serves as a 1 + L-ported unified Instruction and Data Cache that imposes no structural hazards. Because of this you do not need to simulate a data cache.

The data cache has a 2 cycle hit time and a misses are repaired from an L2 cache that always hits.  As such the cache miss penalty is (L1 MISS PENALTY). While caches typically take 2 cycles with 1 cycle for array-lookup and 1 cycle for tag compare, in your simulation, you can just check inst t .dcache miss in cycle 2 in the Load/Store Unit.   In the event that there is a miss, the Load/Store Unit must stall until cycle (2 + L1 MISS PENALTY) at which point the instruction will complete. Note that due to the existence of a store buffer, you only check the cache for loads that

missinthestorebuffer.

This means that Stores always take 1 cycle and Loads can take 1, 2, or 12 cycles.

3.4.2 The Store Buffer

The Store buffer exists as a hit-time reduction technique for store instructions. The Store buffer is allowed to have an unbound number of entries, however you will see in this section that it has an upper bound of the number of entries in the ROB.

In the cycle when a store begins execution, the store address is added to the FIFO (First-In-First- Out) store buffer.

In State Update, we keep a count of the number of stores that are retired that cycle. In the following cycle, we remove that many entries from the FIFO store buffer.  This 1 cycle delay is introduced to maintain the availability of data in a structure until the end of the cycle.

3.5 Fetch and The Driver

The driver exposes the instruction cache (I-cache) to you via the function procsim driver read inst(). The driver will return 1 instruction per call to procsim driver read inst().

In the event of a mispredicted branch, the driver will return the branch instruction and then return NULL (a NOP) until you set retired mispredict out to true in stage state update().  When you do this, procsim do cycle will update the appropriate statistic. (This models the time it takes for the misprediction to be corrected.  The instructions from the wrongly predicted path are not provided by the trace, so we fetch NOPs instead)

In the event of an I-Cache miss, the driver will handle this for you in terms of emulating correct behavior.   The driver will return NULL instructions until it resolves the I-Cache miss,  at which point it will resume returning valid instructions.   This means that your code will only be noti- fied of I-Cache misses once they are resolved.  You will need to inspect instructions returned by

procsim driver read inst() to determine if they experienced an I-Cache misses. If the driver returns a NULL instruction, do not add it to the dispatch queue.

3.6 Dispatch

In dispatch we will attempt to fill the reservation stations in the scheduling queue with instructions from the head of the dispatch queue. Remember that instructions are dispatched in program order. Dispatch will set  a reservation station’s function unit specifier,  will set source pregs using the Register Alias Table, and if an instruction has a destination, it will search the Physical Register File for a free preg and will set the prev preg, set the destination preg, and update the RAT. If you are not able to find a free preg for a destination, dispatch must stall and the instruction cannot be fired.

Note that not every instruction will have all of  src1,  src2,  dest specified.   You will need to account for this in dispatch and schedule.

The dispatch stage will allocate room in the ROB for the instruction as it places it into a reservation station. If there is not sufficient room in the ROB, Dispatch will stall.

3.6.1 The Physical Register File

The physical register is combined with the Architectural register such that the first NUM REGS indices correspond to the Architectural Registers, and the next P registers correspond to physical registers that you can allocate to. When searching for a free preg, dispatch starts at index NUM REGS. Initially, all register file entries are free and ready.

You should use an O(1) access structure for the register file because you will need to access it in multiple places so it is better to access it via an array/vector instead of a list/linked-list.

3.6.2 Register Alias Table

The Register Alias Table (RAT) maps an architectural register to the most recent preg allocated to remove a false dependency.  The RAT is initialized to point to the architectural registers and has NUM REGS entries.

3.7 Schedule

The schedule stage searches the scheduling queue for instructions that are ready to fire (their source pregs are ready) and fires them. In order to ensure determinism and match the solution, if multiple instructions can be fired at the same time, they are fired in program order (but still within the same cycle if possible).  This means that if 2 instructions are both ready for a single function unit, the instruction that comes first in program order would fire first. Use inst t .dyn instruction count as  a mechanism to determine program order.   However,  memory operations cannot be naively reordered like this due to the existence of pointers and aliasing...

3.7.1 Memory Disambiguation and Consistency

Because the superscalar processor may have more than one load/store unit, we need to ensure that any out of order memory transactions do not cause program correctness issues.  You will need to implement the following memory disambiguation algorithm to ensure that we do not violate program correctness.

• A Load instruction can be fired before any other Load instruction that precedes it in program order completes.

• A Load instruction can never be fired before ALL Store instructions that precedes it in program order complete.

• A Store instruction can never be fired before ALL Load and Store instructions that precede it in program order complete.

• Only 1 Store can be fired per cycle.

If you have implemented the scheduling queue correctly, any instruction currently in the scheduling queue has not been completed. Example Pseudocode: FixedconditionforStores

fired_store  =  false

for  CurRS  in  Scheduling_Queue  where  pregs  ready:  //  Scheduling_Queue  sorted  in  program  order if  (  !CurRS .sources_ready  )  continue;  //  skip  if  not  ready

//  Attempting  to  fire  Reservation  Station:  CurRS

//  Other  Opcodes  not  shown

//  Loads:

canfire  =  true;

for  OtherRS  in  Scheduling_Queue  excluding  CurRS:

if  (  (OtherRS  is  STORE)  and  (OtherRS  preceeds  CurRS  in  program  order)  ):

//  Cannot  fire  Load

canfire  =  false

endif

endfor

if  canfire:

//  look  for  available  LSU  and  fire  if  found  one

endif

//  Stores:

canfire  =  true;

for  OtherRS  in  Scheduling_Queue  excluding  CurRS:                //  v1 .1 .0

if  (  (  (  (OtherRS  is  LOAD)  or  (OtherRS  is  STORE)  )    //  v1 .1 .0

and  (OtherRS  preceeds  CurRS  in  program  order)  )  //  v1 .1 .0

or  (fired_store)  ):                                                         //  v1 .1 .0

//  Cannot  fire  store  since  already  fired  store  or

//  preceding memory  operation  is  in  scheduling  queue

canfire  =  false

endif

endfor

if  canfire:

//  look  for  available  LSU

if  found  free  LSU:

//  set  up  lsu

fired_store  =  true

endif

endif

endfor

3.8 Execute

In the execute stage you will move every instruction through its associated function unit and onto a result bus when it completes.  Then you will use the result busses to mark destination pregs as ready and remove entries from the scheduling queue.

3.8.1 ALU

This is a single-stage unit.

3.8.2 MUL

This is a 3-stage unit that is pipelined, meaning that up to 3 instructions may be worked on at any given time in a single MUL unit.

3.8.3 LSU

The Load/Store unit is a single-stage unit that will simulate store buffer and data cache accesses.

First, all Loads progress through the pipeline. The following events may occur:

• Cycle 1: check the store buffer. If there is an entry with the same address as the load instruc- tion’s load/store address, the load instruction is completed, a result bus entry is allocated, and the unit is marked as free.

• Cycle 2: check if the instruction has a cache miss. If there is no cache miss, the load instruction is completed, a result bus entry is allocated, and the unit is marked as free.

• Cycle (2 + L1 MISS PENALTY): The load instruction is completed, a result bus entry is allo- cated, and the unit is marked as free.

If there is a store buffer hit, the Load takes 1 cycle, if there is a cache hit, the load takes 2 cycles, if there is a cache miss, the load takes (2 + L1 MISS PENALTY) cycles.

Then, Stores progress through the pipeline:

• Cycle  1:  Add the instruction’s load/store address into the FIFO store buffer.   The Store instruction is completed, a result bus entry is allocated, and the unit is marked as free.

3.8.4 Result Buses

As an instruction finishes executing in its function unit, it will pass its values to the result buses. These values will be used to mark destination pregs as ready. Completed instructions are removed from the scheduling queue.  These busses will also place the instruction in the ROB in program order. All of this happens within the same cycle!

There are A  +  M  +  L result busses, thus instructions never stall waiting for a free result bus.

3.9 State Update

State update performs 2 functions for us, progressing the store buffer and updating architectural state in program order. Every cycle you will perform the following two operations.

First, you will pop off as many entries from the store buffer as stores that were retired in the previous cycle.

Second, you will, in program order, retire as many instructions as possible. Retiring an instruction will commit their destination register values (if present) to the Architectural Registers, (since we aren’t modeling data, you don’t actually need to model this behavior). Retiring an instruction will also free its prev preg in the physical register file.  If the prev preg is actually an architectural register, do not mark it as free. You will need to count the number of stores retired so you can do step 1 the following cycle.

If you retire a mispredict, set retired mispredict out to true and stop retiring any more instruc- tions.  (Realistically, since the driver will return NULL until you retire the mispredict, there should be no more valid entries in the ROB anyways.

We assume misprediction retirement has side-effects, so instructions cannot begin to fill the pipeline until the following cycle.  This is why the procsim do cycle does not call the other stages in the event of a mispredict retire.  Note that you may have stores that retired in the same cycle as the mispredict so you still need to pop those in the following cycle.

3.10 Initial Conditions

All architectural registers in the register file are ready.

All physical registers in the register file are free but not ready.

All function units are empty/ready.

All queues and the ROB are empty.

4 Statistics

You will need to keep track of the following statistics:

•  cycles: The number of cycles that have passed since the processor was started. (The provided code increments this statistic for you)

•  instructions fetched: The number of instructions fetched by the fetch stage, regardless of whether or not they retire

•  instructions retired: The number of instructions that exit the ROB

• branch mispredictions:  The number of branch mispredictions the processor encounters. (The provided code increments this statistic for you)

•  icache misses:  The number of I-cache misses encountered by fetch.  You should increment this when you see fetch instruction that has the icache miss flag set to true

• reads: The number of load instructions encountered in the execution of the program

•  store buffer read hits: the number of reads that hit in the

• dcache reads: number of reads that go to the L1 cache (only incremented if there is no store buffer hit)

• dcache read misses: number of read misses in the L1 cache

• dcache read hits: number of read hits in the L1 cache

•  store buffer hit ratio: fraction of reads that hit in the store buffer

• dcache read miss ratio: fraction of reads to the L1 cache that miss

• dcache ratio: fraction of reads that go to the L1 cache

• dcache read aat: the AAT for read accesses to the L1 cache

• read aat:  the effective AAT for reads:   1  *  store buffer hit ratio  +  dcache ratio  * dcache read aat

• no dispatch pregs cycles: Cycles where dispatch was stalled due to not being able to find a free preg

• rob stall cycles:  Cycles in which dispatch stops putting instructions into the scheduling queue only because of the constraint on the maximum number of ROB entries

• no fire cycles: cycles where nothing in the scheduling queue could be fired

• dispq max size: The maximum number of instructions in the dispatch queue during execu- tion. You should update this at the end of procsim do cycle()

•  schedq max size: The maximum number of instructions in the scheduling queue during exe- cution. You should update this at the end of procsim do cycle()

• rob max usage:  The maximum number of instructions in the ROB during execution.  You should update this at the end of procsim do cycle()

• dispq avg size: The average number of instructions in the dispatch queue during execution. You should update this at the end of procsim do cycle()

•  schedq avg size: The average number of instructions in the scheduling queue during execu- tion. You should update this at the end of procsim do cycle()

• rob avg size: The average number of instructions in the ROB during execution. You should update this at the end of procsim do cycle()

•  ipc: The average number of instruction retired per cycle

•  instructions in trace:  The number of instructions in the trace  (this is handled by the driver)

The details of the statistics are also available in procsim .hpp.

5 Implementation Details

You have been provided with the following files:

• procsim .cpp - Your simulator implementation will go here

• procsim .hpp - You do not need to modify this file. Header file containing definitions shared between your simulator and the driver

• procsim driver .hpp - You do not need to modify this file. Provided code that reads a trace, maintains a pointer to the next instruction in the trace, and allows your simulator code to read it via procsim driver read inst(). The simulator invokes your procsim do cycle() function repeatedly until all trace instructions have been retired

• run .sh: A shell script that invokes your simulator. You only need to change this if you have made the highly discouraged choice to write your simulator without the provided framework.

• validate .sh:  A shell script which runs your simulator and compares its outputs with the reference outputs. If you want&nb