Phantom Hits & Transition States

I am using a Hermes-like architecture to predict off-chip page walk accesses. The architecture predicts whether a page walk will go off-chip in search of the next page table address. Two packets are sent: one regular (reg) and one special (ddrp) packet.

A page table entry holding a page address is 8 bytes, so a 64-byte cache block holds eight entries. A page is allocated by the page fault mechanism and its address is stored in another page that is part of the page table. When a requested page has just been allocated, the cache block holding its page table entry has one valid 8-byte entry while the remaining seven entries are invalid.

The next access to the same cache block is a cache hit because the tag matches, but it may request one of the seven entries that has not yet been allocated. The hardware reads the entry and brings it to the MMU during the page walk. The MMU checks the valid bit in the entry, determines that it is invalid, and sends a page fault signal to the operating system. The operating system then allocates a page and sends the missing 8-byte entry rather than transferring the whole 64-byte block to the cache.

In my simulator I do not carry the block-level information with a page table request. Instead, I use a central structure that looks up the page number, block ID, and entry index to satisfy cache read requests for translation blocks. Each 8-byte entry has its page-fault flag set to 1 by default. When the fault is read, I allocate the page, update the entry with the page address, and reset the flag to 0.

While modeling regular and ddrp requests, I found that the ddrp request, which moves ahead of the regular request, resets the page-fault flag to 0. Because the block in the cache shares the central structure, that change is immediately reflected there. The regular request should see page-fault=1, but instead sees the value reset by ddrp. This inconsistency increases the false-positive rate of the predictor and lowers its precision.

The problem became clear when I built an oracle predictor that knows whether an access will go off-chip. It looks through all caches, and if the data is absent, sends a ddrp request to the DRAM controller to prefetch the page-table block. The oracle correctly predicts an off-chip access, but the ddrp packet resets page-fault=0. The regular packet then sees both a cached block and a valid entry, reports a hit instead of a forced miss, and incorrectly trains the predictor as a false positive.

To solve this problem, I introduced a transition state (TS) for the page-fault (PF) flag.

Rules at DRAM

  1. PF=1 and ddrp packet: PF becomes TS.
  2. PF=1 and regular packet: PF becomes 0.
  3. PF=0 and ddrp or regular packet: no change.
  4. PF=TS and ddrp packet: no change.
  5. PF=TS and regular packet: PF becomes 0.