CSC/ECE 506 Spring 2012/10b sr - Revision history

Sshanbh: /* Practical performance impact */

2012-04-05T08:51:50Z

Practical performance impact

← Older revision		Revision as of 08:51, 5 April 2012
Line 153:		Line 153:
	* Only one consistent state can be observed. On the other hand, in weak consistency (where different parallel processes or nodes etc.) perceive variables in different states.		* Only one consistent state can be observed. On the other hand, in weak consistency (where different parallel processes or nodes etc.) perceive variables in different states.

	== Practical performance impact ==		== Practical performance impact <ref>http://classes.soe.ucsc.edu/cmpe221/Spring05/papers/29multi.pdf</ref>==

	[[Image:consistency_models.jpg\|thumb\|center\|700px\|Implementation of consistency models]]		[[Image:consistency_models.jpg\|thumb\|center\|700px\|Implementation of consistency models]]

Sshanbh: /* PRAM consistency */

2012-04-05T08:51:03Z

PRAM consistency

← Older revision		Revision as of 08:51, 5 April 2012
Line 104:		Line 104:
	Thus, an object is linearizable if all valid histories of its use can be linearized.		Thus, an object is linearizable if all valid histories of its use can be linearized.

	=== PRAM consistency ===		=== PRAM consistency <ref>http://en.wikipedia.org/wiki/PRAM_consistency</ref>===
	[[Image:pram.jpg\|thumb\|right\|300px\|PRAM Consistency example]]		[[Image:pram.jpg\|thumb\|right\|300px\|PRAM Consistency example]]

Sshanbh: /* Sequential consistency */

2012-04-05T08:45:45Z

Sequential consistency

← Older revision		Revision as of 08:45, 5 April 2012
Line 123:		Line 123:
	* ''lazy'', where all coherence actions are delayed until after a subsequent acquire		* ''lazy'', where all coherence actions are delayed until after a subsequent acquire

	=== Sequential consistency ===		=== Sequential consistency <ref>http://en.wikipedia.org/wiki/Sequential_consistency</ref>===
	[[Image:sc.jpg\|thumb\|right\|300px\|PRAM Consistency example]]		[[Image:sc.jpg\|thumb\|right\|300px\|PRAM Consistency example]]

Sshanbh: /* Release consistency */

2012-04-05T08:44:33Z

Release consistency

← Older revision		Revision as of 08:44, 5 April 2012
Line 113:		Line 113:
	The example shown is legal under PRAM but not under SC or CC. P3 and P4 observe the writes by P1 and P2 in different orders, although W(x)1 and W(x)2 are potentially causally related.		The example shown is legal under PRAM but not under SC or CC. P3 and P4 observe the writes by P1 and P2 in different orders, although W(x)1 and W(x)2 are potentially causally related.

	=== Release consistency ===		=== Release consistency <ref>http://en.wikipedia.org/wiki/Release_consistency</ref>===

	Release consistency is one of the consistency models used in the domain of the concurrent programming (e.g. in distributed shared memory, distributed transactions etc.).		Release consistency is one of the consistency models used in the domain of the concurrent programming (e.g. in distributed shared memory, distributed transactions etc.).

Sshanbh: /* Linearizability */

2012-04-05T08:42:43Z

Linearizability

← Older revision		Revision as of 08:42, 5 April 2012
Line 67:		Line 67:
	* Asynchronous repair: The correction is not part of a read or write operation.		* Asynchronous repair: The correction is not part of a read or write operation.

	=== Linearizability ===		=== Linearizability <ref>http://en.wikipedia.org/wiki/Linearizability</ref>===

	This is also known as strict or atomic consistency. An operation is linearizable if it appears to the rest of the system to occur instantaneously. An atomic operation either occurs completely or does not occur at all. In reality, atomic operations do not actually occur instantaneously. Atomicity is enforced by mutual exclusion. At the software level, locks or semaphores are used to achieve this, while at the hardware level, a cache coherency protocol maybe used. This makes it appear to the user that the entire operation occurred in a single instruction.		This is also known as strict or atomic consistency. An operation is linearizable if it appears to the rest of the system to occur instantaneously. An atomic operation either occurs completely or does not occur at all. In reality, atomic operations do not actually occur instantaneously. Atomicity is enforced by mutual exclusion. At the software level, locks or semaphores are used to achieve this, while at the hardware level, a cache coherency protocol maybe used. This makes it appear to the user that the entire operation occurred in a single instruction.

Sshanbh: /* Eventual consistency */

2012-04-05T08:40:11Z

Eventual consistency

← Older revision		Revision as of 08:40, 5 April 2012
Line 60:		Line 60:
	* After an exclusive mode access to a synchronization variable has been performed, any other process next nonexclusive mode access to that synchronization variable may not be performed until it has performed with respect to that variable's owner.		* After an exclusive mode access to a synchronization variable has been performed, any other process next nonexclusive mode access to that synchronization variable may not be performed until it has performed with respect to that variable's owner.

	=== Eventual consistency ===		=== Eventual consistency <ref>http://en.wikipedia.org/wiki/Eventual_consistency</ref>===

	Given a sufficiently long period of time over which no changes are sent, all updates can be expected to propagate eventually through the system. Thus, all the replicas will be consistent. As the consistency achieved is eventual, the possibility of conflicts is high. The conflicts have to be resolved. There are three types of resolution:		Given a sufficiently long period of time over which no changes are sent, all updates can be expected to propagate eventually through the system. Thus, all the replicas will be consistent. As the consistency achieved is eventual, the possibility of conflicts is high. The conflicts have to be resolved. There are three types of resolution:

Sshanbh: /* Entry consistency */

2012-04-05T08:38:27Z

Entry consistency

← Older revision		Revision as of 08:38, 5 April 2012
Line 50:		Line 50:
	The delta consistency model states that after a fixed time period δ, an update is propagated through the system and all replicas will be consistent. In other words, barring a short bounded interval after a modification, the result of any read operation is consistent with a read on the original copy of an object. If an object is modified, the read will not be consistent during the short period of time following its modification. Once the fixed time period elapses, the modification is propagated and the read is now consistent.		The delta consistency model states that after a fixed time period δ, an update is propagated through the system and all replicas will be consistent. In other words, barring a short bounded interval after a modification, the result of any read operation is consistent with a read on the original copy of an object. If an object is modified, the read will not be consistent during the short period of time following its modification. Once the fixed time period elapses, the modification is propagated and the read is now consistent.

	=== Entry consistency ===		=== Entry consistency <ref>http://cs.gmu.edu/cne/modules/dsm/orange/entry_con.html</ref>===

	This consistency model has been designed to be used with critical sections. Here, the programmer needs to use acquire and release at the start and end of each [http://en.wikipedia.org/wiki/Critical_section critical section] just like in both variants of [http://en.wikipedia.org/wiki/Release_consistency release consistency]. However it also required every ordinary shared variable to be associated with a synchronization variable such as a lock or a barrier. If the elements of an array need to be accessed independently in parallel, then each element of the array must be associated with a lock. When an acquire is done on a synchronization variable, only those ordinary shared variables guarded by that synchronization variable are made consistent. Release consistency does not associate shared variables with locks or barriers and at acquire time has to determine empirically which variables it needs. This is where entry consistency differs from release consistency.		This consistency model has been designed to be used with critical sections. Here, the programmer needs to use acquire and release at the start and end of each [http://en.wikipedia.org/wiki/Critical_section critical section] just like in both variants of [http://en.wikipedia.org/wiki/Release_consistency release consistency]. However it also required every ordinary shared variable to be associated with a synchronization variable such as a lock or a barrier. If the elements of an array need to be accessed independently in parallel, then each element of the array must be associated with a lock. When an acquire is done on a synchronization variable, only those ordinary shared variables guarded by that synchronization variable are made consistent. Release consistency does not associate shared variables with locks or barriers and at acquire time has to determine empirically which variables it needs. This is where entry consistency differs from release consistency.

Sshanbh: /* Delta consistency */

2012-04-05T08:36:43Z

Delta consistency

← Older revision		Revision as of 08:36, 5 April 2012
Line 46:		Line 46:
	The example shown here is a legal execution history under CC but not under SC. Note that W(x)1 and W(x)2 are causally related as P2 observed the first write by P1. Furthermore, P3 and P4 observe the accesses W(x)2 and W(x)3 in different orders, which would not be legal in SC.		The example shown here is a legal execution history under CC but not under SC. Note that W(x)1 and W(x)2 are causally related as P2 observed the first write by P1. Furthermore, P3 and P4 observe the accesses W(x)2 and W(x)3 in different orders, which would not be legal in SC.

	=== Delta consistency ===		=== Delta consistency <ref>http://en.wikipedia.org/wiki/Delta_consistency</ref>===

	The delta consistency model states that after a fixed time period δ, an update is propagated through the system and all replicas will be consistent. In other words, barring a short bounded interval after a modification, the result of any read operation is consistent with a read on the original copy of an object. If an object is modified, the read will not be consistent during the short period of time following its modification. Once the fixed time period elapses, the modification is propagated and the read is now consistent.		The delta consistency model states that after a fixed time period δ, an update is propagated through the system and all replicas will be consistent. In other words, barring a short bounded interval after a modification, the result of any read operation is consistent with a read on the original copy of an object. If an object is modified, the read will not be consistent during the short period of time following its modification. Once the fixed time period elapses, the modification is propagated and the read is now consistent.

Sshanbh: /* Address translation aware memory consistency */

2012-04-05T08:32:52Z

Address translation aware memory consistency

← Older revision		Revision as of 08:32, 5 April 2012
Line 17:		Line 17:
	== Consistency models used ==		== Consistency models used ==

	=== Address translation aware memory consistency ===		=== Address translation aware memory consistency <ref>http://people.ee.duke.edu/~sorin/papers/ieeemicro11_toppick.pdf</ref> ===

	These memory consistency models define the behavior of operations (loads, stores, memory barriers, etc.) on physical addresses and virtual addresses. The two important levels of memory consistency that can be classified as address translation aware are described below:		These memory consistency models define the behavior of operations (loads, stores, memory barriers, etc.) on physical addresses and virtual addresses. The two important levels of memory consistency that can be classified as address translation aware are described below:

Sshanbh: /* Entry consistency */

2012-04-05T07:51:13Z

Entry consistency

← Older revision		Revision as of 07:51, 5 April 2012
Line 52:		Line 52:
	=== Entry consistency ===		=== Entry consistency ===

	This consistency model has been designed to be used with critical sections. Here, the programmer needs to use acquire and release at the start and end of each critical section just like in both variants of release consistency. However it also required every ordinary shared variable to be associated with a synchronization variable such as a lock or a barrier. If the elements of an array need to be accessed independently in parallel, then each element of the array must be associated with a lock. When an acquire is done on a synchronization variable, only those ordinary shared variables guarded by that synchronization variable are made consistent. Release consistency does not associate shared variables with locks or barriers and at acquire time has to determine empirically which variables it needs. This is where entry consistency differs from release consistency.		This consistency model has been designed to be used with critical sections. Here, the programmer needs to use acquire and release at the start and end of each [http://en.wikipedia.org/wiki/Critical_section critical section] just like in both variants of [http://en.wikipedia.org/wiki/Release_consistency release consistency]. However it also required every ordinary shared variable to be associated with a synchronization variable such as a lock or a barrier. If the elements of an array need to be accessed independently in parallel, then each element of the array must be associated with a lock. When an acquire is done on a synchronization variable, only those ordinary shared variables guarded by that synchronization variable are made consistent. Release consistency does not associate shared variables with locks or barriers and at acquire time has to determine empirically which variables it needs. This is where entry consistency differs from release consistency.

	Formally, a memory exhibits entry consistency if the following conditions are met:		Formally, a memory exhibits entry consistency if the following conditions are met: