CSC 456 Spring 2012/ch7 AA - Revision history

Alhamann: /* References */

2012-03-30T13:59:23Z

References

← Older revision		Revision as of 13:59, 30 March 2012
Line 102:		Line 102:
	== References ==		== References ==

	[1] ~~Sarita V. Adve. Kourosh Gharachorloo~~. "~~Shared Memory. Consistency Models~~: ~~A Tutorial~~." ~~Digital Western Research Laboratory 250 University Avenue Palo Alto. <http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7~~.~~pdf>~~		[1] Yan Solihin. "Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems." Solihin Publishing & Consulting LLC, 2009.

	[2] ~~Yan Solihin~~. "~~Fundamentals of Parallel Computer Architecture~~: ~~Multichip and Multicore Systems~~." ~~Solihin Publishing & Consulting LLC, 2009~~.		[2] Sarita V. Adve. Kourosh Gharachorloo. "Shared Memory. Consistency Models: A Tutorial." Digital Western Research Laboratory 250 University Avenue Palo Alto. <http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf>

	[3] Kai Li, and Paul Hudak. "Memory coherence in shared virtual memory systems". Published in Journal ACM Transactions on Computer Systems (TOCS), Volume 7 Issue 4, Nov. 1989 <http://dl.acm.org.prox.lib.ncsu.edu/citation.cfm?id=75104.75105&coll=DL&dl=GUIDE&CFID=251927&CFTOKEN=71004880>.		[3] Kai Li, and Paul Hudak. "Memory coherence in shared virtual memory systems". Published in Journal ACM Transactions on Computer Systems (TOCS), Volume 7 Issue 4, Nov. 1989 <http://dl.acm.org.prox.lib.ncsu.edu/citation.cfm?id=75104.75105&coll=DL&dl=GUIDE&CFID=251927&CFTOKEN=71004880>.

Alhamann: /* Memory Semantics in Uniprocessor Systems */

2012-03-30T13:58:50Z

Memory Semantics in Uniprocessor Systems

← Older revision		Revision as of 13:58, 30 March 2012
Line 61:		Line 61:
	=== Memory Semantics in Uniprocessor Systems ===		=== Memory Semantics in Uniprocessor Systems ===

	Uniprocessor languages use simple sequential semantics for memory operations, which allow the programmer to assume that all memory operations will occur one at a time in the sequential order speciﬁed by the program. Thus, the programmer can expect a read to return the value of the most recent write to the location according to sequential program order. It is sufﬁcient to only maintain uniprocessor data and control dependences. The compiler and hardware can freely reorder operations to different locations if the uniprocessor data and control dependences are respected. This enables compiler optimizations such as register allocation, code motion, and loop transformations, and hardware optimizations, such as pipelining, multiple issue, write buffer bypassing and forwarding, and lockup-free caches, all of which lead to overlapping and reordering of memory operations. [1]		Uniprocessor languages use simple sequential semantics for memory operations, which allow the programmer to assume that all memory operations will occur one at a time in the sequential order speciﬁed by the program. Thus, the programmer can expect a read to return the value of the most recent write to the location according to sequential program order. It is sufﬁcient to only maintain uniprocessor data and control dependences. The compiler and hardware can freely reorder operations to different locations if the uniprocessor data and control dependences are respected. This enables compiler optimizations such as register allocation, code motion, and loop transformations, and hardware optimizations, such as pipelining, multiple issue, write buffer bypassing and forwarding, and lockup-free caches, all of which lead to overlapping and reordering of memory operations. [2]

	=== Memory Semantics in Multiprocessor Systems ===		=== Memory Semantics in Multiprocessor Systems ===

Alhamann: /* Memory Consistency */

2012-03-30T13:58:41Z

Memory Consistency

← Older revision		Revision as of 13:58, 30 March 2012
Line 46:		Line 46:

	==Memory Consistency==		==Memory Consistency==
	''Memory consistency'' deals with the ordering of all memory operations - loads and stores - to different memory locations. It can also be present in systems without caches. The code below from Solihin [2] shows an example of possible inconsistency:		''Memory consistency'' deals with the ordering of all memory operations - loads and stores - to different memory locations. It can also be present in systems without caches. The code below from Solihin [1] shows an example of possible inconsistency:

	<pre>		<pre>

Alhamann: /* Memory Consistency */

2012-03-30T13:58:12Z

Memory Consistency

← Older revision		Revision as of 13:58, 30 March 2012
Line 46:		Line 46:

	==Memory Consistency==		==Memory Consistency==
	''Memory consistency'' deals with the ordering of all memory operations - loads and stores - to different memory locations. It can also be present in systems without caches. The code below from Solihin [2]shows an example of possible inconsistency:		''Memory consistency'' deals with the ordering of all memory operations - loads and stores - to different memory locations. It can also be present in systems without caches. The code below from Solihin [2] shows an example of possible inconsistency:

	<pre>		<pre>

Alhamann: /* Memory Consistency */

2012-03-30T13:57:56Z

Memory Consistency

← Older revision		Revision as of 13:57, 30 March 2012
Line 46:		Line 46:

	==Memory Consistency==		==Memory Consistency==
	''Memory consistency'' deals with the ordering of all memory operations - loads and stores - to different memory locations. It can also be present in systems without caches. The code below from Solihin shows an example of possible inconsistency:		''Memory consistency'' deals with the ordering of all memory operations - loads and stores - to different memory locations. It can also be present in systems without caches. The code below from Solihin [2]shows an example of possible inconsistency:

	<pre>		<pre>

Alhamann: /* Memory Coherence and Shared Virtual Memory */

2012-03-30T13:54:21Z

Memory Coherence and Shared Virtual Memory

← Older revision		Revision as of 13:54, 30 March 2012
Line 83:		Line 83:
	== Memory Coherence and Shared Virtual Memory ==		== Memory Coherence and Shared Virtual Memory ==

	The memory coherence problem in a shared virtual memory system and in multicache systems are different. In a multicache multiprocessor, there are processors sharing a physical memory through their private caches. The relatively small size of a cache and the fast bus connection to the shared memory, enables using a sophisticated coherence protocol for the multicache hardware such that the time delay of conflicting writes to a memory location is small. [2]		The memory coherence problem in a shared virtual memory system and in multicache systems are different. In a multicache multiprocessor, there are processors sharing a physical memory through their private caches. The relatively small size of a cache and the fast bus connection to the shared memory, enables using a sophisticated coherence protocol for the multicache hardware such that the time delay of conflicting writes to a memory location is small. [3]

	In contrast, in a shared virtual memory system on a loosely coupled multiprocessor which has no physical shared memory (with a nontrivial communication cost between processors), conflicts are not likely to be solved with negligible delay. These conflicts resemble a “page fault” in a traditional virtual memory system. Thus, there are two design choices that greatly influence the implementation of a shared virtual memory: the granularity of the memory units (i.e., the “page size”) and the strategy for maintaining coherence.		In contrast, in a shared virtual memory system on a loosely coupled multiprocessor which has no physical shared memory (with a nontrivial communication cost between processors), conflicts are not likely to be solved with negligible delay. These conflicts resemble a “page fault” in a traditional virtual memory system. Thus, there are two design choices that greatly influence the implementation of a shared virtual memory: the granularity of the memory units (i.e., the “page size”) and the strategy for maintaining coherence.

Alhamann: /* References */

2012-03-30T13:53:12Z

References

← Older revision		Revision as of 13:53, 30 March 2012
Line 104:		Line 104:
	[1] Sarita V. Adve. Kourosh Gharachorloo. "Shared Memory. Consistency Models: A Tutorial." Digital Western Research Laboratory 250 University Avenue Palo Alto. <http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf>		[1] Sarita V. Adve. Kourosh Gharachorloo. "Shared Memory. Consistency Models: A Tutorial." Digital Western Research Laboratory 250 University Avenue Palo Alto. <http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf>

	[2] Kai Li, and Paul Hudak. "Memory coherence in shared virtual memory systems". Published in Journal ACM Transactions on Computer Systems (TOCS), Volume 7 Issue 4, Nov. 1989 <http://dl.acm.org.prox.lib.ncsu.edu/citation.cfm?id=75104.75105&coll=DL&dl=GUIDE&CFID=251927&CFTOKEN=71004880>.		[2] Yan Solihin. "Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems." Solihin Publishing & Consulting LLC, 2009.

			[3] Kai Li, and Paul Hudak. "Memory coherence in shared virtual memory systems". Published in Journal ACM Transactions on Computer Systems (TOCS), Volume 7 Issue 4, Nov. 1989 <http://dl.acm.org.prox.lib.ncsu.edu/citation.cfm?id=75104.75105&coll=DL&dl=GUIDE&CFID=251927&CFTOKEN=71004880>.

Alhamann: /* References */

2012-03-30T13:41:43Z

References

← Older revision		Revision as of 13:41, 30 March 2012
Line 104:		Line 104:
	[1] Sarita V. Adve. Kourosh Gharachorloo. "Shared Memory. Consistency Models: A Tutorial." Digital Western Research Laboratory 250 University Avenue Palo Alto. <http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf>		[1] Sarita V. Adve. Kourosh Gharachorloo. "Shared Memory. Consistency Models: A Tutorial." Digital Western Research Laboratory 250 University Avenue Palo Alto. <http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf>

	[2] Kai Li, and Paul Hudak. "Memory coherence in shared virtual memory systems". Published in Journal ACM Transactions on Computer Systems (TOCS), Volume 7 Issue 4, Nov. 1989		[2] Kai Li, and Paul Hudak. "Memory coherence in shared virtual memory systems". Published in Journal ACM Transactions on Computer Systems (TOCS), Volume 7 Issue 4, Nov. 1989 <http://dl.acm.org.prox.lib.ncsu.edu/citation.cfm?id=75104.75105&coll=DL&dl=GUIDE&CFID=251927&CFTOKEN=71004880>.

Alhamann: /* Distributed Manager Algorithm */

2012-03-22T16:10:32Z

Distributed Manager Algorithm

← Older revision		Revision as of 16:10, 22 March 2012
Line 98:		Line 98:

	== Distributed Manager Algorithm ==		== Distributed Manager Algorithm ==
			In order to fix the possibe bottle-neck centralized manager algorithms may create, ''Distributed Manager Algorithms'' assigns tasks to various individual processors. There are several methods of assigning these tasks. In a ''Fixed'' Distributed Manager Algorithm, there is a predetermined set of pages for which each processor is responsible. In a ''Broadcast'' Distributed Manager Algorithm, page faults results in broadcast requests to the other processors. Due to the number of requests, the Broadcast Distributed Manager Algorithm does not scale well. In the case of the ''Dynamic'' Distributed Manager Algorithm, instead of using broadcasting requests to find page owners, each processor holds a page table that stores the owners for each page. Since the processors that own each page (page owners) are not static, each entry in a processor's page table is only a "hint," or a starting point for looking for the true owner.

	== References ==		== References ==

Amchu: /* Protocols */

2012-03-22T03:46:32Z

Protocols

← Older revision		Revision as of 03:46, 22 March 2012
Line 21:		Line 21:
	===Protocols===		===Protocols===

	~~The two basic methods to utilize the inter-core bus to notify other cores when~~ a ~~core~~ changes ~~something~~ in its cache ~~are~~ '''~~update~~''' ~~and~~ '''~~invalidate~~'''. In the update method, if variable 'x' is modified by core 1, core 1 has to send the updated value of 'x' onto the inter-core bus. Each cache listens to the inter-core bus and if a cache sees a variable on the bus which it has a copy of, it will read the updated value. This ensures that all caches have the most up-to-date value of the variable.		Whenever a processor changes a word in its cache, all other caches holding the value must be notified. In order to keep their own values consistent with the freshly written cache, the cache's could be either '''updated''' or '''invalidated'''. In the update method, if variable 'x' is modified by core 1, core 1 has to send the updated value of 'x' onto the inter-core bus. Each cache listens to the inter-core bus and if a cache sees a variable on the bus which it has a copy of, it will read the updated value. This ensures that all caches have the most up-to-date value of the variable.

	In case of invalidation, an invalidation message is sent onto the inter-core bus when a variable is changed. The other caches will read this invalidation signal; if its core attempts to access that variable, it will result in a cache miss and the variable will be read from main memory.		In case of invalidation, an invalidation message is sent onto the inter-core bus when a variable is changed. The other caches will read this invalidation signal; if its core attempts to access that variable, it will result in a cache miss and the variable will be read from main memory.