CSC/ECE 506 Spring 2013/7b lm - Revision history

Llmckee at 04:02, 18 April 2013

2013-04-18T04:02:29Z

← Older revision		Revision as of 04:02, 18 April 2013
Line 10:		Line 10:
	== 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). These changes, and all other page changes, are flushed to all other processors using a series of actions calles TLB Shootdown. 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 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). These changes, and all other page changes, are flushed to all other processors using a series of actions calles TLB Shootdown. 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).
	~~<table>~~
	{{Sidebar		{{Sidebar
	\| name = CSC/ECE 506 Spring 2013/7b lm\| outertitle = Useful Definitions		\| name = CSC/ECE 506 Spring 2013/7b lm\| outertitle = Useful Definitions
Line 63:		Line 62:
	}}		}}

	~~</table>~~
	== Background - Virtual Memory, Paging and TLB ==		== Background - Virtual Memory, Paging and TLB ==
	In this section we introduce the basic terminology and the set-up where TLBs are used.		In this section we introduce the basic terminology and the set-up where TLBs are used.

Llmckee at 04:01, 18 April 2013

2013-04-18T04:01:51Z

← Older revision		Revision as of 04:01, 18 April 2013
Line 10:		Line 10:
	== 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). These changes, and all other page changes, are flushed to all other processors using a series of actions calles TLB Shootdown. 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 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). These changes, and all other page changes, are flushed to all other processors using a series of actions calles TLB Shootdown. 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).
			<table>
	{{Sidebar		{{Sidebar
	\| name = CSC/ECE 506 Spring 2013/7b lm\| outertitle = Useful Definitions		\| name = CSC/ECE 506 Spring 2013/7b lm\| outertitle = Useful Definitions
Line 63:		Line 63:
	}}		}}

			</table>
	== Background - Virtual Memory, Paging and TLB ==		== Background - Virtual Memory, Paging and TLB ==
	In this section we introduce the basic terminology and the set-up where TLBs are used.		In this section we introduce the basic terminology and the set-up where TLBs are used.

Llmckee at 02:26, 18 April 2013

2013-04-18T02:26:07Z

← Older revision		Revision as of 02:26, 18 April 2013
Line 70:		Line 70:
	'''Paging''' is a memory-management scheme that permits the physical address space of a process to be non-contiguous. The basic method involves breaking physical memory into fixed-size blocks called frames and breaking the virtual memory into blocks of the same size called pages. When a process is to be executed its pages are loaded into any available memory frames from the backing storage (for example-a hard drive).		'''Paging''' is a memory-management scheme that permits the physical address space of a process to be non-contiguous. The basic method involves breaking physical memory into fixed-size blocks called frames and breaking the virtual memory into blocks of the same size called pages. When a process is to be executed its pages are loaded into any available memory frames from the backing storage (for example-a hard drive).

	[[File:~~Operation_of_Paging_and_Translation_Lookaside_Buffer~~.png\|400px\|thumb\|right\| Operation of Paging and Translation Lookaside Buffer (TLB) source- Stallings]]		[[File:Operation of Paging and Translation Lookaside Buffer.png\|400px\|thumb\|right\| Operation of Paging and Translation Lookaside Buffer (TLB) source- Stallings]]

	Each process has a '''page table''' that maintains a mapping of virtual pages to physical pages. A page table is a software construct managed by operating system that is kept in main memory. For a process, a pointer to the page table ('''Page-Table Base Register-PTBR''') is stored in a register. Changing page table requires changing only this one register, substantially reducing the context-switch time. (A page table, with virtual page number that is 4 bytes long (32 bits) can point to 2^32 physical page frames. If frame size is 4Kb then a system with 4-byte entries can address 2^44 bytes (or 16 TB) of physical memory).		Each process has a '''page table''' that maintains a mapping of virtual pages to physical pages. A page table is a software construct managed by operating system that is kept in main memory. For a process, a pointer to the page table ('''Page-Table Base Register-PTBR''') is stored in a register. Changing page table requires changing only this one register, substantially reducing the context-switch time. (A page table, with virtual page number that is 4 bytes long (32 bits) can point to 2^32 physical page frames. If frame size is 4Kb then a system with 4-byte entries can address 2^44 bytes (or 16 TB) of physical memory).

Llmckee at 01:54, 18 April 2013

2013-04-18T01:54:29Z

← Older revision		Revision as of 01:54, 18 April 2013
Line 291:		Line 291:

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

	~~;PMT(Page Mapping Table)~~
	: This is an in-memory data structure that primarily helps the operating system map two address spaces two one another: virtual memory and physical memory. In addition to this mapping information, the PMT also stores additional data fields to keep track of whether the virtual memory has been loaded in physical memory, permissions and utilization metrics. Coupled with the TLB, the PMT is a critical component of virtual memory systems. Learn more about page tables [http://en.wikipedia.org/wiki/Page_table here].

	~~;PTE (Page Table Entry)~~
	~~: A row in a page mapping table that relates a single page in virtual memory to a physical memory address or a page frame.~~

	~~;TLB(Translation Look-Aside Buffer)~~
	~~: Associative, high-speed memory used to cache page table information and speed up virtual memory references from the processor.~~

	~~;Presence Bit~~
	~~: One of the data elements in each PMT entry. Indicates whether the page is loaded in main memory (versus stored to disk).~~

	~~;Safe Change~~
	~~: A type of update that can be made to a PMT safely without also updating the cached TLB counterpart.~~

	~~;TLB Coherence Strategy~~
	~~: A process or system for maintaining the consistency of information between the processor TLBs and the PMT entries.~~

	~~;IDT (Interrupt Descriptor Table)~~
	~~: A vector-based data structure used to communicate information between processors during an inter-processor interrupt.~~

	~~;Interrupt~~
	~~: A hardware or software based method for signalling to a processor that there is work for it.~~

	~~;ASID (Address Space Identifier)~~
	: A number assigned to process that is unique within the scope of a processor for a specified time period. A process may be assigned multiple ASIDs across time. Used with the TLB entries, the ASID helps the discard stale TLB entries.

	~~;Hierarchical TLBs~~
	~~: Is analogus concept for TLBS as multilevel L1 and L2 cache~~

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

	~~;UNITD protocol~~
	~~: 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 ==

Llmckee at 01:52, 18 April 2013

2013-04-18T01:52:32Z

← Older revision		Revision as of 01:52, 18 April 2013
Line 76:		Line 76:
	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:Use of a Translation Lookaside Buffer.png?\|400px\|thumb\|right\| Use of a Translation Lookaside Buffer source- Stallings]]		[[File:Use of a Translation Lookaside Buffer.png\|400px\|thumb\|right\| Use of a Translation Lookaside Buffer source- Stallings]]
	[[File:TLB Page Table Entries.png?\|400px\|thumb\|right\| TLB Page Table Entries source- Stallings]]		[[File:TLB Page Table Entries.png\|400px\|thumb\|right\| TLB Page Table Entries source- Stallings]]
	[[File:Translation Lookaside Buffer and Cache Operation.png?\|400px\|thumb\|right\| Translation Lookaside Buffer and Cache Operation source- Stallings]]		[[File:Translation Lookaside Buffer and Cache Operation.png\|400px\|thumb\|right\| Translation Lookaside Buffer and Cache Operation source- Stallings]]

	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.
Line 246:		Line 246:
	[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.

	[[File:Various Cache Addressing Options.png?\|400px\|thumb\|right\| Various Cache Addressing Options source- Solihin 2008-2009]]		[[File:Various Cache Addressing Options.png\|400px\|thumb\|right\| Various Cache Addressing Options source- Solihin 2008-2009]]

	Under this approach, PMT entries may be brought into the processor’s data cache. Though the cache coherence protocol in effect will manage consistency across all processor caches, it does not handle consistency between cached PMT entries and the page tables in main memory. Hence, even in the absence of a TLB there remains a coherence problem between data caches and main memory page tables. As PMT entries in main memory are modified by the operating system kernel, the processor data caches must be reconciled by invalidating stale PMT entries.		Under this approach, PMT entries may be brought into the processor’s data cache. Though the cache coherence protocol in effect will manage consistency across all processor caches, it does not handle consistency between cached PMT entries and the page tables in main memory. Hence, even in the absence of a TLB there remains a coherence problem between data caches and main memory page tables. As PMT entries in main memory are modified by the operating system kernel, the processor data caches must be reconciled by invalidating stale PMT entries.

	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.
	[[File:Translation Lookaside Buffer and Cache Operation.png?\|400px\|thumb\|right\| Translation Lookaside Buffer and Cache Operation source- Stallings]]		[[File:Translation Lookaside Buffer and Cache Operation.png\|400px\|thumb\|right\| Translation Lookaside Buffer and Cache Operation source- Stallings]]

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

Llmckee at 01:47, 18 April 2013

2013-04-18T01:47:27Z

← Older revision		Revision as of 01:47, 18 April 2013
Line 70:		Line 70:
	'''Paging''' is a memory-management scheme that permits the physical address space of a process to be non-contiguous. The basic method involves breaking physical memory into fixed-size blocks called frames and breaking the virtual memory into blocks of the same size called pages. When a process is to be executed its pages are loaded into any available memory frames from the backing storage (for example-a hard drive).		'''Paging''' is a memory-management scheme that permits the physical address space of a process to be non-contiguous. The basic method involves breaking physical memory into fixed-size blocks called frames and breaking the virtual memory into blocks of the same size called pages. When a process is to be executed its pages are loaded into any available memory frames from the backing storage (for example-a hard drive).

	[[File:Operation_of_Paging_and_Translation_Lookaside_Buffer.png?\|400px\|thumb\|right\| Operation of Paging and Translation Lookaside Buffer (TLB) source- Stallings]]		[[File:Operation_of_Paging_and_Translation_Lookaside_Buffer.png\|400px\|thumb\|right\| Operation of Paging and Translation Lookaside Buffer (TLB) source- Stallings]]

	Each process has a '''page table''' that maintains a mapping of virtual pages to physical pages. A page table is a software construct managed by operating system that is kept in main memory. For a process, a pointer to the page table ('''Page-Table Base Register-PTBR''') is stored in a register. Changing page table requires changing only this one register, substantially reducing the context-switch time. (A page table, with virtual page number that is 4 bytes long (32 bits) can point to 2^32 physical page frames. If frame size is 4Kb then a system with 4-byte entries can address 2^44 bytes (or 16 TB) of physical memory).		Each process has a '''page table''' that maintains a mapping of virtual pages to physical pages. A page table is a software construct managed by operating system that is kept in main memory. For a process, a pointer to the page table ('''Page-Table Base Register-PTBR''') is stored in a register. Changing page table requires changing only this one register, substantially reducing the context-switch time. (A page table, with virtual page number that is 4 bytes long (32 bits) can point to 2^32 physical page frames. If frame size is 4Kb then a system with 4-byte entries can address 2^44 bytes (or 16 TB) of physical memory).

Llmckee at 01:44, 18 April 2013

2013-04-18T01:44:06Z

← Older revision		Revision as of 01:44, 18 April 2013
Line 70:		Line 70:
	'''Paging''' is a memory-management scheme that permits the physical address space of a process to be non-contiguous. The basic method involves breaking physical memory into fixed-size blocks called frames and breaking the virtual memory into blocks of the same size called pages. When a process is to be executed its pages are loaded into any available memory frames from the backing storage (for example-a hard drive).		'''Paging''' is a memory-management scheme that permits the physical address space of a process to be non-contiguous. The basic method involves breaking physical memory into fixed-size blocks called frames and breaking the virtual memory into blocks of the same size called pages. When a process is to be executed its pages are loaded into any available memory frames from the backing storage (for example-a hard drive).

	[[File:~~Operation of Paging and Translation Lookaside Buffer~~.png?\|400px\|thumb\|right\| Operation of Paging and Translation Lookaside Buffer (TLB) source- Stallings]]		[[File:Operation_of_Paging_and_Translation_Lookaside_Buffer.png?\|400px\|thumb\|right\| Operation of Paging and Translation Lookaside Buffer (TLB) source- Stallings]]

	Each process has a '''page table''' that maintains a mapping of virtual pages to physical pages. A page table is a software construct managed by operating system that is kept in main memory. For a process, a pointer to the page table ('''Page-Table Base Register-PTBR''') is stored in a register. Changing page table requires changing only this one register, substantially reducing the context-switch time. (A page table, with virtual page number that is 4 bytes long (32 bits) can point to 2^32 physical page frames. If frame size is 4Kb then a system with 4-byte entries can address 2^44 bytes (or 16 TB) of physical memory).		Each process has a '''page table''' that maintains a mapping of virtual pages to physical pages. A page table is a software construct managed by operating system that is kept in main memory. For a process, a pointer to the page table ('''Page-Table Base Register-PTBR''') is stored in a register. Changing page table requires changing only this one register, substantially reducing the context-switch time. (A page table, with virtual page number that is 4 bytes long (32 bits) can point to 2^32 physical page frames. If frame size is 4Kb then a system with 4-byte entries can address 2^44 bytes (or 16 TB) of physical memory).

Llmckee at 01:35, 18 April 2013

2013-04-18T01:35:36Z

← Older revision		Revision as of 01:35, 18 April 2013
Line 4:		Line 4:

	writeup page - https://docs.google.com/document/d/19w10zS7_0LQPZsHzV1aXKCCHVddg2kwx5ef-uH5bj7M/edit		writeup page - https://docs.google.com/document/d/19w10zS7_0LQPZsHzV1aXKCCHVddg2kwx5ef-uH5bj7M/edit
			<p>
	previous page - http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_506_Spring_2012/7b_pk		previous page - http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_506_Spring_2012/7b_pk

Line 11:		Line 12:

	{{Sidebar		{{Sidebar
	\| name = ~~{{subst:~~7b}}		\| name = CSC/ECE 506 Spring 2013/7b lm\| outertitle = Useful Definitions
	\| outertitle = Useful Definitions
	\| topimage =		\| topimage =
	\| pretitle =		\| pretitle =

Llmckee: Created page with "
TLB (Translation Lookaside Buffer) Coherence in Multiprocessing
writeup page - https://docs.google.com/document/d/19w10zS7_0LQPZsHzV1aXKCCHVddg2k..."

2013-04-18T01:27:50Z

Created page with "<p><font size="3"> TLB (Translation Lookaside Buffer) Coherence in Multiprocessing </font></p> writeup page - https://docs.google.com/document/d/19w10zS7_0LQPZsHzV1aXKCCHVddg2k..."

Show changes