CPE 631 Lecture 22 Multiprocessors Aleksandar Milenkovi milenka ece uah edu Electrical and Computer Engineering University of Alabama in Huntsville CPE 631 AM Distributed Directory MPs M P0 P1 Pn C C C I O M I O M I O Interconnection Network C Cache M Memory IO Input Output 14 01 19 UAH CPE631 2 CPE 631 AM Directory Protocol Similar to Snoopy Protocol Three states Shared 1 processors have data memory up to date Uncached no processor has it not valid in any cache Exclusive 1 processor owner has data memory out of date In addition to cache state must track which processors have data when in the shared state usually bit vector 1 if processor has copy Keep it simple r Writes to non exclusive data write miss Processor blocks until access completes Assume messages received and acted upon in order sent 14 01 19 UAH CPE631 3 CPE 631 AM Directory Protocol No bus and don t want to broadcast interconnect no longer single arbitration point all messages have explicit responses Terms typically 3 processors involved Local node where a request originates Home node where the memory location of an address resides Remote node has a copy of a cache block whether exclusive or shared Example messages on next slide P processor number A address 14 01 19 UAH CPE631 4 CPE 631 AM Directory Protocol Messages Message type Read miss Source Destination Msg Content Local cache Home directory P A Processor P reads data at address A make P a read sharer and arrange to send data back Write miss Local cache Home directory P A Processor P writes data at address A make P the exclusive owner and arrange to send data back Invalidate Home directory Remote caches A Invalidate a shared copy at address A Fetch Home directory Remote cache A Fetch the block at address A and send it to its home directory Fetch Invalidate Home directory Remote cache A Fetch the block at address A and send it to its home directory invalidate the block in the cache Data value reply Home directory Local cache Data Return a data value from the home memory read miss response Data write back Remote cache Home directory A Data Write back a data value for address A invalidate response 14 01 19 UAH CPE631 5 CPE 631 AM State Transition Diagram for an Individual Cache Block in a Directory Based System States identical to snoopy case transactions very similar Transitions caused by read misses write misses invalidates data fetch requests Generates read miss write miss msg to home directory Write misses that were broadcast on the bus for snooping explicit invalidate data fetch requests Note on a write a cache block is bigger so need to read the full cache block 14 01 19 UAH CPE631 6 CPE 631 AM CPU Cache State Machine CPU Read hit State machine Invalidate for CPU requests Shared for each Invalid read only CPU Read memory block Send Read Miss Invalid state message CPU read miss if in Send Read Miss CPU Write memory CPU Write Send Send Write Miss msg to h d Fetch Invalidate send Data Write Back message to home directory Exclusive read writ CPU read hit CPU write hit 14 01 19 Write Miss message to home directory Fetch send Data Write Back message to home directory CPU read miss send Data Write Back message and read miss to home directory CPU write miss send Data Write Back message and Write Miss to home UAH CPE631 directory 7 CPE 631 AM State Transition Diagram for the Directory Same states structure as the transition diagram for an individual cache 2 actions update of directory state send msgs to statisfy requests Tracks all copies of memory block Also indicates an action that updates the sharing set Sharers as well as sending a message 14 01 19 UAH CPE631 8 CPE 631 AM Directory State Machine State machine for Directory requests for each memory block Uncached Uncached state if in memory Data Write Back Sharers Write back block Write Miss Sharers P send Fetch Invalidate send Data Value Reply msg to remote cache 14 01 19 Read miss Sharers P send Data Value Reply Write Miss Sharers P send Data Value Reply msg Read miss Sharers P send Data Value Reply Shared read only Write Miss send Invalidate to Sharers then Sharers P send Data Value Reply msg Read miss Sharers P Exclusive send Fetch read writ send Data Value Reply msg to remote cache Write back block UAH CPE631 9 CPE 631 AM Example Directory Protocol Message sent to directory causes two actions Update the directory More messages to satisfy request Block is in Uncached state the copy in memory is the current value only possible requests for that block are Read miss requesting processor sent data from memory requestor made only sharing node state of block made Shared Write miss requesting processor is sent the value becomes the Sharing node The block is made Exclusive to indicate that the only valid copy is cached Sharers indicates the identity of the owner Block is Shared the memory value is up to date Read miss requesting processor is sent back the data from memory requesting processor is added to the sharing set Write miss requesting processor is sent the value All processors in the set Sharers are sent invalidate messages Sharers is set to identity of requesting processor The state of the block is made Exclusive 14 01 19 UAH CPE631 10 CPE 631 AM Example Directory Protocol Block is Exclusive current value of the block is held in the cache of the processor identified by the set Sharers the owner three possible directory requests Read miss owner processor sent data fetch message causing state of block in owner s cache to transition to Shared and causes owner to send data to directory where it is written to memory sent back to requesting processor Identity of requesting processor is added to set Sharers which still contains the identity of the processor that was the owner since it still has a readable copy State is shared Data write back owner processor is replacing the block and hence must write it back making memory copy up to date the home directory essentially becomes the owner the block is now Uncached and the Sharer set is empty Write miss block has a new owner A message is sent to old owner causing the cache to send the value of the block to the directory from which it is sent to the requesting processor which becomes the new owner Sharers is set to identity of new owner and state of block is made Exclusive 14 01 19 UAH CPE631 11 CPE 631 AM Example Processor 1 Processor 2 Interconnect step P1 Write 10 to A1 Directory Memory P1 P2 Bus Directory Memory State Addr Value State Addr Value ActionProc Addr