https://wiki.expertiza.ncsu.edu/api.php?action=feedcontributions&feedformat=atom&user=Ywang50Expertiza_Wiki - User contributions [en]2026-07-13T23:04:04ZUser contributionsMediaWiki 1.41.0https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=62820CSC/ECE 506 Spring 2012/7b yw2012-05-08T03:43:35Z<p>Ywang50: </p>
<hr />
<div>TLB Coherence<br />
--------------------------------------------------------------<br />
<br />
== Introduction ==<br />
--------------------------------------------------------------<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtual Memory ===<br />
--------------------------------------------------------------<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
--------------------------------------------------------------<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Operation diagram of Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
--------------------------------------------------------------<br />
Problems occur when we extend TLB table into multi-processor systems. That is when memory is shared, two processors may have different virtual names for the same block. <br />
<br />
This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data. <br />
<br />
For example, Assume:<br />
* The processor has been running Process 1<br />
* It then switches to Process 2<br />
* Later it switches back to Process 1<br />
<br />
Now Process 2 caches a different copy of the information than Process 1. When Process 2 makes a change, that change is not reflected in Process 1's copy of the information.<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure on the right shows the organization of virtually addressed caches.<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
* Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
<br />
* Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
<br />
* Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
<br />
* Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
<pre><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
</pre><br />
<br />
2. which is(are) true below <br /><br />
<pre><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
</pre><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
<pre><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
</pre><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
<pre><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
</pre><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
<pre><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
</pre><br />
<br />
6. What's the typical function of a TLB in modern microarchitecture? <br /><br />
<br />
7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? <br /><br />
<br />
8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? <br /><br />
<pre><br />
A. Direct-mapped <br /><br />
B. Set-Associative <br /><br />
C. Fully-Associative <br /><br />
D. Non of the above <br /><br />
</pre><br />
<br />
9. What's the main coherence issue discussed in this wiki? <br /><br />
<pre><br />
A. Two physical address share a same virtual address <br /><br />
B. Two virtual addresses share a same physical page <br /><br />
C. Processes might be kicking each others page table off <br /><br />
C. None of the above <br /><br />
</pre><br />
10. According to this wiki, who is running the page table, software or hardware? <br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=60379CSC/ECE 506 Spring 2012/7b yw2012-03-21T15:26:29Z<p>Ywang50: </p>
<hr />
<div>TLB Coherence<br />
--------------------------------------------------------------<br />
<br />
== Introduction ==<br />
--------------------------------------------------------------<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually Memory ===<br />
--------------------------------------------------------------<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
--------------------------------------------------------------<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Operation diagram of Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
--------------------------------------------------------------<br />
Problems occur when we extend TLB table into multi-processor systems. That is when memory is shared, two processors may have different virtual names for the same block. <br />
<br />
This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data. <br />
<br />
For example, Assume:<br />
* The processor has been running Process 1<br />
* It then switches to Process 2<br />
* Later it switches back to Process 1<br />
<br />
Now Process 2 caches a different copy of the information than Process 1. When Process 2 makes a change, that change is not reflected in Process 1's copy of the information.<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure on the right shows the organization of virtually addressed caches.<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
* Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
<br />
* Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
<br />
* Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
<br />
* Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
<pre><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
</pre><br />
<br />
2. which is(are) true below <br /><br />
<pre><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
</pre><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
<pre><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
</pre><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
<pre><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
</pre><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
<pre><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
</pre><br />
<br />
6. What's the typical function of a TLB in modern microarchitecture? <br /><br />
<br />
7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? <br /><br />
<br />
8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? <br /><br />
<pre><br />
A. Direct-mapped <br /><br />
B. Set-Associative <br /><br />
C. Fully-Associative <br /><br />
D. Non of the above <br /><br />
</pre><br />
<br />
9. What's the main coherence issue discussed in this wiki? <br /><br />
<pre><br />
A. Two physical address share a same virtual address <br /><br />
B. Two virtual addresses share a same physical page <br /><br />
C. Processes might be kicking each others page table off <br /><br />
C. None of the above <br /><br />
</pre><br />
10. According to this wiki, who is running the page table, software or hardware? <br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=60378CSC/ECE 506 Spring 2012/7b yw2012-03-21T15:25:24Z<p>Ywang50: </p>
<hr />
<div>TLB Coherence<br />
--------------------------------------------------------------<br />
<br />
== Introduction ==<br />
--------------------------------------------------------------<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually Memory ===<br />
--------------------------------------------------------------<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
--------------------------------------------------------------<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Operation diagram of Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
--------------------------------------------------------------<br />
Problems occur when we extend TLB table into multi-processor systems. That is when memory is shared, two processors may have different virtual names for the same block. <br />
<br />
This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data. <br />
<br />
For example, Assume:<br />
* The processor has been running Process 1<br />
* It then switches to Process 2<br />
* Later it switches back to Process 1<br />
<br />
Now Process 2 caches a different copy of the information than Process 1. When Process 2 makes a change, that change is not reflected in Process 1's copy of the information.<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure on the right shows the organization of virtually addressed caches.<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
<br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
<br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
<br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
<pre><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
</pre><br />
<br />
2. which is(are) true below <br /><br />
<pre><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
</pre><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
<pre><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
</pre><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
<pre><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
</pre><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
<pre><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
</pre><br />
<br />
6. What's the typical function of a TLB in modern microarchitecture? <br /><br />
<br />
7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? <br /><br />
<br />
8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? <br /><br />
<pre><br />
A. Direct-mapped <br /><br />
B. Set-Associative <br /><br />
C. Fully-Associative <br /><br />
D. Non of the above <br /><br />
</pre><br />
<br />
9. What's the main coherence issue discussed in this wiki? <br /><br />
<pre><br />
A. Two physical address share a same virtual address <br /><br />
B. Two virtual addresses share a same physical page <br /><br />
C. Processes might be kicking each others page table off <br /><br />
C. None of the above <br /><br />
</pre><br />
10. According to this wiki, who is running the page table, software or hardware? <br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=60377CSC/ECE 506 Spring 2012/7b yw2012-03-21T15:22:46Z<p>Ywang50: </p>
<hr />
<div>TLB Coherence<br />
--------------------------------------------------------------<br />
<br />
== Introduction ==<br />
--------------------------------------------------------------<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually Memory ===<br />
--------------------------------------------------------------<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
--------------------------------------------------------------<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Operation diagram of Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
--------------------------------------------------------------<br />
Problems occur when we extend TLB table into multi-processor systems. That is when memory is shared, two processors may have different virtual names for the same block. <br />
<br />
This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data. <br />
<br />
For example, Assume:<br />
* The processor has been running Process 1<br />
* It then switches to Process 2<br />
* Later it switches back to Process 1<br />
<br />
Now Process 2 caches a different copy of the information than Process 1. When Process 2 makes a change, that change is not reflected in Process 1's copy of the information.<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure on the right shows the organization of virtually addressed caches.<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
<pre><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
</pre><br />
<br />
2. which is(are) true below <br /><br />
<pre><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
</pre><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
<pre><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
</pre><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
<pre><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
</pre><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
<pre><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
</pre><br />
<br />
6. What's the typical function of a TLB in modern microarchitecture? <br /><br />
<br />
7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? <br /><br />
<br />
8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? <br /><br />
<pre><br />
A. Direct-mapped <br /><br />
B. Set-Associative <br /><br />
C. Fully-Associative <br /><br />
D. Non of the above <br /><br />
</pre><br />
<br />
9. What's the main coherence issue discussed in this wiki? <br /><br />
<pre><br />
A. Two physical address share a same virtual address <br /><br />
B. Two virtual addresses share a same physical page <br /><br />
C. Processes might be kicking each others page table off <br /><br />
C. None of the above <br /><br />
</pre><br />
10. According to this wiki, who is running the page table, software or hardware? <br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=60376CSC/ECE 506 Spring 2012/7b yw2012-03-21T15:20:58Z<p>Ywang50: </p>
<hr />
<div>TLB Coherence<br />
--------------------------------------------------------------<br />
<br />
== Introduction ==<br />
--------------------------------------------------------------<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually Memory ===<br />
--------------------------------------------------------------<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
--------------------------------------------------------------<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
--------------------------------------------------------------<br />
Problems occur when we extend TLB table into multi-processor systems. That is when memory is shared, two processors may have different virtual names for the same block. <br />
<br />
This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data. <br />
<br />
For example, Assume:<br />
* The processor has been running Process 1<br />
* It then switches to Process 2<br />
* Later it switches back to Process 1<br />
<br />
Now Process 2 caches a different copy of the information than Process 1. When Process 2 makes a change, that change is not reflected in Process 1's copy of the information.<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure on the right shows the organization of virtually addressed caches.<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
<pre><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
</pre><br />
<br />
2. which is(are) true below <br /><br />
<pre><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
</pre><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
<pre><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
</pre><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
<pre><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
</pre><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
<pre><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
</pre><br />
<br />
6. What's the typical function of a TLB in modern microarchitecture? <br /><br />
<br />
7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? <br /><br />
<br />
8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? <br /><br />
<pre><br />
A. Direct-mapped <br /><br />
B. Set-Associative <br /><br />
C. Fully-Associative <br /><br />
D. Non of the above <br /><br />
</pre><br />
<br />
9. What's the main coherence issue discussed in this wiki? <br /><br />
<pre><br />
A. Two physical address share a same virtual address <br /><br />
B. Two virtual addresses share a same physical page <br /><br />
C. Processes might be kicking each others page table off <br /><br />
C. None of the above <br /><br />
</pre><br />
10. According to this wiki, who is running the page table, software or hardware? <br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=60375CSC/ECE 506 Spring 2012/7b yw2012-03-21T15:16:47Z<p>Ywang50: </p>
<hr />
<div>TLB Coherence<br />
--------------------------------------------------------------<br />
<br />
== Introduction ==<br />
--------------------------------------------------------------<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually Memory ===<br />
--------------------------------------------------------------<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
--------------------------------------------------------------<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
--------------------------------------------------------------<br />
Problems occur when we extend TLB table into multi-processor systems. That is when memory is shared, two processors may have different virtual names for the same block. <br />
<br />
[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data. <br />
<br />
For example, Assume:<br />
* The processor has been running Process 1<br />
* It then switches to Process 2<br />
* Later it switches back to Process 1<br />
<br />
Now Process 2 caches a different copy of the information than Process 1. When Process 2 makes a change, that change is not reflected in Process 1's copy of the information.<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure on the right shows the organization of virtually addressed caches.<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
<pre><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
</pre><br />
<br />
2. which is(are) true below <br /><br />
<pre><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
</pre><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
<pre><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
</pre><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
<pre><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
</pre><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
<pre><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
</pre><br />
<br />
6. What's the typical function of a TLB in modern microarchitecture? <br /><br />
<br />
7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? <br /><br />
<br />
8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? <br /><br />
<pre><br />
A. Direct-mapped <br /><br />
B. Set-Associative <br /><br />
C. Fully-Associative <br /><br />
D. Non of the above <br /><br />
</pre><br />
<br />
9. What's the main coherence issue discussed in this wiki? <br /><br />
<pre><br />
A. Two physical address share a same virtual address <br /><br />
B. Two virtual addresses share a same physical page <br /><br />
C. Processes might be kicking each others page table off <br /><br />
C. None of the above <br /><br />
</pre><br />
10. According to this wiki, who is running the page table, software or hardware? <br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=60374CSC/ECE 506 Spring 2012/7b yw2012-03-21T15:15:33Z<p>Ywang50: </p>
<hr />
<div>== Introduction ==<br />
--------------------------------------------------------------<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually Memory ===<br />
--------------------------------------------------------------<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
--------------------------------------------------------------<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
--------------------------------------------------------------<br />
Problems occur when we extend TLB table into multi-processor systems. That is when memory is shared, two processors may have different virtual names for the same block. <br />
<br />
[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data. <br />
<br />
For example, Assume:<br />
* The processor has been running Process 1<br />
* It then switches to Process 2<br />
* Later it switches back to Process 1<br />
<br />
Now Process 2 caches a different copy of the information than Process 1. When Process 2 makes a change, that change is not reflected in Process 1's copy of the information.<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure on the right shows the organization of virtually addressed caches.<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
<pre><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
</pre><br />
<br />
2. which is(are) true below <br /><br />
<pre><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
</pre><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
<pre><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
</pre><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
<pre><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
</pre><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
<pre><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
</pre><br />
<br />
6. What's the typical function of a TLB in modern microarchitecture? <br /><br />
<br />
7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? <br /><br />
<br />
8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? <br /><br />
<pre><br />
A. Direct-mapped <br /><br />
B. Set-Associative <br /><br />
C. Fully-Associative <br /><br />
D. Non of the above <br /><br />
</pre><br />
<br />
9. What's the main coherence issue discussed in this wiki? <br /><br />
<pre><br />
A. Two physical address share a same virtual address <br /><br />
B. Two virtual addresses share a same physical page <br /><br />
C. Processes might be kicking each others page table off <br /><br />
C. None of the above <br /><br />
</pre><br />
10. According to this wiki, who is running the page table, software or hardware? <br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=60373CSC/ECE 506 Spring 2012/7b yw2012-03-21T15:14:41Z<p>Ywang50: </p>
<hr />
<div>== Introduction ==<br />
--------------------------------------------------------------<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually Memory ===<br />
--------------------------------------------------------------<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
--------------------------------------------------------------<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
<br />
Problems occur when we extend TLB table into multi-processor systems. That is when memory is shared, two processors may have different virtual names for the same block. <br />
<br />
[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data. <br />
<br />
For example, Assume:<br />
* The processor has been running Process 1<br />
* It then switches to Process 2<br />
* Later it switches back to Process 1<br />
<br />
Now Process 2 caches a different copy of the information than Process 1. When Process 2 makes a change, that change is not reflected in Process 1's copy of the information.<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure on the right shows the organization of virtually addressed caches.<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
<pre><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
</pre><br />
<br />
2. which is(are) true below <br /><br />
<pre><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
</pre><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
<pre><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
</pre><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
<pre><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
</pre><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
<pre><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
</pre><br />
<br />
6. What's the typical function of a TLB in modern microarchitecture? <br /><br />
<br />
7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? <br /><br />
<br />
8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? <br /><br />
<pre><br />
A. Direct-mapped <br /><br />
B. Set-Associative <br /><br />
C. Fully-Associative <br /><br />
D. Non of the above <br /><br />
</pre><br />
<br />
9. What's the main coherence issue discussed in this wiki? <br /><br />
<pre><br />
A. Two physical address share a same virtual address <br /><br />
B. Two virtual addresses share a same physical page <br /><br />
C. Processes might be kicking each others page table off <br /><br />
C. None of the above <br /><br />
</pre><br />
10. According to this wiki, who is running the page table, software or hardware? <br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=60372CSC/ECE 506 Spring 2012/7b yw2012-03-21T15:13:22Z<p>Ywang50: </p>
<hr />
<div>== Introduction ==<br />
<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually Memory ===<br />
<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
<br />
Problems occur when we extend TLB table into multi-processor systems. That is when memory is shared, two processors may have different virtual names for the same block. <br />
<br />
[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data. <br />
<br />
For example, Assume:<br />
* The processor has been running Process 1<br />
* It then switches to Process 2<br />
* Later it switches back to Process 1<br />
<br />
Now Process 2 caches a different copy of the information than Process 1. When Process 2 makes a change, that change is not reflected in Process 1's copy of the information.<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
Figure on the right shows the organization of virtually addressed caches.<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
<pre><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
</pre><br />
<br />
2. which is(are) true below <br /><br />
<pre><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
</pre><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
<pre><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
</pre><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
<pre><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
</pre><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
<pre><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
</pre><br />
<br />
6. What's the typical function of a TLB in modern microarchitecture? <br /><br />
<br />
7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? <br /><br />
<br />
8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? <br /><br />
<pre><br />
A. Direct-mapped <br /><br />
B. Set-Associative <br /><br />
C. Fully-Associative <br /><br />
D. Non of the above <br /><br />
</pre><br />
<br />
9. What's the main coherence issue discussed in this wiki? <br /><br />
<pre><br />
A. Two physical address share a same virtual address <br /><br />
B. Two virtual addresses share a same physical page <br /><br />
C. Processes might be kicking each others page table off <br /><br />
C. None of the above <br /><br />
</pre><br />
10. According to this wiki, who is running the page table, software or hardware? <br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=60371CSC/ECE 506 Spring 2012/7b yw2012-03-21T14:46:27Z<p>Ywang50: </p>
<hr />
<div>== Introduction ==<br />
<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually addressed caches ===<br />
<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
<br />
Problems occur when we extend TLB table into multi-processor systems. That is when memory is shared, two processors may have different virtual names for the same block. <br />
<br />
[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data. <br />
<br />
For example, Assume:<br />
* The processor has been running Process 1<br />
* It then switches to Process 2<br />
* Later it switches back to Process 1<br />
<br />
Now Process 2 caches a different copy of the information than Process 1. When Process 2 makes a change, that change is not reflected in Process 1's copy of the information.<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure shows the organization of virtually addressed caches.<br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
<pre><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
</pre><br />
<br />
2. which is(are) true below <br /><br />
<pre><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
</pre><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
<pre><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
</pre><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
<pre><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
</pre><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
<pre><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
</pre><br />
<br />
6. What's the typical function of a TLB in modern microarchitecture? <br /><br />
<br />
7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? <br /><br />
<br />
8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? <br /><br />
<pre><br />
A. Direct-mapped <br /><br />
B. Set-Associative <br /><br />
C. Fully-Associative <br /><br />
D. Non of the above <br /><br />
</pre><br />
<br />
9. What's the main coherence issue discussed in this wiki? <br /><br />
<pre><br />
A. Two physical address share a same virtual address <br /><br />
B. Two virtual addresses share a same physical page <br /><br />
C. Processes might be kicking each others page table off <br /><br />
C. None of the above <br /><br />
</pre><br />
10. According to this wiki, who is running the page table, software or hardware? <br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=60370CSC/ECE 506 Spring 2012/7b yw2012-03-21T14:44:23Z<p>Ywang50: </p>
<hr />
<div>== Introduction ==<br />
<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually addressed caches ===<br />
<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
<br />
Problems occur when we extend TLB table into multi-processor systems. That is when memory is shared, two processors may have different virtual names for the same block. <br />
<br />
[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data. <br />
<br />
For example, Assume:<br />
* The processor has been running Process 1<br />
* It then switches to Process 2<br />
* Later it switches back to Process 1<br />
<br />
Now Process 2 caches a different copy of the information than Process 1. When Process 2 makes a change, that change is not reflected in Process 1's copy of the information.<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure shows the organization of virtually addressed caches.<br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
<pre><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
</pre><br />
<br />
2. which is(are) true below <br /><br />
<pre><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
</pre><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
<pre><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
</pre><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
<pre><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
</pre><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
<pre><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
</pre><br />
<br />
6. What's the typical function of a TLB in modern microarchitecture? <br /><br />
<br />
7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? <br /><br />
<br />
8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? <br /><br />
<pre><br />
A. Direct-mapped <br /><br />
B. Set-Associative <br /><br />
C. Fully-Associative <br /><br />
D. Non of the above <br /><br />
</pre><br />
<br />
9. What's the main coherence issue discussed in this wiki? <br /><br />
<pre><br />
A. Two physical address share a same virtual address <br /><br />
B. Two virtual addresses share a same physical page <br /><br />
C. Processes might be kicking each others page table off <br /><br />
C. None of the above <br /><br />
</pre><br />
10. According to this wiki, who is running the page table, software or hardware? <br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=59751CSC/ECE 506 Spring 2012/7b yw2012-03-18T23:53:43Z<p>Ywang50: </p>
<hr />
<div>== Introduction ==<br />
<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually addressed caches ===<br />
<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]<br />
<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure shows the organization of virtually addressed caches.<br />
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.[[File:yw3.jpg|200px|thumb|right|TLB shootdown latency <ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
<br />
2. which is(are) true below <br /><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=File:Yw3.jpg&diff=59747File:Yw3.jpg2012-03-18T23:41:21Z<p>Ywang50: </p>
<hr />
<div></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=File:Yw2.jpg&diff=59746File:Yw2.jpg2012-03-18T23:41:14Z<p>Ywang50: </p>
<hr />
<div></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=File:Yw1.jpg&diff=59745File:Yw1.jpg2012-03-18T23:40:32Z<p>Ywang50: </p>
<hr />
<div></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=59744CSC/ECE 506 Spring 2012/7b yw2012-03-18T23:38:48Z<p>Ywang50: </p>
<hr />
<div>== Introduction ==<br />
<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually addressed caches ===<br />
<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
<br />
[[Image:tlbOP.PNG|thumbnail|right|200px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
[[File:yw1.jpg|200px|thumb|right|<ref>lec15 from NCSU ECE506</ref>]]<br />
<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure shows the organization of virtually addressed caches.<br />
[[File:yw2.jpg|200px|thumb|right|<ref>lec15 from NCSU ECE506</ref>]]<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.[[File:yw3.jpg|200px|thumb|right|<ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
<br />
2. which is(are) true below <br /><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/7b_yw&diff=59743CSC/ECE 506 Spring 2012/7b yw2012-03-18T23:37:50Z<p>Ywang50: </p>
<hr />
<div>== Introduction ==<br />
<br />
In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addressed caches are discussed. Then we discuss the need for TLB, a cache-like construct that translate virtual address to physical address. Then we raise the issue of TLB coherence. <br />
<br />
=== Virtually addressed caches ===<br />
<br />
Virtual memory is a memory management technology developed for multithread operating systems. This technique virtualizes a computer architecture's various forms of computer data storage (such as random-access memory and disk storage), allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which behaves like directly addressable read/write memory (RAM). <br />
<br />
[[Image:virtualM.PNG|thumbnail|right|600px|Virtual Memory in modern computer systems<sup><span id="3body"></span></sup>]]<br />
<br />
This technique greatly simplifies programmers job because modern operating system runs each process on its own dedicated virtual memory space. Thus each program runs as if it has the sole access of the virtual memory. In this way, programmers don't have to worry about how operating system switches between processes or how other process operates. Also, Virtual memory makes application programming easier by hiding fragmentation of physical memory; by delegating to the kernel the burden of managing the memory hierarchy (eliminating the need for the program to handle overlays explicitly); and, when each process is run in its own dedicated address space, by obviating the need to relocate program code or to access memory with relative addressing.<br />
<br />
The introducing of virtual memory raise the problem of translating virtual address to physical address since we need physical address to access the actual content stored in cache. And that's where Translation Lookaside Buffer comes into use.<br />
<br />
=== What is TLB ===<br />
<br />
A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. The virtual memory is the space seen from a process. This space is segmented in pages of a prefixed size. The page table (generally loaded in memory) keeps track of where the virtual pages are loaded in the physical memory. The TLB is a cache of the page table; that is, only a subset of its content are stored.<br />
The TLB references physical memory addresses in its table. It may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi-level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation and the resulting physical address is sent to the cache. There are pros and cons to both implementations. Caches that use virtual addressing have for their key part of the virtual address plus, optionally, a key called an "address space identifier" (ASID). Caches that don't have ASIDs must be flushed every context switch in a multiprocessing environment.<br />
In a Harvard architecture or hybrid thereof, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type.<br />
A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. The low-order bits of any virtual address (e.g., in a virtual memory system having 4 KB pages, the lower 12 bits of the virtual address) represent the offset of the desired address within the page, and thus they do not change in the virtual-to-physical translation. During a cache access, two steps are performed: an index is used to find an entry in the cache's data store, and then the tags for the cache line found are compared. If the cache is structured in such a way that it can be indexed using only the bits that do not change in translation, the cache can perform its "index" operation while the TLB translates the upper bits of the address. Then, the translated address from the TLB is passed to the cache. The cache performs a tag comparison to determine if this access was a hit or miss. It is possible to perform the TLB lookup in parallel with the cache access even if the cache must be indexed using some bits that may change upon address translation; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.<br />
<br />
[[Image:tlb.PNG|thumbnail|right|600px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
And here is generally how a typical TLB is working. Note that X is the virtual page number to be translated into a physical page number, X' is the Physical number corresponding to X. and V is the Virtual page number of a victim page(that is a page to be kicked off the table). <br />
<br />
<br />
[[Image:tlbOP.PNG|thumbnail|right|600px|Translation Lookaside Buffer<sup><span id="3body"></span></sup>]]<br />
<br />
<br />
Next in this chapter we are going to discuss problems that are going to occur when we extend this TLB structure to multi-processor systems. The solution to these problems is presented in next chapter.<br />
<br />
=== TLB Coherence issues ===<br />
<br />
<br />
==Solutions==<br />
--------------------------------------------------------------<br />
In this section, we will talk about several solutions to handle TLB coherence problem. We will focus most on the last approach - TLB shootdown - a commonlly used software approach to enforce TLB coherence. Some other approaches will be briefly introduced. <br />
<br />
===Virtually addressed caches===<br />
--------------------------------------------------------------<br />
<br />
This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem. <br />
<br />
When virtually addressed cache is used, address translations only happen when there is a cache miss. Since it is not frequently to access page mappings, we do not need to use TLB any more. Figure shows how virtually addressed cache works.<br />
[[File:yw1.jpg|200px|thumb|right|<ref>lec15 from NCSU ECE506</ref>]]<br />
<br />
<br />
The key distinction between virtually and physically addressed caches is that Virtually addressed caches are indexed using part of a virtual address rather than a physical address. Virtually addressed caches offer potentially faster access times by avoiding the delay associated with address translation. <ref>the effects of virtually addressed caches on virtual memory design and performance JonInouye - et al.</ref><br />
<br />
Figure shows the organization of virtually addressed caches.<br />
[[File:yw2.jpg|200px|thumb|right|<ref>lec15 from NCSU ECE506</ref>]]<br />
<br />
From the figure “ASID” means “address-space identifier,” which is often called a process identifier (PID) in some books. The diagram shows the “V-index” overlapping the (virtual) page number. If not, we wouldn’t need a virtually addressed cache. We could do address translation in parallel with cache access with a physically addressed cache. Also the V-index actually does not stored in the cache. Like the index (“set” or “line”) field in physically addressed caches, it is not stored, but just tells what line or set to look in for the data<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Given the virtually addressed cache which can help us get rid of TLB, problems of coherent still exist to some level. Swap-out and protection information(read or read/write) coherent still need to be enforced. However, since there is no TLB, such information is stored in cache, the coherence problem will be handled by cache-coherence hardware.<br />
<br />
=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===<br />
--------------------------------------------------------------<br />
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.<br />
<br />
This instruction broadcasts the page address on the bus so that the snooping hardware on other processors can automatically invalidate the corresponding TLB entries without interrupting the processor.<br />
<br />
A processor simply issues a TLB_invalidate_entry instruction immediately after changing a page-table entry. This works well on a shared-bus system; if two processors change the same entry at the same time, only one change can be broadcast first on the bus.<br />
<br />
===TLB shootdown===<br />
--------------------------------------------------------------<br />
====General Concept====<br />
TLB shootdown is another approach to enforce TLB coherence. It is a software approach using inter-processor interrupts. Also, it is a very common technique to enforce TLB coherence. How it works? In general, when a processor changes a TLB entry, it will make the other processors which contain the same TLB entries to invalidate their copies. A quick example as below may explain it more clearly.<br />
<br />
Assuming you have some memory shared by all of the processors in your system. One of your processors restricts access to a page of that shared memory now, all of the processors have to flush their TLBs, so that the ones that aren't allowed to access that page can't do so anymore.The actions of one processor causing the TLBs to be flushed on other processors is what is called a TLB shootdown<ref>http://stackoverflow.com/questions/3748384/what-is-tlb-shootdown</ref>.<br />
<br />
====Detailed Steps====<br />
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.<br />
<br />
Step 1. A processor p that wants to modify a page table disables inter-processor interrupts and locks the page table. It also clears its active flag, which indicates whether it is actively using any page table.<br />
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.<br />
Step 3. Each processor that receives the interrupt clears its active flag.<br />
Step 4. Processor p busy-waits till the active flags of all interrupted processors are clear, then modifies the page table. Processor p then releases the page-table lock, sets its active flag, and resumes execution.<br />
Step 5. Each interrupted processor busy-waits until none of the page tables it is using are locked. After executing the required TLB actions and setting its active flag, it resumes execution.<br />
<br />
====Example====<br />
An example of TLB shootdown solution is the one described in Mach VM System. In this module, when an action may potentially cause TLB inconsistency, it will invoke the shootdown algorithm. The algorithm proceeds in four phases after it is invoked<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>. <br />
<br />
1 Initiator: The initiator queues consistency action requests for all processors using the pmap and sets their “action needed” flags. It then sends interrupts to the processors and waits for responses. <br />
2 Responders: Each responder receives its interrupt and removes itself from the set of active processors to acknowledge the interrupt. The responders then spin until the initiator completes its changes to pmap. (This spinning is necessary to ensure that responders neither read nor write the pmap while the update is in progress.) <br />
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done. <br />
4 Responders: The responders perform their required TLB invalidations after the pmap is unlocked and dequeue the corresponding actions. They also clear their “action needed” flags and rejoin the set of active processors.<br />
<br />
The Pseudo-Code of Mach Shootdown Algorithm is as below<ref>Translation Look aside Buffer Consistency: A Software Approach, David L. Black - et al. 1989</ref>.<br />
<br />
<pre><br />
Initiator: <br />
s = disable_interrupts(); <br />
active[mycpul = FALSE; <br />
lockgmap(pmap); <br />
if (inconsistent TLB may result) { <br />
if (pmap->in-uselmycpul) { <br />
invalidate-tlb(pmap,start,end); <br />
}<br />
/* Phase 1 */ <br />
if (other cpus using pmap) {<br />
list_type shoot-list = EMPTY-LIST; <br />
for (every cpu in system) {<br />
if (pmap->in-uselcpul && cpu != mycpu) {<br />
lock-action-structure(cpu): <br />
queue_action(cpu,pmap,start,end); <br />
action-neededlcpul = TRUE; <br />
unlock-action-structure(cpu); <br />
if (idle[cpul == FALSE) { <br />
add cpu to shoot-list <br />
}<br />
}<br />
}<br />
for (every cpu on shoot-list) { <br />
send-shootdown-interrupt(cpu); <br />
}<br />
for (every cpu on shoot-list) { <br />
while (activelcpul && pmap->in-uselcpul) {<br />
pmap->in_use[cpu]){<br />
/* spin */ ; <br />
}<br />
}<br />
}<br />
} <br />
<br />
/* Phase 3 */ <br />
make changes to physical map <br />
<br />
unlock-pmap(pmap); <br />
active[mycpu] = TRUE; <br />
restore-interrupt-state(s); <br />
<br />
Responders: /* Phase 2 */ <br />
s = disable-interrupts(); <br />
while (action-needed[mycpu]) {<br />
active[mycpu] = FALSE; <br />
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu))) <br />
/* spin */ ; <br />
<br />
/* Phase 4 */ <br />
lock-action-structure(mycpu); <br />
process-queuedactions(mycpu); <br />
action-neededlmycpul = FALSE; <br />
unlock-action-structure(mycpu); <br />
active[mycpu] = TRUE; <br />
}<br />
restore-interrupt-state(s); <br />
<br />
</pre><br />
<br />
====Performance Analysis====<br />
Apparently, as number of processors increases, the overhead of this approach scales linearly. Because number of interprocessors interrupts invoked will be O(n) to the number of processors. <br />
<br />
Figure indicates the latency increases linearly as number of cores goes up.[[File:yw3.jpg|200px|thumb|right|<ref>UNified Instruction/Translation/Data (UNITD) Coherence: One Protocol to Rule Them All - Bogdan F. Romanescu et al.</ref>]]<br />
<br />
===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===<br />
--------------------------------------------------------------<br />
1. Modified TLB shootdown<br />
Overhead is the same as for TLB shootdown with two exceptions: Interrupted processors are not idled, and their participation is small and possibly constant. Page-table modification and use are not serialized.<br />
<br />
2. Lazy devaluation<br />
The counter is updated on each TLB reload, invalidation, and replacement. When an unsafe change cannot be postponed, overhead is the same as for TLB shootdown.<br />
<br />
3. Validation<br />
Memory requests contain a generation count. The modifying processor updates the generation count. An extra network trip is needed when a stale TLB entry is used. Overhead also includes a solution to the generation-count wraparound problem.<br />
<br />
==Summary==<br />
--------------------------------------------------------------<br />
<br />
The main goal of multiprocessor is to increase the execution speed. While enforcing the TLB coherent, we should well understand the trade-off of different approaches. Some of the approaches require specific hardware and others(like shootdown) don't. Actually, in real design, it is difficult to conclude which solution will be better, it all depends on what applications running in what kind of environment.<br />
<br />
<br />
==Quiz==<br />
--------------------------------------------------------------<br />
1. Which below is(are) solution(s) to TLB coherence problem <br /><br />
A. MESI protocol<br /><br />
B. TLB shootdown<br /><br />
C. using virtually addressed cache<br /><br />
D. all of above<br /><br />
<br />
2. which is(are) true below <br /><br />
A. TLB shootdown is a software approach<br /><br />
B. using virually addressed cache will decrease cache misses<br /><br />
C. PowerPC has a unique instruction to handle TLB coherence problem<br /><br />
D. TLB is shared by different processors<br /><br />
<br />
3. what is(are) step(s) of TLB shootdown <br /><br />
A. Locks the page table<br /><br />
B. Busy-wait the other processors to inactivate the flags<br /><br />
C. Send interrupt signal<br /><br />
D. Release Locks<br /><br />
<br />
4. Which is(are) incorrect about virtually addressed caches <br /><br />
A. It can be used to decrease the frequency to access map table <br /><br />
B. It can only addressed by virtual address <br /><br />
C. V-index should overlap the page number <br /><br />
D. V-index number is stored in the cache <br /><br />
<br />
5. Which is the correct order of phases in shootdown algorithm <br /><br />
A. responders initiators responders initiators <br /><br />
B. initiators initiators responders responders <br /><br />
C. initiators responders initiators responders <br /><br />
D. responders responders initiators initiators<br /><br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=ECE506_Main_Page&diff=59665ECE506 Main Page2012-03-18T19:17:31Z<p>Ywang50: </p>
<hr />
<div>This page serves as a portal for all wiki material related to CSC506 and ECE506. Link to any new wiki pages from this page, and add links to any current pages.<br />
<br />
=Supplements to Solihin Text=<br />
<br />
Post links to the textbook supplements in this section.<br />
*Chapter 2 [[CSC/ECE 506 Spring 2011/ch2 dm | CSC/ECE 506 Spring 2011/ch2 dm]]<br />
*Chapter 2 [[Parallel_Programming_Models | Parallel Programming Models]]<br />
*Chapter 2 (Still being revised) [[CSC/ECE 506 Spring 2011/ch2 cl | CSC/ECE 506 Spring 2011/ch2 cl]]<br />
*Chapter 2a [[ CSC/ECE 506 Spring 2011/ch2a mc | Current Data-Parallel Architectures ]]<br />
*Chapter 2a [[ CSC/ECE 506 Spring_2012/2a va ]]<br />
*Chapter 2b [[CSC/ECE 506 Spring 2012/ch2b cm | CSC/ECE 506 Spring 2012/ch2b cm]]<br />
*Chapter 2b [[ECE506_CSC/ECE_506_Spring_2012/2b_az | CSC/ECE 506 Spring 2012/2b az - Data-Parallel Processing with the AMD HD 6900 Series Graphics Processing Unit]]<br />
*Chapter 3 (Final Revision) [[ CSC/ECE 506 Spring 2011/ch3 ab | Parallel Architecture Mechanisms and Programming Models ]]<br />
*Chapter 4a[[ CSC/ECE 506 Spring 2011/ch4a ob | Parallelization of Nelder Mead Algorithm ]]<br />
*Chapter 4a (Under Construction) [[ CSC/ECE_506_Spring_2011/ch4a_bm | Parallelization of Algorithms ]]<br />
*Chapter 4a [[ CSC/ECE 506 Spring 2011/ch4a zz | CSC/ECE 506 Spring 2011/ch4a zz ]]<br />
*Chapter 4b [[Chapter 4b CSC/ECE 506 Spring 2011 / ch4b]]<br />
*Chapter 5a [[ CSC/ECE 506 Spring 2012/ch5a ja | CSC/ECE 506 Spring 2012/ch5a ja ]]<br />
*Chapter 6a (Under Construction) [[ CSC/ECE 506 Spring 2011/ch6a jp | CSC/ECE 506 Spring 2011/ch6a jp ]]<br />
*Chapter 6a (Under Construction) [[ CSC/ECE 506 Spring 2011/ch6a ep | CSC/ECE 506 Spring 2011/ch6a ep ]]<br />
*Chapter 6b (Ready for First Review) [[CSC/ECE 506 Spring 2011/ch6b ab | CSC/ECE 506 Spring 2011/ch6b ab]]<br />
*Chapter 7 (Under Construction) [[CSC/ECE 506 Spring 2011/ch7 jp | CSC/ECE 506 Spring 2011/ch7 jp]]<br />
*Chapter 8 [[CSC/ECE 506 Spring 2011/ch8 mc | CSC/ECE 506 Spring 2011/ch8 mc]]<br />
*Chapter 10 (Under Construction) [[CSC/ECE 506 Spring 2011/ch10 sb | CSC/ECE 506 Spring 2011/ch10 sb]]<br />
*Chapter 10a [[CSC/ECE_506_Spring_2011/ch10a_dc | CSC/ECE_506_Spring_2011/ch10a_dc]]<br />
*Chapter 11 [[CSC/ECE_506_Spring_2011/ch11_BB_EP | Chapter 11 Supplement]]<br />
*Chapter 11 [[Scalable_Coherent_Interface | SCI (Scalable Coherent Interface) ]]<br />
*Chapter 12 [[ CSC/ECE 506 Spring 2011/ch12 ob | Interconnection Network Topologies and Routing Algorithms]]<br />
*Chapter 12 (Ready for Final Review) [[ CSC/ECE 506 Spring 2011/ch12 aj | Interconnection Network Topologies and Routing Algorithms]]<br />
*Chapter 12 [[ CSC/ECE 506 Spring 2011/ch12 | Interconnection Network Topologies]]<br />
*[[CSC/ECE 506 Spring 2012/1a ry]]<br />
*[[CSC/ECE 506 Spring 2012/1c dm]]<br />
*[[CSC/ECE 506 Spring 2012/1c cl]]<br />
*[[CSC/ECE 506 Spring 2012/1a mw]]<br />
*[[CSC/ECE 506 Spring 2012/3a yw]]<br />
*[[CSC/ECE 506 Spring 2012/7b yw]]<br />
*[[CSC/ECE 506 Spring 2012/3b sk]]<br />
*[[CSC/ECE 506 Spring 2012/4b rs]]<br />
*[[CSC/ECE 506 Spring 2012/6b am]]<br />
*[[CSC/ECE 506 Spring 2012/8a cj]]<br />
*[[CSC/ECE 506 Spring 2010/8a fu]]<br />
*[[CSC/ECE 506 Spring 2010/8a sk]]</div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_506_Spring_2012/3a_yw&diff=58364CSC/ECE 506 Spring 2012/3a yw2012-02-12T00:38:14Z<p>Ywang50: </p>
<hr />
<div>Patterns of Parallel Programming<br />
--------------------------------------------------------------<br />
<br />
<br />
==Introduction==<br />
--------------------------------------------------------------<br />
<br />
<br />
The trend in general purpose microprocessor design has shifted from single-core to chip multiprocessor. The theoretical performance of a multi-core processor is much higher than that of a single-core processor running at similar clock speed. However, despite the rapid advances in hardware performance, the full potential of processing power is not being exploited in the community for one clear reason: difficulty of designing parallel software. <ref>http://www.cs.uiuc.edu/homes/snir/PPP/patterns/concerns.pdf</ref> Parallel programming requires much more effort than serial programming because the programmers need to find the parallelism that exists in an algorithm, and figure out a way to distribute the workload across multiple processors and still get the same result as the serial program. This turned out to be a difficult task. Identifying tasks, designing parallel algorithm, and managing the load balance among many processors has been a daunting task for novice programmers, and even the experienced programmers are often trapped with design decisions that result in suboptimal performance. <ref>http://www.cs.uiuc.edu/homes/snir/PPP/patterns/concerns.pdf</ref> Therefore, to make parallel programming easier for programmers, several common design patterns have been identified over the last decade.<br />
<br />
What is a design pattern? It can be defined as quality description of problem and solution to a frequently occuring problem in some domain. <ref>http://www.cs.uiuc.edu/homes/snir/PPP/patterns/patterns.ppt</ref> In the area of parallel programming, design patterns refer to the definition, solution and guidelines for common parallelization problems. Such pattern can take the form of templates in software tools, written paragraphs with detailed description, or charts, diagrams and examples.<ref>http://www.cs.uiuc.edu/homes/snir/PPP/patterns/concerns.pdf</ref> Design patterns implement various types of common process structures and interactions found in parallel systems, but with the key components - the application-specific procedures - unspecified. <ref>http://www.cs.uiuc.edu/homes/snir/PPP/skeleton/dpndp.pdf</ref><br />
<br />
===A Sample Pattern===<br />
Let's take a look at an example below. Although the example is not related to parallel programming, it gives you a general idea about what exactly a pattern is, which is helpful for understanding the parallel programming patterns we are going to describe in the following sections.<br />
[[File:Fig1-lunchpattern.jpg|200px|thumb|right|<ref>http://www.cs.uiuc.edu/homes/snir/PPP/patterns/patterns.ppt</ref>]]<br />
The example describes a lunch pattern. As seen from the figure, a pattern is usually made up of definition, driving forces, solution, benefits, difficulties and related patterns. We will follow this format to describe some of the parallel design patterns. <br />
<br />
<br />
==Why Do We Need Parallel Programming Patterns?==<br />
--------------------------------------------------------------<br />
<br />
To fully exploit the performance of parallel hardware, programmers need to design their programs in a totally different manner than serial code. This turned out to be a difficult task. The design patterns will guide the programmers systematically to achieve optimal parallel performance by providing them with the framework of parallel programs. The patterns are abstractions of commonly occuring structures and communication characteristics of parallel applications. Programmers just need to fill in their application specific procedures in these patterns, which enables them to develop parallel codes in a faster and easier manner. Also, using the patterns are likely to guarantee the correct operation of parallel application, since the data structures and communication handling codes are well tested. <ref>http://www.cs.uiuc.edu/homes/snir/PPP/skeleton/dpndp.pdf</ref><br />
<br />
<br />
==Common Parallel Programming Patterns==<br />
--------------------------------------------------------------<br />
<br />
In this section, we present a number of commonly used parallel programming patterns. Based on their parallelism forms, we divided the patterns into three categories - functional parallelism, data parallelism and inseparable. The first few patterns are basic patterns represented in graphs. We will focus our discussion on the patterns which uses geometric or mesh data structures,recursive data structure and pipeline pattern.<br />
<br />
===Functional Parallelism Patterns===<br />
------------------------------------------------------------<br />
Functional parallelism focuses on distributing independent tasks across multiple processors. Each processor executes a different thread on the same or different data. Communications occur among the processors while they are executing the codes. We present two patterns in this category.<br />
====Embarassingly Parallel Pattern====<br />
[[File:Fig3-embpara.jpg|200px|thumb|right|<ref>http://www.cs.uiuc.edu/homes/snir/PPP/patterns/patterns.ppt</ref>]]<br />
<br />
The figure above shows a pattern where we have multiple independent tasks, which are being distributed by the master node to four slave nodes. The tasks are independent of each other so there is no communication between the slave nodes. The communication occurs only between master and slave. The ideal situation is that the master node distribute the same amount of work to each slave node. However, this is dependent of the size of each task, which might vary significantly from one to another. Load balancing is difficult to achieve for this approach.<br />
<br />
====Divide & Conquer====<br />
Divide and Conquer is an approach to solve a big problem by splitting it into several independent smaller problems, which are solved by multiple processors and then the intermediate results are merged to get the final answer. The figure below is a graphical representation of divide and conquer approach. A big problem is divided into multiple smaller problems, which are then distributed to multiple processors. An issue with this approach is that initially when the number of tasks are low, the program is not able to take full advantage of parallel hardware resources. One solution is that we can look for parallelism that exist in each subproblem and try to exploit the parallelism with other patterns.<br />
[[File:Fig4-dc.jpg|200px|thumb|right|<ref>http://www.cs.uiuc.edu/homes/snir/PPP/patterns/patterns.ppt</ref>]]<br />
<br />
===Data Parallelism Patterns===<br />
--------------------------------------------------<br />
====Replicable Pattern====<br />
[[File:Fig5-rep.jpg|200px|thumb|right|<ref>http://www.cs.uiuc.edu/homes/snir/PPP/patterns/patterns.ppt</ref>]]<br />
<br />
The above figure shows a replicable pattern. The issue is that we need to perform a set of operations on a global data structure, which causes dependency across different threads. To solve this problem, each thread makes a local copy of the required global data, performs a certain operation on that local data and produces a partial result. All the partial results are merged together by the master node to generate the final solution. The merging operation is called reduction. Apparently, this approach can also be considered as a divide and conquer approach.<br />
<br />
====Repository Pattern====<br />
[[File:Fig6-repo.jpg|200px|thumb|right|<ref>http://www.cs.uiuc.edu/homes/snir/PPP/patterns/patterns.ppt</ref>]]<br />
<br />
In this case, we have a centralized data structure which is shared by all the computation nodes. Each worker node needs to perform operations on the central data structure in a non-deterministic way. Therefore, the central data structure is controlled by a node to guarantee that each element in the data structure is only accessible by one worker node at any time.<br />
<br />
<br />
<br />
====Recursive Data Pattern<ref>Patterns for Parallel Programming, Timothy G. Mattson, ISBN-10: 0321228111</ref>====<br />
=====Problem Description=====<br />
Suppose the problem involves an operation on a recursive data structure (such as a List, Tree, or Graph) that appears to require sequential processing. How can operations on these data structures be performed in parallel? <br />
=====Driving Forces=====<br />
Recasting the problem to transform an inherently sequential traversal of the recursive data structure into one that allows all elements to be operated upon concurrently does so at the cost of increasing the total work of the computation. This must be balanced against the improved performance available from running in parallel.<br />
This recasting may be difficult to achieve (because it requires looking at the original problem from an unusual perspective) and may lead to a design that is difficult to understand and maintain.<br />
Whether the concurrency exposed by this pattern can be effectively exploited to improve performance depends on how computationally expensive the operation is and on the cost of communication relative to computation on the target parallel computer system. <br />
<br />
=====Solutions=====<br />
The most challenging part of applying this pattern is restructuring the operations over a recursive data structure into a form that exposes additional concurrency. General guidelines are difficult to construct, but the key ideas should be clear from the examples provided below.<br />
Assuming such situation: Suppose we have a forest of rooted directed trees (defined by specifying, for each node, its immediate ancestor, with a root node's ancestor being itself) and want to compute, for each node in the forest, the root of the tree containing that node. To do this in a sequential program, we would probably trace depth-first through each tree from its root to its leaf nodes; as we visit each node, we have the needed information about the corresponding root. Total running time of such a program for a forest of N nodes would be O(N). There is some potential for concurrency (operating on sub-trees concurrently), but there is no obvious way to operate on all elements concurrently, because it appears that we cannot find the root for a particular node without knowing its parent's root.[[File:Recursive1.jpg|200px|thumb|right|Finding roots in a forest. Solid lines represent the original parent-child relationships among nodes; dashed lines point from nodes to their successors.]]<br />
<br />
<br />
However, a rethinking of the problem exposes additional concurrency: We first define for each node a "successor", which initially will be its parent and ultimately will be the root of the tree to which the node belongs. We then calculate for each node its "successor's successor". For nodes one "hop" from the root, this calculation does not change the value of its successor (because a root's parent is itself). For nodes at least two "hops" away from a root, this calculation makes the node's successor its parent's parent. We repeat this calculation until it converges (that is, the values produced by one step are the same as those produced by the preceding step), at which point every node's successor is the desired value. The figure below shows an example requiring three steps to converge. At each step we can operate on all N nodes in the tree concurrently, and the algorithm converges in at most log N steps.<br />
What we have done is transform the original sequential calculation (find roots for nodes one "hop" from a root, then find roots for nodes two "hops" from a root, etc.) into a calculation that computes a partial result (successor) for each node and then repeatedly combines these partial results, first with neighboring results, then with results from nodes two hops away, then with results from nodes four hops away, and so on. This strategy can be applied to other problems that at first appear unavoidably sequential; the Examples section presents other examples. This technique is sometimes referred to as pointer jumping or recursive doubling.<br />
=====Example=====<br />
Algorithms developed with this pattern are a type of data parallel algorithm. They are widely used on SIMD platforms and to a lesser extent in languages such as [http://en.wikipedia.org/wiki/High_Performance_Fortran High Performance Fortran]. These platforms support the fine-grained concurrency required for the pattern and handle synchronization automatically because every computation step (logically if not physically) occurs in lockstep on all the processors. Hillis and Steele <ref> W. Daniel Hillis and Guy L. Steele,, Jr. Data parallel algorithms. Communications of the ACM, 29(12): 1170-1183, 1986.</ref> describe several interesting applications of this pattern, including finding the end of a linked list, computing all partial sums of a linked list, region labeling in two-dimensional images, and parsing.<br />
Pseudocode for finding partial sums of a list<br />
<pre><br />
for all k in parallel<br />
{<br />
temp[k] = next[k];<br />
while temp[k] != null<br />
{<br />
x[temp[k]] = x[k] + x[temp[k]];<br />
temp[k] = temp [temp [k] ];<br />
}<br />
}<br />
</pre><br />
In combinatorial optimization, problems involving traversing all nodes in a graph or tree can often be solved with this pattern by first finding an ordering on the nodes to create a list. [http://en.wikipedia.org/wiki/Euler_tour_technique Euler tour] and [http://en.wikipedia.org/wiki/Ear_decomposition Ear decomposition] are well-known techniques to compute this ordering.<br />
<br />
====Geometric and Irregular Mesh Pattern<ref> http://www.cs.uiuc.edu/homes/snir/PPP/patterns/AMR.pdf</ref>====<br />
=====Problem Description=====<br />
Data-parallelism is exposed on a geometric mesh structure (either irregular or regular),<br />
Where each point iteratively communicates with nearby neighboring points in computing a<br />
Solution until a convergence has been reached. There is a system of formula that<br />
Characterizes and governs the global and local behavior of the mesh structure, exposing each partition of mesh elements to different error and accuracy as the computation progresses in steps. Due to the varying error among the partitions, some mesh points provide sufficiently accurate results within a short number of steps, while others exhibit inaccurate results that may require “refined” computation at more fine-grained resolution. Efficiency is an important requirement of the process, thus it is necessary to adaptively refine meshes for selected regions, while leaving out uninteresting part of the domain at a lower resolution.<br />
<br />
=====Driving Forces=====<br />
*Performance of the adaptively refined computation on the mesh structure must be higher than uniformly refined computation. In other words, the overhead of maintaining adaptive features must be relatively low. <br />
*To provide accurate criterion for further refinement, a good local error estimate must be obtained locally without consulting the global mesh structure. Since global knowledge is limited, useful heuristics must be employed to calculate the local error. <br />
<br />
*Efficient data structure needs to be used to support frequent structural resolution change and to preserve data locality across subsequent refinement.<br />
*Partition and re-partition of the mesh structure after each refinement stage must provide each processing unit balanced computational load and minimum communication overhead.<br />
*At each refinement stage, data migration and work stealing needs to be implemented for dynamically balancing the computational load. <br />
<br />
=====Solutions=====<br />
The solution is an iterative process that consists of multiple components. First, we need an initial partition to divide the mesh points among the processing units. Second, an error indicator that will evaluate how close the locally computed results are to the real solution. Thirdly, when the error is above certain tolerance level, the partition needs to be “refined”, meaning that the mesh size will be reduced by a factor of a constant (usually by power of two). Fourth, as the partition gets altered the mapping of the data elements to the processing units must also be adjusted for better load balance while keeping the data locality at the same time. All these components repeat themselves under efficient data structures designed for efficient access and locality preservation. The outline the algorithm for the Adaptive-Mesh-Refinement pattern, it looks as the following. <br />
<pre><br />
n = number of processors;<br />
m = mesh structure;<br />
Initially partition m over n processors;<br />
while (not all partitions satisfy error tolerance) {<br />
compute locally value of partition p; <br />
// using the system of equations.<br />
<br />
for each mesh points mp in partition p {<br />
if errorEstimate(mp) > tol) {<br />
mark mp for refinement;<br />
}<br />
}<br />
refine mesh structure where marked;<br />
redistribute m OR <br />
migrate individual data between processors;<br />
}<br />
</pre><br />
=====Example=====<br />
[http://ww2.cs.mu.oz.au/498/notes/node51.html Barnes-Hut algorithm] is used in n-body particle simulation problem, to compute the force between each pair among n particles, and thereby updating their positions. The spatial domain is represented as Quad or Octal tree, and iteratively updated as each particle’s position gets changed during the simulation. One special property that the algorithm exploits is the distance between the particles. If a cluster of particle is located sufficiently far away from another, its effective force can be approximated by using a centre of mass of the cluster (without having to visit individual nodes). This effective force can be calculated recursively, thus reducing the number of traversals required to compute force interactions. <br />
Although quite different from partial differential equations, Barnes-Hut also exhibit adaptive refinement aspect in a simply way: it adaptively updates the tree representation depending on the distance of the particles. Unlike PDEs that refines triggered by error condition, Barnes-Hut updates the representation depending on the distance of the particles. The “distance indicator” will act as a guideline in whether to refine or even retract a given data representation as the particle positions move throughout the iterations. As this happens proper load balancing and re-distribution must be followed to increase the performance of the program. <br />
<br />
====Pipeline Pattern<ref> Patterns for Parallel Programming, Timothy G. Mattson, ISBN-10: 0321228111</ref>====<br />
=====Problem Description=====<br />
Suppose that the overall computation involves performing a calculation on many sets of data, where the calculation can be viewed in terms of data flowing through a sequence of stages. How can the potential concurrency be exploited?<br />
An assembly line is a good analogy for this pattern. Suppose we want to manufacture a number of cars. The manufacturing process can be broken down into a sequence of operations each of which adds some component, say the engine or the windshield, to the car. An assembly line (pipeline) assigns a component to each worker. As each car moves down the assembly line, each worker installs the same component over and over on a succession of cars. After the pipeline is full (and until it starts to empty) the workers can all be busy simultaneously, all performing their operations on the cars that are currently at their stations.<br />
<br />
=====Driving Forces=====<br />
*A good solution should make it simple to express the ordering constraints. The ordering constraints in this problem are simple and regular and lend themselves to being expressed in terms of data flowing through a pipeline.<br />
*The target platform can include special-purpose hardware that can perform some of the desired operations.<br />
* In some applications, future additions, modifications, or reordering of the stages in the pipeline are expected.<br />
* In some applications, occasional items in the input sequence can contain errors that prevent their processing.<br />
=====Solutions=====<br />
The key idea of this pattern is captured by the assembly-line analogy, namely that the potential concurrency can be exploited by assigning each operation (stage of the pipeline) to a different worker and having them work simultaneously, with the data elements passing from one worker to the next as operations are completed. In parallel-programming terms, the idea is to assign each task (stage of the pipeline) to a UE and provide a mechanism whereby each stage of the pipeline can send data elements to the next stage. This strategy is probably the most straightforward way to deal with this type of ordering constraints. It allows the application to take advantage of special purpose hardware by appropriate mapping of pipeline stages to PEs and provides a reasonable mechanism for handling errors, described later. It also is likely to yield a modular design that can later be extended or modified.<br />
[[File:Pipeline1 yw.jpg|200px|thumb|right]]<br />
=====Example=====<br />
A type of calculation widely used in signal processing involves performing the following computations repeatedly on different sets of data.<br />
*Perform a discrete Fourier transform (DFT) on a set of data.<br />
* Manipulate the result of the transform elementwise.<br />
* Perform an inverse DFT on the result of the manipulation.<br />
===Inseparable Patterns===<br />
-----------------------------------------------------------<br />
There are some other situations that the patterns above cannot fit. However, when some elements are accessed, they need explicit protection. Examples like [http://en.wikipedia.org/wiki/Mutual_exclusion mutual exclusion] and [http://en.wikipedia.org/wiki/Producer-consumer_problem producer-consumer]<br />
Also, there are some patterns are vaguely defined. <br />
<br />
<br />
==Limitations of Parallel Patterns==<br />
--------------------------------------------------------------<br />
Some argue that the parallel patterns identified so far have little to none contribution towards parallel software development. They claim that parallel design patterns are too trivial and fail to give detailed guidelines for specific parameters that can affect the performance of wide range of complex problem requirements. By experience<br />
in the community, it is coming to a consensus that there are only limited number of patterns; namely pipeline, master & slave, divide & conquer, geometric, replicable, repository, and not many more. So far the community efforts were focused on discovering more design patterns, but new patterns vary a little and fall into range that is not far from one of the patterns mentioned above. The source of ineffectiveness of these patterns, in fact, does not come from its lack of variety, but it comes from inflexibility of how existing patterns are presented.<ref>http://www.cs.uiuc.edu/homes/snir/PPP/patterns/concerns.pdf</ref><br />
<br />
<br />
==Comparison==<br />
--------------------------------------------------------------------------<br />
Although the patterns are very different from each other since they should fit different problems, they do have some similarities. They all have to start from decomposing some sequential problem to expose concurrency. As the two categories state above, the Data parallelism patterns expose concurrency from working on different data elements at the same time. On the other hand, Functional parallelism patterns expose concurrency from working on independent functional tasks at the same time<ref> http://www.cs.uiuc.edu/homes/snir/PPP/ </ref>.<br />
Also, if focused on some certain patterns which resolve similar problems, we can see that they have something in common. For example, in mesh pattern and pipeline pattern, many dependencies exist. On the other hand, in repository and Dvide & Conquer pattern access same memory location a lot. Many memory protections are needed in such patterns.<br />
<br />
<br />
==Quiz==<br />
-------------------------------------------------------<br />
1. Which of the following is NOT defined by a parallel design pattern? <br /><br />
A. Communication framework<br /><br />
B. Application-specific procedures<br /><br />
C. Data structure<br /><br />
D. Type of parallelism<br /><br />
<br />
<br />
2. Which of the following is true for embarassingly parallel pattern? <br /><br />
A. Slave nodes communicate to each other<br /><br />
B. Slave nodes only communicate to master node<br /><br />
C. Slave nodes are responsible for load balancing<br /><br />
D. None of the above<br /><br />
<br />
<br />
3. Which of the following is a characteristic of replicable parallel pattern? <br /><br />
A. Slave nodes perform operations on the global data structure directly. <br /><br />
B. Slave nodes have their own copy of required data. <br /><br />
C. Slave nodes are responsible for reduction. <br /><br />
D. None of the above<br /><br />
<br />
<br />
4. Which pattern has a centralized data structure which independent computations need to be applied to.<br /><br />
A. Pipeline.<br /><br />
B. Repository.<br /><br />
C. Mesh.<br /><br />
D. Replicable.<br /><br />
<br />
<br />
5. Which structure(s) can be example(s) of recursive data structure(s) <br /><br />
A. array.<br /><br />
B. list.<br /><br />
C. tree.<br /><br />
D. graph.<br /><br />
<br />
<br />
6. Barnes-Hut algorithm is an example of which pattern? <br /><br />
A. mesh pattern.<br /><br />
B. pipeline pattern.<br /><br />
C. recursive data pattern.<br /><br />
D. replicable.<br /><br />
<br />
<br />
7. Which are steps to solve the geometric pattern problem..<br /><br />
A. we need an initial partition to divide the mesh points among the processing units..<br /><br />
B. An error indicator that will evaluate how close the locally computed results are to the real solution. <br /><br />
C. When the error is above certain tolerance level, the partition needs to be “refined”..<br /><br />
D. Setup protection for centralized data structure. <br /><br />
<br />
<br />
8. Which may be the most challenging part to solve the recursive data structure pattern problem? <br /><br />
A. rewrite to a form can expose concurrency<br /><br />
B. balance the load of each processor<br /><br />
C. protection of data structure<br /><br />
D. deal with dependencies<br /><br />
<br />
<br />
9. Which pattern can be metaphorized to manufactoria? <br /><br />
A. Pipeline pattern<br /><br />
B. Recursive data pattern<br /><br />
C. Replicable<br /><br />
D. Geometric<br /><br />
<br />
<br />
10. Which is a practice example for pipeline pattern? <br /><br />
A. signal processing<br /><br />
B. tree traversal<br /><br />
C. ocean simulation<br /><br />
D. Barnes-Hut algorithm<br /><br />
<br />
<br />
==References==<br />
<br />
<references></references></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=File:Recursive1.jpg&diff=58295File:Recursive1.jpg2012-02-11T17:03:28Z<p>Ywang50: </p>
<hr />
<div></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=File:Pipeline1_yw.jpg&diff=58294File:Pipeline1 yw.jpg2012-02-11T17:03:05Z<p>Ywang50: </p>
<hr />
<div></div>Ywang50https://wiki.expertiza.ncsu.edu/index.php?title=ECE506_Main_Page&diff=58129ECE506 Main Page2012-02-07T01:19:56Z<p>Ywang50: </p>
<hr />
<div>This page serves as a portal for all wiki material related to CSC506 and ECE506. Link to any new wiki pages from this page, and add links to any current pages.<br />
<br />
=Supplements to Solihin Text=<br />
<br />
Post links to the textbook supplements in this section.<br />
*Chapter 2 [[CSC/ECE 506 Spring 2011/ch2 dm | CSC/ECE 506 Spring 2011/ch2 dm]]<br />
*Chapter 2 [[Parallel_Programming_Models | Parallel Programming Models]]<br />
*Chapter 2 (Still being revised) [[CSC/ECE 506 Spring 2011/ch2 cl | CSC/ECE 506 Spring 2011/ch2 cl]]<br />
*Chapter 2a [[ CSC/ECE 506 Spring 2011/ch2a mc | Current Data-Parallel Architectures ]]<br />
*Chapter 2b [[CSC/ECE 506 Spring 2012/ch2b cm | CSC/ECE 506 Spring 2012/ch2b cm]]<br />
*Chapter 2b [[ECE506_CSC/ECE_506_Spring_2012/2b_az | CSC/ECE 506 Spring 2012/2b az - Data-Parallel Processing with the AMD HD 6900 Series Graphics Processing Unit]]<br />
*Chapter 3 (Final Revision) [[ CSC/ECE 506 Spring 2011/ch3 ab | Parallel Architecture Mechanisms and Programming Models ]]<br />
*Chapter 4a[[ CSC/ECE 506 Spring 2011/ch4a ob | Parallelization of Nelder Mead Algorithm ]]<br />
*Chapter 4a (Under Construction) [[ CSC/ECE_506_Spring_2011/ch4a_bm | Parallelization of Algorithms ]]<br />
*Chapter 4a [[ CSC/ECE 506 Spring 2011/ch4a zz | CSC/ECE 506 Spring 2011/ch4a zz ]]<br />
*Chapter 4b [[Chapter 4b CSC/ECE 506 Spring 2011 / ch4b]]<br />
*Chapter 6a (Under Construction) [[ CSC/ECE 506 Spring 2011/ch6a jp | CSC/ECE 506 Spring 2011/ch6a jp ]]<br />
*Chapter 6a (Under Construction) [[ CSC/ECE 506 Spring 2011/ch6a ep | CSC/ECE 506 Spring 2011/ch6a ep ]]<br />
*Chapter 6b (Ready for First Review) [[CSC/ECE 506 Spring 2011/ch6b ab | CSC/ECE 506 Spring 2011/ch6b ab]]<br />
*Chapter 7 (Under Construction) [[CSC/ECE 506 Spring 2011/ch7 jp | CSC/ECE 506 Spring 2011/ch7 jp]]<br />
*Chapter 8 [[CSC/ECE 506 Spring 2011/ch8 mc | CSC/ECE 506 Spring 2011/ch8 mc]]<br />
*Chapter 10 (Under Construction) [[CSC/ECE 506 Spring 2011/ch10 sb | CSC/ECE 506 Spring 2011/ch10 sb]]<br />
*Chapter 10a [[CSC/ECE_506_Spring_2011/ch10a_dc | CSC/ECE_506_Spring_2011/ch10a_dc]]<br />
*Chapter 11 [[CSC/ECE_506_Spring_2011/ch11_BB_EP | Chapter 11 Supplement]]<br />
*Chapter 11 [[Scalable_Coherent_Interface | SCI (Scalable Coherent Interface) ]]<br />
*Chapter 12 [[ CSC/ECE 506 Spring 2011/ch12 ob | Interconnection Network Topologies and Routing Algorithms]]<br />
*Chapter 12 (Ready for Final Review) [[ CSC/ECE 506 Spring 2011/ch12 aj | Interconnection Network Topologies and Routing Algorithms]]<br />
*Chapter 12 [[ CSC/ECE 506 Spring 2011/ch12 | Interconnection Network Topologies]]<br />
*[[CSC/ECE 506 Spring 2012/1a ry]]<br />
*[[CSC/ECE 506 Spring 2012/1c dm]]<br />
*[[CSC/ECE 506 Spring 2012/1c cl]]<br />
*[[CSC/ECE 506 Spring 2012/1a mw]]<br />
*[[CSC/ECE 506 Spring 2012/3a yw]]</div>Ywang50