CSC/ECE 506 Spring 2011/ch11 sw - Revision history

Sseshad: /* SCI protocol solution to the Race Condition */

2011-04-24T01:33:21Z

SCI protocol solution to the Race Condition

← Older revision		Revision as of 01:33, 24 April 2011
Line 196:		Line 196:
	[[Image: RACE2.jpg\|center\|frame]]		[[Image: RACE2.jpg\|center\|frame]]

	In this diagram, both X and Y send a request to Home for access to the memory block (indicated by 1 and 2). Suppose Y's request reaches first. Then, Y goes into a busy state and waits for a response. Home responds to Y with the data which is delayed (indicated by 3). Also, Home responds to the request from X and informs it that Y is the current Head node (indicated by 4). X then sends a request to Y to demote itself ~~9indicated~~ by 5). Since Y still hasn't received the response from Home, and is in a transaction, it tells X that it is busy. X will have to retry the request.		In this diagram, both X and Y send a request to Home for access to the memory block (indicated by 1 and 2). Suppose Y's request reaches first. Then, Y goes into a busy state and waits for a response. Home responds to Y with the data which is delayed (indicated by 3). Also, Home responds to the request from X and informs it that Y is the current Head node (indicated by 4). X then sends a request to Y to demote itself (indicated by 5). Since Y still hasn't received the response from Home, and is in a transaction, it tells X that it is busy (indicated by 6). X will have to retry the request.

			In this way, SCI protocol avoids race conditions. Also, the use of ''PENDING'' state and ''purging'' avoid race conditions arising in case of simultaneous deletion and invalidation or concurrent deletions on a list etc.

	== References ==		== References ==

Sseshad: /* SCI protocol solution to the Race Condition */

2011-04-24T01:29:06Z

SCI protocol solution to the Race Condition

← Older revision		Revision as of 01:29, 24 April 2011
Line 195:		Line 195:

	[[Image: RACE2.jpg\|center\|frame]]		[[Image: RACE2.jpg\|center\|frame]]

			In this diagram, both X and Y send a request to Home for access to the memory block (indicated by 1 and 2). Suppose Y's request reaches first. Then, Y goes into a busy state and waits for a response. Home responds to Y with the data which is delayed (indicated by 3). Also, Home responds to the request from X and informs it that Y is the current Head node (indicated by 4). X then sends a request to Y to demote itself 9indicated by 5). Since Y still hasn't received the response from Home, and is in a transaction, it tells X that it is busy. X will have to retry the request.

	== References ==		== References ==

Sseshad: /* SCI protocol solution to the Race Condition */

2011-04-24T01:20:36Z

SCI protocol solution to the Race Condition

← Older revision		Revision as of 01:20, 24 April 2011
Line 191:		Line 191:

	=== SCI protocol solution to the Race Condition ===		=== SCI protocol solution to the Race Condition ===

			The following picture depicts how the early invalidation situation mentioned above is prevented in SCI protocol:

			[[Image: RACE2.jpg\|center\|frame]]

	== References ==		== References ==

Sseshad: /* How race conditions are prevented */

2011-04-24T01:07:18Z

How race conditions are prevented

← Older revision		Revision as of 01:07, 24 April 2011
Line 180:		Line 180:
	A transaction is a set or sequence of sub-actions necessary to complete some requested action. For instance, querying memory for a data or invalidation message can be treated as transactions. Transactions are primarily a request-response pair, where one node acts as the initiating node by sending a request to another node and waiting for the response. The transaction is said to be complete when the response returns.		A transaction is a set or sequence of sub-actions necessary to complete some requested action. For instance, querying memory for a data or invalidation message can be treated as transactions. Transactions are primarily a request-response pair, where one node acts as the initiating node by sending a request to another node and waiting for the response. The transaction is said to be complete when the response returns.

	[[http://en.wikipedia.org/wiki/Atomicity_%28programming%29 Atomic transactions]] proceed continuously between the request and the response and should be uninterrupted. So, for example, if node ''X'' is in the middle of a transaction with node ''Y'' and node ''Z'' tries to make a request to node ''X'', node ''X'' should respond to node ''Z'' that it is busy, telling node ''Z'' to try again.		[http://en.wikipedia.org/wiki/Atomicity_%28programming%29 Atomic transactions] proceed continuously between the request and the response and should be uninterrupted. So, for example, if node ''X'' is in the middle of a transaction with node ''Y'' and node ''Z'' tries to make a request to node ''X'', node ''X'' should respond to node ''Z'' that it is busy, telling node ''Z'' to try again.

	* '''Head Node'''		* '''Head Node'''
Line 187:		Line 187:
	* '''Access to Memory'''		* '''Access to Memory'''
	The ''Home'' node is modified in SCI to avoid race conditions. Here, ''Home'' node is only responsible for keeping track of who the current ''Head''. The memory block physically resides in the ''Home'' node. This requirement thus, serializes the order of access, as the ''Home'' node services a new request only after the previous request is finished, and the requests are processed in FIFO order. Also, the ''Head'' node of the sharing list is notified by the new ''Head'' when it is demoted. In this way, all nodes involved in a potential race are thus communicating with each other. This prevents the occurrence of the race condition itself.		The ''Home'' node is modified in SCI to avoid race conditions. Here, ''Home'' node is only responsible for keeping track of who the current ''Head''. The memory block physically resides in the ''Home'' node. This requirement thus, serializes the order of access, as the ''Home'' node services a new request only after the previous request is finished, and the requests are processed in FIFO order. Also, the ''Head'' node of the sharing list is notified by the new ''Head'' when it is demoted. In this way, all nodes involved in a potential race are thus communicating with each other. This prevents the occurrence of the race condition itself.

			Consider the early invalidation example mentioned in the previous section. The atomic transactions property of the SCI protocol would prevent node Y from invalidating node X, as node X will be in the middle of a transaction, after requesting a block of data from memory and waiting for a response. Also, due of the memory access condition, when the Head node is in FRESH state and wants to write while another node wants to read, cannot hold good. This situation is avoided since both nodes must make their request to the Home node. The Head node must in turn request the ability to write, and the other node will have to request the data from the Home node. Either of the requests will reach the Home node first and the other request will thus, be deferred.

			=== SCI protocol solution to the Race Condition ===

	== References ==		== References ==

Sseshad: /* How race conditions are prevented */

2011-04-24T00:38:44Z

How race conditions are prevented

← Older revision		Revision as of 00:38, 24 April 2011
Line 174:		Line 174:

	=== How race conditions are prevented ===		=== How race conditions are prevented ===

			SCI prevents race conditions based on the following three policies:

			* '''Atomic transactions'''
			A transaction is a set or sequence of sub-actions necessary to complete some requested action. For instance, querying memory for a data or invalidation message can be treated as transactions. Transactions are primarily a request-response pair, where one node acts as the initiating node by sending a request to another node and waiting for the response. The transaction is said to be complete when the response returns.

			[[http://en.wikipedia.org/wiki/Atomicity_%28programming%29 Atomic transactions]] proceed continuously between the request and the response and should be uninterrupted. So, for example, if node ''X'' is in the middle of a transaction with node ''Y'' and node ''Z'' tries to make a request to node ''X'', node ''X'' should respond to node ''Z'' that it is busy, telling node ''Z'' to try again.

			* '''Head Node'''
			SCI makes the ''Head'' node of a sharing list perform most of the coherence actions so that only one node is performing actions such as writes and invalidation of other sharers. The possibility of concurrent actions is thus decreased. When another node wishes to write, it can do so by becoming the Head Node of the sharing list for the cache line.

			* '''Access to Memory'''
			The ''Home'' node is modified in SCI to avoid race conditions. Here, ''Home'' node is only responsible for keeping track of who the current ''Head''. The memory block physically resides in the ''Home'' node. This requirement thus, serializes the order of access, as the ''Home'' node services a new request only after the previous request is finished, and the requests are processed in FIFO order. Also, the ''Head'' node of the sharing list is notified by the new ''Head'' when it is demoted. In this way, all nodes involved in a potential race are thus communicating with each other. This prevents the occurrence of the race condition itself.

	== References ==		== References ==

Sseshad: /* Handling Overlapped Processing of Requests */

2011-04-23T21:39:41Z

Handling Overlapped Processing of Requests

← Older revision		Revision as of 21:39, 23 April 2011
Line 163:		Line 163:

	[[Image: race1.jpg\|center\|frame]]		[[Image: race1.jpg\|center\|frame]]

			The following is the sequence of actions taking place:

			* Step 1: ''A'' sends a read request to ''Home''
			* Step 2: ''Home'' sends the reply (ReplyD) to ''A'' which is delayed.
			* Step 3: ''B'' sends a read exclusive request to ''Home''
			* Step 4: ''Home'' sends an invalidation message to ''A'' thinking ''A'' has cached the block. This request reaches ''A'' sooner than ReplyD.

			Thus, ''A'' and directory see different sequence of requests and so, ''A'' doesn't know how to respond to the invalidation message. SCI protocol is designed to combat such situations and its possible to avoid race conditions in SCI. The following section describes how SCI prevents race conditions.

			=== How race conditions are prevented ===

	== References ==		== References ==

Sseshad: /* Handling Overlapped Processing of Requests */

2011-04-23T20:43:05Z

Handling Overlapped Processing of Requests

← Older revision		Revision as of 20:43, 23 April 2011
Line 160:		Line 160:
	=== Handling Overlapped Processing of Requests ===		=== Handling Overlapped Processing of Requests ===

			Figure 11.8 in Solihin depicts an example of race condition occurring due to early invalidation. The figure is redrawn here to explain the situation:

			[[Image: race1.jpg\|center\|frame]]

	== References ==		== References ==

Sseshad: /* References */

2011-04-23T19:59:23Z

References

← Older revision		Revision as of 19:59, 23 April 2011
Line 149:		Line 149:

	Similar to SCI, there is a distributed directory protocol as well. It is known as '''''Scalable Distributed Directory''''' (SDD) protocol.		Similar to SCI, there is a distributed directory protocol as well. It is known as '''''Scalable Distributed Directory''''' (SDD) protocol.

			== Race conditions ==

			[http://en.wikipedia.org/wiki/Race_condition Race condition] is an undesirable situation that arises when two or more processes or devices try to manipulate the same shared data variable and the output is dependent on the sequence of operations that are carried out on this variable. Race conditions are likely in multi-threaded or distributed programs. Thus, in a DSM which lacks serialization of actions and is prone to network errors and congestion issues, race conditions are inevitable. Thus, it is the responsibility of the cache coherence protocol to avoid such race conditions.

			Section 11.4.1 in Solihin discusses race conditions occurring due to out-of-sync directory states. This occurs due to the directory having an inconsistent view of the cache states since updating doesn't happen in a lock step. The cache coherence protocol handles such situations by splitting the EM state as mentioned on page 340 in Solihin book. Thus, with a few modifications in the protocol at the directory and every node's cache coherence controller was enough to handle the race conditions and the out-of-sync view of cache states at the directory.

			But handling races arising due to non-instantaneous processing of requests is not this simple. Section 11.4.2 discusses a few scenarios. The following section shows how SCI solves this problem.

			=== Handling Overlapped Processing of Requests ===


	== References ==		== References ==

Sseshad: /* State Diagram */

2011-04-23T08:37:21Z

State Diagram

← Older revision		Revision as of 08:37, 23 April 2011
Line 112:		Line 112:
	Based on the states mentioned in the previous section, the state diagrams for the SCI protocol are as follows:		Based on the states mentioned in the previous section, the state diagrams for the SCI protocol are as follows:

	[[Image: MEM.jpg\|center\|frame\|Memory ~~States~~ Diagram]]		[[Image: MEM.jpg\|center\|frame\|Memory State Diagram]]

			The cache-line state diagram is as shown below:

			[[Image: CACHE.jpg\|center\|frame\|Cache Line State Diagram]]

			In the above diagram, the first value indicates the request to the directory by a node for memory access and the value in the parenthesis indicates the memory state at the time of the request.

	=== Examples of line sharing in SCI ===		=== Examples of line sharing in SCI ===

Sseshad: /* State Diagram */

2011-04-23T07:49:16Z

State Diagram

← Older revision		Revision as of 07:49, 23 April 2011
Line 112:		Line 112:
	Based on the states mentioned in the previous section, the state diagrams for the SCI protocol are as follows:		Based on the states mentioned in the previous section, the state diagrams for the SCI protocol are as follows:

	[[		[[Image: MEM.jpg\|center\|frame\|Memory States Diagram]]

	=== Examples of line sharing in SCI ===		=== Examples of line sharing in SCI ===