CSC/ECE 506 Spring 2012/ch5a ja: Difference between revisions

From Expertiza_Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 10: Line 10:


The basic process for copy-scan would be to:
The basic process for copy-scan would be to:
   a) Copy row 1 to row 2
   a) Copy row 1 to row 2.
   b) Copy row 1 to row 3, row 2 to row 4, etc
   b) Copy row 1 to row 3, row 2 to row 4, etc on the next run.
   c) Continue in this manner until all rows have been copied in a logn fashion.
   c) Continue in this manner until all rows have been copied in a log(n) fashion.
 
Similarly, in the linked list world, there is the concept of pointer doubling.
  a) Each processor will make a copy of the pointer it holds to it's neighbor.
  b) Next, each processor will make a pointer to the processor 2 steps away.
  c) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.


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

Revision as of 15:02, 23 February 2012

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 in your software design, many programmers will focus exclusively on loop or array structures, rather than also considering the possibilities that linked-list pointer-based structures could also provide.

For example, one parallel technique used in array processing is the copy-scan technique. Take the following grid:

The basic process for copy-scan would be to:

 a) Copy row 1 to row 2.
 b) Copy row 1 to row 3, row 2 to row 4, etc on the next run.
 c) Continue in this manner until all rows have been copied in a log(n) fashion.

Similarly, in the linked list world, there is the concept of pointer doubling.

 a) Each processor will make a copy of the pointer it holds to it's neighbor.
 b) Next, each processor will make a pointer to the processor 2 steps away.
 c) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.

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 Conflicts

Insertions

Deletions

Search

Linked Data Structures

Trees

Tree Intro

Serial Code Example

Parallel Code Solution

Hash Tables

Hash Table Intro

Serial Code Example

Parallel Code Solution

Graphs

Graph Intro

Serial Code Example

Parallel Code Solution

Quiz

References