An interaction of coherence protocols and memory consistency models in DSM systems.
Coherence protocols and memory consistency models are two improtant issues in hardware coherent shared memory multiprocessors and softare distributed shared memory(DSM) systems. Over the years, many researchers have made extensive study on these two issues repectively. However, the interaction between them has not been studied in the literature. In this paper, we study the coherence protocols and memory consistency models used by hardware and software DSM systems in detail. Based on our analysis, we draw a general definition for memory consistency model, i.e., memory consistency model is the logical sum of the ordering of events in each processor and coherence protocol. We also point that in hardware DSM system the emphasis of memory consistency model is relaxing the restriction of event ordering, while in software DSM system, memory consistency model focuses mainly on relaxing coherence protocol. Taking Lazy Release Consistency(LRC) as an example, we analyze the relationship between coherence protocols and memory consistency models in software DSM systems, and find that whether the advantages of LRC can be exploited or not depends greatly on it's corresponding protocol. We draw the conclusion that the more relaxed consistency model is, the more relaxed coherence protocol needed to support it. This conclusion is very useful when we design a new consistency model. Furthermore, we make some improvements on traditional multiple writer protocol, and as far as we aware, we describe the complex state transition for multiple writer protocol for the first time. In the end, we list the main research directions for memory consistency models in hardware and software DSM systems.
Introduction
Distributed Shared Memory(DSM) systems have gained popular acceptance by combining the scalability
and low cost of distributed system with the ease of use of the single address space. Generally,
there are two methods to implement DSM systems: hardware vs software. Cache-Coherent Non-
Uniform-Memory-Access Multiprocessors(CC-NUMA) are the dominant direction of hardware DSM
The work of this paper is supported by the CLIMBING Program and the President Foundation of the Chinese
Academy of Sciences.
systems. To date, there are many commercial and research systems, such as Stanford DASH[34],
Stanford FLASH[31], MIT Alewife[5], StartT-Voyager[10], SGI Origin series. While in software
DSM alternatives, the general method is supplying a high-level shared memory abstraction on the
top of underlying messaging passing based system, such as multicomputers and LAN-connected
NOW. For example, Rice Munin[13], Rice TreadMarks[19], Princeton IVY[33], CMU Midwary[12],
Utah Quarks[28], Marland CVM[26], DIKU CarlOS[29] are current commercial or research software
DSM systems in the world.
Cache coherences and memory consistency models are two important issues in CC-NUMA ar-
chitecture. Cache coherence is mainly used to keep multiple copies of one cache block consistent
to all processors, while the role of memory consistency models is specifying how memory behaviors
with respect to read and write operations from multiple processors. Both of these two issues
have gained extensive study in the past 20 years. There are several cache coherence protocols
and memory consistency models have been proposed in the literature. Coherence protocols include
write-invalidate, write-update, delay-update. Memory consistency models include sequential
consistency[32], processor consistency[22] [21], weak ordering[3], release consistency[21] et al.
Coherent problem remains in software DSM systems. The difference between hardware and
software implementation is the granularity of coherence unit. In software DSM systems the coherence
unit is page, while in hardware DSM systems the coherence unit is cache block line.
Since the role of page in software DSM systems is similar to that of cache in hardware DSM
systems, for simplicity, we will use cache coherence in both cases in the rest of this paper. The
coherence protocols widely adopted in software DSM systems include multiple writer protocol
(i.e., write-shared protocol)[13], single writer protocol[26][8]. The memory consistency models are
mainly used to reduce the frequency of communication and message traffic[27]. Examples of relaxed
consistency models adopted in software DSM systems include eager release consistency[13],
lazy release consistency[27], entry consistency[12], automatic update release consistency[23], scope
consistency[24], home-based lazy release consistency[43], singer-writer lazy release consistency [26],
message-driven release consistency[29], and affinity entry consistency[6].
In fact, both cache coherence protocols and memory consistency models describe the behaviours
of DSM systems. They are interdependent on each other and the relationship between them is very
complex. Up to now as we know, there is no research on this problem.
In this paper, we first describe a clear understanding about coherence and memory consistency
model and propose a general definition for memory consistency model. We also point that in hardware
DSM system the emphasis of memory consistency model is relaxing the restriction of event
ordering, while in software DSM system, memory consistency model focuses mainly on relaxing
coherence protocol. Taking Lazy Release Consistency(LRC) as an example, we analyze the relationship
between coherence protocols and memory consistency models in software DSM systems.
We draw the conclusion that the more relaxed consistency model is, the more relaxed coherence
protocol needed to support it. This conclusion is very useful when we design a new consistency
model. Furthermore, we make some improvements on traditional multiple writer protocol by adding
a new state, and as far as we aware, we describe the complex state transition for multiple writer
protocol for the first time. In the end, we list the main research directions for memory consistency
models in hardware and software DSM systems.
The remainder of the paper is organized as follows. In section 2 we briefly overview the development
of coherence protocols and memory consistency models, and propose a general definition
for memory consistency model. Taking LRC as an example, the relationship between coherence
protocols and memory consistency models is deduced in section 3. Furthermore, the state transition
graph for new improved multiple writer protocol is shown in section 3. Related works and
conclusions remarks are listed in section 4 and section 5 respectively.
General Definition for Memory Consistency Model
Censier and Feautrier defined a coherent memory scheme as follows[14]:
Definition 2.1: A memory scheme is coherent if the value returned on a LOAD instruction is
always the value given by the latest STORE instruction with the same address.
This definition, while intuitively appealing, is vague and simplistic. The reality is much more
complex. In a computer system where STORE can be buffered in a store buffer, it is not clear
whether "last STORE" refer to the execution of the STORE by a processor, or to the update of
memory. In fact, the above definition contains two different aspects of memory system behaviours,
both of which are critical to writing correct shared memory programs. The first aspect, called
coherence, defines what values can be returned by a read operation. The second aspect, called
event ordering in each processor, determines when a written value will be returned by a read
operation. Coherence ensures that multiple processors see a coherent view of the same location,
while event ordering in a processor describes that when other processor sees a value that has been
updated by this processor. In [38] Hennessy and Patterson presented the sufficient conditions to
coherence as follows.
1. A read by a processor, P, to a location X that follows a write by P to X, with no writes of X
by another processor occurring between the write and the read by P, always returns the value
written by P.
2. A read by a processor to location X that follows a write by another processor to X returns the
written value if the read and write are sufficiently separated and no other writes to X occur
between the two accesses.
3. Writes to the same location are serialized: that is, two writes to the same location by any two
processors are seen in the same order by all processors. For example, if the values 1 and then
are written to a location, processors can never read the value of the location as 2 and then
later read it as 1.
The above three conditions only guarantee that all the processors have a coherent view about position
X. However, Since they don't tell us the event ordering in each processor, we can't determine
when a written value will be seen by other processors. As such, in order to capture the behaviors
of memory system accurately, we need to restrict both the coherence and the event ordering, this
is the role of memory consistency model. We will use the strictest memory consistency model
-sequential consistency as an example to explain this in the following.
Scheurish and Dubois[39] described a sufficient condition to sequential consistency as follows:
1. All processors issue memory accesses in program order.
2. If a processor issues a STORE, then the processor may not issue another memory access until
the value written has become accessible by all other processors.
3. If a processor issues a LOAD, then the processor may not issue another memory access until
the value which is to be read has both been bound to the LOAD operation and become accessible
to all other processors.
From above two sufficient conditions for coherence and consistency, we see that coherence and consistency
are related tightly. The conditions of coherence is a subset of the conditions of memory
consistency model. The former considers the different events from different processors to the same
location only, while consistency model not only considers the different events to the same location
but also imposes constraints on the ordering of event within each processor, that is, the execution
order in each processor. As such, the combination of cache coherence and event ordering will determine
the behaviour of whole memory system. Based on our understanding, we propose a general
definition for memory consistency model to reveal the relationship between them.
memory consistency model = coherence protocol event ordering in each processor
Some researchers use event ordering and memory consistency model interchangely. However, we
believe that our new understanding can describe the memory system behaviours more accurately
than them.
In our new definition, the role of coherence is to ensure that the coherent view of the given
memory location by multiple processors. Ordering of events describes the happen sequence of
memory events issued by each processor. Here, we use memory events to represent the read and
store operation to the memory[17]. Memory consistency model is the logical sum of coherence
protocol and event ordering in each processor. For example, sequential consistency, defined by
Lamport in 1979[32], can be viewed as two conditions[2]:
1. all memory access appear to execute automatically in some total order.
2. all memory accesses of each processor appear to execute in an order specified by its programmer

The first condition, atomicity, is ensured by coherence protocol. There are two base kinds of cache
coherence protocols: write invalidate and write update[41]. Write update protocol ensures that all
processors which keep copies will see the new value simultaneously with modified processor, while
invalidate protocol reaches the coherent view by invalidate all other copies.
The second condition, program order, is determined by the executing order of events. If we
restrict all the events in one processor to be issued, performed in program order, this condition will
be satisfied. However, the above constraint is too strict to improve the performance. Especially,
many hardware and compiler optimizations, such as write buffer, look-up free, non-binding reading,
register allocation, dynamic scheduling, multiple issues, can't be utilized in this memory consistency
model.
These two conditions for sequential consistency model show that there are two directions for
us to relax this strictest consistency model. In hardware DSM systems, over the years, there are
several consistency models proposed to exploit hardware and complier optimization techniques.
Such as, processor consistency, weakly order, weak ordering(new definition), release consistency,
DRF1, PLpc model[20]. Almost all the hardware and compiler optimization techniques have been
exploited in PLpc memory consistency model. In these relaxed consistency models, however, only
the event ordering in each processor is relaxed, such as W!R, W!W, R!R, R!W operations
in successive synchronization operation, while the atomicity demand changes little. For example,
in RC, all the operations between two synchronization operations can be completed out of order if
no data dependence is violated. However, the atomicity is maintained by write invalidate protocol
which is similar to that in sequential consistency model.
In software DSM systems, the communication overhead is so expensive that the cost for maintaining
atomicity is more expensive than that in hardware DSM systems. Therefore, reducing the
frequency of communication and message traffic is more important in software DSM systems than
in hardware DSM systems. Furthermore, since the coherence unit in software DSM system is page
or larger than page[9], the false sharing problem is more serious than that in hardware DSM sys-
tems. As such, how to eliminate the false sharing problem effectively is also an important issue in
software DSM systems.
Before discussing the solution for false sharing, we first give a clear description about false
sharing. False sharing occurs when two processors access logically unrelated data that happen to fall
on the same page and at least one of them writes the data, causing the coherence mechanisms to
ping-pong the page between these processors. It includes two categories: write-write false sharing and
write-read false sharing. False sharing will entail many useless communication among processors[25].
In order to reduce the communication overhead in software DSM systems, several new memory
consistency models are proposed in the past. The represented consistency models for software
DSM systems include Eager Release Consistency(ERC) in Munin[13], Lazy Release Consis-
in TreadMarks [27], Entry Consistency(EC) in Midway[12], Automatic Update Release
Consistency(AURC) in SHRIMP[23], Scope Consistency(ScC)[24], Home-based Lazy Release
Consistency(HLRC)[43], Singer Writer Lazy Release Consistency(SW-LRC)[26], Message-Driven
Release Consistency(MDRC) in CarlOS [29], and Affinity Entry Consistency[6] in NCP2.
Among these consistency models, the ordering of events in each processor is similar to one
another, in other words, the main difference of these models is the method to maintain coherence.
This includes two aspects: (1) Which coherence protocol is used;(2) How this protocol is imple-
mented. All the coherence protocols adopted in software DSM systems are more relaxed than the
strict single writer protocol used in hardware DSM systems. Relaxed coherence protocols include
write-shared protocol(multiple-writer)[13], relaxed single-writer protocol(or, delay invalidate)[26] 1 .
For example, both TreadMarks and Munin systems use multiple writer protocol, while CVM adopts
relaxed single writer protocol.
Among above described memory consistency models, the main difference lies in when the up-dated
value made by one processor can be available by other processors. For example, in LRC,
when other processors execute an acquire operation , they will see all the updated value modified
before it in happen-before-1 partial order. However, in EC and ScC, only the shared data associate
with the same synchronization object are available when one processor acquires a synchronization
object.
Based on the analysis of hardware and software DSM systems in this section, we see the coherence
protocol and event ordering in each processor are two important parts of memory consistency
model. In particular, in software DSM system the difference among different consistency models
depends greatly on corresponding coherence protocols. we will analyze their relationship in detail
in the following section.In order to differentiate this improved single writer protocol from strict single writer protocol, we use relaxed
single-writer to represent it here. In next section, the operation procedure of relaxed single writer protocol will be
shown.
3 Interaction between Coherence and Consistency in LRC
In this section, we take lazy release consistency as an example to analyze the relationship between
coherence protocol and consistency model in detail.
3.1 Lazy Release Consistency
LRC[27] is an all-software, page-based, write-invalidated based multiple writer memory consistency
model. It has been implemented in TreadMarks system[19]. Since the objective of this section is
analyzing the interaction between coherence protocol and consistency model, we describe the key
idea of lazy release consistency in this subsection , and multiple writer protocol will be described
in the following subsection. LRC is a lazy implementation of RC[21] or ERC[13]. It delays the
propagation of modifications to a processor until that processor executes an acquire operation.
The main idea of the consistency model is to use timestamps, or intervals to establish the happen-
before-1 ordering between causal-related events. Local intervals are delimited by synchronization
events, such as LOCKs, BARRIERs. LRC uses the happen- before-1 partial order to maintain
ordering of events. The happen-before-1 partial order is the union of the total processor order of
the memory accesses on each individual processor and the partial order of release-acquire pairs.
Vector timestamps are used to represent the partial order. When a processor executes an acquire,
it sends its current vector timestamp in the acquire message. The last releaser then piggybacks on
its response a set of write notices. The write notices include the processor id, the vector timestamp
for the interval during which the page was modified and the modified page number. A faulting
processor uses write notices to locate and apply the modifications required to update its copy of the
page. Both write-invalidate and write-update protocols can be used to implement above algorithms.
In the following discussion, we assume that write invalidate protocol is used.
3.2 Multiple Writer Protocol
Multiple Writer(MW) protocol has been developed to address the write-write false sharing problem.
With a MW protocol, two or more processors can modify their local copies of a shared page
simultaneously. Their modifications are merged at the next synchronization operation. Therefore
the effect of false sharing is reduced.
There are two key issues to implement MW protocol: write trapping and write collection. Where
write trapping is the method to detect what shared memory location has been changed, twinning
and software dirty bit[12] are two general methods used in software DSM systems. Write collection
refers to the mechanism used for determining what modified data needs to be propagated to the
acquirer. Timestamp and diffing are two methods used in Midway and TreadMarks respectively.
For more details, please refer to [8]. In TreadMarks twining and diffing mechanisms are adopted.
Although multiple writer protocol was first introduced by Carter in Munin, this protocol is not
a new idea. It is derived from the idea of delay update in [11]. In [11], Bennett et al. pointed out
In order to avoid unnecessary synchronization that is not required by the pro-
gram's semantics. When a thread modifies a shared object, we can delay sending
the update to remote copies of the object until remote threads could otherwise
indirectly detect that the object has been modified.
This is original description about delay update protocol. It is very vague for understanding, for
example, what "indirectly" means? Whether two or more processors can modify the same unit si-
multaneously? If we assign different understanding for this idea, we will obtain different coherence
protocols. For example, if two or more processor 2 are allowed to modify the same page simultane-
ously, the delay update protocol will evolve multiple writer protocol. If at any time there is only
one writer is allowed to exist, and multiple reader can coexisted with single writer, the delay update
protocol evolves relaxed single writer protocol. This protocol has been proved very useful in some
applications [26]. The implementation of these protocol will be shown in the next subsection.
Multiple writer protocol has several benefits as follows:
multiple nodes can update the same page simultaneously, the protocol can greatly reduce
the protocol overhead due to false sharing.
ffl The protocol can reduce the communication traffic due to data transfer: instead of transfering
the whole page each time, it transfers diffs only.
ffl The protocol can relaxed the ordering of events in an interval further since without the ownership
is required before a write operation.
3.3 Interaction between LRC and its corresponding Protocol
According to above description of LRC and multiple-writer protocol, we find that LRC and multiple
writer protocol are closely related. We will analyze the relationship between them step by step,
from the strict single writer protocol to the most relaxed multiple writer protocol.
If LRC uses the strict singer-writer single-reader protocol which is adopted in release consistency,
i.e., before one processor writes a cache block, it must obtain the ownership first, and when other
processors receive invalidate message, they must invalidate their local pages immediately. Therefore,
at release operation, no write notices are needed to record because that all other processors have
already known the modification executed in this processor which will release the lock. When other
processor executes an acquire operation in the following, no write notices are needed since all the
pages should be invalidated in lazy release consistency have been invalidated already. As such, the
lazy property can not be exploited at all. In this case, the write notices and vector timestamps
are only used to help faulting processors to locate the valided page, just like the role of "home" in
CC-NUMA machine. Furthermore, the write-write and write-read false sharing cannot be resolved.
In this case, the performance of LRC will be similar to that of RC.
If the relaxed single writer protocol (i.e., singer-writer multiple-reader protocol used in [26]) is
adopted, when one processor receives invalidate messages, it doesn't invalidate those pages immedi-
ately, on the contrary, it keeps its own copies appear valid to itself until the next acquire operation.
2 In this paper, we assume that each processor has only one thread, therefore, we use thread, process, and processor
interchangely.
In this case, the write-read false sharing is eliminated partially, while write-write false sharing remains
too. In order to depict this protocol accurately, we must introduce a new state stale, which
is used to represent the state of a page during the interval between receiving an invalidate message
about this page and next acquire operation. The messages received at an acquire operation in this
coherence protocol include 3 categories :(1)necessary messages, (2) unnecessary messages entailed
by false sharing, (3) unrelated messages about other pages which will be not used by the requiring
processor. For example, in Fig 1, p1, p2 are two processors, variable x0,x1,x2,x3,x4 are 5 shared
data, where x0 and x2 are allocated on the page 0, x1 and x3 are allocated on the page 1, x4
is allocated on page 2 solely. Lock L0, L2 are 2 locks used by users to create critical sections to
protect the use of shared data. With relaxed single writer protocol, when p1 wants to write x1, it
must obtain the ownership before write operation and the procedure of invalidating other copies
can be overlapped with other operations following this write operation. When p2 receives the invalidate
message, it doesn't invalidate page 1 immediately, and keeps it appear to valid until next
lock acquiring operation, therefore, at the time when p2 read x3, it doesn't cause page fault error,
this read-write false sharing case can be eliminated. However, when p2 wants to read x3 after an
acquire operation, it will cause a page fault error. Therefore, the read-write false sharing problem
does not be eliminated completely in relaxed single writer protocol. On the other hand, when p2
writes x2, it must cause a write fault since only one writer is allowed to write a page at a given
time. As such, the write-write false sharing problem remains. In fig 1, the message 1 and 2 belong
to both first category and second category, while message 3 is unrelated message, message 4 and 5
are the unnecessary messages entailed by false sharing.
In above example, if the strict single-writer protocol is used , the page 0 in p2 will be invalidated
immediately, and the first read of x3 will cause false sharing. So, we find that the relaxed single
writer protocol is better than strict single writer protocol. On the other hand, in relaxed single
writer protocol, when page fault occurs, the whole page will be transfered, which results in a great
message traffic. In order to solve false sharing problem completely and reduce large communication
traffic, multiple writer protocol is proposed and widely used in software DSM systems.
In traditional MW protocol, however, when the acquiring processor receives the write notices,
it will invalidate its corresponding pages immediately, which results in write-read false sharing
as entailed by strict single writer protocol. Therefore, we improve the multiple writer protocol
by combining the traditional MW protocol and relaxed single writer protocol. When improved
multiple writer coherence protocol is adopted, the advantages of LRC can be exploited completely.
Almost all the false sharing effects will be eliminated. Furthermore, with improved MW protocol,
the write operations within one interval can forward without waiting the ownership. In this case,
the messages received at an acquire operation include:(1)necessary message(such as write notices)
, (2) some unrelated messages about other pages which will be not used by requiring processor,
such as invalidate message for page 2 in Fig 1. These unrelated messages will be solved in Entry
consistency and our new NLLS consistency model[40]. This is beyond the scope of this paper. In
multiple writer protocol, since two or more writers can modify the same page simultaneously, the
state of each page will be more complex than above two protocols. For example, when two writers
write the same page, whch one is the owner? When a third processor want to write a page, to whom
it should to inform? Diffing and twinning mechanism only tell us the implementation method for
certain protocol, however, its don't tell us how to maintain the state transition in multiple writer
protocol. We will describe the state transition in next subsection.
From above analysis, we draw the following conclusions as shown in Table 1. For completeness,
page 0
page 1 page 2
x3
Invalidate page 1
invalidate page 2
Invalidate page 0
release (L0)
acquire (L2)24ask for ownership
send ownership
no page fault cccur
page fault occur
page fault occur

Figure

1: An example of write-invalidate-based relaxed single writer protocol.
we list the strictest sequential consistency as the base for comparison.
memory consistency model corresponding coherence protocol
sequential consistency (1)require all memory operations atomically, (2)send and receive
invalidate messages immediately, and(3)stop until the
acknowledgement is received.
release consistency (1)the atomicity demand relaxed, but the ownership must
obtain before write, (2)send and receive invalidate message
immediately, and (3)the receiving of acknowledgement can be
delayed until the following release synchronization operation
LRC(single writer) (1)the atomicity demand relaxed, but the ownership must
obtain immediately before write, (2)send invalidate message,
the receiver delay accept the invalidate message until next
acquire synchronization operation, and (3)the receiving of
acknowledgement can be delayed until the following release
synchronization operation
LRC(multiple writer) (1)the atomicity demand was relaxed further, no ownership is
needed before write(if this processor has already had a copy
of this page), (2)both send and receive of invalidate messages
can be delayed, and(3)the receiving of acknowledgement
can be delayed until the following release synchronization
operation

Table

1: The relationship between memory consistency model and coherence protocol.
According to the performance comparisons presented by other researchers[8],[36][26] and our
analysis shown in Table 1, we find that the advantages of consistency models depend closely on
their corresponding coherence protocols. The more relaxed consistency model is, the more relaxed
coherence protocol needed to support it. This conclusion is very useful when we design a new
consistency model. For example, with the support of MW protocol, scope consistency [24] is more
relaxed than LRC, It combines the advantages of EC and LRC, distinguishes different Locks, i.e.,
the acquiring processor obtains the modified data from the releasers which use the same Lock.
Therefore, many useless messages in above three protocols can be reduced greatly 3 .
3.4 The State Transition for Invalidate-based Multiple Writer Protocol
As described above, in order to depict the coherence transition for relaxed single writer protocol
and improved multiple writer protocol, we must add a new state named stale, which means that
this coherence unit is modified by other processors, however, it appears to valid for this processor
itself. Fig 2 shows a state transition graph for write-invalidated-based multiple writer protocol for
LRC. As far as we aware, this is the first time a whole state transition graph for multiple writer
protocol is shown.
Exclusive shared
Invalid stale
Ri,
Wj, Rj
Ri,Rj.W,
Ri: Read from local processor
Wi: write from local processor
Rj: Read from remote processor
Acquire(l):Acquire lock
Release (l): Release lock l.
Wj: Write from remote processor
Create DIFFi
(create DIFFi and send it to exclusive node)
Wi(create Twin,. keep write notices)

Figure

2: The state transition graph for write-invalidated-based multiple writer protocol for LRC.
3 Although in [24], the authors didn't tell us the multiple writer protocol is adopted, from the examples shown in
that paper we deduce that scope consistency uses multiple writer protocol too.
4 Related Works
Dubios et.al in [17] analyzed the relationship between synchronization, coherence and event order-
ing. Although they separated the concepts of coherence and event ordering, they didn't present
the relationship between them, and they equalized event ordering with memory consistency model,
which is different from our viewpoint. They defined strong ordering and weak ordering in that paper
and presented that strong ordering is the same as sequential consistency. In fact, this viewpoint is
wrong because the cache coherence protocol is not considered, Adve and Hill gave an example in
[4] to demonstrate this wrong case.
Per Stenstrom in 1990 presented an excellent survey about cache coherence protocols[41]. Adve
and Gharachorloo discuss an extensive survey about memory consistency models[2]. However,
both of them considered the case for hardware DSM systems only. In our paper, we consider
both hardware and software DSM systems together, and study the relationship between coherence
protocol and memory consistency model.
Recently, Zhou et.al discussed the relationship between relaxed consistency model and coherence
granularity in DSM systems[44]. They only consider the granularity of coherence protocol, while
never consider the coherence protocol.
Dubios et.al in [18] proposed delay consistency model for a release consistent system where an
invalidation is buffered at the receiving processor until a subsequent acquire is executed by the
processor. The delay consistency model is a coherence protocol which includes two categories:delay
receive and delay-send delay receive, where delay receive is the same as relaxed single writer protocol,
delay send and delay receive is similar to multiple writer protocol. They presented the state
transition for hardware shared memory in detail. In this paper we describe the state transition for
software DSM systems for the first time.
5 Conclusion and Future Work
In this paper, starting with a classical coherent memory scheme, we point out that memory coherent
includes two issues:coherency and event ordering in each processor. Based on a clear description
of these two concepts, we define a general definition about memory consistency model, which is
the logical sum of coherence protocol and event ordering in each processor. Second, we analyze
the consistency models used in hardware DSM systems and software DSM systems under our new
definition. We point out that in hardware DSM systems, the relaxed consistency model is devoted
to relax the ordering of events, such as W!R, W!W, R!R, R!W operations, to utilize the
hardware and complier optimization techniques. While coherence protocol does not make much
progress in the past years. In software DSM systems, the main obstacle to performance is high
communication overhead and the useless coherence-related messages entailed by the large coherence
granularity. Therefore, the main purpose of the consistency model in software DSM system is to
reduce the number of message and message traffic. while the event ordering in each processor of
all new consistency models are similar to that of release consistency,
Third, taking the LRC as an example, we analyze the relationship between coherence protocol
and consistency model in software DSM systems, and conclude that these two issues are closed
related. The more relaxed consistency model is, the more relaxed coherence protocol needed to
support it. This conclusion is very useful when we design a new consistency model.
Fourth, we make some improvements on traditional multiple writer protocol by adding a new
state, and describe the state transition graph for invalidate-based multiple writer protocol for the
first time.
Finally, based on the analysis in this paper, we propose that the main directions of memory
consistency model research in the future as following:
For hardware DSM systems:
ffl Relaxing the coherence protocol further, such as allowing multiple writers in hardware-
coherent DSM system. This is possible because of the much progress of semi-conductor
technology[37].
ffl Considering the hybrid hierarchical DSM MPP system, where each node uses hardware to
implement DSM , while shared memory abstraction among nodes is supported by software
DSM.
For software DSM systems:
ffl Relaxing coherence protocol further.
ffl Using hybrid coherence protocols for different shared data, such as shared data protected by
locks and shared data protected by barriers.
ffl Intergrating more memory consistency model together to support different applications.
ffl Considering the interaction with other latency tolerate techniques, such as multithreading
and prefetching.



--R

A Comparison of Entry Consistency and Lazy Release Consistency Implementations.
Shared Memory Consistency Models: A Tutorial.
Weak Ordering:A new definition.
Implementing Sequential Consistency In Cache Based Systems.
The MIT Alewife Machine: Architecture and Performance.
The Affinity Entry Consistency Protocol.
TreadMarks: Shared Memory Computing on Networks of Workstations.
Software DSM Protocols that Adapt between Single Writer and Multiple Writer.
Tradeoffs between False Sharing and Aggregation in Software Distributed Shared Memory.
Larry Rudolph and Arvind.
Munin: Distributed Shared Memory Based on Type-Specific Memory Coherence
The Midway Distributed Shared Memory System.
Implementation and Performance of Munin.
A New Solution to Coherence Problems in Multicache Systems.
Parallel Computer Architecture (alpha version).
Memory Access Buffering in Multiprocessors.

Jin Chin Wang
TreadMarks Distributed Shared Memory on standard workstations and operating systems.
Programming for Different Memory Models.
Memory consistency and event ordering in scalable shared memory multiprocessors.
Cache consistency and sequential consistency.
Improving Release-Consistent Shared Virtual Memory using Automatic Update

Understanding Application performance on Shared Virtual Memory systems.
The Relative Importance of Concurrent Writes and Weak Consistency Mod- els
Lazy Release Consistency for software Distributed Shared Memory.
Portable Distributed Shared Memory on UNIX.

Lazy Release Consistency for Hardware-Coherent Multiprocessor
The Stanford FLASH Multiprocessor.
How to Make a Multiprocessors Computer That Correctly Executes Multiprocessor Programs.
IVY:A Shared Virtual Memory System for Parallel Computing.
The Standard Dash Multiprocessor.
ADSM: A hybrid DSM Protocol that Efficiently Adapts to Sharing Patterns.
An Evaluation of Memory Consistency Models for Shared Memory Systems with ILP Processors.
Intelligent RAM (IRAM): Chips that Remember and Compute Revised
Computer Architecture: A Quantitative Approach.
Correct Memory Operation of Cache-Based Mul- tiprocessors
Memory Consistency Models for Distributed Shared Memory Systems
A Survey of Cache Coherence Schemes for Multiprocessors.
The SPLASH-2 Programs: Characterization and Methodological Considerations
Performance Evaluation of Two Home-based Lazy Release Consistency Protocols for Shared virtual Memory Systems

--TR

--CTR
optimization and integration in DSM, ACM SIGOPS Operating Systems Review, v.34 n.3, p.29-39, July 2000
event ordering;software DSM systems;memory consistency models;coherence protocol;hardware DSM systems