And corresponds one the entries the lru tree

Tree-based LRU Approximation

Information

A cache is referred to as being n-way set associative if, given a memory address requested by the processor,

there are n possible cache entries that could be used to store data for that address. The tree-based LRU approximation algorithm that you will write will return the LRU entry that would be returned after a stream of memory references. Each memory reference is to one of the entries represented by the leafs in the tree.

bitOffset(Child-0) = bitOffset(Parent)*2
bitOffset(Child-1) = bitOffset(Parent)*2 + 1 bitOffset(Parent) = floor(bitOffset(Child)/2)

You will need to handle converting the bit offset into a memory address, and isolating the necessary bits for your accesses.

Return Values: None

Execution: This function will be called only once, right at the beginning of execution, and should be used to set up your cache simulation. All the nodes of your binary tree should be initialized to zero, meaning that the beginning LRU entry should be entry 0.

$v0 = 0000 0000 0000 0000 0000 0000 0001 0011

Execution: read the number specified the references from the stream of bits. Each entry is formed by log2(n) bits, where n is the associativity of the cache, and corresponds to one of the entries in the LRU tree. Each reference will be used to update the LRU tree according to the LRU approximation algorithm specified above. After the last reference has been processed, return the approximation to the the LRU entry.

Running with an associativity that is not a power of 2 causes undefined behavior and will not be tested.

The references in the bit stream are allowed to cross over word boundaries. Thus, make sure that you handle this situation correctly.

On the other hand, registers $s0 - $s7 are considered "source" registers. As a programmer, you should always assume no other subroutine will disrupt the values of this set of registers. If a subroutine uses any of these, it is an obligation to save them first, and restore the original values before it returns control to the oringinal caller. These registers are referred to as callee-saved registers.

Only the registers that are actually used must be saved and restored. For efficiency, a caller should only save/restore $t registers that contain a variable whose value will be used after the call. In compiler parlance, a register that contains a value that will be used later in the program is called a live variable. Likewise, a subroutine should only save/restore $s registers that it modifies.

The MIPS architecture has two special registers, $fp and $sp, that can be used to manage stack frames. $fp is the frame pointer, and points to the beginning of the frame of the procedure that is currently executing. The value of $fp changes only on entry to and exit from a procedure - during the body of the procedure, its value is constant. $sp is the stack pointer: it should always point to the last location in use on the stack. The value of $sp may change during the execution of a procedure when values are pushed onto and popped off the stack.

The $fp register, known as the frame pointer is used when referencing values stored in the stack frame because the offset of a value saved in the frame is constant relative to $fp.

# Restore our values
lw $ra, -4($fp)

Here is some pseudo-code to help you think about how to write code to read a bitfield that spans over a word boundary.

Marking Guide

12% For not altering the cache in non-writing function calls

Here is the mark sheet used for grading