CSC/ECE 506 Spring 2011/ch11 BB EP - Revision history

Beburrou: /* Solihin 11.4 Resolution */

2011-04-23T20:40:41Z

Solihin 11.4 Resolution

← Older revision		Revision as of 20:40, 23 April 2011
Line 141:		Line 141:
	# ''A'' still hasn't received the response from ''Home'', so it is still in a transaction, and it tells ''B'' that it is busy. ''B'' will have to retry the request.		# ''A'' still hasn't received the response from ''Home'', so it is still in a transaction, and it tells ''B'' that it is busy. ''B'' will have to retry the request.

	It should be noted that ''B'' will be in the ''PENDING''<sup><span class = "plainlinks">[[#Definitions_and_Terms\|[~~def~~]]]</span></sup> state, so any requests to demote it from the ''Head'' position will be delayed.. This could lead to a chaining of nodes in the ''PENDING'' state, but as soon as node ''A'' receives its response from ''Home'' or times out, the requests in the chain will be successively accepted and processed.		It should be noted that ''B'' will be in the ''PENDING''<sup><span class = "plainlinks">[[#Definitions_and_Terms\|[definitions]]]</span></sup> state, so any requests to demote it from the ''Head'' position will be delayed.. This could lead to a chaining of nodes in the ''PENDING'' state, but as soon as node ''A'' receives its response from ''Home'' or times out, the requests in the chain will be successively accepted and processed.

	=== Other Possible Race Conditions ===		=== Other Possible Race Conditions ===

Beburrou: /* Concurrent List Deletions */

2011-04-19T03:53:53Z

Concurrent List Deletions

← Older revision		Revision as of 03:53, 19 April 2011
Line 147:		Line 147:

	==== Concurrent List Deletions ====		==== Concurrent List Deletions ====
	Even though the ''Head'' node performs most of the coherence actions for a shard list, the individual nodes are able to invalidate themselves, such as when they evict the block from their cache. This is referred to in the SCI standard as a "deletion" from the sharing list. Deletion is accomplished by having the invalidating node "lock" itself and then inform its forward and back nodes that they should now point to each other. This "locking" is essentially another ''PENDING'' state. A problem could arise, then, when two neighboring nodes try to invalidate themselves at the same time, as they would both be locked and not respond to each other's message. In this case, though, the protocol specifies that the node that is closest to the tail takes priority. So, the deadlock and/or race condition is averted by ordering the deletion from the tail towards the head.		Even though the ''Head'' node performs most of the coherence actions for a shard list, the individual nodes are able to invalidate themselves, such as when they evict the block from their cache. This is referred to in the SCI standard as a "deletion" from the sharing list. Deletion is accomplished by having the invalidating node "lock" itself and then inform its forward and back nodes that they should now point to each other. This "locking" is essentially another ''PENDING'' state. A problem could arise, then, when two neighboring nodes try to invalidate themselves at the same time, as they would both be locked and not respond to each other's message. In this case, though, the protocol specifies that the node that is closest to the tail takes priority (IEEE pg156)<sup><span id="1body">[[#1foot\|[1]]]</span></sup>. So, the deadlock and/or race condition is averted by ordering the deletion from the tail towards the head.

	==== Simultaneous Deletion and Invalidation ====		==== Simultaneous Deletion and Invalidation ====

Beburrou: /* Simultaneous Deletion and Invalidation */

2011-04-19T03:50:53Z

Simultaneous Deletion and Invalidation

← Older revision		Revision as of 03:50, 19 April 2011
Line 155:		Line 155:
	The second option is more difficult. If the ''Head'' node's message arrives first, node ''A'' will be invalidated, so that when the message from node ''B'' is sent again, node ''A'' will simply inform node ''B'' that it is no longer part of the list. As well, the ''Head'' node will now have its forward pointer pointing at node ''B''. Node ''A'' has thus been successfully purged, but we arrive at an impasse, as now the ''Head'' node will try to invalidate the locked node ''B'', while node ''B'' will try to tell the ''Head'' node to change its forward pointer, with both nodes being inside a transaction. This situation is illustrated by the following figure.		The second option is more difficult. If the ''Head'' node's message arrives first, node ''A'' will be invalidated, so that when the message from node ''B'' is sent again, node ''A'' will simply inform node ''B'' that it is no longer part of the list. As well, the ''Head'' node will now have its forward pointer pointing at node ''B''. Node ''A'' has thus been successfully purged, but we arrive at an impasse, as now the ''Head'' node will try to invalidate the locked node ''B'', while node ''B'' will try to tell the ''Head'' node to change its forward pointer, with both nodes being inside a transaction. This situation is illustrated by the following figure.
	[[Image:PurgeDelete2.png\|center]]		[[Image:PurgeDelete2.png\|center]]
	The protocol does not specify how to handle this situation, but it would make sense for the protocol to allow one of the messages through, presumably the ''Head'' node's message. Node ''B'' could simply respond in the affirmative, telling the ''Head'' node what the following node is, but this would only work if node ''B'' notifies the next node of the deletion after it notifies node ''A''. Otherwise, the node following ''B'' would have its back pointer pointing to the wrong node. The protocol standard seems to suggest that this is the case (IEEE, pg162).		The protocol does not specify how to handle this situation, but it would make sense for the protocol to allow one of the messages through, presumably the ''Head'' node's message. Node ''B'' could simply respond in the affirmative, telling the ''Head'' node what the following node is, but this would only work if node ''B'' notifies the next node of the deletion after it notifies node ''A''. Otherwise, the node following ''B'' would have its back pointer pointing to the wrong node. The protocol standard seems to suggest that this is the case (IEEE, pg162)<sup><span id="1body">[[#1foot\|[1]]]</span></sup>.

	== Definitions and Terms ==		== Definitions and Terms ==

Beburrou: /* Simultaneous Deletion and Invalidation */

2011-04-19T03:49:30Z

Simultaneous Deletion and Invalidation

← Older revision		Revision as of 03:49, 19 April 2011
Line 150:		Line 150:

	==== Simultaneous Deletion and Invalidation ====		==== Simultaneous Deletion and Invalidation ====
			Another potential race condition occurs when the ''Head'' node tries to purge the list of sharers at the same time as a node in the list tries to remove itself from the list. Suppose that the ''Head'' node is trying to purge node ''A'', which has node ''B'' as its next node in the list, while at the same time, node ''B'' is trying to remove itself from the list. Node ''B'' needs to tell node ''A'' to update its next pointer, but the ''Head'' node will need to access node ''A'''s next pointer to know what the next node in the list is. An illustration is shown below. The ''1'' and the ''2'' represent the messages being sent from the respective node to node ''A'' that have not yet arrived.
			[[Image:PurgeDelete.png\|center]]
			What will happen is that one of the messages will reach node ''A'' first. While ''A'' is responding to this message, it will tell other nodes that it is busy, in a similar manner to the notion of the atomic transactions. If node ''B'''s message arrives first, causing the message from the ''Head'' node to be rejected. Node ''A'' will have its forward pointer changed at this point, so when the ''Head'' node resends its request, all will work as expected.
			The second option is more difficult. If the ''Head'' node's message arrives first, node ''A'' will be invalidated, so that when the message from node ''B'' is sent again, node ''A'' will simply inform node ''B'' that it is no longer part of the list. As well, the ''Head'' node will now have its forward pointer pointing at node ''B''. Node ''A'' has thus been successfully purged, but we arrive at an impasse, as now the ''Head'' node will try to invalidate the locked node ''B'', while node ''B'' will try to tell the ''Head'' node to change its forward pointer, with both nodes being inside a transaction. This situation is illustrated by the following figure.
			[[Image:PurgeDelete2.png\|center]]
			The protocol does not specify how to handle this situation, but it would make sense for the protocol to allow one of the messages through, presumably the ''Head'' node's message. Node ''B'' could simply respond in the affirmative, telling the ''Head'' node what the following node is, but this would only work if node ''B'' notifies the next node of the deletion after it notifies node ''A''. Otherwise, the node following ''B'' would have its back pointer pointing to the wrong node. The protocol standard seems to suggest that this is the case (IEEE, pg162).

	== Definitions and Terms ==		== Definitions and Terms ==

Beburrou: /* Concurrent List Deletions */

2011-04-19T02:06:03Z

Concurrent List Deletions

← Older revision		Revision as of 02:06, 19 April 2011
Line 147:		Line 147:

	==== Concurrent List Deletions ====		==== Concurrent List Deletions ====
			Even though the ''Head'' node performs most of the coherence actions for a shard list, the individual nodes are able to invalidate themselves, such as when they evict the block from their cache. This is referred to in the SCI standard as a "deletion" from the sharing list. Deletion is accomplished by having the invalidating node "lock" itself and then inform its forward and back nodes that they should now point to each other. This "locking" is essentially another ''PENDING'' state. A problem could arise, then, when two neighboring nodes try to invalidate themselves at the same time, as they would both be locked and not respond to each other's message. In this case, though, the protocol specifies that the node that is closest to the tail takes priority. So, the deadlock and/or race condition is averted by ordering the deletion from the tail towards the head.

	==== Simultaneous Deletion and Invalidation ====		==== Simultaneous Deletion and Invalidation ====

Beburrou: /* Simultaneous Deletion and Invalidation */

2011-04-19T02:05:55Z

Simultaneous Deletion and Invalidation

← Older revision		Revision as of 02:05, 19 April 2011
Line 150:		Line 150:

	==== Simultaneous Deletion and Invalidation ====		==== Simultaneous Deletion and Invalidation ====
	Even though the ''Head'' node performs most of the coherence actions for a shard list, the individual nodes are able to invalidate themselves, such as when they evict the block from their cache. This is referred to in the SCI standard as a "deletion" from the sharing list. Deletion is accomplished by having the invalidating node "lock" itself and then inform its forward and back nodes that they should now point to each other. This "locking" is essentially another ''PENDING'' state. A problem could arise, then, when two neighboring nodes try to invalidate themselves at the same time, as they would both be locked and not respond to each other's message. In this case, though, the protocol specifies that the node that is closest to the tail takes priority. So, the deadlock and/or race condition is averted by ordering the deletion from the tail towards the head.

	== Definitions and Terms ==		== Definitions and Terms ==

Eapotter at 01:48, 19 April 2011

2011-04-19T01:48:26Z

← Older revision		Revision as of 01:48, 19 April 2011
Line 3:		Line 3:


	(Unless otherwise noted, the contents of this article is derived from the IEEE standardization document titled "IEEE Standard for Scalable Coherent Interface (SCI)"<sup><span class = "plainlinks">[[#References\|[~~def~~]]]</span></sup> .)		(Unless otherwise noted, the contents of this article is derived from the IEEE standardization document titled "IEEE Standard for Scalable Coherent Interface (SCI)"<sup><span class = "plainlinks">[[#References\|[1]]]</span></sup> .)

	== Background ==		== Background ==

Eapotter at 01:48, 19 April 2011

2011-04-19T01:48:10Z

← Older revision		Revision as of 01:48, 19 April 2011
Line 3:		Line 3:


	(Unless otherwise noted, the contents of this article is derived from the IEEE standardization document titled "IEEE Standard for Scalable Coherent Interface (SCI)".)		(Unless otherwise noted, the contents of this article is derived from the IEEE standardization document titled "IEEE Standard for Scalable Coherent Interface (SCI)"<sup><span class = "plainlinks">[[#References\|[def]]]</span></sup> .)

	== Background ==		== Background ==

Eapotter: /* Background */

2011-04-19T01:45:57Z

Background

← Older revision		Revision as of 01:45, 19 April 2011
Line 2:		Line 2:



			(Unless otherwise noted, the contents of this article is derived from the IEEE standardization document titled "IEEE Standard for Scalable Coherent Interface (SCI)".)

	== Background ==		== Background ==

Eapotter: /* Memory States */

2011-04-19T01:40:25Z

Memory States

← Older revision		Revision as of 01:40, 19 April 2011
Line 53:		Line 53:
	\|}		\|}

	Below is a state diagram that depicts the transition between these states:
			These states are used by the coherency model to determine the state of the cache line when memory transactions are performed by individual processors. Likewise, these memory states are impacted when these memory transactions occur.

			Below is a state diagram that depicts the transition between these memory states: