DOC PREVIEW
Berkeley COMPSCI 152 - Directory-based Cache Coherence Protocol

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Handout #6CS152 Computer Architecture and DesignDirectory-based Cache Coherence Protocol 4/23/2009Before introducing a directory-based cache coherence protocol, we make the followingassumptions about the interconnection network:· Message passing is reliable, and free from deadlock, livelock and starvation. In otherwords, the transfer latency of any protocol message is finite.· Message passing is FIFO. That is, protocol messages with the same source anddestination sites are always received in the same order as that in which they were issued.Cache states: For each cache line, there are 4 possible states:· C-invalid (= Nothing): The accessed data is not resident in the cache.· C-shared (= Sh): The accessed data is resident in the cache, and possibly also cached atother sites. The data in memory is valid.· C-modified (= Ex): The accessed data is exclusively resident in this cache, and has beenmodified. Memory does not have the most up-to-date data.· C-transient (= Pending): The accessed data is in a transient state (for example, the sitehas just issued a protocol request, but has not received the corresponding protocol reply).Home directory states: For each memory block, there are 4 possible states:· R(dir): The memory block is shared by the sites specified in dir (dir is a set of sites). Thedata in memory is valid in this state. If dir is empty (i.e., dir = ε), the memory block isnot cached by any site.· W(id): The memory block is exclusively cached at site id, and has been modified at thatsite. Memory does not have the most up-to-date data.· TR(dir): The memory block is in a transient state waiting for the acknowledgements to theinvalidation requests that the home site has issued.· TW(id): The memory block is in a transient state waiting for a block exclusively cached atsite id (i.e., in C-modified state) to make the memory block at the home site up-to-date.Protocol messages: There are 10 different protocol messages, which are summarized in thefollowing table (their meaning will become clear later). Category MessagesCache to Memory RequestsShReq, ExReqMemory to Cache RequestsWbReq, InvReq, FlushReqCache to Memory ResponsesWbRep(v), InvRep, FlushRep(v)Memory to Cache ResponsesShRep(v), ExRep(v)1Handout #6No.Current State Handling Message Next State Dequeue Message?Action1 C-nothing Load C-pending No ShReq(id,Home,a)2 C-nothingStoreC-pending No ExReq(id,Home,a)3 C-nothingWbReq(a)C-nothing Yes None4 C-nothingFlushReq(a)C-nothing Yes None5 C-nothing InvReq(a) C-nothing Yes None6 C-nothing ShRep (a) C-shared Yes updates cache with prefetch data7 C-nothing ExRep (a) C-exclusive Yes updates cache with data8 C-shared Load C-shared Yes Reads cache9 C-sharedWbReq(a)C-shared Yes None10 C-sharedFlushReq(a)C-nothing Yes InvRep(id, Home, a)11 C-sharedInvReq(a)C-nothing Yes InvRep(id, Home, a)12 C-shared ExRep(a) C-exclusive Yes None13 C-shared (Voluntary Invalidate) C-nothing N/A InvRep(id, Home, a)14 C-exclusive Load C-exclusive Yes reads cache15 C-exclusiveStoreC-exclusive Yes writes cache16 C-exclusiveWbReq(a)C-shared Yes WbRep(id, Home, data(a))17 C-exclusiveFlushReq(a)C-nothing Yes FlushRep(id, Home, data(a))18 C-exclusive (Voluntary Writeback) C-shared N/A WbRep(id, Home, data(a))19 C-exclusive (Voluntary Flush) C-nothing N/A FlushRep(id, Home, data(a))20 C-pending WbReq(a) C-pending Yes None21 C-pending FlushReq(a) C-pending Yes None22 C-pendingInvReq(a)C-pending Yes None23 C-pendingShRep(a)C-shared Yes updates cache with data24 C-pendingExRep(a)C-exclusive Yes update cache with dataTable H12-1: Cache State Transitions2Handout #6No. Current State Message Received Next State Dequeue Message?Action1 R(dir) & (dir = ε) ShReq(a) R({id}) Yes ShRep(Home, id, data(a))2 R(dir) & (dir = ε) ExReq(a) W(id) Yes ExRep(Home, id, data(a))3 R(dir) & (dir = ε) (Voluntary Prefetch) R({id}) N/A ShRep(Home, id, data(a))4 R(dir) & (id  dir)& (dir ≠ ε)ShReq(a) R(dir + {id}) Yes ShRep(Home, id, data(a))5 R(dir) & (id  dir)& (dir ≠ ε)ExReq(a) Tr(dir) No InvReq(Home, dir, a)6 R(dir) & (id  dir)& (dir ≠ ε)(Voluntary Prefetch) R(dir + {id}) N/A ShRep(Home, id, data(a))7 R(dir) & (dir = {id}) ShReq(a) R(dir) Yes None8 R(dir) & (dir = {id}) ExReq(a) W(id) Yes ExRep(Home, id, data(a))9 R(dir) & (dir = {id}) InvRep(a) R(ε) Yes None10 R(dir) & (id  dir)& (dir ≠ {id})ShReq(a) R(dir) Yes None11 R(dir) & (id  dir)& (dir ≠ {id})ExReq(a)Tr(dir-{id}) No InvReq(Home, dir - {id}, a)12 R(dir) & (id  dir)& (dir ≠ {id})InvRep(a) R(dir - {id}) Yes None13 W(id’) ShReq(a) Tw(id’) No WbReq(Home, id’, a)14 W(id’)ExReq(a)Tw(id’) No FlushReq(Home, id’, a)15 W(id) ExReq(a) W(id) Yes None16 W(id) WbRep(a) R({id}) Yes data -> memory17 W(id) FlushRep(a) R(ε) Yes data -> memory18 Tr(dir) & (id  dir) InvRep(a) Tr(dir - {id}) Yes None19 Tr(dir) & (id  dir) InvRep(a) Tr(dir) Yes None20 Tw(id) WbRep(a) R({id}) Yes data-> memory21 Tw(id) FlushRep(a) R(ε) Yes data-> memoryTable H12-2: Home Directory State Transitions, Messages sent from site id


View Full Document

Berkeley COMPSCI 152 - Directory-based Cache Coherence Protocol

Documents in this Course
Quiz 5

Quiz 5

9 pages

Memory

Memory

29 pages

Quiz 5

Quiz 5

15 pages

Memory

Memory

29 pages

Memory

Memory

35 pages

Memory

Memory

15 pages

Quiz

Quiz

6 pages

Midterm 1

Midterm 1

20 pages

Quiz

Quiz

12 pages

Memory

Memory

33 pages

Quiz

Quiz

6 pages

Homework

Homework

19 pages

Quiz

Quiz

5 pages

Memory

Memory

15 pages

Load more
Download Directory-based Cache Coherence Protocol
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Directory-based Cache Coherence Protocol and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Directory-based Cache Coherence Protocol 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?