Cache Real Estate Management

The Lookup

When a cache miss occurs, a new line must be fetched from memory and placed in the cache. Refer to Figure 17-4 on page 404. Assume that a memory address was submitted to the cache for a lookup and, as shown in the illustration, the Line portion of the address selected set 3 in the directories (i.e., the set of four directory entries at offset 3 in each of the four directories). Assume that all four of the entries are valid, that the cache is a MESI cache (i.e., a WB cache), and that the four entries contain the following:

• Entry 3 in Directory 0 contains a Page address of 0349A03h and its 2-bit State field indicates that the line is in the E (Exclusive) state. This means that the cache contains line 3 from page 0349A03h in entry 3 of Way 0.

• Entry 3 in Directory 1 contains a Page address of 07FA3E2h and its 2-bit State field indicates that the line is in the M (Modified) state. This means that the cache contains line 3 from page 07FA3E2h in entry 3 of Way 1.

• Entry 3 in Directory 2 contains a Page address of 0FED345h and its 2-bit State field indicates that the line is in the E (Exclusive) state. This means that the cache contains line 3 from page 0FED345h in entry 3 of Way 2.

• Entry 3 in Directory 3 contains a Page address of 0683AB4h and its 2-bit State field indicates that the line is in the S (Shared) state. This means that the cache contains line 3 from page 0683AB4h in entry 3 of Way 3.

Now assume that the target page address is 09DF537h. The cache compares the target page address to the page address stored in all four directory entries and has a miscompare. Although the cache currently contains line 3 from pages 0349A03h, 07FA3E2h, 0FED345h and 0683AB4h, it does not contain line 3 from page 09DF537h. It's a miss.

The Cache Initiates the Fetch of the New Line

The cache immediately forwards the request for the new line upstream to the next level of the memory hierarchy (i.e., to the next higher processor cache if there is one, or to the FSB to fetch the line from memory).

And Immediately Decides Where to Store It

Rather than wait for the return of the new line to decide where to store it, the cache immediately consults the LRU bit field associated with set 3 to determine which of the four cache Ways to store the line in. The following are two examples.

Example 1: Castout of a Modified Line

The LRU bit field indicates that entry 3 in Directory 1 represents the least-recently used of the four lines. Line 3 from page 07FA3E2h must therefore be cast out of the cache to make room for the new line that will be returned shortly.

Since this line has been Modified since it was read from memory, it cannot just be deleted. Rather, it is unloaded from the cache and is placed into a writeback buffer. It must be sent upstream to the next level of the memory hierarchy (i.e., to the next higher processor cache if there is one, or to the FSB to be written back to memory).

Example 2: Castout of an E or S Line

The LRU bit field indicates that entry 3 in Directory 2 represents the least-recently used of the four lines. Line 3 from page 0FED345h must be cast out of the cache to make room for the new line that will be returned shortly. This line is in the E state, so it has not been Modified since it was read from memory. It can therefore just be deleted.