CSC/ECE 506 Spring 2012/7b pk - Revision history

Kgrover: /* Background - Virtual Memory, Paging and TLB */

2012-03-26T23:50:26Z

Background - Virtual Memory, Paging and TLB

← Older revision		Revision as of 23:50, 26 March 2012
Line 18:		Line 18:
	Every address is divided into two parts – a '''page number''' (p) and a '''page of'''fset (d). The page number is used as an index into the page table. The page table contains the base address of each page in physical memory. The base address is combined with the page offset to define the physical memory address that is sent to the memory unit. The problem with this approach is the time required to access a user memory location. If we want to access location, we must first index into the page table (that requires a memory access of PTBR) and then find the frame number from the page table and thereafter access the required frame number. The memory access is slowed down by a factor of 2.		Every address is divided into two parts – a '''page number''' (p) and a '''page of'''fset (d). The page number is used as an index into the page table. The page table contains the base address of each page in physical memory. The base address is combined with the page offset to define the physical memory address that is sent to the memory unit. The problem with this approach is the time required to access a user memory location. If we want to access location, we must first index into the page table (that requires a memory access of PTBR) and then find the frame number from the page table and thereafter access the required frame number. The memory access is slowed down by a factor of 2.

	[[File:TLB.png‎\|400px\|thumb\|right\| Virtual to physical page mapping using TLB and Page table]]		[[File:TLB.png‎\|400px\|thumb\|right\| Virtual to physical page mapping using TLB and Page table (Source-Operating System Concepts - Silberschatz, Galvin, Gagne)]]

	The standard solution to this problem is to use a special, small fast lookup hardware cache called a '''Translation Look-Aside Buffer''' (TLB). The TLB is fully associate, high-speed memory. Each entry in TLB consists of two parts –a key (tag) and a value. When the associative memory is presented with an item, the item is compared with all keys simultaneously. If the item is found, the corresponding value field is returned. The search is fast; the hardware, however is expensive. Typically, the number of entries in a TLB is small, often numbering between 64 to 1024.		The standard solution to this problem is to use a special, small fast lookup hardware cache called a '''Translation Look-Aside Buffer''' (TLB). The TLB is fully associate, high-speed memory. Each entry in TLB consists of two parts –a key (tag) and a value. When the associative memory is presented with an item, the item is compared with all keys simultaneously. If the item is found, the corresponding value field is returned. The search is fast; the hardware, however is expensive. Typically, the number of entries in a TLB is small, often numbering between 64 to 1024.

Kgrover: /* Performance */

2012-03-26T23:49:24Z

Performance

← Older revision		Revision as of 23:49, 26 March 2012
Line 222:		Line 222:
	UNITD is efficient in ensuring translation coherence, as it performs as well as the system with ideal TLB invalidations. UNITD speedups increase with the number of TLB shootdowns and with the number of cores. Third, as expected, UNITD has no impact on performance in the absence of TLB shootdowns. (Refer to the graph below).		UNITD is efficient in ensuring translation coherence, as it performs as well as the system with ideal TLB invalidations. UNITD speedups increase with the number of TLB shootdowns and with the number of cores. Third, as expected, UNITD has no impact on performance in the absence of TLB shootdowns. (Refer to the graph below).

	[[File:TLBFigure7.png\|frame\|none\|alt=alt text\|Figure 5: single_unmap benchmark. UNITD speedup over baseline system for directory.]]		[[File:TLBFigure7.png\|frame\|none\|alt=alt text\|Figure 5: (Source-UNITD protocol paper by Romanescu/Lebeck/Sorin/Bracy) single_unmap benchmark. UNITD speedup over baseline system for directory.]]

	== Definitions ==		== Definitions ==

Kgrover: /* UNITD Coherence Implementation */

2012-03-26T23:48:51Z

UNITD Coherence Implementation

← Older revision		Revision as of 23:48, 26 March 2012
Line 210:		Line 210:
	In order to integrate TLB coherence with the existing cache coherence protocol with minimal architectural changes, we relax the correspondence of the translations to the memory block containing the PTE, rather than the PTE itself. Maintaining translation granularity at a coarser grain (i.e., cache block, rather than PTE) trades a small performance penalty for ease of integration. Because multiple PTEs can be placed in the same cache block, the PCAM can hold multiple copies of the same datum. For simplicity, PCAM entries are referred as PTE addresses.		In order to integrate TLB coherence with the existing cache coherence protocol with minimal architectural changes, we relax the correspondence of the translations to the memory block containing the PTE, rather than the PTE itself. Maintaining translation granularity at a coarser grain (i.e., cache block, rather than PTE) trades a small performance penalty for ease of integration. Because multiple PTEs can be placed in the same cache block, the PCAM can hold multiple copies of the same datum. For simplicity, PCAM entries are referred as PTE addresses.

	[[File:TLBFigure6.png\|frame\|none\|alt=alt text\|Figure 2: Shows the two operations associated with the PCAM: (a) inserting an entry into the PCAM and (b) performing a coherence invalidation at the PCAM. PTE addresses are added in the PCAM simultaneously with the insertion of their corresponding translations in the TLB.]]		[[File:TLBFigure6.png\|frame\|none\|alt=alt text\|Figure 2: (Source-UNITD protocol paper by Romanescu/Lebeck/Sorin/Bracy) Shows the two operations associated with the PCAM: (a) inserting an entry into the PCAM and (b) performing a coherence invalidation at the PCAM. PTE addresses are added in the PCAM simultaneously with the insertion of their corresponding translations in the TLB.]]

	Because the PCAM has the same structure as the TLB, a PTE address is inserted in the PCAM at the same index as its corresponding translation in the TLB (physical address 12 in Figure 2(a) above. Note that there can be multiple PCAM entries with the same physical address, as in Figure 2a; this situation occurs when multiple cached translations correspond to PTEs residing in the same cache block.		Because the PCAM has the same structure as the TLB, a PTE address is inserted in the PCAM at the same index as its corresponding translation in the TLB (physical address 12 in Figure 2(a) above. Note that there can be multiple PCAM entries with the same physical address, as in Figure 2a; this situation occurs when multiple cached translations correspond to PTEs residing in the same cache block.

Kgrover: /* UNITD Coherence Implementation */

2012-03-26T23:48:10Z

UNITD Coherence Implementation

← Older revision		Revision as of 23:48, 26 March 2012
Line 206:		Line 206:
	As mentioned before, TLB entries are read-only. (Virtual to physical address mapping are never modified in the TLBs themselves but rather in the page table entries). There are only two coherence states: Shared (read-only) and Invalid. UNITD uses a Valid bit in TLB to maintain an entry’s coherence state. When a translation is inserted into a TLB, it is marked as Shared. The cached translation can be accessed by the local core as long as it is in the Shared state. The translation remains in Shared state until a TLB coherence message invalidates it. Thereafter subsequent memory accesses depending on it will miss in the TLB and reacquire the translation from the memory system.		As mentioned before, TLB entries are read-only. (Virtual to physical address mapping are never modified in the TLBs themselves but rather in the page table entries). There are only two coherence states: Shared (read-only) and Invalid. UNITD uses a Valid bit in TLB to maintain an entry’s coherence state. When a translation is inserted into a TLB, it is marked as Shared. The cached translation can be accessed by the local core as long as it is in the Shared state. The translation remains in Shared state until a TLB coherence message invalidates it. Thereafter subsequent memory accesses depending on it will miss in the TLB and reacquire the translation from the memory system.

	[[File:Figure5.png\|frame\|none\|alt=alt text\|Figure 1: Shows how the PCAM is integrated into the system, with interfaces to the TLB insertion/eviction mechanism (for inserting/evicting the corresponding PCAM entries), the coherence controller (for receiving coherence invalidations) and the processor core . The PCAM is off the critical path of a memory access; it is not accessed during regular TLB lookups for obtaining translations.]].		[[File:Figure5.png\|frame\|none\|alt=alt text\|Figure 1: (Source-UNITD protocol paper by Romanescu/Lebeck/Sorin/Bracy) Shows how the PCAM is integrated into the system, with interfaces to the TLB insertion/eviction mechanism (for inserting/evicting the corresponding PCAM entries), the coherence controller (for receiving coherence invalidations) and the processor core . The PCAM is off the critical path of a memory access; it is not accessed during regular TLB lookups for obtaining translations.]].

	In order to integrate TLB coherence with the existing cache coherence protocol with minimal architectural changes, we relax the correspondence of the translations to the memory block containing the PTE, rather than the PTE itself. Maintaining translation granularity at a coarser grain (i.e., cache block, rather than PTE) trades a small performance penalty for ease of integration. Because multiple PTEs can be placed in the same cache block, the PCAM can hold multiple copies of the same datum. For simplicity, PCAM entries are referred as PTE addresses.		In order to integrate TLB coherence with the existing cache coherence protocol with minimal architectural changes, we relax the correspondence of the translations to the memory block containing the PTE, rather than the PTE itself. Maintaining translation granularity at a coarser grain (i.e., cache block, rather than PTE) trades a small performance penalty for ease of integration. Because multiple PTEs can be placed in the same cache block, the PCAM can hold multiple copies of the same datum. For simplicity, PCAM entries are referred as PTE addresses.

Kgrover: /* Background */

2012-03-26T23:47:20Z

Background

← Older revision		Revision as of 23:47, 26 March 2012
Line 193:		Line 193:

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

	[[File:TLBFigure3.png\|400px\|thumb\|right\|Figure 4: Shootdown performance overhead on Phoenix benchmarks. Source-UNITD protocol paper by Romanescu/Lebeck/Sorin/Bracy ]]		[[File:TLBFigure3.png\|400px\|thumb\|right\|Figure 4: Shootdown performance overhead on Phoenix benchmarks. Source-UNITD protocol paper by Romanescu/Lebeck/Sorin/Bracy ]]

Kgrover: /* Background */

2012-03-26T23:46:53Z

Background

← Older revision		Revision as of 23:46, 26 March 2012
Line 195:		Line 195:
	[[File:TLBFigure1.png\|400px\|thumb\|right\|Figure 3: Per-shootdown Latency]]		[[File:TLBFigure1.png\|400px\|thumb\|right\|Figure 3: Per-shootdown Latency]]

	[[File:TLBFigure3.png\|400px\|thumb\|right\|Figure 4: Shootdown performance overhead on Phoenix benchmarks]]		[[File:TLBFigure3.png\|400px\|thumb\|right\|Figure 4: Shootdown performance overhead on Phoenix benchmarks. Source-UNITD protocol paper by Romanescu/Lebeck/Sorin/Bracy ]]

	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.

Kgrover: /* UNITD Coherence Implementation */

2012-03-26T23:39:04Z

UNITD Coherence Implementation

← Older revision		Revision as of 23:39, 26 March 2012
Line 204:		Line 204:
	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.

	As mentioned before, TLB entries are read-only. (Virtual to physical address mapping are never modified in the TLBs themselves but rather in the page table entries). There are only two coherence states: Shared (read-only) and Invalid. UNITD uses a Valid bit in TLB to maintain an entry’s coherence state. When a translation is inserted into a TLB, it is marked as Shared. The cached translation can be accessed by the local core as long as it is in the Shared state. The translation remains in ~~this~~ state until ~~the~~ TLB ~~receives a~~ coherence message ~~invalidating the translation~~. ~~The translation is then Invalid and thus~~ subsequent memory accesses depending on it will miss in the TLB and reacquire the translation from the memory system.		As mentioned before, TLB entries are read-only. (Virtual to physical address mapping are never modified in the TLBs themselves but rather in the page table entries). There are only two coherence states: Shared (read-only) and Invalid. UNITD uses a Valid bit in TLB to maintain an entry’s coherence state. When a translation is inserted into a TLB, it is marked as Shared. The cached translation can be accessed by the local core as long as it is in the Shared state. The translation remains in Shared state until a TLB coherence message invalidates it. Thereafter subsequent memory accesses depending on it will miss in the TLB and reacquire the translation from the memory system.

	[[File:Figure5.png\|frame\|none\|alt=alt text\|Figure 1: Shows how the PCAM is integrated into the system, with interfaces to the TLB insertion/eviction mechanism (for inserting/evicting the corresponding PCAM entries), the coherence controller (for receiving coherence invalidations) and the processor core . The PCAM is off the critical path of a memory access; it is not accessed during regular TLB lookups for obtaining translations.]].		[[File:Figure5.png\|frame\|none\|alt=alt text\|Figure 1: Shows how the PCAM is integrated into the system, with interfaces to the TLB insertion/eviction mechanism (for inserting/evicting the corresponding PCAM entries), the coherence controller (for receiving coherence invalidations) and the processor core . The PCAM is off the critical path of a memory access; it is not accessed during regular TLB lookups for obtaining translations.]].

Kgrover: /* References */

2012-03-26T23:20:22Z

References

← Older revision		Revision as of 23:20, 26 March 2012
Line 277:		Line 277:
	== References ==		== References ==

	1. Operating System Concepts - Silberschatz, Galvin, Gagne. Seventh Edition, Wiley publication, ~~2004~~		1. Operating System Concepts - Silberschatz, Galvin, Gagne. Seventh Edition, Wiley publication, 2005

	2. Fundamentals of Parallel Computer Architecture, Yan Solihin, 2008-2009		2. Fundamentals of Parallel Computer Architecture, Yan Solihin, 2008-2009

Kgrover: /* UNITD Coherence Implementation */

2012-03-26T23:16:31Z

UNITD Coherence Implementation

← Older revision		Revision as of 23:16, 26 March 2012
Line 208:		Line 208:
	[[File:Figure5.png\|frame\|none\|alt=alt text\|Figure 1: Shows how the PCAM is integrated into the system, with interfaces to the TLB insertion/eviction mechanism (for inserting/evicting the corresponding PCAM entries), the coherence controller (for receiving coherence invalidations) and the processor core . The PCAM is off the critical path of a memory access; it is not accessed during regular TLB lookups for obtaining translations.]].		[[File:Figure5.png\|frame\|none\|alt=alt text\|Figure 1: Shows how the PCAM is integrated into the system, with interfaces to the TLB insertion/eviction mechanism (for inserting/evicting the corresponding PCAM entries), the coherence controller (for receiving coherence invalidations) and the processor core . The PCAM is off the critical path of a memory access; it is not accessed during regular TLB lookups for obtaining translations.]].

	In order to integrate TLB coherence with the existing cache coherence protocol with minimal ~~microarchitectural~~ changes, we relax the correspondence of the translations to the memory block containing the PTE, rather than the PTE itself. Maintaining translation granularity at a coarser grain (i.e., cache block, rather than PTE) trades a small performance penalty for ease of integration. Because multiple PTEs can be placed in the same cache block, the PCAM can hold multiple copies of the same datum. For simplicity, ~~we refer to~~ PCAM entries ~~simply~~ as PTE addresses.		In order to integrate TLB coherence with the existing cache coherence protocol with minimal architectural changes, we relax the correspondence of the translations to the memory block containing the PTE, rather than the PTE itself. Maintaining translation granularity at a coarser grain (i.e., cache block, rather than PTE) trades a small performance penalty for ease of integration. Because multiple PTEs can be placed in the same cache block, the PCAM can hold multiple copies of the same datum. For simplicity, PCAM entries are referred as PTE addresses.

	[[File:TLBFigure6.png\|frame\|none\|alt=alt text\|Figure 2: Shows the two operations associated with the PCAM: (a) inserting an entry into the PCAM and (b) performing a coherence invalidation at the PCAM. PTE addresses are added in the PCAM simultaneously with the insertion of their corresponding translations in the TLB.]]		[[File:TLBFigure6.png\|frame\|none\|alt=alt text\|Figure 2: Shows the two operations associated with the PCAM: (a) inserting an entry into the PCAM and (b) performing a coherence invalidation at the PCAM. PTE addresses are added in the PCAM simultaneously with the insertion of their corresponding translations in the TLB.]]

Kgrover: /* Definitions */

2012-03-26T23:10:02Z

Definitions

← Older revision		Revision as of 23:10, 26 March 2012
Line 258:		Line 258:
	;Page Table Base Register		;Page Table Base Register
	: Pointer to page table location is maintained in this register		: Pointer to page table location is maintained in this register

	~~;Page table~~
	~~: Per process software construct/table created by operating system that maps virtual to physical memory pages~~

	;UNITD protocol		;UNITD protocol
	: A protocol that combine cache and TLB coherence proposed by Romanescu/Lebeck/Sorin/Bracy		: A protocol that combine cache and TLB coherence proposed by Romanescu/Lebeck/Sorin/Bracy

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

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

			;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

	== Links ==		== Links ==