CSC/ECE 506 Spring 2011/ch7 ss - Revision history

Admin: /* Translation Look-aside Buffer (TLB) Coherence */

2011-05-09T04:40:47Z

Translation Look-aside Buffer (TLB) Coherence

← Older revision		Revision as of 04:40, 9 May 2011
Line 58:		Line 58:
	== Translation Look-aside Buffer (TLB) Coherence ==		== Translation Look-aside Buffer (TLB) Coherence ==

	A TLB is a on-chip cache of the page table entries(PTEs) used to speed up virtual-to-physical-address translation. A PTE can reside in TLBs of multiple processors due to actual sharing or process migration. PTEs can be modified (during page swapping or changing its protection) leading to the direct analog of cache coherence problem.		A TLB is a on-chip cache of the page table entries (PTEs) used to speed up virtual-to-physical-address translation. A PTE can reside in TLBs of multiple processors due to actual sharing or process migration. PTEs can be modified (during page swapping or changing its protection) leading to the direct analog of cache coherence problem.

	A variety of solutions have been proposed to solve this problem based on whether hardware loads PTEs directly into the TLB or if PTEs are loaded into TLBs under software control and how several variables in TLBs and operating system are implemented. Software solutions (through operating system) are more widely used, as TLB coherence operations are less frequent than cache coherence operations. Hardware solutions are also used by few systems when TLB operations are not visible to software.		A variety of solutions have been proposed to solve this problem based on whether hardware loads PTEs directly into the TLB or if PTEs are loaded into TLBs under software control and how several variables in TLBs and operating system are implemented. Software solutions (through operating system) are more widely used, as TLB coherence operations are less frequent than cache coherence operations. Hardware solutions are also used by few systems when TLB operations are not visible to software.

Admin: /* Translation Look-aside Buffer(TLB) Coherence */

2011-05-09T04:40:35Z

Translation Look-aside Buffer(TLB) Coherence

← Older revision		Revision as of 04:40, 9 May 2011
Line 56:		Line 56:
	The MOESI protocol is a combination of the MESI and MOSI protocols.		The MOESI protocol is a combination of the MESI and MOSI protocols.

	== Translation Look-aside Buffer(TLB) Coherence ==		== Translation Look-aside Buffer (TLB) Coherence ==

	A TLB is a on-chip cache of the page table entries(PTEs) used to speed up virtual-to-physical-address translation. A PTE can reside in TLBs of multiple processors due to actual sharing or process migration. PTEs can be modified (during page swapping or changing its protection) leading to the direct analog of cache coherence problem.		A TLB is a on-chip cache of the page table entries(PTEs) used to speed up virtual-to-physical-address translation. A PTE can reside in TLBs of multiple processors due to actual sharing or process migration. PTEs can be modified (during page swapping or changing its protection) leading to the direct analog of cache coherence problem.

Sunimbho: /* Translation Look-aside Buffer(TLB) Coherence */

2011-03-21T20:09:30Z

Translation Look-aside Buffer(TLB) Coherence

← Older revision		Revision as of 20:09, 21 March 2011
Line 58:		Line 58:
	== Translation Look-aside Buffer(TLB) Coherence ==		== Translation Look-aside Buffer(TLB) Coherence ==

	A TLB is a cache on the page table entries(PTEs) used ~~for~~ virtual-to-physical-address translation. A PTE can reside in TLBs of multiple processors due to actual sharing or process migration. PTEs can be modified (during page swapping or changing its protection) leading to the direct analog of cache coherence problem.		A TLB is a on-chip cache of the page table entries(PTEs) used to speed up virtual-to-physical-address translation. A PTE can reside in TLBs of multiple processors due to actual sharing or process migration. PTEs can be modified (during page swapping or changing its protection) leading to the direct analog of cache coherence problem.

	A variety of solutions have been proposed to solve this problem based on whether hardware loads PTEs directly into the TLB or if PTEs are loaded into TLBs under software control and how several variables in TLBs and operating system are implemented. Software solutions (through operating system) are ~~mode~~ widely used, as TLB coherence operations are less frequent than cache coherence operations. Hardware solutions are also used by few systems when TLB operations are not visible to software.		A variety of solutions have been proposed to solve this problem based on whether hardware loads PTEs directly into the TLB or if PTEs are loaded into TLBs under software control and how several variables in TLBs and operating system are implemented. Software solutions (through operating system) are more widely used, as TLB coherence operations are less frequent than cache coherence operations. Hardware solutions are also used by few systems when TLB operations are not visible to software.

	Some of the approaches for implementing TLB coherence are as listed below:		Some of the approaches for implementing TLB coherence are as listed below:

Sseshad: /* See Also */

2011-03-21T01:35:57Z

Sseshad: /* Translation Look-aside Buffer(TLB) Coherence */

2011-03-21T01:32:26Z

Translation Look-aside Buffer(TLB) Coherence

← Older revision		Revision as of 01:32, 21 March 2011
Line 57:		Line 57:

	== Translation Look-aside Buffer(TLB) Coherence ==		== Translation Look-aside Buffer(TLB) Coherence ==

			A TLB is a cache on the page table entries(PTEs) used for virtual-to-physical-address translation. A PTE can reside in TLBs of multiple processors due to actual sharing or process migration. PTEs can be modified (during page swapping or changing its protection) leading to the direct analog of cache coherence problem.

			A variety of solutions have been proposed to solve this problem based on whether hardware loads PTEs directly into the TLB or if PTEs are loaded into TLBs under software control and how several variables in TLBs and operating system are implemented. Software solutions (through operating system) are mode widely used, as TLB coherence operations are less frequent than cache coherence operations. Hardware solutions are also used by few systems when TLB operations are not visible to software.

			Some of the approaches for implementing TLB coherence are as listed below:

			* Virtually addressed caches
			* Software TLB shootdown
			* Address space identifiers (ASIDs)
			* Hardware TLB coherence

	= Memory Consistency =		= Memory Consistency =

Sseshad: /* Memory Consistency */

2011-03-21T01:06:06Z

Memory Consistency

← Older revision		Revision as of 01:06, 21 March 2011
Line 79:		Line 79:
	In a single processor system, in order to maintain memory consistency, it needs to ensure that the compiler preserves the program order when accessing synchronization variables. But in a multiprocessor system, it is required to ensure that accesses of one processor appear to execute in program order to all other processors, atleast partially.		In a single processor system, in order to maintain memory consistency, it needs to ensure that the compiler preserves the program order when accessing synchronization variables. But in a multiprocessor system, it is required to ensure that accesses of one processor appear to execute in program order to all other processors, atleast partially.

	== 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 last write to the same location before it by the 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. [4]		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 last write to the same location before it by the 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. [4]

	== Memory semantics in multiprocessor systems ==		=== Memory semantics in multiprocessor systems ===

	Programmer's implicit expectations are:		Programmer's implicit expectations are:

Sseshad: /* Cache Coherence Protocols */

2011-03-21T01:04:21Z

Cache Coherence Protocols

← Older revision		Revision as of 01:04, 21 March 2011
Line 55:		Line 55:

	The MOESI protocol is a combination of the MESI and MOSI protocols.		The MOESI protocol is a combination of the MESI and MOSI protocols.

			== Translation Look-aside Buffer(TLB) Coherence ==

	= Memory Consistency =		= Memory Consistency =

Sseshad: /* Introduction to Shared Memory Multiprocessors */

2011-03-21T01:03:21Z

Introduction to Shared Memory Multiprocessors

← Older revision		Revision as of 01:03, 21 March 2011
Line 1:		Line 1:
	~~= Introduction to Shared Memory Multiprocessors =~~

	Though the migration from [http://en.wikipedia.org/wiki/Uniprocessor_system uniprocessor system] to [http://en.wikipedia.org/wiki/Multiprocessing multiprocessing] systems is not new, the world of parallel computers is undergoing a continuous change. Parallel computers, which started as high-end super-computing systems for carrying out huge calculations, are now ubiquitous and are present in all mainstream architectures for servers, desktops, and embedded systems. In order to design parallel architectures to meet programmer's needs and expectations more closely, exciting and challenging changes exist. The three main areas which are being considered by scientists today are: [http://en.wikipedia.org/wiki/Cache_coherence cache coherence], memory consistency and [http://en.wikipedia.org/wiki/Synchronization_%28computer_science%29 synchronization].		Though the migration from [http://en.wikipedia.org/wiki/Uniprocessor_system uniprocessor system] to [http://en.wikipedia.org/wiki/Multiprocessing multiprocessing] systems is not new, the world of parallel computers is undergoing a continuous change. Parallel computers, which started as high-end super-computing systems for carrying out huge calculations, are now ubiquitous and are present in all mainstream architectures for servers, desktops, and embedded systems. In order to design parallel architectures to meet programmer's needs and expectations more closely, exciting and challenging changes exist. The three main areas which are being considered by scientists today are: [http://en.wikipedia.org/wiki/Cache_coherence cache coherence], memory consistency and [http://en.wikipedia.org/wiki/Synchronization_%28computer_science%29 synchronization].

Sseshad: /* References */

2011-03-21T00:45:25Z

References

← Older revision		Revision as of 00:45, 21 March 2011
Line 185:		Line 185:

	[4] 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>		[4] 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>

			[5] 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

	= See Also =		= See Also =

Sseshad: /* Memory semantics in multiprocessor systems */

2011-03-21T00:43:06Z

Memory semantics in multiprocessor systems

← Older revision		Revision as of 00:43, 21 March 2011
Line 109:		Line 109:
	* one-copy serializability		* one-copy serializability
	* entry consistency		* entry consistency

			== 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. [5]

			In contrast, in a shared virtual memory on a loosely coupled multiprocessor which has no physically shared memory, and having a nontrivial communication cost between processors, conflicts are not likely to be solved with negligible delay, and they resemble much more 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.

			Memory coherence strategies are classified based on how they deal with '''''page synchronization''''' and '''''page ownership'''''. The algorithms for memory coherence depend on the page fault handlers, their servers and the data structures used. So ''page table'' becomes an important part of these protocols.

	= Synchronization =		= Synchronization =

← Older revision		Revision as of 01:35, 21 March 2011
Line 202:		Line 202:
	= See Also =		= See Also =

	[1] ~~AHO~~, A. V., ~~HOPCROFT~~, J. E., ~~AND ULLMAN~~, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. 1974.		[1] Aho, A. V., Hopcroft, J. E., and Ullman, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. 1974.

	[2] ~~ARCHIBALD~~, J., ~~AND BAER~~, J. An economical solution to the cache coherence problem. In Proceedings of the 11th Annual Symposium on Computer Architecture (Ann Arbor, Mich., June 1984). pp. 355-363.		[2] Archibald, J., and Baer, J. An economical solution to the cache coherence problem. In Proceedings of the 11th Annual Symposium on Computer Architecture (Ann Arbor, Mich., June 1984). pp. 355-363.

	[3] ~~CENSIER~~, L. M., ~~AND FEAUTRIER~~, P. A new solution to coherence problems in multicache systems. IEEE Trans. Comput. C-27,12 (Dec. 1978), 1112-1118.		[3] Censier, L. M., and Feautrier, P. A new solution to coherence problems in multicache systems. IEEE Trans. Comput. C-27,12 (Dec. 1978), 1112-1118.

	[4] ~~EGGERS~~, S. J., ~~AND KATZ~~, R. H. A characterization of sharing in parallel programs and its applications to coherence protocol evaluation. In Proceedings of the 15th Annual International Symposium on Computer Architecture (Honolulu, June 1988).		[4] Eggers, S. J., and Katz, R. H. A characterization of sharing in parallel programs and its applications to coherence protocol evaluation. In Proceedings of the 15th Annual International Symposium on Computer Architecture (Honolulu, June 1988).