Difference between revisions of "Cache Coherence Protocols"

Revision as of 11:40, 25 April 2011

Common Notations and Data Structures

Coherence Messages

These are described in the <protocol-name>-msg.sm file for each protocol.

AccessPermissions

These are associated with each cache block and determine what operations are permitted on that block. It is closely correlated with coherence protocol states.

Data Structures

• Message Buffers:TODO
• TBE Table: TODO
• Timer Table: This maintains a map of address-based timers. For each target address, a timeout value can be associated and added to the Timer table. This data structure is used, for example, by the L1 cache controller implementation of the MOESI_CMP_directory protocol to trigger separate timeouts for cache blocks. Internally, the Timer Table uses the event queue to schedule the timeouts. The TimerTable supports a polling-based interface, isReady() to check if a timeout has occurred. Timeouts on addresses can be set using the set() method and removed using the unset() method.

Related Files:

src/mem/ruby/system/TimerTable.hh: Declares the TimerTable class

src/mem/ruby/system/TimerTable.cc: Implementation of the methods of the TimerTable class, that deals with setting addresses & timeouts, scheduling events using the event queue.

Coherence controller FSM Diagrams

• The Finite State Machines show only the stable states
• Transitions are annotated using the notation "Event list" or "Event list : Action list" or "Event list : Action list : Event list". For example, Store : GETX indicates that on a Store event, a GETX message was sent whereas GETX : Mem Read indicates that on receiving a GETX message, a memory read request was sent. Only the main triggers and actions are listed.
• Optional actions (e.g. writebacks depending on whether or not the block is dirty) are enclosed within [ ]
• In the diagrams, the transition labels are associated with the arc that cuts across the transition label or the closest arc.

MI example

Protocol Overview

• This is a simple cache coherence protocol that is used to illustrate protocol specification using SLICC.
• This protocol assumes a 1-level cache hierarchy. The cache is private to each node. The caches are kept coherent by a directory controller. Since the hierarchy is only 1-level, there is no inclusion/exclusion requirement.
• This protocol does not differentiate between loads and stores.
• This protocol cannot implement the semantics of LL/SC instructions, because external GETS requests that hit a block within a LL/SC sequence steal exclusive permissions, thus causing the SC instruction to fail.

Related Files

• src/mem/protocols
  • MI_example-cache.sm: cache controller specification
  • MI_example-dir.sm: directory controller specification
  • MI_example-dma.sm: dma controller specification
  • MI_example-msg.sm: message type specification
  • MI_example.slicc: container file

Stable States and Invariants

The notation used in the controller FSM diagrams is described here.

Cache controller

• Requests, Responses, Triggers:
  • Load, Instruction fetch, Store from the core
  • Replacement from self
  • Data from the directory controller
  • Forwarded request (intervention) from the directory controller
  • Writeback acknowledgement from the directory controller
  • Invalidations from directory controller (on dma activity)

• Main Operation:
  • On a load/Instruction fetch/Store request from the core:
    • it checks whether the corresponding block is present in the M state. If so, it returns a hit
    • otherwise, if in I state, it initiates a GETX request from the directory controller

• • On a replacement trigger from self:
    • it evicts the block, issues a writeback request to the directory controller
    • it waits for acknowledgement from the directory controller (to prevent races)

• • On a forwarded request from the directory controller:
    • This means that the block was in M state at this node when the request was generated by some other node
    • It sends the block directly to the requesting node (cache-to-cache transfer)
    • It evicts the block from this node

• • Invalidations are similar to replacements

Directory controller

• Requests, Responses, Triggers:
  • GETX from the cores, Forwarded GETX to the cores
  • Data from memory, Data to the cores
  • Writeback requests from the cores, Writeback acknowledgements to the cores
  • DMA read, write requests from the DMA controllers

• Main Operation:
  • The directory maintains track of which core has a block in the M state. It designates this core as owner of the block.
  • On a GETX request from a core:
    • If the block is not present, a memory fetch request is initiated
    • If the block is already present, then it means the request is generated from some other core
      • In this case, a forwarded request is sent to the original owner
      • Ownership of the block is transferred to the requestor
  • On a writeback request from a core:
    • If the core is owner, the data is written to memory and acknowledgement is sent back to the core
    • If the core is not owner, a NACK is sent back
      • This can happen in a race condition
      • The core evicted the block while a forwarded request some other core was on the way and the directory has already changed ownership for the core
      • The evicting core holds the data till the forwarded request arrives
  • On DMA accesses (read/write)
    • Invalidation is sent to the owner node (if any). Otherwise data is fetched from memory.
    • This ensures that the most recent data is available.

Other features

• • MI protocols don't support LL/SC semantics. A load from a remote core will invalidate the cache block.
  • This protocol has no timeout mechanisms.

MOESI_hammer

This is an implementation of AMD's Hammer protocol, which is used in AMD's Hammer chip (also know as the Opteron or Athlon 64). The protocol implements both the original a HyperTransport protocol, as well as the more recent ProbeFilter protocol. The protocol also includes a full-bit directory mode.

Related Files

• src/mem/protocols
  • MOESI_hammer-cache.sm: cache controller specification
  • MOESI_hammer-dir.sm: directory controller specification
  • MOESI_hammer-dma.sm: dma controller specification
  • MOESI_hammer-msg.sm: message type specification
  • MOESI_hammer.slicc: container file

Cache Hierarchy

This protocol implements a 2-level private cache hierarchy. It assigns separate Instruction and Data L1 caches, and a unified L2 cache to each core. These caches are private to each core and are controlled with one shared cache controller. This protocol enforce exclusion between L1 and L2 caches.

Stable States and Invariants

Cache controller

The notation used in the controller FSM diagrams is described here.

MOESI_hammer supports cache flushing. To flush a cache line, the cache controller first issues a GETF request to the directory to block the line until the flushing is completed. It then issues a PUTF and writes back the cache line.

Directory controller

MOESI_hammer memory module, unlike a typical directory protocol, does not contain any directory state and instead broadcasts requests to all the processors in the system. In parallel, it fetches the data from the DRAM and forward the response to the requesters.

probe filter: TODO

• Stable States and Invariants

• Controller

The notation used in the controller FSM diagrams is described here.

MOESI_CMP_token

Protocol Overview

• This protocol also models a 2-level cache hierarchy.

• It maintains coherence permission by explicitly exchanging and counting tokens.

• A fix number of token are assigned to each cache block in the beginning, the number of token remains unchanged.

• To write a block, the processor must have all the token for that block. For reading at least one token is required.

• The protocol also has a persistent message support to avoid starvation.

Related Files

• src/mem/protocols
  • MOESI_CMP_token-L1cache.sm: L1 cache controller specification
  • MOESI_CMP_token-L2cache.sm: L2 cache controller specification
  • MOESI_CMP_token-dir.sm: directory controller specification
  • MOESI_CMP_token-dma.sm: dma controller specification
  • MOESI_CMP_token-msg.sm: message type specification
  • MOESI_CMP_token.slicc: container file

Controller Description

• L1 Cache

• L2 cache

• Directory controller

MOESI_CMP_directory

Editing in progress.

Protocol Overview

• TODO: cache hierarchy

• In contrast with the MESI protocol, the MOESI protocol introduces an additional Owned state.
• The MOESI protocol also includes many coalescing optimizations not available in the MESI protocol.

Related Files

• src/mem/protocols
  • MOESI_CMP_directory-L1cache.sm: L1 cache controller specification
  • MOESI_CMP_directory-L2cache.sm: L2 cache controller specification
  • MOESI_CMP_directory-dir.sm: directory controller specification
  • MOESI_CMP_directory-dma.sm: dma controller specification
  • MOESI_CMP_directory-msg.sm: message type specification
  • MOESI_CMP_directory.slicc: container file

L1 Cache Controller

• Stable States and Invariants

• FSM Abstraction

The notation used in the controller FSM diagrams is described here.

• • Optimizations

The notation used in the controller FSM diagrams is described here.

L2 Cache Controller

• Stable States and Invariants

• FSM Abstraction

The controller is described in 2 parts. The first picture shows transitions between all "intra-chip inclusion" categories and within categories 1, 3, 4. Transitions within category 2 (Not in L2, but in 1 or more L1s at this chip) are shown in the second picture.

The notation used in the controller FSM diagrams is described here. Transitions involving other chips are annotated in brown.

The second picture below expands the central hexagonal portion of the above picture to show transitions within category 2 (Not in L2, but in 1 or more L1s at this chip).

The notation used in the controller FSM diagrams is described here. Transitions involving other chips are annotated in brown.

Directory Controller

• Stable States and Invariants

• FSM Abstraction

The notation used in the controller FSM diagrams is described here.

Other features

• Timeouts:

Rathijit will do it

MESI_CMP_directory

Protocol Overview

• This protocol models two-level cache hierarchy. The L1 cache is private to a core, while the L2 cache is shared among the cores. L1 Cache is split into Instruction and Data cache.
• Inclusion is maintained between the L1 and L2 cache.
• At high level the protocol has four stable states, M, E, S and I. A block in M state means the blocks is writable (i.e. has exclusive permission) and has been dirtied (i.e. its the only valid copy on-chip). E state represent a cache block with exclusive permission (i.e. writable) but is not written yet. S state means the cache block is only readable and possible multiple copies of it exists in multiple private cache and as well as in the shared cache. I means that the cache block is invalid.
• The on-chip cache coherence is maintained through Directory Coherence scheme, where the directory information is co-located with the corresponding cache blocks in the shared L2 cache.
• The protocol has four types of controllers -- L1 cache controller, L2 cache controller, Directory controller and DMA controller. L1 cache controller is responsible for managing L1 Instruction and L1 Data Cache. Number of instantiation of L1 cache controller is equal to the number of cores in the simulated system. L2 cache controller is responsible for managing the shared L2 cache and for maintaining coherence of on-chip data through directory coherence scheme. The Directory controller act as interface to the Memory Controller/Off-chip main memory and also responsible for coherence across multiple chips/and external coherence request from DMA controller. DMA controller is responsible for satisfying coherent DMA requests.
• One of the primary optimization in this protocol is that if a L1 Cache request a data block even for read permission, the L2 cache controller if finds that no other core has the block, it returns the cache block with exclusive permission. This is an optimization done in anticipation that a cache blocks read would be written by the same core soon and thus save an extra request with this optimization. This is exactly why E state exits (i.e. when a cache block is writable but not yet written).
• The protocol supports silent eviction of clean cache blocks from the private L1 caches. This means that cache blocks which have not been written to and has readable permission only can drop the cache block from the private L1 cache without informing the L2 cache. This optimization helps reducing write-back traffic to the L2 cache controller.

Related Files

• src/mem/protocols
  • MESI_CMP_directory-L1cache.sm: L1 cache controller specification
  • MESI_CMP_directory-L2cache.sm: L2 cache controller specification
  • MESI_CMP_directory-dir.sm: directory controller specification
  • MESI_CMP_directory-dma.sm: dma controller specification
  • MESI_CMP_directory-msg.sm: coherence message type specifications. This defines different field of different type of messages that would be used by the given protocol
  • MESI_CMP_directory.slicc: container file

Controller Description

• L1 cache controller

• L2 cache controller

Recall that the on-chip directory is co-located with the corresponding cache blocks in the L2 Cache. Thus following states in the L2 cache block encodes the information about the status and permissions of the cache blocks in the L2 cache as well as the coherence status of the cache block that may be present in one or more private L1 caches. Beyond the coherence states there are also two more important fields per cache block that aids to make proper coherence actions. These fields are Sharers field, which can be thought of as a bit-vector indicating which of the private L1 caches potentially have the given cache block. The other important field is the Owner field, which is the identity of the private L1 cache in case the cache block is held with exclusive permission in a L1 cache.

Network_test

This is a dummy cache coherence protocol that is used to operate the ruby network tester. The details about running the network tester can be found here.

Related Files

• src/mem/protocols
  • Network_test-cache.sm: cache controller specification
  • Network_test-dir.sm: directory controller specification
  • Network_test-msg.sm: message type specification
  • Network_test.slicc: container file

Cache Hierarchy

This protocol assumes a 1-level cache hierarchy. The role of the cache is to simply send messages from the cpu to the appropriate directory (based on the address), in the appropriate virtual network (based on the message type). It does not track any state. Infact, no CacheMemory is created unlike other protocols. The directory receives the messages from the caches, but does not send any back. The goal of this protocol is to enable simulation/testing of just the interconnection network.

Stable States and Invariants

Cache controller

• Requests, Responses, Triggers:
  • Load, Instruction fetch, Store from the core.

The network tester (in src/cpu/testers/networktest/networktest.cc) generates packets of the type ReadReq, INST_FETCH, and WriteReq, which are converted into RubyRequestType:LD, RubyRequestType:IFETCH, and RubyRequestType:ST, respectively, by the RubyPort (in src/mem/ruby/system/RubyPort.hh/cc). These messages reach the cache controller via the Sequencer. The destination for these messages is determined by the traffic type, and embedded in the address. More details can be found here.

• Main Operation:
  • The goal of the cache is only to act as a source node in the underlying interconnection network. It does not track any states.
  • On a LD from the core:
    • it returns a hit, and
    • maps the address to a directory, and issues a message for it of type MSG, and size Control (8 bytes) in the request vnet (0).
    • Note: vnet 0 could also be made to broadcast, instead of sending a directed message to a particular directory, by uncommenting the appropriate line in the a_issueRequest action in Network_test-cache.sm
  • On a IFETCH from the core:
    • it returns a hit, and
    • maps the address to a directory, and issues a message for it of type MSG, and size Control (8 bytes) in the forward vnet (1).
  • On a ST from the core:
    • it returns a hit, and
    • maps the address to a directory, and issues a message for it of type MSG, and size Data (72 bytes) in the response vnet (2).
  • Note: request, forward and response are just used to differentiate the vnets, but do not have any physical significance in this protocol.

Directory controller

• Requests, Responses, Triggers:
  • MSG from the cores

• Main Operation:
  • The goal of the directory is only to act as a destination node in the underlying interconnection network. It does not track any states.
  • The directory simply pops its incoming queue upon receiving the message.

Other features

• • This protocol assumes only 3 vnets.
  • It should only be used when running the ruby network test.