CSC/ECE 506 Spring 2014/7b ks - Revision history

Kmuthia: /* Validation Based Approach */

2014-03-24T11:49:43Z

Validation Based Approach

← Older revision		Revision as of 11:49, 24 March 2014
Line 166:		Line 166:

	* Lazy Devaluation : This approach is used in MIPS R2000 processor running the System 5.3 Unix operating system.		* Lazy Devaluation : This approach is used in MIPS R2000 processor running the System 5.3 Unix operating system.


	* Address Space Identifier (ASID) based Approach : The IRIX 5.2 operating system uses this mechanism on MIPS as well as the AMD64 operating system.		* Address Space Identifier (ASID) based Approach : The IRIX 5.2 operating system uses this mechanism on MIPS as well as the AMD64 operating system.


	===Approaches requiring Hardware Cache consistency===		===Approaches requiring Hardware Cache consistency===

Kmuthia at 11:49, 24 March 2014

2014-03-24T11:49:09Z

← Older revision		Revision as of 11:49, 24 March 2014
Line 169:		Line 169:

	* Address Space Identifier (ASID) based Approach : The IRIX 5.2 operating system uses this mechanism on MIPS as well as the AMD64 operating system.		* Address Space Identifier (ASID) based Approach : The IRIX 5.2 operating system uses this mechanism on MIPS as well as the AMD64 operating system.

	* Validation Based Approach :

Kmuthia at 03:19, 17 March 2014

2014-03-17T03:19:49Z

Kmuthia at 03:13, 17 March 2014

2014-03-17T03:13:40Z

← Older revision		Revision as of 03:13, 17 March 2014
Line 261:		Line 261:
	: Software based TLB coherence method that requires one processor to shoot-down/disable TLB entries in other processors before providing them with a new TLB entry		: Software based TLB coherence method that requires one processor to shoot-down/disable TLB entries in other processors before providing them with a new TLB entry

	== References ==		== Textbook References ==

	1. Operating System Concepts - Silberschatz, Galvin, Gagne. Seventh Edition, Wiley publication, 2005		1. Operating System Concepts - Silberschatz, Galvin, Gagne. Seventh Edition, Wiley publication, 2005
Line 271:		Line 271:
	4. Microprocessor Memory Management Unit, Milan Milenkovic, IEEE, Vol10, Issue-2, 1990, Pages 70-85		4. Microprocessor Memory Management Unit, Milan Milenkovic, IEEE, Vol10, Issue-2, 1990, Pages 70-85

	==Internet ~~Links~~==		==Internet References==
	<references>		<references>
	{{reflist}}		{{reflist}}

Kmuthia at 03:12, 17 March 2014

2014-03-17T03:12:55Z

← Older revision		Revision as of 03:12, 17 March 2014
Line 83:		Line 83:
	2. Approaches without hardware cache consistency		2. Approaches without hardware cache consistency

	==Approaches without hardware cache consistency==		===Approaches without hardware cache consistency===

	=== Virtually Indexed Caches ===		==== Virtually Indexed Caches ====

	[http://en.wikipedia.org/wiki/CPU_cache#tocsection-16 Virtually indexed caches] may be accessed using the virtual memory reference. This approach eliminates the TLB altogether and its associated coherence issue. This approach requires processors to index data cache values using virtual addresses and thereby avoid the need for virtual-physical address translations between the processor and the L1 cache. Ultimately, however, in order to address physical main memory on an L1 miss (or L2 miss depending on the indexing strategy of the L2 cache), translation is still required from the virtual reference to a physical address in memory. In a non-TLB architecture, this translation uses the page mapping tables directly.		[http://en.wikipedia.org/wiki/CPU_cache#tocsection-16 Virtually indexed caches] may be accessed using the virtual memory reference. This approach eliminates the TLB altogether and its associated coherence issue. This approach requires processors to index data cache values using virtual addresses and thereby avoid the need for virtual-physical address translations between the processor and the L1 cache. Ultimately, however, in order to address physical main memory on an L1 miss (or L2 miss depending on the indexing strategy of the L2 cache), translation is still required from the virtual reference to a physical address in memory. In a non-TLB architecture, this translation uses the page mapping tables directly.
Line 93:		Line 93:
	Since this coherence issues relates more to PMT-data cache coherence (versus TLB coherence), it will not be discussed further in this section.		Since this coherence issues relates more to PMT-data cache coherence (versus TLB coherence), it will not be discussed further in this section.

	=== TLB Shootdown ===		==== TLB Shootdown ====

	The TLB Shootdown method is the most widely used TLB coherence approach. The approach has variants that turn on several factors, how many processors participate in the TLB update (the victim list) and the extent of hardware support for the process, which in turn may determine the visibility of the TLB by operating system kernel.		The TLB Shootdown method is the most widely used TLB coherence approach. The approach has variants that turn on several factors, how many processors participate in the TLB update (the victim list) and the extent of hardware support for the process, which in turn may determine the visibility of the TLB by operating system kernel.
Line 117:		Line 117:


	===Modified TLB Shootdown===		====Modified TLB Shootdown====

	The Modified TLB shootdown method of TLB coherence allows a processor to modify the table without waiting for other processors to synchronize. A processor using the table need not busy wait while the table is being modified. Also, processors can use a shared page table during a modification, since modifications are performed atomically. This version of TLB shootdown requires extra hardware support, but it is as effective as the original method and performs better.<ref>		The Modified TLB shootdown method of TLB coherence allows a processor to modify the table without waiting for other processors to synchronize. A processor using the table need not busy wait while the table is being modified. Also, processors can use a shared page table during a modification, since modifications are performed atomically. This version of TLB shootdown requires extra hardware support, but it is as effective as the original method and performs better.<ref>
	[http://www.cs.uwaterloo.ca/~brecht/courses/702/Possible-Readings/multiprocessor/tlb-consistency-computer-1990.pdf "Teller, Patricia J. Translation-Lookaside Buffer Consistency"]</ref>		[http://www.cs.uwaterloo.ca/~brecht/courses/702/Possible-Readings/multiprocessor/tlb-consistency-computer-1990.pdf "Teller, Patricia J. Translation-Lookaside Buffer Consistency"]</ref>

	=== Hierarchical TLBs ===		==== Hierarchical TLBs ====

	Hierarchical TLB includes a second level of TLB in the system called the L2 TLB which keeps a larger set of relevant data on the chip. This helps to keep relevant data on the chip for a longer time and improves the reload time of L1 TLBs. Many L1 TLBs can share a single L2 TLB. Having many cores share a single TLB helps improve the performance of the system many fold. Many possible coherence schemes can be used to maintain coherency between TLBs of different levels.<ref>		Hierarchical TLB includes a second level of TLB in the system called the L2 TLB which keeps a larger set of relevant data on the chip. This helps to keep relevant data on the chip for a longer time and improves the reload time of L1 TLBs. Many L1 TLBs can share a single L2 TLB. Having many cores share a single TLB helps improve the performance of the system many fold. Many possible coherence schemes can be used to maintain coherency between TLBs of different levels.<ref>
Line 128:		Line 128:
	</ref>		</ref>

	=== Instruction-based Invalidation ===		==== Instruction-based Invalidation ====

	Some processors have modified their instruction set to include a TLB invalidate instruction. The instruction is invoked by the operating system kernel to broadcast the modified page address from the initiating processor. The instruction is placed on the shared bus and a snooper on each processor detects the instruction and invalidates the appropriate TLB entries.		Some processors have modified their instruction set to include a TLB invalidate instruction. The instruction is invoked by the operating system kernel to broadcast the modified page address from the initiating processor. The instruction is placed on the shared bus and a snooper on each processor detects the instruction and invalidates the appropriate TLB entries.

	===Lazy devaluation===		====Lazy devaluation====

	In this method, invalidating the TLB emtries is postponed till it is absolutely necessary. The eviction of a page will be postponed till all related TLB entries are invalidated by a system wide TLB flush. The remapping of the page will be done when no TLB contains an entry for the page. If a remapping cannot be stalled all TLBs are flushed so that the change can occur. This approach works well unless processes run in parallel in the same address space.		In this method, invalidating the TLB emtries is postponed till it is absolutely necessary. The eviction of a page will be postponed till all related TLB entries are invalidated by a system wide TLB flush. The remapping of the page will be done when no TLB contains an entry for the page. If a remapping cannot be stalled all TLBs are flushed so that the change can occur. This approach works well unless processes run in parallel in the same address space.
Line 138:		Line 138:
	[http://www.cs.uwaterloo.ca/~brecht/courses/702/Possible-Readings/multiprocessor/tlb-consistency-computer-1990.pdf "Teller, Patricia J. Translation-Lookaside Buffer Consistency"]</ref>		[http://www.cs.uwaterloo.ca/~brecht/courses/702/Possible-Readings/multiprocessor/tlb-consistency-computer-1990.pdf "Teller, Patricia J. Translation-Lookaside Buffer Consistency"]</ref>

	=== Address Space Identifier (ASID) based Approach ===		==== Address Space Identifier (ASID) based Approach ====

	The MIPS family of processors assigns each TLB entry a unique identifier called an ASID. The ASID is similar to a process identifier (PID) except that its uniqueness is not guaranteed for the life of a process. Each process is assigned a unique ASID on each processor. Hence, a PID may have many ASIDs. A separate array is used to keep track of this mapping.		The MIPS family of processors assigns each TLB entry a unique identifier called an ASID. The ASID is similar to a process identifier (PID) except that its uniqueness is not guaranteed for the life of a process. Each process is assigned a unique ASID on each processor. Hence, a PID may have many ASIDs. A separate array is used to keep track of this mapping.
Line 147:		Line 147:


	=== Validation Based Approach ===		==== Validation Based Approach ====

	Under this approach, TLB invalidation is postponed until memory is accessed. This approach eliminates the need for interrupts and synchronization. Each frame in the page table is assigned a generation count. When a change modifies the mapping between a frame and a virtual page or when the permissions are restricted (e.g., from read-write to read-only), the memory manager modifies the generation count on the frame.		Under this approach, TLB invalidation is postponed until memory is accessed. This approach eliminates the need for interrupts and synchronization. Each frame in the page table is assigned a generation count. When a change modifies the mapping between a frame and a virtual page or when the permissions are restricted (e.g., from read-write to read-only), the memory manager modifies the generation count on the frame.
Line 155:		Line 155:
	</ref>		</ref>

	~~===~~Implementations~~===~~		'''Implementations'''

	* TLB Shootdown : This algorithm is implemented by in Carnegie Mellon University’s Mach operating system, which has been ported to multiprocessor architectures including the BBN Butterfly, Encore’s Multimax, IBM’s RP3, and Sequent’s Balance and Symmetry systems.		* TLB Shootdown : This algorithm is implemented by in Carnegie Mellon University’s Mach operating system, which has been ported to multiprocessor architectures including the BBN Butterfly, Encore’s Multimax, IBM’s RP3, and Sequent’s Balance and Symmetry systems.
Line 173:		Line 173:


	==Approaches requiring Hardware Cache consistency==		===Approaches requiring Hardware Cache consistency===

	=== Unified Cache and TLB coherence solution ===		==== Unified Cache and TLB coherence solution ====

	In this section the salient features of UNified Instruction/Translation/Data (UNITD) Coherence protocol proposed by Romanescu/Lebeck/Sorin/Bracy in their paper <ref>[http://people.ee.duke.edu/~sorin/papers/hpca10_unitd.pdf UNified Instruction Translation Data UNITD Coherence One Protocol to Rule Them All, Romanescu/Lebeck/Sorin/Bracy]</ref>		In this section the salient features of UNified Instruction/Translation/Data (UNITD) Coherence protocol proposed by Romanescu/Lebeck/Sorin/Bracy in their paper <ref>[http://people.ee.duke.edu/~sorin/papers/hpca10_unitd.pdf UNified Instruction Translation Data UNITD Coherence One Protocol to Rule Them All, Romanescu/Lebeck/Sorin/Bracy]</ref>
Line 182:		Line 182:
	UNITD is a unified hardware coherence framework that integrates TLB coherence into existing cache coherence protocol. In this protocol, the TLBs participate in cache coherence updates without needing any change to existing cache coherence protocol. This protocol is an improvement over the software based shootdown approach for TLB coherence and reduces the performance penalty due to TLB coherence significantly.		UNITD is a unified hardware coherence framework that integrates TLB coherence into existing cache coherence protocol. In this protocol, the TLBs participate in cache coherence updates without needing any change to existing cache coherence protocol. This protocol is an improvement over the software based shootdown approach for TLB coherence and reduces the performance penalty due to TLB coherence significantly.

	~~===~~ Background ~~===~~		''' Background '''
	[[File:TLBFigure1.png\|400px\|thumb\|right\|Figure 3: Per-shootdown Latency Source-UNITD protocol paper by Romanescu/Lebeck/Sorin/Bracy ]]		[[File:TLBFigure1.png\|400px\|thumb\|right\|Figure 3: Per-shootdown Latency Source-UNITD protocol paper by Romanescu/Lebeck/Sorin/Bracy ]]

Line 191:		Line 191:
	TLB shootdowns are invisible to user applications, although they directly impact user performance. The performance impact depends on - a) position of TLB in memory heirarchy, b) shoot down algorithm used, c) number of processors. The position of TLB in memory heirarchy refers to whether the TLB is placed close to processor or is close to memory. Shoot down algorithms trade performance v/s complexity. The performance penalty for shootdown increases with the number of processors as can be seen from Figure-3 that shows latency of the processor issuing shootdown and the ones receiving shootdowns. The effective latency is more than shown in the graphs because of TLB invalidations resulting in extra cycles spent in repopulating the TLB that can happen either from either cache or main memory depending on the case. The latency from TLB shootdowns can be higher for application that use the routine more often. (Refer to Figure-4).		TLB shootdowns are invisible to user applications, although they directly impact user performance. The performance impact depends on - a) position of TLB in memory heirarchy, b) shoot down algorithm used, c) number of processors. The position of TLB in memory heirarchy refers to whether the TLB is placed close to processor or is close to memory. Shoot down algorithms trade performance v/s complexity. The performance penalty for shootdown increases with the number of processors as can be seen from Figure-3 that shows latency of the processor issuing shootdown and the ones receiving shootdowns. The effective latency is more than shown in the graphs because of TLB invalidations resulting in extra cycles spent in repopulating the TLB that can happen either from either cache or main memory depending on the case. The latency from TLB shootdowns can be higher for application that use the routine more often. (Refer to Figure-4).

	== UNITD Coherence Implementation ==		=== UNITD Coherence Implementation ===
	At a high level, UNITD integrates the TLBs into the existing cache coherence protocol (such as typical MOSI -Modified Owned Share Invalid coherence states). TLBs are simply additional caches that participate in the coherence protocol however like read-only instruction caches. UNITD has no impact on the cache coherence protocol and thus does not increase its complexity.		At a high level, UNITD integrates the TLBs into the existing cache coherence protocol (such as typical MOSI -Modified Owned Share Invalid coherence states). TLBs are simply additional caches that participate in the coherence protocol however like read-only instruction caches. UNITD has no impact on the cache coherence protocol and thus does not increase its complexity.

Line 206:		Line 206:
	PCAM entries are removed as a result of the replacement of the corresponding translation in the TLB or due to an incoming coherence request for read-write access. If a coherence request hits in the PCAM, the Valid bit for the corresponding TLB entry is cleared. If multiple TLB translations have the same PTE block address, a PCAM lookup on this block address results in the identification of all associated TLB entries. Figure 2(b) above illustrates a coherence invalidation of physical address 12 that hits in two PCAM entries.		PCAM entries are removed as a result of the replacement of the corresponding translation in the TLB or due to an incoming coherence request for read-write access. If a coherence request hits in the PCAM, the Valid bit for the corresponding TLB entry is cleared. If multiple TLB translations have the same PTE block address, a PCAM lookup on this block address results in the identification of all associated TLB entries. Figure 2(b) above illustrates a coherence invalidation of physical address 12 that hits in two PCAM entries.

	=== Performance ===		==== Performance ====
	The performance of the UNITD protocol is compared to a) a baseline system that relies on TLB shootdowns and b) to a system with ideal (zero-latency) translation invalidations. (The ideal-invalidation system uses the same modified OS as UNITD (i.e., with no TLB shootdown support) and verifies that a translation is coherent whenever it is accessed in the TLB. The validation		The performance of the UNITD protocol is compared to a) a baseline system that relies on TLB shootdowns and b) to a system with ideal (zero-latency) translation invalidations. (The ideal-invalidation system uses the same modified OS as UNITD (i.e., with no TLB shootdown support) and verifies that a translation is coherent whenever it is accessed in the TLB. The validation
	is done in the background and has no performance impact).		is done in the background and has no performance impact).

Kmuthia at 03:05, 17 March 2014

2014-03-17T03:05:11Z

← Older revision		Revision as of 03:05, 17 March 2014
Line 175:		Line 175:
	==Approaches requiring Hardware Cache consistency==		==Approaches requiring Hardware Cache consistency==

	== Unified Cache and TLB coherence solution ==		=== Unified Cache and TLB coherence solution ===

	In this section the salient features of UNified Instruction/Translation/Data (UNITD) Coherence protocol proposed by Romanescu/Lebeck/Sorin/Bracy in their paper <ref>[http://people.ee.duke.edu/~sorin/papers/hpca10_unitd.pdf UNified Instruction Translation Data UNITD Coherence One Protocol to Rule Them All, Romanescu/Lebeck/Sorin/Bracy]</ref>		In this section the salient features of UNified Instruction/Translation/Data (UNITD) Coherence protocol proposed by Romanescu/Lebeck/Sorin/Bracy in their paper <ref>[http://people.ee.duke.edu/~sorin/papers/hpca10_unitd.pdf UNified Instruction Translation Data UNITD Coherence One Protocol to Rule Them All, Romanescu/Lebeck/Sorin/Bracy]</ref>

Kmuthia at 02:44, 17 March 2014

2014-03-17T02:44:20Z

← Older revision		Revision as of 02:44, 17 March 2014
Line 51:		Line 51:
	A safe change results from (a) modification of access rights from read-only to read/write or (b) a page is becoming memory-resident. A TLB entry that is inconsistent due to a safe change can be avoided by designing the hardware so that using the entry throws an exception and invokes the appropriate Operating System trap routine that invalidates the TLB entry. Consider an example shown in the figure: Consider the translation information of page a stored in a valid TLB entry is accessed by processor X which defines the page’s protection as read-only. Now, a process executing on processor Y subsequently modifies a’s page-table entry to change the protection from read-only to read/write. When process executing on processor X now attempts to write a, the Operating system finds that the protection has been increased and invalidates the stale TLB entry for a and resumes execution. Thus a is successfully modifies and this results in consistency.An unsafe change causes inconsistencies in the TLB that cannot be detected during program execution. This kind of multiprocessor architecture with multiple TLBs, in addition to a consistency problem between a page table and a TLB, a consistency problem exists among the system’s multiple TLBs and page tables.		A safe change results from (a) modification of access rights from read-only to read/write or (b) a page is becoming memory-resident. A TLB entry that is inconsistent due to a safe change can be avoided by designing the hardware so that using the entry throws an exception and invokes the appropriate Operating System trap routine that invalidates the TLB entry. Consider an example shown in the figure: Consider the translation information of page a stored in a valid TLB entry is accessed by processor X which defines the page’s protection as read-only. Now, a process executing on processor Y subsequently modifies a’s page-table entry to change the protection from read-only to read/write. When process executing on processor X now attempts to write a, the Operating system finds that the protection has been increased and invalidates the stale TLB entry for a and resumes execution. Thus a is successfully modifies and this results in consistency.An unsafe change causes inconsistencies in the TLB that cannot be detected during program execution. This kind of multiprocessor architecture with multiple TLBs, in addition to a consistency problem between a page table and a TLB, a consistency problem exists among the system’s multiple TLBs and page tables.

	Some architectures ~~donot~~ follow TLB coherence for each datum (i.e., TLBs may contain different values). These architectures require TLB coherence only for unsafe changes made to address translations. Unsafe changes include a) mapping modifications, b) decreasing the page privileges (e.g., from read-write to read-only) or c) marking the translation as invalid. The remaining possible changes (e.g., d) increasing page privileges, e) updating the accessed/dirty bits) are considered to be safe and do not require TLB coherence. Consider one core that has a translation marked as read-only in the TLB, while another core updates the translation in the page table to be read-write. This translation update does not have to be immediately visible to the first core. Instead, the first core's TLB can be lazily updated when the core attempts to execute a store instruction; an access violation will occur and the page fault handler can load the updated translation.		Some architectures do not follow TLB coherence for each datum (i.e., TLBs may contain different values). These architectures require TLB coherence only for unsafe changes made to address translations. Unsafe changes include a) mapping modifications, b) decreasing the page privileges (e.g., from read-write to read-only) or c) marking the translation as invalid. The remaining possible changes (e.g., d) increasing page privileges, e) updating the accessed/dirty bits) are considered to be safe and do not require TLB coherence. Consider one core that has a translation marked as read-only in the TLB, while another core updates the translation in the page table to be read-write. This translation update does not have to be immediately visible to the first core. Instead, the first core's TLB can be lazily updated when the core attempts to execute a store instruction; an access violation will occur and the page fault handler can load the updated translation.

	A variety of solutions have been used for TLB coherence. Software solutions through operating systems are popular since TLB coherence operations are less frequent than cache coherence operations. The exact solution depends on whether PTEs (Page Table Entries) are loaded into TLBs directly by hardware or under software control. Hardware solutions are used where TLBs are not visible to software.		A variety of solutions have been used for TLB coherence. Software solutions through operating systems are popular since TLB coherence operations are less frequent than cache coherence operations. The exact solution depends on whether PTEs (Page Table Entries) are loaded into TLBs directly by hardware or under software control. Hardware solutions are used where TLBs are not visible to software.
Line 127:		Line 127:
	[http://www.cs.berkeley.edu/~kubitron/courses/cs258-S08/projects/reports/project8_report_ver3.pdf "Address Translation for Manycore Systems"]		[http://www.cs.berkeley.edu/~kubitron/courses/cs258-S08/projects/reports/project8_report_ver3.pdf "Address Translation for Manycore Systems"]
	</ref>		</ref>


	=== Instruction-based Invalidation ===		=== Instruction-based Invalidation ===
Line 134:		Line 133:

	===Lazy devaluation===		===Lazy devaluation===

	In this method, invalidating the TLB emtries is postponed till it is absolutely necessary. The eviction of a page will be postponed till all related TLB entries are invalidated by a system wide TLB flush. The remapping of the page will be done when no TLB contains an entry for the page. If a remapping cannot be stalled all TLBs are flushed so that the change can occur. This approach works well unless processes run in parallel in the same address space.		In this method, invalidating the TLB emtries is postponed till it is absolutely necessary. The eviction of a page will be postponed till all related TLB entries are invalidated by a system wide TLB flush. The remapping of the page will be done when no TLB contains an entry for the page. If a remapping cannot be stalled all TLBs are flushed so that the change can occur. This approach works well unless processes run in parallel in the same address space.
	Lazy devaluation works well when the target systems without excessive TLB flushing. The performance of this approach can be improved by doing a selective invalidation of TLB entries instead of doing a system-wide flushes. <ref>		Lazy devaluation works well when the target systems without excessive TLB flushing. The performance of this approach can be improved by doing a selective invalidation of TLB entries instead of doing a system-wide flushes. <ref>
Line 163:		Line 163:
	* Hierarchical TLBs : The Intel Nehalem platform uses a hierarchical TLB.		* Hierarchical TLBs : The Intel Nehalem platform uses a hierarchical TLB.

	* Instruction based invalidation :		* Instruction based invalidation : Examples of this include the Intel Itanium architecture (via the ptc.g and ptc.ga instructions) and the tlbivax instruction on IBM’s Power series (for Power ISA 2.06). An example of an operating system that uses the Itanium support for instruction based TLB invalidation is the Linux kernel

	* Lazy Devaluation :		* Lazy Devaluation : This approach is used in MIPS R2000 processor running the System 5.3 Unix operating system.

	* Address Space Identifier (ASID) based Approach :
			* Address Space Identifier (ASID) based Approach : The IRIX 5.2 operating system uses this mechanism on MIPS as well as the AMD64 operating system.

	* Validation Based Approach :		* Validation Based Approach :
Line 259:		Line 260:
	;TLB Shootdown		;TLB Shootdown
	: Software based TLB coherence method that requires one processor to shoot-down/disable TLB entries in other processors before providing them with a new TLB entry		: Software based TLB coherence method that requires one processor to shoot-down/disable TLB entries in other processors before providing them with a new TLB entry

	~~== Links ==~~

	~~[http://sequoia.ict.pwr.wroc.pl/~iro/RISC/sm/www.hp.com/acd-18.html#HEADING18-0 Address Resolution and the TLB]~~

	== References ==		== References ==
Line 274:		Line 271:
	4. Microprocessor Memory Management Unit, Milan Milenkovic, IEEE, Vol10, Issue-2, 1990, Pages 70-85		4. Microprocessor Memory Management Unit, Milan Milenkovic, IEEE, Vol10, Issue-2, 1990, Pages 70-85

	==~~Notes~~==		==Internet Links==
	<references>		<references>
	{{reflist}}		{{reflist}}

Kmuthia at 01:59, 17 March 2014

2014-03-17T01:59:10Z

Show changes

Kmuthia at 22:18, 16 March 2014

2014-03-16T22:18:28Z

← Older revision		Revision as of 22:18, 16 March 2014
Line 79:		Line 79:
	Any modifications to the mapping between a virtual page and main memory frame are also unsafe without a TLB coherence mechanism. This is in large part due to the fact that page numbers are formed by splitting a finite address space into discrete units. These pages in turn are mapped to physical memory frames as needed by the operating system. The mapping of a page to a frame is a transient condition and the same page may be mapped to different frames across time. Without a TLB coherence mechanism, it is possible that a processor may attempt to use a stale page-frame mapping to reference a frame that has been reassigned.		Any modifications to the mapping between a virtual page and main memory frame are also unsafe without a TLB coherence mechanism. This is in large part due to the fact that page numbers are formed by splitting a finite address space into discrete units. These pages in turn are mapped to physical memory frames as needed by the operating system. The mapping of a page to a frame is a transient condition and the same page may be mapped to different frames across time. Without a TLB coherence mechanism, it is possible that a processor may attempt to use a stale page-frame mapping to reference a frame that has been reassigned.

	''TLB ~~Coherence Strategies''~~		TLB coherence approaches are of two types :
			1. Approaches requiring Hardware Cache consistency
			2. Approaches without hardware cache consistency

	~~There are several approaches to maintaining coherence or~~ consistency ~~among multiple TLBs in a multi-processor machine and the page tables in main memory.~~		==Approaches without hardware cache consistency==

	=== Virtually Indexed Caches ===		=== Virtually Indexed Caches ===
Line 187:		Line 189:
	[http://www.cs.uwaterloo.ca/~brecht/courses/702/Possible-Readings/multiprocessor/tlb-consistency-computer-1990.pdf "Teller, Patricia J. Translation-Lookaside Buffer Consistency"]		[http://www.cs.uwaterloo.ca/~brecht/courses/702/Possible-Readings/multiprocessor/tlb-consistency-computer-1990.pdf "Teller, Patricia J. Translation-Lookaside Buffer Consistency"]
	</ref>		</ref>

			==Approaches requiring Hardware Cache consistency==

	== Unified Cache and TLB coherence solution ==		== Unified Cache and TLB coherence solution ==

Sramesh3: /* Definitions */

2014-03-15T13:38:05Z

Definitions

← Older revision		Revision as of 13:38, 15 March 2014
Line 242:		Line 242:

	;Safe Change		;Safe Change
	: A type of update that can be made to a PMT safely without also updating the cached TLB counterpart.		: A type of update that can be made to a PMT safely without also updating the cached TLB counterpart. A safe change results from (a) modification of access rights from read-only to read/write or (b) a page is becoming memory-resident.

	;TLB Coherence Strategy		;TLB Coherence Strategy
Line 260:		Line 260:

	;Page Table Base Register		;Page Table Base Register
	: Pointer to page table location is maintained in this register		: Pointer to the page table location is maintained in this register.

	;UNITD protocol		;UNITD protocol
	: A protocol that ~~combine~~ cache ~~and TLB~~ coherence proposed by Romanescu/Lebeck/Sorin/Bracy		: A protocol that combines TLB and existing cache coherence protocols (proposed by Romanescu/Lebeck/Sorin/Bracy)

	;Validation based approach		;Validation based approach
	: In this approach TLB entries are not updated until used		: In this approach TLB entries are not updated until they are used.

	;Virtual Index Cache		;Virtual Index Cache
	: Cache that stores data based on virtual page number		: Cache that stores data based on virtual page number.

	;TLB Shootdown		;TLB Shootdown

← Older revision		Revision as of 03:19, 17 March 2014
Line 5:		Line 5:

	== Overview ==		== Overview ==
	The cache coherence problem in multiprocessing architectures and their hardware based protocol solutions have received great attention. Another coherence problem in ~~multiprocesing~~ is that of TLBs (Transaction Lookaside Buffers). A TLB is a fully associate hardware cache that maintains virtual to physical mapping of most recently used pages. TLB is used by CPU for fast look up of the physical page frame number for a virtual memory location. The same ~~lookup~~ from the page-table for the process (software based construct) is slower. A page may become invalid due to a swap out to memory or may change protection level (read v/s read-write). Maintaining coherence between TLB entries on different processors for the same page (as its state changes) is called TLB coherence problem. This coherence is ~~mantained~~ most often by software based solutions by the operating systems. In this note, we explain a) the background for used of TLB hardware, b) current solutions for maintaining TLB coherence and c) finally a proposal for a unified cache-TLB coherence protocol (that is hardware based).		The cache coherence problem in multiprocessing architectures and their hardware based protocol solutions have received great attention. Another coherence problem in multiprocessing is that of TLBs (Transaction Lookaside Buffers). A TLB is a fully associate hardware cache that maintains virtual to physical mapping of most recently used pages. TLB is used by CPU for fast look up of the physical page frame number for a virtual memory location. The same look up from the page-table for the process (software based construct) is slower. A page may become invalid due to a swap out to memory or may change protection level (read v/s read-write). Maintaining coherence between TLB entries on different processors for the same page (as its state changes) is called TLB coherence problem. This coherence is maintained most often by software based solutions by the operating systems. In this note, we explain a) the background for used of TLB hardware, b) current solutions for maintaining TLB coherence and c) finally a proposal for a unified cache-TLB coherence protocol (that is hardware based).

	== Background - Virtual Memory, Paging and TLB ==		== Background - Virtual Memory, Paging and TLB ==
Line 28:		Line 28:
	A page table typically has an additional bit per entry to indicate whether the frame number is read only or both read-write ('''protection level'''). Another bit '''valid-invalid''' is also added to indicate whether the frame is part of that particular process.		A page table typically has an additional bit per entry to indicate whether the frame number is read only or both read-write ('''protection level'''). Another bit '''valid-invalid''' is also added to indicate whether the frame is part of that particular process.

	'''~~Mutilevel pages~~ tables''' are often used rather than single page table per process. The first level page table points to the entry in the next level page table and so on until the mapping of virtual to physical page is obtained from the last level page table.		'''Multilevel page tables''' are often used rather than single page table per process. The first level page table points to the entry in the next level page table and so on until the mapping of virtual to physical page is obtained from the last level page table.

	It may be noted that caches typically use "Virtual Indexed Physically Tagged" solution that enables simultaneous look-up of both L-1 cache and TLB. If the page block is not found in L-1 cache, a TLB look-up of address is used to refresh the page block. ~~Simultanous~~ look-up of both L-1 cache and TLB makes the process efficient.		It may be noted that caches typically use "Virtual Indexed Physically Tagged" solution that enables simultaneous look-up of both L-1 cache and TLB. If the page block is not found in L-1 cache, a TLB look-up of address is used to refresh the page block. Simultaneous look-up of both L-1 cache and TLB makes the process efficient.

	== TLB coherence problem in multiprocessing ==		== TLB coherence problem in multiprocessing ==
Line 134:		Line 134:
	====Lazy devaluation====		====Lazy devaluation====

	In this method, invalidating the TLB ~~emtries~~ is postponed till it is absolutely necessary. The eviction of a page will be postponed till all related TLB entries are invalidated by a system wide TLB flush. The remapping of the page will be done when no TLB contains an entry for the page. If a remapping cannot be stalled all TLBs are flushed so that the change can occur. This approach works well unless processes run in parallel in the same address space.		In this method, invalidating the TLB entries is postponed till it is absolutely necessary. The eviction of a page will be postponed till all related TLB entries are invalidated by a system wide TLB flush. The remapping of the page will be done when no TLB contains an entry for the page. If a remapping cannot be stalled all TLBs are flushed so that the change can occur. This approach works well unless processes run in parallel in the same address space.
	Lazy devaluation works well when the target systems without excessive TLB flushing. The performance of this approach can be improved by doing a selective invalidation of TLB entries instead of doing a system-wide flushes. <ref>		Lazy devaluation works well when the target systems without excessive TLB flushing. The performance of this approach can be improved by doing a selective invalidation of TLB entries instead of doing a system-wide flushes. <ref>
	[http://www.cs.uwaterloo.ca/~brecht/courses/702/Possible-Readings/multiprocessor/tlb-consistency-computer-1990.pdf "Teller, Patricia J. Translation-Lookaside Buffer Consistency"]</ref>		[http://www.cs.uwaterloo.ca/~brecht/courses/702/Possible-Readings/multiprocessor/tlb-consistency-computer-1990.pdf "Teller, Patricia J. Translation-Lookaside Buffer Consistency"]</ref>
Line 189:		Line 189:
	Cache coherence protocols are all-hardware based because this provides a) higher performance and b) decoupling with architectural issues. On the Other hand, the shootdown protocol used for TLB coherence is essentially software based. A hardware based TLB coherence can a) improve TLB coherence performance significantly for high number of processors and b)provide a cleaner interface to the Operating system.		Cache coherence protocols are all-hardware based because this provides a) higher performance and b) decoupling with architectural issues. On the Other hand, the shootdown protocol used for TLB coherence is essentially software based. A hardware based TLB coherence can a) improve TLB coherence performance significantly for high number of processors and b)provide a cleaner interface to the Operating system.

	TLB shootdowns are invisible to user applications, although they directly impact user performance. The performance impact depends on - a) position of TLB in memory ~~heirarchy~~, b) shoot down algorithm used, c) number of processors. The position of TLB in memory ~~heirarchy~~ refers to whether the TLB is placed close to processor or is close to memory. Shoot down algorithms trade performance v/s complexity. The performance penalty for shootdown increases with the number of processors as can be seen from Figure-3 that shows latency of the processor issuing shootdown and the ones receiving shootdowns. The effective latency is more than shown in the graphs because of TLB invalidations resulting in extra cycles spent in repopulating the TLB that can happen either from either cache or main memory depending on the case. The latency from TLB shootdowns can be higher for application that use the routine more often. (Refer to Figure-4).		TLB shootdowns are invisible to user applications, although they directly impact user performance. The performance impact depends on - a) position of TLB in memory hierarchy, b) shoot down algorithm used, c) number of processors. The position of TLB in memory hierarchy refers to whether the TLB is placed close to processor or is close to memory. Shoot down algorithms trade performance v/s complexity. The performance penalty for shootdown increases with the number of processors as can be seen from Figure-3 that shows latency of the processor issuing shootdown and the ones receiving shootdowns. The effective latency is more than shown in the graphs because of TLB invalidations resulting in extra cycles spent in repopulating the TLB that can happen either from either cache or main memory depending on the case. The latency from TLB shootdowns can be higher for application that use the routine more often. (Refer to Figure-4).

	=== UNITD Coherence Implementation ===		=== UNITD Coherence Implementation ===