Project 3 - CacheRaces


Last updated: April 13, 2014

Each question is marked with the date it was added. If there is no date, the question was the in the original version of the FAQ. If applicable, the writeup will be updated to reflect information from new questions.

Why does my bot perform much worse than the example bot even if I just rename a public bot?
When you edit the TARGETS in Makefile, you should consider enabling the compiler optimization for your bot, by adding "FLAGS_[yourbot] = -O3" (Notice this is the letter O, not the number 0!!)
If I prepare a Balrog on my opponent's side and I activate it (write to that location in memory), what will happen?
You will be stalled for 1,000,000 cycles.
If I fire an Nazgul_Screech and within 100 cycles I fire another one, do the durations overlap or accumulate?
The durations will accumulate, so the duration will increase by 100 cycles.
I want to access my own stack, or my opponent's stack. How do I know where it is?
To start off, for each core there is a mips_core_data structure which contains an array R. This array stores the content of the registers for that core. Work from there.
How do we determine what addresses the opponent currently has in the cache?
Use the rdctag function to read a cache tag. Check titfortat.c for an example of the proper usage
What is the policy for coherence between the cache and memory?

The cache is write-allocate: If you want to write to an address, it must be in the cache first (and therefore you suffer a cache miss if it wasn't in there already).

The cache is write-through: Once a line is in the cache, any writes to it immediately appear in memory (and therefore immediately increase your score).

Finally, the cache automatically updates from memory: In particular, if you have the taunt array in cache, and a new bot enters equip_ring mode, the taunt array in cache updates immediately.

How should we time our prefetches? How does prefetching work, anyway?

It's possible to prefetch too early, such that the line you prefetch arrives in the cache while you're still working on a different line. In this case, you'll doubly penalize yourself, as you'll suffer a miss for the line you're currently accessing, and then miss on the line you meant to prefetch in the first place. Oops! Don't do that.

If you prefetch slightly late, you only lose the difference. If address 0x01000000 is not in the cache, but you prefetch it, wait 50 cycles, then try to write to/read from it, you'll still miss but only stall 50 cycles instead of the usual 100, since 50 of the cycles were alerady taken up by the prefetch. This is why prefetching is beneficial. If you run the simulator in "very verbose mode" via simulate -vvvv, you'll see messages like "upgrades existing prefetch", and this is the meaning of that message.

On the other hand, if address 0x01000400 is in the cache, you prefetch 0x01000200, then try to read/write 0x01000000, the prefetch is canceled, You miss 0x01000000, and stall the full 100 cycles, no matter how far along the prefetch was.

Can I call prefetch, but continue working on the line currently in the cache?
Of course. prefetch(ptr) does not automatically call invalidate(ptr); that's why they're separate function calls. The line currently in the cache is still valid until the prefetch finishes.
Since only one prefetch can be in progress for a line at a time, what happens if we call prefetch twice?

The earlier one sticks. The writeup states "prefetch requests are ignored if a fetch is already in progress for that line", and in this context "fetch" means either an earlier prefetch or a core waiting on the cache line to fill due to a cache miss.

What activates a Balrog, reading or writing? (April 6)

Balrogs are triggered when any core attempts to write to a memory location that currently holds the Balrog byte. Such an attempt causes the write to fail and the writing core to be stalled for 1,000,000 (FLY_YOU_FOOLS) cycles. Since the write fails, multiple cores can be trapped at the same memory location.

Balrogs are not triggered by reading memory.