· Shared memory

· Shared bus

· A set of independent (off-the-shelf) processors with L1 (and L2)

· Simple—essentially the same as for SISD

· Limited—memory and bus are the bottleneck

· Cache consistency maintenance (hw, sw, or hybrid)

· Snoopy

· Directory

· Fully distributed information related to coherence

· Responsibility for coherence maintenance on local cache controllers

· Broadcast notification

· Snooping capability

· Ideally suited for bus-based multiprocessors

- Limited scalability

· Write-invalidate (WI) protocols

· Write-update (WU) protocols

· Multiple copies with simultaneous read permission

· Only one copy with write permission at a time

· Write to a shared copy preceded by an invalidation signal
(to prevent the use of stale copies)

· Cheap, local writes to an exclusive copy

· Multiple copies with write permission

· Distributed write approach (updated word broadcast to other sharers)

· Special bus line for dynamic detection of sharing

· Write-back for private data (local writes)

· Write-through for shared data

· Sweazy + Smith, 1986

· Standardization of snoopy cache coherence protocols

· Class of compatible protocols

· MOESI (Modified, Owned, Exclusive, Shared, Invalid) state model

· Standard superset protocol for the IEEE Futurebus

· Seven special bus lines

· Coexistence of modules in the same system with different protocols
and
memory update policies (write-back, write-through, and non-caching)

· Memory system state is consistent
as long as any system component
dynamically selects any action permitted by any protocol

· Number of earlier protocols falls within this class,
as proposed (Berkeley, Dragon) or
with some modifications (Illinois, Firefly, Write-Once)

· Derived protocol - MESI
implemented in a number of contemporary microprocessors
(another derived protocol - SI)

· Responsibility for coherence maintenance on centralized controller

· Individual commands to known locations

· Write-invalidate protocols (most often)

· Suitable for general ICN

· Global information organized in a form of directory:

· DirN NB - complete bit vector (a presence bit per processor + dirty bit)

· Two bits in a cache directory entry (valid + modified)

- Directory storage O(MN) ~ O(N2): not scalable

- Centralized controller: a potential fault-tolerance bottleneck
and a performance degradation factor

- Inflexible for expansion: adding a new node requires system changes

· Results of several sharing studies Þ
prevalent type of sharing:
block is shared by a small number of processors

· Diri X - limited number of pointers (i < N)

· Mechanism to handle pointer overflow

· No-broadcast (X = NB) and broadcast (X = B) variants

- Performance affected by increased sharing

· Agarwal, et al., 1989.

· Pointer overflow Þ one shared copy is invalidated to free a pointer

Figure SMPU6: Explanation of the no-broadcast scheme (source: [Tomasevic96]).

- Restriction on the number of simultaneously cached copies
(overhead even for read sharing)

- Degradation for intensive sharing of read-only and read-mostly data,
due to increased miss ratio

· No restriction on read sharing

· Pointer overflow Þ broadcast bit set

· Subsequent write Þ invalidation broadcast (some of them unnecessary)

· Distributed directories spread across local caches (chains of pointers)

· Shared copies of a block chained into a list
(head pointer kept in memory)

· Singly- (e.g., SDD) or doubly-linked (e.g., SCI) lists

+ Reduced directory storage (~ O(log N)), without the restriction of sharing

- Higher write latency and increased complexity

· Performance close to the full-map schemes [Chaiken90]

· Agarwal et al., MIT.

· Standard limited directory protocol (dir_iB or dir_iNB),
with a software mechanism to handle pointer overflow.

· If pointer overflow, then interrupt:
hardware pointers get stored to memory,
to free up directory space for lower-intensity sharers.

· Simoni, Stanford.

· Directory entry:

· Pointer/link store:

· A hardware implementation of LimitLESS!

· Problem: Scalability and Standardization

· Idea: IEEE 1596–1992 SCI Standard

· Reading a shared value:

· Writing to a shared value:

· Advantages of doubling the links:

· Prete, University of Pisa, 1991.

· Goals:

· Based on Dragon (and Firefly):

· Difference to Dragon:

· Difference to Firefly:

- Lower probability of cache supply

· Problem for WU: false sharing due to process migration

· Idea: detecting and destroying the remaining copies
from previous processes

· Protocol requirements (in addition to Dragon):

· Basic protocol actions (for reducing of false sharing)

+ Lower false sharing Þ lower bus usage, cache interference,

- Not all unused copies eliminated

· Problem for WU: passive sharing due to process migration

· Idea: modification of the general UCR strategy

· Tomasevic + Milutinovic, University of Belgrade, 1991.

· Finer-grain, partial block invalidation

· Word invalidation Þ existence of partially valid blocks:

· Block ownership

· Dynamic recognition of sharing status

· Pollution point - criterion of inactive sharing
(when reached, invalidation of the entire block)

· Read word bus operation

· Less invalidation misses, higher hit ratio Þ better data utilization

· Reduced false sharing

· Appropriate sequential pattern of sharing

· Additional complexity: one state bit per block + one valid bit per word