Project requirements and approach

[nkanderson]

@mdhardenburgh @reecewayt @d-engler Skip the overview section if you've already gotten a good grasp on this from the PDF Mark released. It's here for reference as we discuss. I think the main aspects I'm currently stuck on boil down to the following:

• What are the senders and receivers for the trace file events at op codes 0-6? I think these are all on a bus shared across all procs and caches, and the procs generate the requests, but then I don't know how to determine which cache takes action on the event.
• At least one of the provided function signatures is confusing to me. For the first one, int SnoopResult is passed in and then updated - should it be a pointer in the signature? Should it not be in the signature at all?
• This sentence from the project description:

snoop results that your LLC reports on the bus in response to snooping the simulated bus operations of other processors and their caches 🫠

Overview

Architecture

We're simulating an LLC with the following characteristics:

• 16 MB capacity
• 64-byte lines
• 16-way set associative
• Uses MESI protocol
• Employs a write-allocate policy
• Must maintain inclusivity
• Uses a pseudo-LRU scheme

The L1 cache does not need to be modeled, but its actions and content will impact our cache. It has the following characteristics:

• 64-byte lines
• 4-way set associative
• Employs a write-once policy: the first write to a line is write through; subsequent writes to the same line are write-back
• Based on the events in the trace file, it seems that we need to consider this as 2 separate caches, the data and instruction caches

There are 3 other processors in addition to the one that our cache is associated with. These caches exist in a shared memory configuration.

Program input and output

Our simulation program receives as input a series of events with op codes:

0 read request from L1 data cache
1 write request from L1 data cache
2 read request from L1 instruction cache
3 snooped read request
4 snooped write request
5 snooped read with intent to modify request
6 snooped invalidate command
8 clear the cache and reset all state
9 print contents and state of each valid cache line (doesn’t end simulation!)

We need to track and report the following:

• Number of cache reads
• Number of cache writes
• Number of cache hits
• Number of cache misses
• Cache hit ratio

In addition to the above, need to be able to output (in normal mode) the following:

• Each bus operation
• Snoop results, which include whether an operation resulted in a hit, no hit, or hit to modified line
• Communication to the L1 cache (request data for modified line in L1, send requested cache line to L1, invalidate a line in L1, evict a line from L1 (evict could be done by requesting data then invalidating it))

Other functionality

We need to implement the equivalent of the following functions:

/*
Used to simulate a bus operation and to capture the snoop results of last level
caches of other processors
*/
void BusOperation(int BusOp, unsigned int Address, int SnoopResult) {
  SnoopResult = GetSnoopResult(Address);
  if (NormalMode)
    printf(“BusOp: %d, Address: %h, Snoop Result: %d\n”,BusOp,Address, SnoopResult);
}

/* Simulate the reporting of snoop results by other caches */
int GetSnoopResult(unsigned int Address) {
  /* returns HIT, NOHIT, or HITM */
}

/* Report the result of our snooping bus operations performed by other caches */
void PutSnoopResult(unsigned int Address, int SnoopResult) {
  if (NormalMode)
    printf(“SnoopResult: Address %h, SnoopResult: %d\n”, Address, SnoopResult);
}

/* Used to simulate communication to our upper level cache */
void MessageToCache(int Message, unsigned int Address); {
  if (NormalMode)
    printf(“L2: %d %h\n”, Message, Address);
}

Questions and assumptions

General

1. Is the bus look through or look aside?
2. Shared memory configuration - assuming this means all the caches are associated only with their processor, but share the DRAM main memory.
3. When we report out the statistics, is that just for our cache, or for all caches?
4. The implication of the GetSnoopResult function seems to be that we know the contents and status of each entry in each cache. Is that correct?

Trace file events

1. Does "request from L1" (op codes 0-2) mean L1 is requesting from our L2 cache?
2. Do the snooped commands (op codes 3-6) mean that command type for that address is taking place for some other cache which could be the L1 or it could be an L1 or L2 for another processor? Or it's a memory reference issued by an unknown CPU, so all caches respond?

(Very) High level algorithm

I think we need to understand the events better before actually being able to flesh this out, but at a very high level, I think we'd do the following:

1. Iterate over each event from the trace file, using case or similar and match each op code to a series of actions
   • If it's an action like "request from L1", do the following:
     • Call BusOperation function, which calls GetSnoopResult
     • If in normal mode, display required content
     • TODO: Figure out what our cache needs to do, with regard to updating our entries or issuing other messages. Will probably need to call MessageToCache
     • Update the output data (number of cache reads, writes, etc.)
   • If it's an action like "snooped read request", do the following:
     • Call BusOperation function, which calls GetSnoopResult
     • If in normal mode, display required content
     • TODO: Figure out what our cache needs to do, with regard to updating our entries or issuing other messages
     • Update the output data (number of cache reads, writes, etc.)
   • If "clear the cache and reset all state":
     • Clear all valid bits in our cache (write zeros to those bits)
     • Reset our tallied number of reads, writes, etc. (I think? We should confirm)
   • If "print contents":
     • Iterate over each set and each block in our cache and if valid, display contents and state. Note: This content is output regardless of mode (i.e. it happens in silent and normal)
2. After iteration is complete, output the summary of stats on cache reads, writes, etc.