Expertiza_Wiki - User contributions [en]

CSC/ECE 506 Spring 2012/7b yw

2012-03-19T02:34:45Z

Xzhang26: /* Quiz */

== Introduction ==

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.

=== Virtually addressed caches ===

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).

[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems]]

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.

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.

=== What is TLB ===

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.
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.
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.
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.

[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer]]

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).

[[Image:tlbOP.PNG|thumbnail|right|200px|Translation Lookaside Buffer]]

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.

=== TLB Coherence issues ===

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.

[[Image:tlbCo.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems]]

This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data.

For example, Assume:
* The processor has been running Process 1
* It then switches to Process 2
* Later it switches back to Process 1

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.

==Solutions==
--------------------------------------------------------------
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.

===Virtually addressed caches===
--------------------------------------------------------------

This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem.

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.
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]

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>

Figure shows the organization of virtually addressed caches.
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]

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>.

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.

=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===
--------------------------------------------------------------
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.

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.

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.

===TLB shootdown===
--------------------------------------------------------------
====General Concept====
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.

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>.

====Detailed Steps====
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.

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.
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.
Step 3. Each processor that receives the interrupt clears its active flag.
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.
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.

====Example====
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>.

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.
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.)
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done.
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.

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>.

<pre>
Initiator:
s = disable_interrupts();
active[mycpul = FALSE;
lockgmap(pmap);
if (inconsistent TLB may result) {
if (pmap->in-uselmycpul) {
invalidate-tlb(pmap,start,end);
}
/* Phase 1 */
if (other cpus using pmap) {
list_type shoot-list = EMPTY-LIST;
for (every cpu in system) {
if (pmap->in-uselcpul && cpu != mycpu) {
lock-action-structure(cpu):
queue_action(cpu,pmap,start,end);
action-neededlcpul = TRUE;
unlock-action-structure(cpu);
if (idle[cpul == FALSE) {
add cpu to shoot-list
}
}
}
for (every cpu on shoot-list) {
send-shootdown-interrupt(cpu);
}
for (every cpu on shoot-list) {
while (activelcpul && pmap->in-uselcpul) {
pmap->in_use[cpu]){
/* spin */ ;
}
}
}
}

/* Phase 3 */
make changes to physical map

unlock-pmap(pmap);
active[mycpu] = TRUE;
restore-interrupt-state(s);

Responders: /* Phase 2 */
s = disable-interrupts();
while (action-needed[mycpu]) {
active[mycpu] = FALSE;
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu)))
/* spin */ ;

/* Phase 4 */
lock-action-structure(mycpu);
process-queuedactions(mycpu);
action-neededlmycpul = FALSE;
unlock-action-structure(mycpu);
active[mycpu] = TRUE;
}
restore-interrupt-state(s);

</pre>

====Performance Analysis====
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.

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

===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===
--------------------------------------------------------------
1. Modified TLB shootdown
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.

2. Lazy devaluation
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.

3. Validation
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.

==Summary==
--------------------------------------------------------------

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.

==Quiz==
--------------------------------------------------------------
1. Which below is(are) solution(s) to TLB coherence problem 
A. MESI protocol 
B. TLB shootdown 
C. using virtually addressed cache 
D. all of above 

2. which is(are) true below 
A. TLB shootdown is a software approach 
B. using virually addressed cache will decrease cache misses 
C. PowerPC has a unique instruction to handle TLB coherence problem 
D. TLB is shared by different processors 

3. what is(are) step(s) of TLB shootdown 
A. Locks the page table 
B. Busy-wait the other processors to inactivate the flags 
C. Send interrupt signal 
D. Release Locks 

4. Which is(are) incorrect about virtually addressed caches 
A. It can be used to decrease the frequency to access map table 
B. It can only addressed by virtual address 
C. V-index should overlap the page number 
D. V-index number is stored in the cache 

5. Which is the correct order of phases in shootdown algorithm 
A. responders initiators responders initiators 
B. initiators initiators responders responders 
C. initiators responders initiators responders 
D. responders responders initiators initiators 

6. What's the typical function of a TLB in modern microarchitecture? 

7. What's the main advantage of adding a virtual address layer rather than using physical addresses directly? 

8. From the function of TLB described in this wiki, what's the best possible placement policy of a TLB? 
A. Direct-mapped 
B. Set-Associative 
C. Fully-Associative 
D. Non of the above 

9. What's the main coherence issue discussed in this wiki? 
A. Two physical address share a same virtual address 
B. Two virtual addresses share a same physical page 
C. Processes might be kicking each others page table off 
C. None of the above 

10. According to this wiki, who is running the page table, software or hardware? 

==References==

<references></references>

CSC/ECE 506 Spring 2012/7b yw

2012-03-19T02:33:30Z

Xzhang26:

CSC/ECE 506 Spring 2012/7b yw

2012-03-19T02:20:29Z

Xzhang26: /* TLB Coherence issues */

File:TlbCo.PNG

2012-03-19T02:18:25Z

Xzhang26:

CSC/ECE 506 Spring 2012/7b yw

2012-03-19T02:17:59Z

Xzhang26: /* TLB Coherence issues */

== Introduction ==

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.

=== Virtually addressed caches ===

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).

[[Image:virtualM.PNG|thumbnail|right|200px|Virtual Memory in modern computer systems]]

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.

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.

=== What is TLB ===

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.
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.
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.
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.

[[Image:tlb.PNG|thumbnail|right|200px|Translation Lookaside Buffer]]

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).

[[Image:tlbOP.PNG|thumbnail|right|200px|Translation Lookaside Buffer]]

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.

=== TLB Coherence issues ===

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.

tlbCo.PNG

This cause inconsistent loads and stores when more than one processors are trying to access the same blocks of data.

For example, Assume:
* The processor has been running Process 1
* It then switches to Process 2
* Later it switches back to Process 1

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.

==Solutions==
--------------------------------------------------------------
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.

===Virtually addressed caches===
--------------------------------------------------------------

This method is to get rid of TLB. If we do not need TLB, we will not have the Coherence problem.

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.
[[File:yw1.jpg|200px|thumb|right|procedure block of addressing cache<ref>lec15 from NCSU ECE506</ref>]]

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>

Figure shows the organization of virtually addressed caches.
[[File:yw2.jpg|200px|thumb|right|Organization of Virtual Addressed Caches<ref>lec15 from NCSU ECE506</ref>]]

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>.

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.

=== Invalidate instructions<ref>lec15 from NCSU ECE506</ref>===
--------------------------------------------------------------
Some processors, notably the PowerPC, have a “TLB_invalidate_entry” instruction.

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.

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.

===TLB shootdown===
--------------------------------------------------------------
====General Concept====
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.

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>.

====Detailed Steps====
Some steps are needed to implement this approach.<ref>lec15 from NCSU ECE506</ref>.

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.
Step 2. Processor p sends an interrupt to other processors that might be using the page table, describing the TLB actions to be performed.
Step 3. Each processor that receives the interrupt clears its active flag.
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.
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.

====Example====
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>.

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.
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.)
3 Initiator: The initiator performs its pmap changes after all responders using the pmap are spinning. It unlocks the pmap when it is done.
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.

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>.

<pre>
Initiator:
s = disable_interrupts();
active[mycpul = FALSE;
lockgmap(pmap);
if (inconsistent TLB may result) {
if (pmap->in-uselmycpul) {
invalidate-tlb(pmap,start,end);
}
/* Phase 1 */
if (other cpus using pmap) {
list_type shoot-list = EMPTY-LIST;
for (every cpu in system) {
if (pmap->in-uselcpul && cpu != mycpu) {
lock-action-structure(cpu):
queue_action(cpu,pmap,start,end);
action-neededlcpul = TRUE;
unlock-action-structure(cpu);
if (idle[cpul == FALSE) {
add cpu to shoot-list
}
}
}
for (every cpu on shoot-list) {
send-shootdown-interrupt(cpu);
}
for (every cpu on shoot-list) {
while (activelcpul && pmap->in-uselcpul) {
pmap->in_use[cpu]){
/* spin */ ;
}
}
}
}

/* Phase 3 */
make changes to physical map

unlock-pmap(pmap);
active[mycpu] = TRUE;
restore-interrupt-state(s);

Responders: /* Phase 2 */
s = disable-interrupts();
while (action-needed[mycpu]) {
active[mycpu] = FALSE;
while (pmap is locked(kernel-pmap) && pmapIisIlocked(user-pmap(mycpu)))
/* spin */ ;

/* Phase 4 */
lock-action-structure(mycpu);
process-queuedactions(mycpu);
action-neededlmycpul = FALSE;
unlock-action-structure(mycpu);
active[mycpu] = TRUE;
}
restore-interrupt-state(s);

</pre>

====Performance Analysis====
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.

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

===Some Other Approaches<ref>Translation-Lookaside Buffer Consistency Patricia J. Teller - et al.</ref>===
--------------------------------------------------------------
1. Modified TLB shootdown
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.

2. Lazy devaluation
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.

3. Validation
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.

==Summary==
--------------------------------------------------------------

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.

==Quiz==
--------------------------------------------------------------
1. Which below is(are) solution(s) to TLB coherence problem 
A. MESI protocol 
B. TLB shootdown 
C. using virtually addressed cache 
D. all of above 

2. which is(are) true below 
A. TLB shootdown is a software approach 
B. using virually addressed cache will decrease cache misses 
C. PowerPC has a unique instruction to handle TLB coherence problem 
D. TLB is shared by different processors 

3. what is(are) step(s) of TLB shootdown 
A. Locks the page table 
B. Busy-wait the other processors to inactivate the flags 
C. Send interrupt signal 
D. Release Locks 

4. Which is(are) incorrect about virtually addressed caches 
A. It can be used to decrease the frequency to access map table 
B. It can only addressed by virtual address 
C. V-index should overlap the page number 
D. V-index number is stored in the cache 

5. Which is the correct order of phases in shootdown algorithm 
A. responders initiators responders initiators 
B. initiators initiators responders responders 
C. initiators responders initiators responders 
D. responders responders initiators initiators 

==References==

<references></references>

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T22:10:43Z

Xzhang26: /* What is TLB */

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T22:10:26Z

Xzhang26: /* What is TLB */

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T22:09:39Z

Xzhang26: /* What is TLB */

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T22:06:48Z

Xzhang26: /* What is TLB */

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T22:05:43Z

Xzhang26: /* What is TLB */

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T22:04:14Z

Xzhang26: /* Virtually addressed caches */

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T22:03:51Z

Xzhang26: /* Virtually addressed caches */

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T22:03:21Z

Xzhang26: /* Virtually addressed caches */

File:TlbOP.PNG

2012-03-18T22:00:27Z

Xzhang26:

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T22:00:09Z

Xzhang26: /* What is TLB */

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T21:49:07Z

Xzhang26: /* What is TLB */

File:Tlb.PNG

2012-03-18T21:48:19Z

Xzhang26:

File:VirtualM.PNG

2012-03-18T21:47:49Z

Xzhang26:

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T21:47:28Z

Xzhang26: /* Virtually addressed caches */

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T21:28:10Z

Xzhang26: /* Virtually addressed caches */

CSC/ECE 506 Spring 2012/7b yw

2012-03-18T20:35:17Z

Xzhang26: Created page with "== Introduction == In this chapter we will first introduce the concept of virtual address memories, more precisely, virtually addressed caches. Pros and cons of virtually addres..."

CSC/ECE 506 Spring 2012/ch5a ja

2012-02-27T21:24:22Z

Xzhang26: /* References */

== Chapter 5a CSC/ECE 506 Spring 2012 / ch5a ==

An exploration and summary of concurrency issues as it relates to linked-list based data structures such as hash tables, trees, and graphs. This topic examines concurrency problems related to each type and possible solutions to allow for parallelization.

= Introduction to Linked-List Parallel Programming =

In determining opportunities for parallel programming during the software design process, many programmers will focus exclusively on loop or array structures, rather than also considering that linked-list pointer-based structures could also provide opportunities to run code in parallel across different processors.

For example, one common parallel technique used in an array processing algorithm is the copy-scan technique. This technique involves copying rows of data from one processor to another in a log(n) fashion until all processors have their own copy of that row. From there, you could perform a reduction technique to generate a sum of all the data, all while working in a parallel fashion. Take the following grid:

The basic process for copy-scan would be to:
Step 1) Copy the row 1 array to row 2.
Step 2) Copy the row 1 array to row 3, row 2 to row 4, etc on the next run.
Step 3) Continue in this manner until all rows have been copied in a log(n) fashion.
Step 4) Perform the parallel operations to generate the desired result (reduction for sum, etc.).

[[File:CopyScan.gif]]

But how does this same process work in the linked list world?

With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.

Step 1) Each processor will make a copy of the pointer it holds to it's neighbor.
Step 2) Next, each processor will make a pointer to the processor 2 steps away.
Step 3) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.
Step 4) Perform the parallel operations to generate the desired result.

[[File:linkedlist.gif]]

However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism on critical sections to avoid race conditions. To make sure the results are correct, it is important that operations can be serialized appropriately and that data remains current and synchronized.

In this chapter, we will explore 3 linked-list based data structures and the concurrency issues they present: hash tables, trees, and graphs.

= Linked Data Structure algorithms extension =
== Lock free algorithms ==

In order to overcome the ABA problems (shown in figure blow), we add auxiliary nodes to the data we structure. An auxiliary node is a cell that contains only a next field. We require that every normal cell in the list have an auxiliary node as its predecessor and as its successor. We permit “chains” of auxiliary nodes in the list (i.e., we do not require that every auxiliary node have a normal cell as its predecessor and successor), although such chains are undesirable for performance reasons.

[[File:fig3.PNG]]

The list also contains two dummy cells as the first and last normal cells in the list. These two cells are pointed at by the root pointers First and Last. These dummy cells need not, respectively, be preceded and followed by auxiliary nodes. Thus, m empty list data structure consists of these two dummy cells separated by an auxiliary node.

A cursor is implemented as three pointers into the data structure: target is a pointer to the cell at the position the cursor is visiting. If the cursor is visiting the end-of-list position, then target will be equal to Last. The pointer pre-aux points to an auxiliary node in the data structure. For a cursor c, if c“.pre-aux = c“.target, then the cursor is valid; otherwise it is invalid. The pointer pre.cell points to a regular cell in the data structure. This pointer is used only by the TRYDELETE operation described below. An invalid cursor indicates that the structure of the list in t he vicinity of the cursor has changed (due to a concurrent insert ion or deletion by another process) since the pointers in the cursor were last read. The UPDATE algorithm, given in Figure 5, examines the state of the list and updates the pointers in the cursor so that it becomes valid. Since the list structure contains auxiliary nodes (perhaps more than one in a row), the UPDATE algorithm must skip over them. If two adjacent auxiliary nodes axe found in the list, the UPDATE algorithm will remove one of them.

[[File:fig5.PNG]]

Traversal of the list data structure is accomplished by using the FIRST and NEXT operations, which use the UPDATE operation. Algorithms are given in Figures 6 and 7. The NEXT operation returns FALSE if the cursor is already at the end of the list and cannot be advanced. Adding new cells into the list requires the insertion of both the cell and a new auxiliary node. This insertion is restricted to occur in the following way: The new auxiliary node will follow the new cell in the list, and insertion can only occur between an auxiliary node and a normal cell, as shown in Figure 8.

[[File:fig6.PNG]]
[[File:fig7.PNG]]
[[File:fig8.PNG]]

Figure 9 gives an algorithm, which takes as arguments a cursor and pointers to a new cell and auxiliary node. The algorithm will try to insert the new cell and auxiliary node at the position specified by the cursor, returning the value
TRUE if successful.

[[File:fig9.PNG]]

If the cursor becomes invalid, then the operation returns without inserting the new cell and returns the value FALSE. This allows a higher-level operation to detect that a change to the structure of the list occurred and to take it into account before attempting to insert the new cell again. For example, in the next section we show how the items in the list can be kept sorted using this technique.

Given a valid cursor, the cell that it is visiting can also be deleted from the list. As with the insertion of new cells, if the list structure changes (i.e., the cursor becomes invalid) then the operation fails and must be tried again. Figure 10 gives the TRYDELETE algorithm. The deletion of the cell from the list leaves an “extra” auxiliary node; concurrent processes deleting adjacent cells can result in longer chains. Most of the TRYDELETE algorithm is concerned with removing the extra auxiliary nodes from the list. Normally, removing the extra auxiliary node that results from the deletion of a cell from the list is accomplished by simply swinging the pointer in the cell pointed at by the pre-cell pointer in the cursor.

[[File:fig10.PNG]]

However, this does not always work; in particular, this cell may have itself been deleted from the list, in which case swinging its next pointer will not remove the extra auxiliary node: In order to overcome this problem, we add a back~ink field to the normal cells in the list. When a cell is deleted from the list, the pre.cell field of the cursor is copied into the cell’s backdink field. The TRYDELETE algorithm can then use these pointers to reverse back to a cell that has not been deleted from the list.

With just two processes, it is possible to create a chain of auxiliary nodes (with no intervening normal cells) of any length. However, any such chain can exist in the list only as long as some process is executing the TRYDELETE algorithm.

If all deletions have been completed, then the list will contain no extra auxiliary nodes. To see this, assume that there is a chain of two or more-+ auxiliary nodes in the list. Let z be the normal cell that was deleted from between the first two auxiliary nodes in the chain. Note that this implies that the normal cell that immediately preceded x in the list has not been deleted.
By assumption, the operation that deleted z has completed. Consider the loop at lines 17–21 of the TRYDELETE algorithm. The only way for the process to exit this 100P, and hence to complete the operation, is for another deletion operation to have extended the chain of auxiliary nodes by deleting the normal cell g immediately following the chain, since the cell z is at the front of the chain.
Furthermore, the deletion of y must have occurred after the operation deleting x had set its back_link pointer at line 6; otherwise the auxiliary node following y would have been included in the chain found in lines 13–16. Thus, the chain of back_link pointers followed by the process that deleted y will lead to the same normal cell that preceded x.

Now, the only way for the operation that deleted y to have completed is for the same reason as above; i.e., another TRYDELETE operation must extend the chain of auxiliary nodes by deleting a cell z. Since the length of the list must be finite, there must be a last such deletion which, but by the argument above, cannot have completed. Thus this operation must still be in progress, contradicting the assumption that there were no TRYDELETE operations in progress.

[[File:fig11.PNG]]

== Trees ==

This chapter gives a serial code for a tree traversal, and a parallel solution to implement same function.

=== Serial Code Example ===

Below is a code for tree traversal algorithms
its behavior is as figure below shows:

[[File: tree.PNG]]

procedure Tree_Traversal is
type Node;
type Node_Access is access Node;
type Node is record
Left : Node_Access := null;
Right : Node_Access := null;
Data : Integer;
end record;
procedure Destroy_Tree(N : in out Node_Access) is
procedure free is new Ada.Unchecked_Deallocation(Node, Node_Access);
begin
if N.Left /= null then
Destroy_Tree(N.Left);
end if;
if N.Right /= null then
Destroy_Tree(N.Right);
end if;
Free(N);
end Destroy_Tree;
function Tree(Value : Integer; Left : Node_Access; Right : Node_Access) return Node_Access is
Temp : Node_Access := new Node;
begin
Temp.Data := Value;
Temp.Left := Left;
Temp.Right := Right;
return Temp;
end Tree;
procedure Preorder(N : Node_Access) is
begin
Put(Integer'Image(N.Data));
if N.Left /= null then
Preorder(N.Left);
end if;
if N.Right /= null then
Preorder(N.Right);
end if;
end Preorder;
procedure Inorder(N : Node_Access) is
begin
if N.Left /= null then
Inorder(N.Left);
end if;
Put(Integer'Image(N.Data));
if N.Right /= null then
Inorder(N.Right);
end if;
end Inorder;
procedure Postorder(N : Node_Access) is
begin
if N.Left /= null then
Postorder(N.Left);
end if;
if N.Right /= null then
Postorder(N.Right);
end if;
Put(Integer'Image(N.Data));
end Postorder;
procedure Levelorder(N : Node_Access) is
package Queues is new Ada.Containers.Doubly_Linked_Lists(Node_Access);
use Queues;
Node_Queue : List;
Next : Node_Access;
begin
Node_Queue.Append(N);
while not Is_Empty(Node_Queue) loop
Next := First_Element(Node_Queue);
Delete_First(Node_Queue);
Put(Integer'Image(Next.Data));
if Next.Left /= null then
Node_Queue.Append(Next.Left);
end if;
if Next.Right /= null then
Node_Queue.Append(Next.Right);
end if;
end loop;
end Levelorder;
N : Node_Access;
begin
N := Tree(1,
Tree(2,
Tree(4,
Tree(7, null, null),
null),
Tree(5, null, null)),
Tree(3,
Tree(6,
Tree(8, null, null),
Tree(9, null, null)),
null));

Put("preorder: ");
Preorder(N);
New_Line;
Put("inorder: ");
Inorder(N);
New_Line;
Put("postorder: ");
Postorder(N);
New_Line;
Put("level order: ");
Levelorder(N);
New_Line;
Destroy_Tree(N);
end Tree_traversal;

=== Parallel Code Solution ===

This part we implement a parallel algorithm with the same definition of traversal.
First, we difine a function NEXT[x].The function NEXT[ x,], defining the successor of a field x, (of node x) in the Euler tour, is given as

[[File: para_tree1.PNG]]

Note that this NEXT function does not provide the successor of the last field of the root-node r in the tour. This is because we break the tour into a linked list such that u, is the starting field and r is the terminal field, where m = no-of-chiidren[r] + 1. The proposed linked list structure can be represented as an array [I . 2n - l] of SNODEREC:

[[File: para2.PNG]]
This data structure can be constructed from the following algorithm when the input tree is represented
by a “parent-of” relation with explicit ordering of children. Each field of a tree-node in this algorithm is a record of type SNODEREC.

Algorithm GEN-COMP-NEXT
[[File: para3.PNG]]

To obtain the required tree-traversals, the following rules are operated on the linked list produced by algorithm GEN-COMP-NEXT:

pre-order traversal: select the first copy of
each node;

post-order traversal: select the last copy of
each node;

in-order traversal: delete the first copy of each node if it is not
a leaf and delete the last copy of each node if it has more than one child.

== Hash Tables ==
=== Hash Table Intro ===

Hash tables are very efficient data structures often used in searching algorithms for fast lookup operations. Hash tables contain a series of "buckets" that function like indexes into an array, each of which can be accessed directly using their key value. The bucket for which a piece of data will be placed is determine by a special hashing function.

The major advantage of a hash table is that lookup times are essentially a constant value, much like an array with a known index. With a proper hashing function in place, it should be fairly rare that any 2 keys would generate the same value.

In the case that 2 keys do map to the same position, there is a conflict that must be dealt with in some fashion to obtain the correct value. One way that is relevant to linked list structures is to have a chained hash table in which a linked list is created with all values that have been placed in that particular bucket. The developer would have to not only take into account the proper bucket for the data being searched for, but also must considered the chained linked list.

[[File:315px-Hash table 3 1 1 0 1 0 0 SP.svg.png]]
=== Serial Code Example ===

''' Insert Example: Create new node if hash bucket doesnt exist, else append to the chain.'''

/**
* Put a key/value pair into the table by hashing the key to get the array
* index of the chain that should hold the node containing the pair.
* If an existing node with the same key is present then overwrite its value,
* otherwise add a new node.
*
*@param key key object reference
*@param val data object reference
*/
public void put(Object key, Object val)
{
int index = getIndex(key);
Node node = find(key, data[index]);
// Use helper method to determine if node with same key is already in
// chain. If not, add a new node to head of chain.
if (node == null)
{
data[index] = new Node(data[index], key, val);
}
else
{
// Otherwise update data value of existing node.
node.val = val;
}
}

/**
* Given a key object, return a data object from the table or
* null if it is not found.
*
*@param key key object reference
*@return data object reference or null if no object found
*/
public Object get(Object key)
{
Node temp = find(key, data[getIndex(key)]);
if (temp != null)
{
return temp.val;
}
else
{
return null;
}
}

''' Delete Example: Delete a node from the chain.'''
/**
* Remove a key/value pair from table if present, otherwise make no change.
*
*@param key key object reference
*/
public void remove(Object key)
{
int index = getIndex(key);
Node ref = data[index];
Node previous = null;
while (ref != null)
{
if ((ref.key).equals(key))
{
if (previous == null)
{
data[index] = ref.next;
}
else
{
previous.next = ref.next;
}
return;
}
previous = ref;
ref = ref.next;
}
}

/**
* Given a key, use a hash function to obtain the array index of the chain
* corresponding to the key.
* The hashCode method inherited (and possibly overridden)
* from class Object is called to do the hashing, with the returned
* value constrained to the hash table array bounds.
* The distribution of objects in the hash table will depend
* on the quality of the hash function implemented by hashCode.
*
*@param key reference to object to be hashed
*@return array index of chain corresponding to key
*/
private int getIndex(Object key)
{
return Math.abs(key.hashCode() % data.length);
}

/**
* Find node given a key and a chain to search.
*
*@param key key object reference
*@param ref node object reference where search will start
*@return node object holding key or null if not found
*/
private Node find(Object key, Node ref)
{
while (ref != null)
{
if ((ref.key).equals(key))
{
return ref;
}
ref = ref.next;
}
return null;
}

=== Parallel Code Solution ===

The key issue in a hash table in a parallel environment is to make sure any update/insert/delete sequences have been completed properly prior to attempting subsequent operations to make sure the data has been synched appropriately. However, since access speed is such a critical component of the design of a hash table, it is essential to try and avoid using too many locks for performing synchronization. Fortunately, a number of lock-free hash designs have been implemented to avoid this bottleneck.

== Graphs ==
=== Graph Intro ===

A graph data structure is another type of linked-list structure that focuses on data that requires linking according to various types of relationships. For example, in a networking application, one network node may have connections to a variety of other network nodes. These nodes then also link to a variety of other nodes in the network. Using this connection of nodes, it would be possible to then find a path from one specific node to another in the chain. This could be accomplished by having each node contain a linked list of pointers to all other reachable nodes.

=== Serial Code Example ===

/**
* Add a new edge to the graph.
*/
public void addEdge( String sourceName, String destName, double cost )
{
Vertex v = getVertex( sourceName );
Vertex w = getVertex( destName );
v.adj.add( new Edge( w, cost ) );
}

/**
* Single-source unweighted shortest-path algorithm.
*/
public void unweighted( String startName )
{
clearAll( );

Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );

LinkedList q = new LinkedList( );
q.addLast( start ); start.dist = 0;

while( !q.isEmpty( ) )
{
Vertex v = (Vertex) q.removeFirst( );

for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
if( w.dist == INFINITY )
{
w.dist = v.dist + 1;
w.prev = v;
q.addLast( w );
}
}
}
}

=== Parallel Code Solution ===

= Quiz =
= References =
http://oreilly.com/catalog/masteralgoc/chapter/ch08.pdf

http://www.devjavasoft.org/code/classhashtable.html

http://osr600doc.sco.com/en/SDK_c++/_Intro_graph.html

web.eecs.utk.edu/~berry/cs302s02/src/code/Chap14/Graph.java

http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html

http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg

http://rosettacode.org/wiki/Talk:Tree_traversal

CSC/ECE 506 Spring 2012/ch5a ja

2012-02-27T21:23:24Z

Xzhang26: /* Trees */

CSC/ECE 506 Spring 2012/ch5a ja

2012-02-27T21:12:03Z

Xzhang26: /* Linked Data Structures */

== Chapter 5a CSC/ECE 506 Spring 2012 / ch5a ==

An exploration and summary of concurrency issues as it relates to linked-list based data structures such as hash tables, trees, and graphs. This topic examines concurrency problems related to each type and possible solutions to allow for parallelization.

= Introduction to Linked-List Parallel Programming =

In determining opportunities for parallel programming during the software design process, many programmers will focus exclusively on loop or array structures, rather than also considering that linked-list pointer-based structures could also provide opportunities to run code in parallel across different processors.

For example, one common parallel technique used in an array processing algorithm is the copy-scan technique. This technique involves copying rows of data from one processor to another in a log(n) fashion until all processors have their own copy of that row. From there, you could perform a reduction technique to generate a sum of all the data, all while working in a parallel fashion. Take the following grid:

The basic process for copy-scan would be to:
Step 1) Copy the row 1 array to row 2.
Step 2) Copy the row 1 array to row 3, row 2 to row 4, etc on the next run.
Step 3) Continue in this manner until all rows have been copied in a log(n) fashion.
Step 4) Perform the parallel operations to generate the desired result (reduction for sum, etc.).

[[File:CopyScan.gif]]

But how does this same process work in the linked list world?

With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.

Step 1) Each processor will make a copy of the pointer it holds to it's neighbor.
Step 2) Next, each processor will make a pointer to the processor 2 steps away.
Step 3) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.
Step 4) Perform the parallel operations to generate the desired result.

[[File:linkedlist.gif]]

However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism on critical sections to avoid race conditions. To make sure the results are correct, it is important that operations can be serialized appropriately and that data remains current and synchronized.

In this chapter, we will explore 3 linked-list based data structures and the concurrency issues they present: hash tables, trees, and graphs.

= Linked Data Structure algorithms extension =
== Lock free algorithms ==

In order to overcome the ABA problems (shown in figure blow), we add auxiliary nodes to the data we structure. An auxiliary node is a cell that contains only a next field. We require that every normal cell in the list have an auxiliary node as its predecessor and as its successor. We permit “chains” of auxiliary nodes in the list (i.e., we do not require that every auxiliary node have a normal cell as its predecessor and successor), although such chains are undesirable for performance reasons.

[[File:fig3.PNG]]

The list also contains two dummy cells as the first and last normal cells in the list. These two cells are pointed at by the root pointers First and Last. These dummy cells need not, respectively, be preceded and followed by auxiliary nodes. Thus, m empty list data structure consists of these two dummy cells separated by an auxiliary node.

A cursor is implemented as three pointers into the data structure: target is a pointer to the cell at the position the cursor is visiting. If the cursor is visiting the end-of-list position, then target will be equal to Last. The pointer pre-aux points to an auxiliary node in the data structure. For a cursor c, if c“.pre-aux = c“.target, then the cursor is valid; otherwise it is invalid. The pointer pre.cell points to a regular cell in the data structure. This pointer is used only by the TRYDELETE operation described below. An invalid cursor indicates that the structure of the list in t he vicinity of the cursor has changed (due to a concurrent insert ion or deletion by another process) since the pointers in the cursor were last read. The UPDATE algorithm, given in Figure 5, examines the state of the list and updates the pointers in the cursor so that it becomes valid. Since the list structure contains auxiliary nodes (perhaps more than one in a row), the UPDATE algorithm must skip over them. If two adjacent auxiliary nodes axe found in the list, the UPDATE algorithm will remove one of them.

[[File:fig5.PNG]]

Traversal of the list data structure is accomplished by using the FIRST and NEXT operations, which use the UPDATE operation. Algorithms are given in Figures 6 and 7. The NEXT operation returns FALSE if the cursor is already at the end of the list and cannot be advanced. Adding new cells into the list requires the insertion of both the cell and a new auxiliary node. This insertion is restricted to occur in the following way: The new auxiliary node will follow the new cell in the list, and insertion can only occur between an auxiliary node and a normal cell, as shown in Figure 8.

[[File:fig6.PNG]]
[[File:fig7.PNG]]
[[File:fig8.PNG]]

Figure 9 gives an algorithm, which takes as arguments a cursor and pointers to a new cell and auxiliary node. The algorithm will try to insert the new cell and auxiliary node at the position specified by the cursor, returning the value
TRUE if successful.

[[File:fig9.PNG]]

If the cursor becomes invalid, then the operation returns without inserting the new cell and returns the value FALSE. This allows a higher-level operation to detect that a change to the structure of the list occurred and to take it into account before attempting to insert the new cell again. For example, in the next section we show how the items in the list can be kept sorted using this technique.

Given a valid cursor, the cell that it is visiting can also be deleted from the list. As with the insertion of new cells, if the list structure changes (i.e., the cursor becomes invalid) then the operation fails and must be tried again. Figure 10 gives the TRYDELETE algorithm. The deletion of the cell from the list leaves an “extra” auxiliary node; concurrent processes deleting adjacent cells can result in longer chains. Most of the TRYDELETE algorithm is concerned with removing the extra auxiliary nodes from the list. Normally, removing the extra auxiliary node that results from the deletion of a cell from the list is accomplished by simply swinging the pointer in the cell pointed at by the pre-cell pointer in the cursor.

[[File:fig10.PNG]]

However, this does not always work; in particular, this cell may have itself been deleted from the list, in which case swinging its next pointer will not remove the extra auxiliary node: In order to overcome this problem, we add a back~ink field to the normal cells in the list. When a cell is deleted from the list, the pre.cell field of the cursor is copied into the cell’s backdink field. The TRYDELETE algorithm can then use these pointers to reverse back to a cell that has not been deleted from the list.

With just two processes, it is possible to create a chain of auxiliary nodes (with no intervening normal cells) of any length. However, any such chain can exist in the list only as long as some process is executing the TRYDELETE algorithm.

If all deletions have been completed, then the list will contain no extra auxiliary nodes. To see this, assume that there is a chain of two or more-+ auxiliary nodes in the list. Let z be the normal cell that was deleted from between the first two auxiliary nodes in the chain. Note that this implies that the normal cell that immediately preceded x in the list has not been deleted.
By assumption, the operation that deleted z has completed. Consider the loop at lines 17–21 of the TRYDELETE algorithm. The only way for the process to exit this 100P, and hence to complete the operation, is for another deletion operation to have extended the chain of auxiliary nodes by deleting the normal cell g immediately following the chain, since the cell z is at the front of the chain.
Furthermore, the deletion of y must have occurred after the operation deleting x had set its back_link pointer at line 6; otherwise the auxiliary node following y would have been included in the chain found in lines 13–16. Thus, the chain of back_link pointers followed by the process that deleted y will lead to the same normal cell that preceded x.

Now, the only way for the operation that deleted y to have completed is for the same reason as above; i.e., another TRYDELETE operation must extend the chain of auxiliary nodes by deleting a cell z. Since the length of the list must be finite, there must be a last such deletion which, but by the argument above, cannot have completed. Thus this operation must still be in progress, contradicting the assumption that there were no TRYDELETE operations in progress.

[[File:fig11.PNG]]

== Trees ==
=== Serial Code Example ===

Below is a code for tree traversal algorithms
its behavior is as figure below shows:

[[File: tree.PNG]]

procedure Tree_Traversal is
type Node;
type Node_Access is access Node;
type Node is record
Left : Node_Access := null;
Right : Node_Access := null;
Data : Integer;
end record;
procedure Destroy_Tree(N : in out Node_Access) is
procedure free is new Ada.Unchecked_Deallocation(Node, Node_Access);
begin
if N.Left /= null then
Destroy_Tree(N.Left);
end if;
if N.Right /= null then
Destroy_Tree(N.Right);
end if;
Free(N);
end Destroy_Tree;
function Tree(Value : Integer; Left : Node_Access; Right : Node_Access) return Node_Access is
Temp : Node_Access := new Node;
begin
Temp.Data := Value;
Temp.Left := Left;
Temp.Right := Right;
return Temp;
end Tree;
procedure Preorder(N : Node_Access) is
begin
Put(Integer'Image(N.Data));
if N.Left /= null then
Preorder(N.Left);
end if;
if N.Right /= null then
Preorder(N.Right);
end if;
end Preorder;
procedure Inorder(N : Node_Access) is
begin
if N.Left /= null then
Inorder(N.Left);
end if;
Put(Integer'Image(N.Data));
if N.Right /= null then
Inorder(N.Right);
end if;
end Inorder;
procedure Postorder(N : Node_Access) is
begin
if N.Left /= null then
Postorder(N.Left);
end if;
if N.Right /= null then
Postorder(N.Right);
end if;
Put(Integer'Image(N.Data));
end Postorder;
procedure Levelorder(N : Node_Access) is
package Queues is new Ada.Containers.Doubly_Linked_Lists(Node_Access);
use Queues;
Node_Queue : List;
Next : Node_Access;
begin
Node_Queue.Append(N);
while not Is_Empty(Node_Queue) loop
Next := First_Element(Node_Queue);
Delete_First(Node_Queue);
Put(Integer'Image(Next.Data));
if Next.Left /= null then
Node_Queue.Append(Next.Left);
end if;
if Next.Right /= null then
Node_Queue.Append(Next.Right);
end if;
end loop;
end Levelorder;
N : Node_Access;
begin
N := Tree(1,
Tree(2,
Tree(4,
Tree(7, null, null),
null),
Tree(5, null, null)),
Tree(3,
Tree(6,
Tree(8, null, null),
Tree(9, null, null)),
null));

Put("preorder: ");
Preorder(N);
New_Line;
Put("inorder: ");
Inorder(N);
New_Line;
Put("postorder: ");
Postorder(N);
New_Line;
Put("level order: ");
Levelorder(N);
New_Line;
Destroy_Tree(N);
end Tree_traversal;

=== Parallel Code Solution ===
== Hash Tables ==
=== Hash Table Intro ===

Hash tables are very efficient data structures often used in searching algorithms for fast lookup operations. Hash tables contain a series of "buckets" that function like indexes into an array, each of which can be accessed directly using their key value. The bucket for which a piece of data will be placed is determine by a special hashing function.

The major advantage of a hash table is that lookup times are essentially a constant value, much like an array with a known index. With a proper hashing function in place, it should be fairly rare that any 2 keys would generate the same value.

In the case that 2 keys do map to the same position, there is a conflict that must be dealt with in some fashion to obtain the correct value. One way that is relevant to linked list structures is to have a chained hash table in which a linked list is created with all values that have been placed in that particular bucket. The developer would have to not only take into account the proper bucket for the data being searched for, but also must considered the chained linked list.

[[File:315px-Hash table 3 1 1 0 1 0 0 SP.svg.png]]
=== Serial Code Example ===

''' Insert Example: Create new node if hash bucket doesnt exist, else append to the chain.'''

/**
* Put a key/value pair into the table by hashing the key to get the array
* index of the chain that should hold the node containing the pair.
* If an existing node with the same key is present then overwrite its value,
* otherwise add a new node.
*
*@param key key object reference
*@param val data object reference
*/
public void put(Object key, Object val)
{
int index = getIndex(key);
Node node = find(key, data[index]);
// Use helper method to determine if node with same key is already in
// chain. If not, add a new node to head of chain.
if (node == null)
{
data[index] = new Node(data[index], key, val);
}
else
{
// Otherwise update data value of existing node.
node.val = val;
}
}

/**
* Given a key object, return a data object from the table or
* null if it is not found.
*
*@param key key object reference
*@return data object reference or null if no object found
*/
public Object get(Object key)
{
Node temp = find(key, data[getIndex(key)]);
if (temp != null)
{
return temp.val;
}
else
{
return null;
}
}

''' Delete Example: Delete a node from the chain.'''
/**
* Remove a key/value pair from table if present, otherwise make no change.
*
*@param key key object reference
*/
public void remove(Object key)
{
int index = getIndex(key);
Node ref = data[index];
Node previous = null;
while (ref != null)
{
if ((ref.key).equals(key))
{
if (previous == null)
{
data[index] = ref.next;
}
else
{
previous.next = ref.next;
}
return;
}
previous = ref;
ref = ref.next;
}
}

/**
* Given a key, use a hash function to obtain the array index of the chain
* corresponding to the key.
* The hashCode method inherited (and possibly overridden)
* from class Object is called to do the hashing, with the returned
* value constrained to the hash table array bounds.
* The distribution of objects in the hash table will depend
* on the quality of the hash function implemented by hashCode.
*
*@param key reference to object to be hashed
*@return array index of chain corresponding to key
*/
private int getIndex(Object key)
{
return Math.abs(key.hashCode() % data.length);
}

/**
* Find node given a key and a chain to search.
*
*@param key key object reference
*@param ref node object reference where search will start
*@return node object holding key or null if not found
*/
private Node find(Object key, Node ref)
{
while (ref != null)
{
if ((ref.key).equals(key))
{
return ref;
}
ref = ref.next;
}
return null;
}

=== Parallel Code Solution ===

The key issue in a hash table in a parallel environment is to make sure any update/insert/delete sequences have been completed properly prior to attempting subsequent operations to make sure the data has been synched appropriately. However, since access speed is such a critical component of the design of a hash table, it is essential to try and avoid using too many locks for performing synchronization. Fortunately, a number of lock-free hash designs have been implemented to avoid this bottleneck.

== Graphs ==
=== Graph Intro ===

A graph data structure is another type of linked-list structure that focuses on data that requires linking according to various types of relationships. For example, in a networking application, one network node may have connections to a variety of other network nodes. These nodes then also link to a variety of other nodes in the network. Using this connection of nodes, it would be possible to then find a path from one specific node to another in the chain. This could be accomplished by having each node contain a linked list of pointers to all other reachable nodes.

=== Serial Code Example ===

/**
* Add a new edge to the graph.
*/
public void addEdge( String sourceName, String destName, double cost )
{
Vertex v = getVertex( sourceName );
Vertex w = getVertex( destName );
v.adj.add( new Edge( w, cost ) );
}

/**
* Single-source unweighted shortest-path algorithm.
*/
public void unweighted( String startName )
{
clearAll( );

Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );

LinkedList q = new LinkedList( );
q.addLast( start ); start.dist = 0;

while( !q.isEmpty( ) )
{
Vertex v = (Vertex) q.removeFirst( );

for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
if( w.dist == INFINITY )
{
w.dist = v.dist + 1;
w.prev = v;
q.addLast( w );
}
}
}
}

=== Parallel Code Solution ===

= Quiz =
= References =
http://oreilly.com/catalog/masteralgoc/chapter/ch08.pdf

http://www.devjavasoft.org/code/classhashtable.html

http://osr600doc.sco.com/en/SDK_c++/_Intro_graph.html

web.eecs.utk.edu/~berry/cs302s02/src/code/Chap14/Graph.java

http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html

http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg

CSC/ECE 506 Spring 2012/ch5a ja

2012-02-27T21:10:50Z

Xzhang26: /* Serial Code Example */

== Chapter 5a CSC/ECE 506 Spring 2012 / ch5a ==

An exploration and summary of concurrency issues as it relates to linked-list based data structures such as hash tables, trees, and graphs. This topic examines concurrency problems related to each type and possible solutions to allow for parallelization.

= Introduction to Linked-List Parallel Programming =

In determining opportunities for parallel programming during the software design process, many programmers will focus exclusively on loop or array structures, rather than also considering that linked-list pointer-based structures could also provide opportunities to run code in parallel across different processors.

For example, one common parallel technique used in an array processing algorithm is the copy-scan technique. This technique involves copying rows of data from one processor to another in a log(n) fashion until all processors have their own copy of that row. From there, you could perform a reduction technique to generate a sum of all the data, all while working in a parallel fashion. Take the following grid:

The basic process for copy-scan would be to:
Step 1) Copy the row 1 array to row 2.
Step 2) Copy the row 1 array to row 3, row 2 to row 4, etc on the next run.
Step 3) Continue in this manner until all rows have been copied in a log(n) fashion.
Step 4) Perform the parallel operations to generate the desired result (reduction for sum, etc.).

[[File:CopyScan.gif]]

But how does this same process work in the linked list world?

With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.

Step 1) Each processor will make a copy of the pointer it holds to it's neighbor.
Step 2) Next, each processor will make a pointer to the processor 2 steps away.
Step 3) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.
Step 4) Perform the parallel operations to generate the desired result.

[[File:linkedlist.gif]]

However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism on critical sections to avoid race conditions. To make sure the results are correct, it is important that operations can be serialized appropriately and that data remains current and synchronized.

In this chapter, we will explore 3 linked-list based data structures and the concurrency issues they present: hash tables, trees, and graphs.

= Linked Data Structure algorithms extension =
== Lock free algorithms ==

In order to overcome the ABA problems (shown in figure blow), we add auxiliary nodes to the data we structure. An auxiliary node is a cell that contains only a next field. We require that every normal cell in the list have an auxiliary node as its predecessor and as its successor. We permit “chains” of auxiliary nodes in the list (i.e., we do not require that every auxiliary node have a normal cell as its predecessor and successor), although such chains are undesirable for performance reasons.

[[File:fig3.PNG]]

The list also contains two dummy cells as the first and last normal cells in the list. These two cells are pointed at by the root pointers First and Last. These dummy cells need not, respectively, be preceded and followed by auxiliary nodes. Thus, m empty list data structure consists of these two dummy cells separated by an auxiliary node.

A cursor is implemented as three pointers into the data structure: target is a pointer to the cell at the position the cursor is visiting. If the cursor is visiting the end-of-list position, then target will be equal to Last. The pointer pre-aux points to an auxiliary node in the data structure. For a cursor c, if c“.pre-aux = c“.target, then the cursor is valid; otherwise it is invalid. The pointer pre.cell points to a regular cell in the data structure. This pointer is used only by the TRYDELETE operation described below. An invalid cursor indicates that the structure of the list in t he vicinity of the cursor has changed (due to a concurrent insert ion or deletion by another process) since the pointers in the cursor were last read. The UPDATE algorithm, given in Figure 5, examines the state of the list and updates the pointers in the cursor so that it becomes valid. Since the list structure contains auxiliary nodes (perhaps more than one in a row), the UPDATE algorithm must skip over them. If two adjacent auxiliary nodes axe found in the list, the UPDATE algorithm will remove one of them.

[[File:fig5.PNG]]

Traversal of the list data structure is accomplished by using the FIRST and NEXT operations, which use the UPDATE operation. Algorithms are given in Figures 6 and 7. The NEXT operation returns FALSE if the cursor is already at the end of the list and cannot be advanced. Adding new cells into the list requires the insertion of both the cell and a new auxiliary node. This insertion is restricted to occur in the following way: The new auxiliary node will follow the new cell in the list, and insertion can only occur between an auxiliary node and a normal cell, as shown in Figure 8.

[[File:fig6.PNG]]
[[File:fig7.PNG]]
[[File:fig8.PNG]]

Figure 9 gives an algorithm, which takes as arguments a cursor and pointers to a new cell and auxiliary node. The algorithm will try to insert the new cell and auxiliary node at the position specified by the cursor, returning the value
TRUE if successful.

[[File:fig9.PNG]]

If the cursor becomes invalid, then the operation returns without inserting the new cell and returns the value FALSE. This allows a higher-level operation to detect that a change to the structure of the list occurred and to take it into account before attempting to insert the new cell again. For example, in the next section we show how the items in the list can be kept sorted using this technique.

Given a valid cursor, the cell that it is visiting can also be deleted from the list. As with the insertion of new cells, if the list structure changes (i.e., the cursor becomes invalid) then the operation fails and must be tried again. Figure 10 gives the TRYDELETE algorithm. The deletion of the cell from the list leaves an “extra” auxiliary node; concurrent processes deleting adjacent cells can result in longer chains. Most of the TRYDELETE algorithm is concerned with removing the extra auxiliary nodes from the list. Normally, removing the extra auxiliary node that results from the deletion of a cell from the list is accomplished by simply swinging the pointer in the cell pointed at by the pre-cell pointer in the cursor.

[[File:fig10.PNG]]

However, this does not always work; in particular, this cell may have itself been deleted from the list, in which case swinging its next pointer will not remove the extra auxiliary node: In order to overcome this problem, we add a back~ink field to the normal cells in the list. When a cell is deleted from the list, the pre.cell field of the cursor is copied into the cell’s backdink field. The TRYDELETE algorithm can then use these pointers to reverse back to a cell that has not been deleted from the list.

With just two processes, it is possible to create a chain of auxiliary nodes (with no intervening normal cells) of any length. However, any such chain can exist in the list only as long as some process is executing the TRYDELETE algorithm.

If all deletions have been completed, then the list will contain no extra auxiliary nodes. To see this, assume that there is a chain of two or more-+ auxiliary nodes in the list. Let z be the normal cell that was deleted from between the first two auxiliary nodes in the chain. Note that this implies that the normal cell that immediately preceded x in the list has not been deleted.
By assumption, the operation that deleted z has completed. Consider the loop at lines 17–21 of the TRYDELETE algorithm. The only way for the process to exit this 100P, and hence to complete the operation, is for another deletion operation to have extended the chain of auxiliary nodes by deleting the normal cell g immediately following the chain, since the cell z is at the front of the chain.
Furthermore, the deletion of y must have occurred after the operation deleting x had set its back_link pointer at line 6; otherwise the auxiliary node following y would have been included in the chain found in lines 13–16. Thus, the chain of back_link pointers followed by the process that deleted y will lead to the same normal cell that preceded x.

Now, the only way for the operation that deleted y to have completed is for the same reason as above; i.e., another TRYDELETE operation must extend the chain of auxiliary nodes by deleting a cell z. Since the length of the list must be finite, there must be a last such deletion which, but by the argument above, cannot have completed. Thus this operation must still be in progress, contradicting the assumption that there were no TRYDELETE operations in progress.

[[File:fig11.PNG]]

= Linked Data Structures =

Given this background knowledge, we can begin to explore solutions to some specific data structures that also utilized linked lists in some fashion.

== Trees ==
=== Serial Code Example ===

Below is a code for tree traversal algorithms
its behavior is as figure below shows:

[[File: tree.PNG]]

procedure Tree_Traversal is
type Node;
type Node_Access is access Node;
type Node is record
Left : Node_Access := null;
Right : Node_Access := null;
Data : Integer;
end record;
procedure Destroy_Tree(N : in out Node_Access) is
procedure free is new Ada.Unchecked_Deallocation(Node, Node_Access);
begin
if N.Left /= null then
Destroy_Tree(N.Left);
end if;
if N.Right /= null then
Destroy_Tree(N.Right);
end if;
Free(N);
end Destroy_Tree;
function Tree(Value : Integer; Left : Node_Access; Right : Node_Access) return Node_Access is
Temp : Node_Access := new Node;
begin
Temp.Data := Value;
Temp.Left := Left;
Temp.Right := Right;
return Temp;
end Tree;
procedure Preorder(N : Node_Access) is
begin
Put(Integer'Image(N.Data));
if N.Left /= null then
Preorder(N.Left);
end if;
if N.Right /= null then
Preorder(N.Right);
end if;
end Preorder;
procedure Inorder(N : Node_Access) is
begin
if N.Left /= null then
Inorder(N.Left);
end if;
Put(Integer'Image(N.Data));
if N.Right /= null then
Inorder(N.Right);
end if;
end Inorder;
procedure Postorder(N : Node_Access) is
begin
if N.Left /= null then
Postorder(N.Left);
end if;
if N.Right /= null then
Postorder(N.Right);
end if;
Put(Integer'Image(N.Data));
end Postorder;
procedure Levelorder(N : Node_Access) is
package Queues is new Ada.Containers.Doubly_Linked_Lists(Node_Access);
use Queues;
Node_Queue : List;
Next : Node_Access;
begin
Node_Queue.Append(N);
while not Is_Empty(Node_Queue) loop
Next := First_Element(Node_Queue);
Delete_First(Node_Queue);
Put(Integer'Image(Next.Data));
if Next.Left /= null then
Node_Queue.Append(Next.Left);
end if;
if Next.Right /= null then
Node_Queue.Append(Next.Right);
end if;
end loop;
end Levelorder;
N : Node_Access;
begin
N := Tree(1,
Tree(2,
Tree(4,
Tree(7, null, null),
null),
Tree(5, null, null)),
Tree(3,
Tree(6,
Tree(8, null, null),
Tree(9, null, null)),
null));

Put("preorder: ");
Preorder(N);
New_Line;
Put("inorder: ");
Inorder(N);
New_Line;
Put("postorder: ");
Postorder(N);
New_Line;
Put("level order: ");
Levelorder(N);
New_Line;
Destroy_Tree(N);
end Tree_traversal;

=== Parallel Code Solution ===
== Hash Tables ==
=== Hash Table Intro ===

Hash tables are very efficient data structures often used in searching algorithms for fast lookup operations. Hash tables contain a series of "buckets" that function like indexes into an array, each of which can be accessed directly using their key value. The bucket for which a piece of data will be placed is determine by a special hashing function.

The major advantage of a hash table is that lookup times are essentially a constant value, much like an array with a known index. With a proper hashing function in place, it should be fairly rare that any 2 keys would generate the same value.

In the case that 2 keys do map to the same position, there is a conflict that must be dealt with in some fashion to obtain the correct value. One way that is relevant to linked list structures is to have a chained hash table in which a linked list is created with all values that have been placed in that particular bucket. The developer would have to not only take into account the proper bucket for the data being searched for, but also must considered the chained linked list.

[[File:315px-Hash table 3 1 1 0 1 0 0 SP.svg.png]]
=== Serial Code Example ===

''' Insert Example: Create new node if hash bucket doesnt exist, else append to the chain.'''

/**
* Put a key/value pair into the table by hashing the key to get the array
* index of the chain that should hold the node containing the pair.
* If an existing node with the same key is present then overwrite its value,
* otherwise add a new node.
*
*@param key key object reference
*@param val data object reference
*/
public void put(Object key, Object val)
{
int index = getIndex(key);
Node node = find(key, data[index]);
// Use helper method to determine if node with same key is already in
// chain. If not, add a new node to head of chain.
if (node == null)
{
data[index] = new Node(data[index], key, val);
}
else
{
// Otherwise update data value of existing node.
node.val = val;
}
}

/**
* Given a key object, return a data object from the table or
* null if it is not found.
*
*@param key key object reference
*@return data object reference or null if no object found
*/
public Object get(Object key)
{
Node temp = find(key, data[getIndex(key)]);
if (temp != null)
{
return temp.val;
}
else
{
return null;
}
}

''' Delete Example: Delete a node from the chain.'''
/**
* Remove a key/value pair from table if present, otherwise make no change.
*
*@param key key object reference
*/
public void remove(Object key)
{
int index = getIndex(key);
Node ref = data[index];
Node previous = null;
while (ref != null)
{
if ((ref.key).equals(key))
{
if (previous == null)
{
data[index] = ref.next;
}
else
{
previous.next = ref.next;
}
return;
}
previous = ref;
ref = ref.next;
}
}

/**
* Given a key, use a hash function to obtain the array index of the chain
* corresponding to the key.
* The hashCode method inherited (and possibly overridden)
* from class Object is called to do the hashing, with the returned
* value constrained to the hash table array bounds.
* The distribution of objects in the hash table will depend
* on the quality of the hash function implemented by hashCode.
*
*@param key reference to object to be hashed
*@return array index of chain corresponding to key
*/
private int getIndex(Object key)
{
return Math.abs(key.hashCode() % data.length);
}

/**
* Find node given a key and a chain to search.
*
*@param key key object reference
*@param ref node object reference where search will start
*@return node object holding key or null if not found
*/
private Node find(Object key, Node ref)
{
while (ref != null)
{
if ((ref.key).equals(key))
{
return ref;
}
ref = ref.next;
}
return null;
}

=== Parallel Code Solution ===

The key issue in a hash table in a parallel environment is to make sure any update/insert/delete sequences have been completed properly prior to attempting subsequent operations to make sure the data has been synched appropriately. However, since access speed is such a critical component of the design of a hash table, it is essential to try and avoid using too many locks for performing synchronization. Fortunately, a number of lock-free hash designs have been implemented to avoid this bottleneck.

== Graphs ==
=== Graph Intro ===

A graph data structure is another type of linked-list structure that focuses on data that requires linking according to various types of relationships. For example, in a networking application, one network node may have connections to a variety of other network nodes. These nodes then also link to a variety of other nodes in the network. Using this connection of nodes, it would be possible to then find a path from one specific node to another in the chain. This could be accomplished by having each node contain a linked list of pointers to all other reachable nodes.

=== Serial Code Example ===

/**
* Add a new edge to the graph.
*/
public void addEdge( String sourceName, String destName, double cost )
{
Vertex v = getVertex( sourceName );
Vertex w = getVertex( destName );
v.adj.add( new Edge( w, cost ) );
}

/**
* Single-source unweighted shortest-path algorithm.
*/
public void unweighted( String startName )
{
clearAll( );

Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );

LinkedList q = new LinkedList( );
q.addLast( start ); start.dist = 0;

while( !q.isEmpty( ) )
{
Vertex v = (Vertex) q.removeFirst( );

for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
if( w.dist == INFINITY )
{
w.dist = v.dist + 1;
w.prev = v;
q.addLast( w );
}
}
}
}

=== Parallel Code Solution ===

= Quiz =
= References =
http://oreilly.com/catalog/masteralgoc/chapter/ch08.pdf

http://www.devjavasoft.org/code/classhashtable.html

http://osr600doc.sco.com/en/SDK_c++/_Intro_graph.html

web.eecs.utk.edu/~berry/cs302s02/src/code/Chap14/Graph.java

http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html

http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg

File:Tree.PNG

2012-02-27T21:10:10Z

Xzhang26:

CSC/ECE 506 Spring 2012/ch5a ja

2012-02-27T21:09:33Z

Xzhang26: /* Serial Code Example */

== Chapter 5a CSC/ECE 506 Spring 2012 / ch5a ==

An exploration and summary of concurrency issues as it relates to linked-list based data structures such as hash tables, trees, and graphs. This topic examines concurrency problems related to each type and possible solutions to allow for parallelization.

= Introduction to Linked-List Parallel Programming =

In determining opportunities for parallel programming during the software design process, many programmers will focus exclusively on loop or array structures, rather than also considering that linked-list pointer-based structures could also provide opportunities to run code in parallel across different processors.

For example, one common parallel technique used in an array processing algorithm is the copy-scan technique. This technique involves copying rows of data from one processor to another in a log(n) fashion until all processors have their own copy of that row. From there, you could perform a reduction technique to generate a sum of all the data, all while working in a parallel fashion. Take the following grid:

The basic process for copy-scan would be to:
Step 1) Copy the row 1 array to row 2.
Step 2) Copy the row 1 array to row 3, row 2 to row 4, etc on the next run.
Step 3) Continue in this manner until all rows have been copied in a log(n) fashion.
Step 4) Perform the parallel operations to generate the desired result (reduction for sum, etc.).

[[File:CopyScan.gif]]

But how does this same process work in the linked list world?

With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.

Step 1) Each processor will make a copy of the pointer it holds to it's neighbor.
Step 2) Next, each processor will make a pointer to the processor 2 steps away.
Step 3) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.
Step 4) Perform the parallel operations to generate the desired result.

[[File:linkedlist.gif]]

However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism on critical sections to avoid race conditions. To make sure the results are correct, it is important that operations can be serialized appropriately and that data remains current and synchronized.

In this chapter, we will explore 3 linked-list based data structures and the concurrency issues they present: hash tables, trees, and graphs.

= Linked Data Structure algorithms extension =
== Lock free algorithms ==

In order to overcome the ABA problems (shown in figure blow), we add auxiliary nodes to the data we structure. An auxiliary node is a cell that contains only a next field. We require that every normal cell in the list have an auxiliary node as its predecessor and as its successor. We permit “chains” of auxiliary nodes in the list (i.e., we do not require that every auxiliary node have a normal cell as its predecessor and successor), although such chains are undesirable for performance reasons.

[[File:fig3.PNG]]

The list also contains two dummy cells as the first and last normal cells in the list. These two cells are pointed at by the root pointers First and Last. These dummy cells need not, respectively, be preceded and followed by auxiliary nodes. Thus, m empty list data structure consists of these two dummy cells separated by an auxiliary node.

A cursor is implemented as three pointers into the data structure: target is a pointer to the cell at the position the cursor is visiting. If the cursor is visiting the end-of-list position, then target will be equal to Last. The pointer pre-aux points to an auxiliary node in the data structure. For a cursor c, if c“.pre-aux = c“.target, then the cursor is valid; otherwise it is invalid. The pointer pre.cell points to a regular cell in the data structure. This pointer is used only by the TRYDELETE operation described below. An invalid cursor indicates that the structure of the list in t he vicinity of the cursor has changed (due to a concurrent insert ion or deletion by another process) since the pointers in the cursor were last read. The UPDATE algorithm, given in Figure 5, examines the state of the list and updates the pointers in the cursor so that it becomes valid. Since the list structure contains auxiliary nodes (perhaps more than one in a row), the UPDATE algorithm must skip over them. If two adjacent auxiliary nodes axe found in the list, the UPDATE algorithm will remove one of them.

[[File:fig5.PNG]]

Traversal of the list data structure is accomplished by using the FIRST and NEXT operations, which use the UPDATE operation. Algorithms are given in Figures 6 and 7. The NEXT operation returns FALSE if the cursor is already at the end of the list and cannot be advanced. Adding new cells into the list requires the insertion of both the cell and a new auxiliary node. This insertion is restricted to occur in the following way: The new auxiliary node will follow the new cell in the list, and insertion can only occur between an auxiliary node and a normal cell, as shown in Figure 8.

[[File:fig6.PNG]]
[[File:fig7.PNG]]
[[File:fig8.PNG]]

Figure 9 gives an algorithm, which takes as arguments a cursor and pointers to a new cell and auxiliary node. The algorithm will try to insert the new cell and auxiliary node at the position specified by the cursor, returning the value
TRUE if successful.

[[File:fig9.PNG]]

If the cursor becomes invalid, then the operation returns without inserting the new cell and returns the value FALSE. This allows a higher-level operation to detect that a change to the structure of the list occurred and to take it into account before attempting to insert the new cell again. For example, in the next section we show how the items in the list can be kept sorted using this technique.

Given a valid cursor, the cell that it is visiting can also be deleted from the list. As with the insertion of new cells, if the list structure changes (i.e., the cursor becomes invalid) then the operation fails and must be tried again. Figure 10 gives the TRYDELETE algorithm. The deletion of the cell from the list leaves an “extra” auxiliary node; concurrent processes deleting adjacent cells can result in longer chains. Most of the TRYDELETE algorithm is concerned with removing the extra auxiliary nodes from the list. Normally, removing the extra auxiliary node that results from the deletion of a cell from the list is accomplished by simply swinging the pointer in the cell pointed at by the pre-cell pointer in the cursor.

[[File:fig10.PNG]]

However, this does not always work; in particular, this cell may have itself been deleted from the list, in which case swinging its next pointer will not remove the extra auxiliary node: In order to overcome this problem, we add a back~ink field to the normal cells in the list. When a cell is deleted from the list, the pre.cell field of the cursor is copied into the cell’s backdink field. The TRYDELETE algorithm can then use these pointers to reverse back to a cell that has not been deleted from the list.

With just two processes, it is possible to create a chain of auxiliary nodes (with no intervening normal cells) of any length. However, any such chain can exist in the list only as long as some process is executing the TRYDELETE algorithm.

If all deletions have been completed, then the list will contain no extra auxiliary nodes. To see this, assume that there is a chain of two or more-+ auxiliary nodes in the list. Let z be the normal cell that was deleted from between the first two auxiliary nodes in the chain. Note that this implies that the normal cell that immediately preceded x in the list has not been deleted.
By assumption, the operation that deleted z has completed. Consider the loop at lines 17–21 of the TRYDELETE algorithm. The only way for the process to exit this 100P, and hence to complete the operation, is for another deletion operation to have extended the chain of auxiliary nodes by deleting the normal cell g immediately following the chain, since the cell z is at the front of the chain.
Furthermore, the deletion of y must have occurred after the operation deleting x had set its back_link pointer at line 6; otherwise the auxiliary node following y would have been included in the chain found in lines 13–16. Thus, the chain of back_link pointers followed by the process that deleted y will lead to the same normal cell that preceded x.

Now, the only way for the operation that deleted y to have completed is for the same reason as above; i.e., another TRYDELETE operation must extend the chain of auxiliary nodes by deleting a cell z. Since the length of the list must be finite, there must be a last such deletion which, but by the argument above, cannot have completed. Thus this operation must still be in progress, contradicting the assumption that there were no TRYDELETE operations in progress.

[[File:fig11.PNG]]

= Linked Data Structures =

Given this background knowledge, we can begin to explore solutions to some specific data structures that also utilized linked lists in some fashion.

== Trees ==
=== Serial Code Example ===

Below is a code for tree traversal algorithms
its behavior is as figure below shows:

[[File: tree.PNG]]
procedure Tree_Traversal is
type Node;
type Node_Access is access Node;
type Node is record
Left : Node_Access := null;
Right : Node_Access := null;
Data : Integer;
end record;
procedure Destroy_Tree(N : in out Node_Access) is
procedure free is new Ada.Unchecked_Deallocation(Node, Node_Access);
begin
if N.Left /= null then
Destroy_Tree(N.Left);
end if;
if N.Right /= null then
Destroy_Tree(N.Right);
end if;
Free(N);
end Destroy_Tree;
function Tree(Value : Integer; Left : Node_Access; Right : Node_Access) return Node_Access is
Temp : Node_Access := new Node;
begin
Temp.Data := Value;
Temp.Left := Left;
Temp.Right := Right;
return Temp;
end Tree;
procedure Preorder(N : Node_Access) is
begin
Put(Integer'Image(N.Data));
if N.Left /= null then
Preorder(N.Left);
end if;
if N.Right /= null then
Preorder(N.Right);
end if;
end Preorder;
procedure Inorder(N : Node_Access) is
begin
if N.Left /= null then
Inorder(N.Left);
end if;
Put(Integer'Image(N.Data));
if N.Right /= null then
Inorder(N.Right);
end if;
end Inorder;
procedure Postorder(N : Node_Access) is
begin
if N.Left /= null then
Postorder(N.Left);
end if;
if N.Right /= null then
Postorder(N.Right);
end if;
Put(Integer'Image(N.Data));
end Postorder;
procedure Levelorder(N : Node_Access) is
package Queues is new Ada.Containers.Doubly_Linked_Lists(Node_Access);
use Queues;
Node_Queue : List;
Next : Node_Access;
begin
Node_Queue.Append(N);
while not Is_Empty(Node_Queue) loop
Next := First_Element(Node_Queue);
Delete_First(Node_Queue);
Put(Integer'Image(Next.Data));
if Next.Left /= null then
Node_Queue.Append(Next.Left);
end if;
if Next.Right /= null then
Node_Queue.Append(Next.Right);
end if;
end loop;
end Levelorder;
N : Node_Access;
begin
N := Tree(1,
Tree(2,
Tree(4,
Tree(7, null, null),
null),
Tree(5, null, null)),
Tree(3,
Tree(6,
Tree(8, null, null),
Tree(9, null, null)),
null));

Put("preorder: ");
Preorder(N);
New_Line;
Put("inorder: ");
Inorder(N);
New_Line;
Put("postorder: ");
Postorder(N);
New_Line;
Put("level order: ");
Levelorder(N);
New_Line;
Destroy_Tree(N);
end Tree_traversal;

=== Parallel Code Solution ===
== Hash Tables ==
=== Hash Table Intro ===

Hash tables are very efficient data structures often used in searching algorithms for fast lookup operations. Hash tables contain a series of "buckets" that function like indexes into an array, each of which can be accessed directly using their key value. The bucket for which a piece of data will be placed is determine by a special hashing function.

The major advantage of a hash table is that lookup times are essentially a constant value, much like an array with a known index. With a proper hashing function in place, it should be fairly rare that any 2 keys would generate the same value.

In the case that 2 keys do map to the same position, there is a conflict that must be dealt with in some fashion to obtain the correct value. One way that is relevant to linked list structures is to have a chained hash table in which a linked list is created with all values that have been placed in that particular bucket. The developer would have to not only take into account the proper bucket for the data being searched for, but also must considered the chained linked list.

[[File:315px-Hash table 3 1 1 0 1 0 0 SP.svg.png]]
=== Serial Code Example ===

''' Insert Example: Create new node if hash bucket doesnt exist, else append to the chain.'''

/**
* Put a key/value pair into the table by hashing the key to get the array
* index of the chain that should hold the node containing the pair.
* If an existing node with the same key is present then overwrite its value,
* otherwise add a new node.
*
*@param key key object reference
*@param val data object reference
*/
public void put(Object key, Object val)
{
int index = getIndex(key);
Node node = find(key, data[index]);
// Use helper method to determine if node with same key is already in
// chain. If not, add a new node to head of chain.
if (node == null)
{
data[index] = new Node(data[index], key, val);
}
else
{
// Otherwise update data value of existing node.
node.val = val;
}
}

/**
* Given a key object, return a data object from the table or
* null if it is not found.
*
*@param key key object reference
*@return data object reference or null if no object found
*/
public Object get(Object key)
{
Node temp = find(key, data[getIndex(key)]);
if (temp != null)
{
return temp.val;
}
else
{
return null;
}
}

''' Delete Example: Delete a node from the chain.'''
/**
* Remove a key/value pair from table if present, otherwise make no change.
*
*@param key key object reference
*/
public void remove(Object key)
{
int index = getIndex(key);
Node ref = data[index];
Node previous = null;
while (ref != null)
{
if ((ref.key).equals(key))
{
if (previous == null)
{
data[index] = ref.next;
}
else
{
previous.next = ref.next;
}
return;
}
previous = ref;
ref = ref.next;
}
}

/**
* Given a key, use a hash function to obtain the array index of the chain
* corresponding to the key.
* The hashCode method inherited (and possibly overridden)
* from class Object is called to do the hashing, with the returned
* value constrained to the hash table array bounds.
* The distribution of objects in the hash table will depend
* on the quality of the hash function implemented by hashCode.
*
*@param key reference to object to be hashed
*@return array index of chain corresponding to key
*/
private int getIndex(Object key)
{
return Math.abs(key.hashCode() % data.length);
}

/**
* Find node given a key and a chain to search.
*
*@param key key object reference
*@param ref node object reference where search will start
*@return node object holding key or null if not found
*/
private Node find(Object key, Node ref)
{
while (ref != null)
{
if ((ref.key).equals(key))
{
return ref;
}
ref = ref.next;
}
return null;
}

=== Parallel Code Solution ===

The key issue in a hash table in a parallel environment is to make sure any update/insert/delete sequences have been completed properly prior to attempting subsequent operations to make sure the data has been synched appropriately. However, since access speed is such a critical component of the design of a hash table, it is essential to try and avoid using too many locks for performing synchronization. Fortunately, a number of lock-free hash designs have been implemented to avoid this bottleneck.

== Graphs ==
=== Graph Intro ===

A graph data structure is another type of linked-list structure that focuses on data that requires linking according to various types of relationships. For example, in a networking application, one network node may have connections to a variety of other network nodes. These nodes then also link to a variety of other nodes in the network. Using this connection of nodes, it would be possible to then find a path from one specific node to another in the chain. This could be accomplished by having each node contain a linked list of pointers to all other reachable nodes.

=== Serial Code Example ===

/**
* Add a new edge to the graph.
*/
public void addEdge( String sourceName, String destName, double cost )
{
Vertex v = getVertex( sourceName );
Vertex w = getVertex( destName );
v.adj.add( new Edge( w, cost ) );
}

/**
* Single-source unweighted shortest-path algorithm.
*/
public void unweighted( String startName )
{
clearAll( );

Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );

LinkedList q = new LinkedList( );
q.addLast( start ); start.dist = 0;

while( !q.isEmpty( ) )
{
Vertex v = (Vertex) q.removeFirst( );

for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
if( w.dist == INFINITY )
{
w.dist = v.dist + 1;
w.prev = v;
q.addLast( w );
}
}
}
}

=== Parallel Code Solution ===

= Quiz =
= References =
http://oreilly.com/catalog/masteralgoc/chapter/ch08.pdf

http://www.devjavasoft.org/code/classhashtable.html

http://osr600doc.sco.com/en/SDK_c++/_Intro_graph.html

web.eecs.utk.edu/~berry/cs302s02/src/code/Chap14/Graph.java

http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html

http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg

CSC/ECE 506 Spring 2012/ch5a ja

2012-02-27T21:04:43Z

Xzhang26: /* Tree Intro */

== Chapter 5a CSC/ECE 506 Spring 2012 / ch5a ==

An exploration and summary of concurrency issues as it relates to linked-list based data structures such as hash tables, trees, and graphs. This topic examines concurrency problems related to each type and possible solutions to allow for parallelization.

= Introduction to Linked-List Parallel Programming =

In determining opportunities for parallel programming during the software design process, many programmers will focus exclusively on loop or array structures, rather than also considering that linked-list pointer-based structures could also provide opportunities to run code in parallel across different processors.

For example, one common parallel technique used in an array processing algorithm is the copy-scan technique. This technique involves copying rows of data from one processor to another in a log(n) fashion until all processors have their own copy of that row. From there, you could perform a reduction technique to generate a sum of all the data, all while working in a parallel fashion. Take the following grid:

The basic process for copy-scan would be to:
Step 1) Copy the row 1 array to row 2.
Step 2) Copy the row 1 array to row 3, row 2 to row 4, etc on the next run.
Step 3) Continue in this manner until all rows have been copied in a log(n) fashion.
Step 4) Perform the parallel operations to generate the desired result (reduction for sum, etc.).

[[File:CopyScan.gif]]

But how does this same process work in the linked list world?

With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.

Step 1) Each processor will make a copy of the pointer it holds to it's neighbor.
Step 2) Next, each processor will make a pointer to the processor 2 steps away.
Step 3) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.
Step 4) Perform the parallel operations to generate the desired result.

[[File:linkedlist.gif]]

However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism on critical sections to avoid race conditions. To make sure the results are correct, it is important that operations can be serialized appropriately and that data remains current and synchronized.

In this chapter, we will explore 3 linked-list based data structures and the concurrency issues they present: hash tables, trees, and graphs.

= Linked Data Structure algorithms extension =
== Lock free algorithms ==

In order to overcome the ABA problems (shown in figure blow), we add auxiliary nodes to the data we structure. An auxiliary node is a cell that contains only a next field. We require that every normal cell in the list have an auxiliary node as its predecessor and as its successor. We permit “chains” of auxiliary nodes in the list (i.e., we do not require that every auxiliary node have a normal cell as its predecessor and successor), although such chains are undesirable for performance reasons.

[[File:fig3.PNG]]

The list also contains two dummy cells as the first and last normal cells in the list. These two cells are pointed at by the root pointers First and Last. These dummy cells need not, respectively, be preceded and followed by auxiliary nodes. Thus, m empty list data structure consists of these two dummy cells separated by an auxiliary node.

A cursor is implemented as three pointers into the data structure: target is a pointer to the cell at the position the cursor is visiting. If the cursor is visiting the end-of-list position, then target will be equal to Last. The pointer pre-aux points to an auxiliary node in the data structure. For a cursor c, if c“.pre-aux = c“.target, then the cursor is valid; otherwise it is invalid. The pointer pre.cell points to a regular cell in the data structure. This pointer is used only by the TRYDELETE operation described below. An invalid cursor indicates that the structure of the list in t he vicinity of the cursor has changed (due to a concurrent insert ion or deletion by another process) since the pointers in the cursor were last read. The UPDATE algorithm, given in Figure 5, examines the state of the list and updates the pointers in the cursor so that it becomes valid. Since the list structure contains auxiliary nodes (perhaps more than one in a row), the UPDATE algorithm must skip over them. If two adjacent auxiliary nodes axe found in the list, the UPDATE algorithm will remove one of them.

[[File:fig5.PNG]]

Traversal of the list data structure is accomplished by using the FIRST and NEXT operations, which use the UPDATE operation. Algorithms are given in Figures 6 and 7. The NEXT operation returns FALSE if the cursor is already at the end of the list and cannot be advanced. Adding new cells into the list requires the insertion of both the cell and a new auxiliary node. This insertion is restricted to occur in the following way: The new auxiliary node will follow the new cell in the list, and insertion can only occur between an auxiliary node and a normal cell, as shown in Figure 8.

[[File:fig6.PNG]]
[[File:fig7.PNG]]
[[File:fig8.PNG]]

Figure 9 gives an algorithm, which takes as arguments a cursor and pointers to a new cell and auxiliary node. The algorithm will try to insert the new cell and auxiliary node at the position specified by the cursor, returning the value
TRUE if successful.

[[File:fig9.PNG]]

If the cursor becomes invalid, then the operation returns without inserting the new cell and returns the value FALSE. This allows a higher-level operation to detect that a change to the structure of the list occurred and to take it into account before attempting to insert the new cell again. For example, in the next section we show how the items in the list can be kept sorted using this technique.

Given a valid cursor, the cell that it is visiting can also be deleted from the list. As with the insertion of new cells, if the list structure changes (i.e., the cursor becomes invalid) then the operation fails and must be tried again. Figure 10 gives the TRYDELETE algorithm. The deletion of the cell from the list leaves an “extra” auxiliary node; concurrent processes deleting adjacent cells can result in longer chains. Most of the TRYDELETE algorithm is concerned with removing the extra auxiliary nodes from the list. Normally, removing the extra auxiliary node that results from the deletion of a cell from the list is accomplished by simply swinging the pointer in the cell pointed at by the pre-cell pointer in the cursor.

[[File:fig10.PNG]]

However, this does not always work; in particular, this cell may have itself been deleted from the list, in which case swinging its next pointer will not remove the extra auxiliary node: In order to overcome this problem, we add a back~ink field to the normal cells in the list. When a cell is deleted from the list, the pre.cell field of the cursor is copied into the cell’s backdink field. The TRYDELETE algorithm can then use these pointers to reverse back to a cell that has not been deleted from the list.

With just two processes, it is possible to create a chain of auxiliary nodes (with no intervening normal cells) of any length. However, any such chain can exist in the list only as long as some process is executing the TRYDELETE algorithm.

If all deletions have been completed, then the list will contain no extra auxiliary nodes. To see this, assume that there is a chain of two or more-+ auxiliary nodes in the list. Let z be the normal cell that was deleted from between the first two auxiliary nodes in the chain. Note that this implies that the normal cell that immediately preceded x in the list has not been deleted.
By assumption, the operation that deleted z has completed. Consider the loop at lines 17–21 of the TRYDELETE algorithm. The only way for the process to exit this 100P, and hence to complete the operation, is for another deletion operation to have extended the chain of auxiliary nodes by deleting the normal cell g immediately following the chain, since the cell z is at the front of the chain.
Furthermore, the deletion of y must have occurred after the operation deleting x had set its back_link pointer at line 6; otherwise the auxiliary node following y would have been included in the chain found in lines 13–16. Thus, the chain of back_link pointers followed by the process that deleted y will lead to the same normal cell that preceded x.

Now, the only way for the operation that deleted y to have completed is for the same reason as above; i.e., another TRYDELETE operation must extend the chain of auxiliary nodes by deleting a cell z. Since the length of the list must be finite, there must be a last such deletion which, but by the argument above, cannot have completed. Thus this operation must still be in progress, contradicting the assumption that there were no TRYDELETE operations in progress.

[[File:fig11.PNG]]

= Linked Data Structures =

Given this background knowledge, we can begin to explore solutions to some specific data structures that also utilized linked lists in some fashion.

== Trees ==
=== Serial Code Example ===
=== Parallel Code Solution ===
== Hash Tables ==
=== Hash Table Intro ===

Hash tables are very efficient data structures often used in searching algorithms for fast lookup operations. Hash tables contain a series of "buckets" that function like indexes into an array, each of which can be accessed directly using their key value. The bucket for which a piece of data will be placed is determine by a special hashing function.

The major advantage of a hash table is that lookup times are essentially a constant value, much like an array with a known index. With a proper hashing function in place, it should be fairly rare that any 2 keys would generate the same value.

In the case that 2 keys do map to the same position, there is a conflict that must be dealt with in some fashion to obtain the correct value. One way that is relevant to linked list structures is to have a chained hash table in which a linked list is created with all values that have been placed in that particular bucket. The developer would have to not only take into account the proper bucket for the data being searched for, but also must considered the chained linked list.

[[File:315px-Hash table 3 1 1 0 1 0 0 SP.svg.png]]
=== Serial Code Example ===

''' Insert Example: Create new node if hash bucket doesnt exist, else append to the chain.'''

/**
* Put a key/value pair into the table by hashing the key to get the array
* index of the chain that should hold the node containing the pair.
* If an existing node with the same key is present then overwrite its value,
* otherwise add a new node.
*
*@param key key object reference
*@param val data object reference
*/
public void put(Object key, Object val)
{
int index = getIndex(key);
Node node = find(key, data[index]);
// Use helper method to determine if node with same key is already in
// chain. If not, add a new node to head of chain.
if (node == null)
{
data[index] = new Node(data[index], key, val);
}
else
{
// Otherwise update data value of existing node.
node.val = val;
}
}

/**
* Given a key object, return a data object from the table or
* null if it is not found.
*
*@param key key object reference
*@return data object reference or null if no object found
*/
public Object get(Object key)
{
Node temp = find(key, data[getIndex(key)]);
if (temp != null)
{
return temp.val;
}
else
{
return null;
}
}

''' Delete Example: Delete a node from the chain.'''
/**
* Remove a key/value pair from table if present, otherwise make no change.
*
*@param key key object reference
*/
public void remove(Object key)
{
int index = getIndex(key);
Node ref = data[index];
Node previous = null;
while (ref != null)
{
if ((ref.key).equals(key))
{
if (previous == null)
{
data[index] = ref.next;
}
else
{
previous.next = ref.next;
}
return;
}
previous = ref;
ref = ref.next;
}
}

/**
* Given a key, use a hash function to obtain the array index of the chain
* corresponding to the key.
* The hashCode method inherited (and possibly overridden)
* from class Object is called to do the hashing, with the returned
* value constrained to the hash table array bounds.
* The distribution of objects in the hash table will depend
* on the quality of the hash function implemented by hashCode.
*
*@param key reference to object to be hashed
*@return array index of chain corresponding to key
*/
private int getIndex(Object key)
{
return Math.abs(key.hashCode() % data.length);
}

/**
* Find node given a key and a chain to search.
*
*@param key key object reference
*@param ref node object reference where search will start
*@return node object holding key or null if not found
*/
private Node find(Object key, Node ref)
{
while (ref != null)
{
if ((ref.key).equals(key))
{
return ref;
}
ref = ref.next;
}
return null;
}

=== Parallel Code Solution ===

The key issue in a hash table in a parallel environment is to make sure any update/insert/delete sequences have been completed properly prior to attempting subsequent operations to make sure the data has been synched appropriately. However, since access speed is such a critical component of the design of a hash table, it is essential to try and avoid using too many locks for performing synchronization. Fortunately, a number of lock-free hash designs have been implemented to avoid this bottleneck.

== Graphs ==
=== Graph Intro ===

A graph data structure is another type of linked-list structure that focuses on data that requires linking according to various types of relationships. For example, in a networking application, one network node may have connections to a variety of other network nodes. These nodes then also link to a variety of other nodes in the network. Using this connection of nodes, it would be possible to then find a path from one specific node to another in the chain. This could be accomplished by having each node contain a linked list of pointers to all other reachable nodes.

=== Serial Code Example ===

/**
* Add a new edge to the graph.
*/
public void addEdge( String sourceName, String destName, double cost )
{
Vertex v = getVertex( sourceName );
Vertex w = getVertex( destName );
v.adj.add( new Edge( w, cost ) );
}

/**
* Single-source unweighted shortest-path algorithm.
*/
public void unweighted( String startName )
{
clearAll( );

Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );

LinkedList q = new LinkedList( );
q.addLast( start ); start.dist = 0;

while( !q.isEmpty( ) )
{
Vertex v = (Vertex) q.removeFirst( );

for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
if( w.dist == INFINITY )
{
w.dist = v.dist + 1;
w.prev = v;
q.addLast( w );
}
}
}
}

=== Parallel Code Solution ===

= Quiz =
= References =
http://oreilly.com/catalog/masteralgoc/chapter/ch08.pdf
http://www.devjavasoft.org/code/classhashtable.html
http://osr600doc.sco.com/en/SDK_c++/_Intro_graph.html
web.eecs.utk.edu/~berry/cs302s02/src/code/Chap14/Graph.java
http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html
http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg

CSC/ECE 506 Spring 2012/ch5a ja

2012-02-27T21:03:51Z

Xzhang26:

== Chapter 5a CSC/ECE 506 Spring 2012 / ch5a ==

An exploration and summary of concurrency issues as it relates to linked-list based data structures such as hash tables, trees, and graphs. This topic examines concurrency problems related to each type and possible solutions to allow for parallelization.

= Introduction to Linked-List Parallel Programming =

In determining opportunities for parallel programming during the software design process, many programmers will focus exclusively on loop or array structures, rather than also considering that linked-list pointer-based structures could also provide opportunities to run code in parallel across different processors.

For example, one common parallel technique used in an array processing algorithm is the copy-scan technique. This technique involves copying rows of data from one processor to another in a log(n) fashion until all processors have their own copy of that row. From there, you could perform a reduction technique to generate a sum of all the data, all while working in a parallel fashion. Take the following grid:

The basic process for copy-scan would be to:
Step 1) Copy the row 1 array to row 2.
Step 2) Copy the row 1 array to row 3, row 2 to row 4, etc on the next run.
Step 3) Continue in this manner until all rows have been copied in a log(n) fashion.
Step 4) Perform the parallel operations to generate the desired result (reduction for sum, etc.).

[[File:CopyScan.gif]]

But how does this same process work in the linked list world?

With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.

Step 1) Each processor will make a copy of the pointer it holds to it's neighbor.
Step 2) Next, each processor will make a pointer to the processor 2 steps away.
Step 3) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.
Step 4) Perform the parallel operations to generate the desired result.

[[File:linkedlist.gif]]

However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism on critical sections to avoid race conditions. To make sure the results are correct, it is important that operations can be serialized appropriately and that data remains current and synchronized.

In this chapter, we will explore 3 linked-list based data structures and the concurrency issues they present: hash tables, trees, and graphs.

= Linked Data Structure algorithms extension =
== Lock free algorithms ==

In order to overcome the ABA problems (shown in figure blow), we add auxiliary nodes to the data we structure. An auxiliary node is a cell that contains only a next field. We require that every normal cell in the list have an auxiliary node as its predecessor and as its successor. We permit “chains” of auxiliary nodes in the list (i.e., we do not require that every auxiliary node have a normal cell as its predecessor and successor), although such chains are undesirable for performance reasons.

[[File:fig3.PNG]]

The list also contains two dummy cells as the first and last normal cells in the list. These two cells are pointed at by the root pointers First and Last. These dummy cells need not, respectively, be preceded and followed by auxiliary nodes. Thus, m empty list data structure consists of these two dummy cells separated by an auxiliary node.

A cursor is implemented as three pointers into the data structure: target is a pointer to the cell at the position the cursor is visiting. If the cursor is visiting the end-of-list position, then target will be equal to Last. The pointer pre-aux points to an auxiliary node in the data structure. For a cursor c, if c“.pre-aux = c“.target, then the cursor is valid; otherwise it is invalid. The pointer pre.cell points to a regular cell in the data structure. This pointer is used only by the TRYDELETE operation described below. An invalid cursor indicates that the structure of the list in t he vicinity of the cursor has changed (due to a concurrent insert ion or deletion by another process) since the pointers in the cursor were last read. The UPDATE algorithm, given in Figure 5, examines the state of the list and updates the pointers in the cursor so that it becomes valid. Since the list structure contains auxiliary nodes (perhaps more than one in a row), the UPDATE algorithm must skip over them. If two adjacent auxiliary nodes axe found in the list, the UPDATE algorithm will remove one of them.

[[File:fig5.PNG]]

Traversal of the list data structure is accomplished by using the FIRST and NEXT operations, which use the UPDATE operation. Algorithms are given in Figures 6 and 7. The NEXT operation returns FALSE if the cursor is already at the end of the list and cannot be advanced. Adding new cells into the list requires the insertion of both the cell and a new auxiliary node. This insertion is restricted to occur in the following way: The new auxiliary node will follow the new cell in the list, and insertion can only occur between an auxiliary node and a normal cell, as shown in Figure 8.

[[File:fig6.PNG]]
[[File:fig7.PNG]]
[[File:fig8.PNG]]

Figure 9 gives an algorithm, which takes as arguments a cursor and pointers to a new cell and auxiliary node. The algorithm will try to insert the new cell and auxiliary node at the position specified by the cursor, returning the value
TRUE if successful.

[[File:fig9.PNG]]

If the cursor becomes invalid, then the operation returns without inserting the new cell and returns the value FALSE. This allows a higher-level operation to detect that a change to the structure of the list occurred and to take it into account before attempting to insert the new cell again. For example, in the next section we show how the items in the list can be kept sorted using this technique.

Given a valid cursor, the cell that it is visiting can also be deleted from the list. As with the insertion of new cells, if the list structure changes (i.e., the cursor becomes invalid) then the operation fails and must be tried again. Figure 10 gives the TRYDELETE algorithm. The deletion of the cell from the list leaves an “extra” auxiliary node; concurrent processes deleting adjacent cells can result in longer chains. Most of the TRYDELETE algorithm is concerned with removing the extra auxiliary nodes from the list. Normally, removing the extra auxiliary node that results from the deletion of a cell from the list is accomplished by simply swinging the pointer in the cell pointed at by the pre-cell pointer in the cursor.

[[File:fig10.PNG]]

However, this does not always work; in particular, this cell may have itself been deleted from the list, in which case swinging its next pointer will not remove the extra auxiliary node: In order to overcome this problem, we add a back~ink field to the normal cells in the list. When a cell is deleted from the list, the pre.cell field of the cursor is copied into the cell’s backdink field. The TRYDELETE algorithm can then use these pointers to reverse back to a cell that has not been deleted from the list.

With just two processes, it is possible to create a chain of auxiliary nodes (with no intervening normal cells) of any length. However, any such chain can exist in the list only as long as some process is executing the TRYDELETE algorithm.

If all deletions have been completed, then the list will contain no extra auxiliary nodes. To see this, assume that there is a chain of two or more-+ auxiliary nodes in the list. Let z be the normal cell that was deleted from between the first two auxiliary nodes in the chain. Note that this implies that the normal cell that immediately preceded x in the list has not been deleted.
By assumption, the operation that deleted z has completed. Consider the loop at lines 17–21 of the TRYDELETE algorithm. The only way for the process to exit this 100P, and hence to complete the operation, is for another deletion operation to have extended the chain of auxiliary nodes by deleting the normal cell g immediately following the chain, since the cell z is at the front of the chain.
Furthermore, the deletion of y must have occurred after the operation deleting x had set its back_link pointer at line 6; otherwise the auxiliary node following y would have been included in the chain found in lines 13–16. Thus, the chain of back_link pointers followed by the process that deleted y will lead to the same normal cell that preceded x.

Now, the only way for the operation that deleted y to have completed is for the same reason as above; i.e., another TRYDELETE operation must extend the chain of auxiliary nodes by deleting a cell z. Since the length of the list must be finite, there must be a last such deletion which, but by the argument above, cannot have completed. Thus this operation must still be in progress, contradicting the assumption that there were no TRYDELETE operations in progress.

[[File:fig11.PNG]]

= Linked Data Structures =

Given this background knowledge, we can begin to explore solutions to some specific data structures that also utilized linked lists in some fashion.

== Trees ==
=== Tree Intro ===
=== Serial Code Example ===
=== Parallel Code Solution ===
== Hash Tables ==
=== Hash Table Intro ===

Hash tables are very efficient data structures often used in searching algorithms for fast lookup operations. Hash tables contain a series of "buckets" that function like indexes into an array, each of which can be accessed directly using their key value. The bucket for which a piece of data will be placed is determine by a special hashing function.

The major advantage of a hash table is that lookup times are essentially a constant value, much like an array with a known index. With a proper hashing function in place, it should be fairly rare that any 2 keys would generate the same value.

In the case that 2 keys do map to the same position, there is a conflict that must be dealt with in some fashion to obtain the correct value. One way that is relevant to linked list structures is to have a chained hash table in which a linked list is created with all values that have been placed in that particular bucket. The developer would have to not only take into account the proper bucket for the data being searched for, but also must considered the chained linked list.

[[File:315px-Hash table 3 1 1 0 1 0 0 SP.svg.png]]
=== Serial Code Example ===

''' Insert Example: Create new node if hash bucket doesnt exist, else append to the chain.'''

/**
* Put a key/value pair into the table by hashing the key to get the array
* index of the chain that should hold the node containing the pair.
* If an existing node with the same key is present then overwrite its value,
* otherwise add a new node.
*
*@param key key object reference
*@param val data object reference
*/
public void put(Object key, Object val)
{
int index = getIndex(key);
Node node = find(key, data[index]);
// Use helper method to determine if node with same key is already in
// chain. If not, add a new node to head of chain.
if (node == null)
{
data[index] = new Node(data[index], key, val);
}
else
{
// Otherwise update data value of existing node.
node.val = val;
}
}

/**
* Given a key object, return a data object from the table or
* null if it is not found.
*
*@param key key object reference
*@return data object reference or null if no object found
*/
public Object get(Object key)
{
Node temp = find(key, data[getIndex(key)]);
if (temp != null)
{
return temp.val;
}
else
{
return null;
}
}

''' Delete Example: Delete a node from the chain.'''
/**
* Remove a key/value pair from table if present, otherwise make no change.
*
*@param key key object reference
*/
public void remove(Object key)
{
int index = getIndex(key);
Node ref = data[index];
Node previous = null;
while (ref != null)
{
if ((ref.key).equals(key))
{
if (previous == null)
{
data[index] = ref.next;
}
else
{
previous.next = ref.next;
}
return;
}
previous = ref;
ref = ref.next;
}
}

/**
* Given a key, use a hash function to obtain the array index of the chain
* corresponding to the key.
* The hashCode method inherited (and possibly overridden)
* from class Object is called to do the hashing, with the returned
* value constrained to the hash table array bounds.
* The distribution of objects in the hash table will depend
* on the quality of the hash function implemented by hashCode.
*
*@param key reference to object to be hashed
*@return array index of chain corresponding to key
*/
private int getIndex(Object key)
{
return Math.abs(key.hashCode() % data.length);
}

/**
* Find node given a key and a chain to search.
*
*@param key key object reference
*@param ref node object reference where search will start
*@return node object holding key or null if not found
*/
private Node find(Object key, Node ref)
{
while (ref != null)
{
if ((ref.key).equals(key))
{
return ref;
}
ref = ref.next;
}
return null;
}

=== Parallel Code Solution ===

The key issue in a hash table in a parallel environment is to make sure any update/insert/delete sequences have been completed properly prior to attempting subsequent operations to make sure the data has been synched appropriately. However, since access speed is such a critical component of the design of a hash table, it is essential to try and avoid using too many locks for performing synchronization. Fortunately, a number of lock-free hash designs have been implemented to avoid this bottleneck.

== Graphs ==
=== Graph Intro ===

A graph data structure is another type of linked-list structure that focuses on data that requires linking according to various types of relationships. For example, in a networking application, one network node may have connections to a variety of other network nodes. These nodes then also link to a variety of other nodes in the network. Using this connection of nodes, it would be possible to then find a path from one specific node to another in the chain. This could be accomplished by having each node contain a linked list of pointers to all other reachable nodes.

=== Serial Code Example ===

/**
* Add a new edge to the graph.
*/
public void addEdge( String sourceName, String destName, double cost )
{
Vertex v = getVertex( sourceName );
Vertex w = getVertex( destName );
v.adj.add( new Edge( w, cost ) );
}

/**
* Single-source unweighted shortest-path algorithm.
*/
public void unweighted( String startName )
{
clearAll( );

Vertex start = (Vertex) vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );

LinkedList q = new LinkedList( );
q.addLast( start ); start.dist = 0;

while( !q.isEmpty( ) )
{
Vertex v = (Vertex) q.removeFirst( );

for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )
{
Edge e = (Edge) itr.next( );
Vertex w = e.dest;
if( w.dist == INFINITY )
{
w.dist = v.dist + 1;
w.prev = v;
q.addLast( w );
}
}
}
}

=== Parallel Code Solution ===

= Quiz =
= References =
http://oreilly.com/catalog/masteralgoc/chapter/ch08.pdf
http://www.devjavasoft.org/code/classhashtable.html
http://osr600doc.sco.com/en/SDK_c++/_Intro_graph.html
web.eecs.utk.edu/~berry/cs302s02/src/code/Chap14/Graph.java
http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html
http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg

File:Para3.PNG

2012-02-27T20:53:20Z

Xzhang26:

File:Para2.PNG

2012-02-27T20:53:00Z

Xzhang26:

File:Para tree1.PNG

2012-02-27T20:52:37Z

Xzhang26:

File:Fig11.PNG

2012-02-27T20:51:03Z

Xzhang26:

File:Fig10.PNG

2012-02-27T20:50:49Z

Xzhang26:

File:Fig9.PNG

2012-02-27T20:50:39Z

Xzhang26:

File:Fig8.PNG

2012-02-27T20:50:26Z

Xzhang26:

File:Fig7.PNG

2012-02-27T20:50:16Z

Xzhang26:

File:Fig6.PNG

2012-02-27T20:49:18Z

Xzhang26:

File:Fig5.PNG

2012-02-27T20:48:51Z

Xzhang26:

File:Fig3.PNG

2012-02-27T20:48:29Z

Xzhang26: