Yoav Yerushalmi Massachusetts Institute of Technology Zulfikar Ramzan 6.823: Computer System Architecture Raj Iyer Problem Set 5 Solutions

Question 1: Virtual Memory

1.A TLB Protection/Status Bits Question (a): If a page is modified in memory and then later needs to be read, the read should see the modifications. Thus the page must be written back to disk (unless future reads will access the copy in memory). The M bit keeps track of which pages need to be written back. In a given TLB entry, the M bit may have changed from 0 to 1, reflecting that the page was modified and may need to be written back to disk. When the TLB entry is invalidated, it is about to be deleted from the TLB. Thus the M bit must be written to the page table to keep track of the page’s ”dirty” status.

Question (b): When inserting a new VPN into a full TLB, we’d like to replace the least recently used entry. The hope is that such an entry is least likely to be accessed in the future, and if so, our action would minimize miss rate. The U bit helps us determine which are the least recently used entries. Ben is correct. The U bit and replacement policy affect the system’s performance, not its correctness. If a heavily accessed page’s VPN is (mistakenly) removed from the TLB, the VPN will simply be reloaded on the next access, causing a delay, not an error.

1.B Multiprocessing & Context Switch Question (c): Suppose we switch from process A to process B. Each process is allocated a virtual address space which is independent of the virtual address space of other proceses. Thus we can have two cases:

1. A maps VPN X to PPN S and B maps VPN X to PPN T (same VPN mapping to different PPNs).

2. A maps VPN X to PPN S and B maps VPN Y to PPN S (different VPNs mapping to same PPN).

Now, given VPN X, the TLB checks to see if it contains X. If A accessed its VPN X, then X will be in the TLB, but it may not map to same PPN as B’s VPN X (case 1). This is one reason why the TLB must be flushed. Setting all the V bits of all the TLB entries to 0 is equivalent to removing every entry from the TLB, thus avoiding the problem in the previous paragraph. This is may not be sufficient, however, since A may have modified some pages that B needs to read (case 2). If B always loads the disk copies of the pages, then A’s modifications must be written back to disk so that B can load them. However, if B checks first to see if the desired page is already in memory, then it need not load from disk, in which case setting the V bits to 0 is sufficient for flushing the cache.

Question (d): When B begins to execute after the context switch, it must be unable to use any of A’s TLB entries because of the problem with case 1. To avoid explicitly flushing the TLB (by setting all V bits to 0), we could attach the process ID to each TLB entry. Thus every access to the TLB after the context switch would result in a miss, even if the VPNs were identical. Again, this is only sufficient if B searches for a page in memory before going to disk, as described in (c).

Question 2: Synchronization in SMPs

2.A Atomic Acquire For this problem, we were not told anything about the MSI cache coherence protocol, so we made the assumption that it works like most protocols, in which a read doesn’t generate messages (or broadcasts) to other sites, but that writes do (to invalidate other cache entries). Notably, ALL writes do, even if the written value is the same as the old one that was there. The code Louis writes is inefficient in this case:

1  ADDI Rm, R0, _mutex
2  ADDI Ri, R0, 1
3  Loop:   LWRV Rt, (Rm)
4  STCD (Rm), Ri, Rs
5  BEQZ Rs, Loop
6  BNEZ Rt, Loop

Specifically, if five threads are all trying to grab the lock, only one will get it, and the rest will be stuck in the loop (lines 3-6) until the lock is released. However, this involves letting one of those threads successfully write a 1 to the mutex address each pass (even though the mutex was already a 1, and therefore grabbed). This means that the value of the memory address will be flushed from all the other caches, only to be loaded back in almost immediately. This is not really necessary once the mutex has been grabbed.

2.B Improving Efficiency To fix this, we can check whether the value is 1 BEFORE trying to set it ourselves. If it is a 1, we know the mutex has been grabbed, and therefore know we will not succeed in grabbing it ourselves. We move line 6 up thus:

1  ADDI Rm, R0, _mutex
2  ADDI Ri, R0, 1
3  Loop:   LWRV Rt, (Rm)
4  BNEZ Rt, Loop
5  STCD (Rm), Ri, Rs
6  BEQZ Rs, Loop

Once the mutex is grabbed, NO thread will succeed in getting to the STCD (the expensive operation). They will all be in a smaller loop (lines 3-4). However, if it is still free, then at least one thread will get to the STCD line, and at that point, STCD will decide which of those gets the mutex. Another interesting optimization is possible if we assume that the LWRV instruction is somehow more expensive to the system as a whole than a basic LOAD operation (not just for the particular CPU calling the instruction, but to some shared resource among the system). If this is the case, we can lower the number of times we call LWRV by having an early loop that just uses LOAD (no reservation set) to test the value in the mutex. If we believe the value to be zero, we proceed with the reservation system, but if we believe it to be a 1, we wait in a small pre-loop for it to be a zero:

1  ADDI Rm, R0, _mutex
2  ADDI Ri, R0, 1
3  pre:    LOAD Rt, (Rm)
4  BNEZ Rt, pre
5  Loop:   LWRV Rt, (Rm)
6  BNEZ Rt, Loop
7  STCD (Rm), Ri, Rs
8  BEQZ Rs, Loop

This code is indeed SLOWER for every particular instance, but if it does not slow down the entire machine as a whole, then it could make the entire system faster.

Question 3: Directory-based cache coherence protocol

3.A Cache State Transitions The two new entries in Table 1 are:

12 C-modified replace  C-invalid write-back → home
14 C-modified exclusive-copy-request C-invalid exclusive-copy-reply → home

3.B Directory State Transitions The two new entries in Table 2 are:

4 H-shared[S] store-request  H-transient[|S|] ∀s ∈ S, invalidate-request → s
13 H-transient shared-copy-reply H-shared[{j, k}] load-reply → j

3.C Protocol Understanding Figure 1 is a protocol-timing diagram demonstrating a scenario where a site that is NOT a home site for a piece of data is in a transient state and yet receives an exclusivecopy-request. The basic idea is that a site has a write-locked copy of some data, which another site wants to write to. However, the original site flushes the data due to a cache replacement algorithm. Before the flushing info gets to the home site however, the second site makes a store-request to the home site, which generates the exclusivecopy-request. For this diagram, the cache lines all refer to lines for a particular address (A_{1}) and the vertical lines refer to the current state for that cache line. The diagonal lines are messages being passed around.

Figure 1: Protocol scenario which demonstrates excl-copy-req in C-transient

It looks like this situation not only results in the exclusive-copy-request arriving during a transient state. What’s worse is that this protocol results in site 3 NEVER receiving a reply to its request. More interestingly, home will get an exclusive-copy-reply when it is in an H-modified[site1] state, which in our table, is not documented (although it is pretty obvious that the entry in the table for this situation should look like:

7.5 H-modified[m] exclusive-copy-reply H-modified[j] store-reply → j

Of course, there are other more complex interactions that could occur here, but the above line solves the situation in this scenario.

3.D non-FIFO Network Finally, it is very likely that this protocol will outright fail in many situations if FIFO was not guaranteed. Each site is basically an FSM which goes from one state to another based on the kind of inputs it is expecting. If FIFO is no longer the case, then it is fair to assume a larger set of inputs, and more state to account for every possibility (although there will have to be a broadcast of ’reset’ which will deal with situations when the home no longer knows what is going on and wants to reset. It will then have to wait for a reply from all sites acknowledging the reset before it resumes). However, we do not have the above tables. So if FIFO fails, Figure 2 is one situation where our current system breaks. The idea here is that site1 requests a read copy of a piece of data, to which the home replies with a positive answer. This answer gets extremely delayed however. In the meanwhile, site3 requests to write to the address. The home sends an invalidation request to site 1, which is quickly replied to (site1 is still in transient state), and the home thinks it can now successfully tell site 3 that it may edit the data to its heart content. Finally the delayed message telling site1 that it can share-read the data arrives. So site3 is happily editing the data, and site1 is happily reading the data. Only site1 is reading an old and inaccurate copy of the data, and none of the sights know this. Another solution to the above problem is to simply define this behavior as correct. That is: a site editing a value doesn’t really mean that other sites get the latest value, only that they will have a value that was correct at some point. (This will in fact allow us to simplify the protocol considerably, at the cost of being not-very-useful to many programmers).

Figure 2: Protocol scenario which demonstrates problems for lack of FIFO 7