Problem Q5.1: Sequential Consistency 18 points8 pointsProblem Q5.2: Relaxed Memory Models 15 pointsProblem Q5.3: Directory Protocols 20 pointsProblem Q5.4: Where has all the speedup gone? 26 pointsComputer Architecture and Engineering CS152 Quiz #5April 29, 2010Professor Krste AsanovicName:____ ANSWER KEY ____ This is a closed book, closed notes exam.80 Minutes 10 PagesNotes:- Not all questions are of equal difficulty, so look over the entire exam and budget your time carefully.- Please carefully state any assumptions you make.- Please write your name on every page in the quiz.- You must not discuss a quiz's contents with students who have not yet taken the quiz. If you have inadvertently been exposed to the quiz prior to taking it, you must tell the instructor or TA.- You will receive no credit for selecting multiple-choice answers without giving explanations if the instructions ask you to explain your choice.Writing name on each sheet ________ 1 PointQuestion 1 ________ 18 PointsQuestion 2 ________ 15 Points Question 3 ________ 20 PointsQuestion 4 ________ 26 PointsTOTAL ________ 80 PointsNAME:_________________________Problem Q5.1: Sequential Consistency 18 pointsIn this problem, we consider the implementation of sequential consistency (SC) in acache-coherent multiprocessor that uses a snoopy bus. A processor can intervene in a bustransaction by asserting the retry signal, causing the processor that initiated the request toattempt it again later. The bus supports only one outstanding cache miss at a time for theentire system. Each processor is equipped with a non-blocking data cache that supports hit-under-miss:while the cache is processing a miss, accesses that hit in the cache can still proceed. Thecache does not support miss-under-miss, so it will block in the event of a second miss. Aprocessor sends loads and stores to its cache in program order.Problem Q5.1.A 10 pointsWithout further modifications, the hit-under-miss scheme can lead to violations ofsequential consistency. Carefully explain why. Additionally, provide a short pseudocodesequence for two processors that could result in a sequentially inconsistent execution.Indicate whether each data memory access in your example is a cache hit or miss.Hit-under-miss enables younger memory accesses that hit in the cache to be made visiblebefore an older memory access that misses in the cache. Another processor could seethese accesses out of program order, which violates SC.Assume that variables X and Y start out as 0. Because the write to Y may proceed beforethe write to X, the following sequence of accesses could result in r1 = 1, r2 = 0, which isclearly a violation of SC.Processor 0 Hit/Miss Processor 1 Hit/Miss___X=1_____________ ___M____ ___r1=Y____________ ___M_______Y=1_____________ ___H____ ___r2=X____________ ___H____NAME:_________________________Problem Q5.1.B 8 pointsFortunately, it is possible to make the hit-under-miss scheme appear to be sequentiallyconsistent by leveraging the snoopy bus. Describe how to implement SC whilemaintaining hit-under-miss.Reordering only violates SC if other processors can observe it. The only way for e.g. P1 to observe P0’s accesses is via a bus transaction. So, if P1 initiates a bus transaction while P0 is servicing a miss that has been hit-under, P0 can tell P1 to retry until the miss has been resolved. This way, the miss and all subsequent hits are made visible at the same time.NAME:_________________________Problem Q5.2: Relaxed Memory Models 15 pointsThe following code implements a seqlock, which is a reader-writer lock that supports a single writer and multiple readers. The writer never has to wait to update the data protected by the lock, but readers may have to wait if the writer is busy. We use a seqlock to protect a variable that holds the current time. The lock is necessary because the variable is 64 bits and thus cannot be read or written atomically on a 32-bit system.The seqlock is implemented using a sequence number, seqno, which is initially zero. Thewriter begins by incrementing seqno. It then writes the new time value, which is split into the 32-bit values time_lo and time_hi. Finally, it increments seqno again. Thus, if and only if seqno is odd, the writer is currently updating the counter.The reader begins by waiting until seqno is even. It then reads time_lo and time_hi. Finally, it reads seqno again. If seqno didn't change from the first read, then the read was successful; otherwise, the read is retried.This code is correct on a sequentially consistent system, but on a system with a fullyrelaxed memory model it may not be. Insert the minimum number of memory fences tomake the code correct on a system with a relaxed memory model. To insert a fence, writethe needed fence (MembarLL, MembarLS, MembarSL, MembarSS) in between the lines ofcode below.Writer ReaderLOAD Rseqno, (seqno)ADD Rseqno, Rseqno, 1STORE (seqno), RseqnoMembarSS STORE (time_lo), Rtime_loSTORE (time_hi), Rtime_hiMembarSSADD Rseqno, Rseqno, 1STORE (seqno), RseqnoLoop: LOAD Rseqno_before, (seqno)IF(Rseqno_before & 1)goto LoopMembarLL LOAD Rtime_lo, (time_lo)LOAD Rtime_hi, (time_hi)MembarLLLOAD Rseqno_after, (seqno)IF(Rseqno_before != Rseqno_after)goto LoopNAME:_________________________Problem Q5.3: Directory Protocols 20 pointsAlice P. Hacker is designing a large-scale cache-coherent multiprocessor. Recalling thatdirectories are more scalable than snoopy buses, Alice decides to implement a full-mapdirectory to maintain coherence. Problem Q5.3.A 6 pointsAlice’s first directory design maintains a bit vector for each cache-line-sized block ofmain memory. For a given memory block, each bit in the bit vector represents whether ornot one processor in the machine has that line cached. For a 256-processor system with64B cache lines and 8GB of main memory, how large would Alice’s directory be?Directory size = (# of cache lines)*(# of processors) bits = (8GB/64B)*(256) bits = 32 Gbits = 4GB________4GB_______ Problem Q5.3.B 6 pointsAlice realizes that her initial design might be impractical to implement. She insteadconsiders a directory organization that supports up to four sharers of a line at a time. If afifth processor requests a copy of the line, one of the original four sharers is invalidated.For each memory line, this approach requires
View Full Document
Unlocking...