CSC/ECE 506 Spring 2014/5a rm - Revision history

Admin: /* Conclusion */

2014-04-26T20:14:44Z

Conclusion

← Older revision		Revision as of 20:14, 26 April 2014
Line 520:		Line 520:

	= Conclusion =		= Conclusion =
	Through this ~~Wikipedia~~ page we have shown how parallelization can be done for trees, hash tables, and graphs. While the structures are more complex than the single linked lists outlined in the Solihin ~~text book~~, their parallelization methods pull heavily from the fundamental locking techniques taught there. In several cases, the exact same locking techniques are used and it is the LDS which is manipulated to create single linked lists. In this way we are able to show how these basic principals taught by the text book are able to be expanded and carried into more complex structures and problems.		Through this wiki page we have shown how parallelization can be done for trees, hash tables, and graphs. While the structures are more complex than the single linked lists outlined in the Solihin textbook, their parallelization methods pull heavily from the fundamental locking techniques taught there. In several cases, the exact same locking techniques are used and it is the LDS which is manipulated to create single linked lists. In this way we are able to show how these basic principals taught by the text book are able to be expanded and carried into more complex structures and problems.


	= Quiz =		= Quiz =

Remcelfr: /* Introduction to Linked-List Parallel Programming */

2014-03-04T02:28:45Z

Introduction to Linked-List Parallel Programming

← Older revision		Revision as of 02:28, 4 March 2014
Line 44:		Line 44:
	[[File:PartialSums4.png]]		[[File:PartialSums4.png]]

	The advantages of pointer doubling aren't just for single linked lists. This algorithm can also be used for finding the roots of trees, which we will talk more about in the next section. The way in which this algorithm is used, is similar to the previous example. Each node will point to the next node until it reaches the end. The result is that every node will have a pointer to the root of the tree. Below is an example of this process.[[#References]<sup>[24]</sup>]]		The advantages of pointer doubling aren't just for single linked lists. This algorithm can also be used for finding the roots of trees, which we will talk more about in the next section. The way in which this algorithm is used, is similar to the previous example. Each node will point to the next node until it reaches the end. The result is that every node will have a pointer to the root of the tree. Below is an example of this process.[[#References\|<sup>[24]</sup>]]

	[[File:Pointer_Jumping_Example.png]]		[[File:Pointer_Jumping_Example.png]]

Remcelfr: /* Introduction to Linked-List Parallel Programming */

2014-03-04T02:28:11Z

Introduction to Linked-List Parallel Programming

← Older revision		Revision as of 02:28, 4 March 2014
Line 44:		Line 44:
	[[File:PartialSums4.png]]		[[File:PartialSums4.png]]

	The advantages of pointer doubling aren't just for single linked lists. This algorithm can also be used for finding the roots of trees, which we will talk more about in the next section. The way in which this algorithm is used, is similar to the previous example. Each node will point to the next node until it reaches the end. The result is that every node will have a pointer to the root of the tree. Below is an example of this process.[[#References]<sup>[24]</sup]]		The advantages of pointer doubling aren't just for single linked lists. This algorithm can also be used for finding the roots of trees, which we will talk more about in the next section. The way in which this algorithm is used, is similar to the previous example. Each node will point to the next node until it reaches the end. The result is that every node will have a pointer to the root of the tree. Below is an example of this process.[[#References]<sup>[24]</sup>]]

	[[File:Pointer_Jumping_Example.png]]		[[File:Pointer_Jumping_Example.png]]

Remcelfr: /* References */

2014-03-04T02:27:43Z

References

← Older revision		Revision as of 02:27, 4 March 2014
Line 570:		Line 570:
	#P.-A. Larson, M. R. Krishnan,and G. V. Reilly, “Scaleable hash table for shared-memory multiprocessor system,” US Patent number: 6578131, 2003 http://ww2.cs.mu.oz.au/~pjs/papers/paralleldp.pdf		#P.-A. Larson, M. R. Krishnan,and G. V. Reilly, “Scaleable hash table for shared-memory multiprocessor system,” US Patent number: 6578131, 2003 http://ww2.cs.mu.oz.au/~pjs/papers/paralleldp.pdf
	#Calvin C.-Y.Chen, Sajal K. Das, "Parallel Breadth-first and Breadth-depth traversals of general trees", Advances in Computing and Information - ICCP '90, ISBN: 978-3-540-46677-2		#Calvin C.-Y.Chen, Sajal K. Das, "Parallel Breadth-first and Breadth-depth traversals of general trees", Advances in Computing and Information - ICCP '90, ISBN: 978-3-540-46677-2
			#http://en.wikipedia.org/wiki/Pointer_jumping

Remcelfr: /* Introduction to Linked-List Parallel Programming */

2014-03-04T02:27:19Z

Introduction to Linked-List Parallel Programming

← Older revision		Revision as of 02:27, 4 March 2014
Line 44:		Line 44:
	[[File:PartialSums4.png]]		[[File:PartialSums4.png]]

	The advantages of pointer doubling aren't just for single linked lists. This algorithm can also be used for finding the roots of trees, which we will talk more about in the next section. The way in which this algorithm is used, is similar to the previous example. Each node will point to the next node until it reaches the end. The result is that every node will have a pointer to the root of the tree. Below is an example of this process.[[#References]<sup>[22]</sup]]		The advantages of pointer doubling aren't just for single linked lists. This algorithm can also be used for finding the roots of trees, which we will talk more about in the next section. The way in which this algorithm is used, is similar to the previous example. Each node will point to the next node until it reaches the end. The result is that every node will have a pointer to the root of the tree. Below is an example of this process.[[#References]<sup>[24]</sup]]

	[[File:Pointer_Jumping_Example.~~svg~~]]		[[File:Pointer_Jumping_Example.png]]

	However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism or other parallel technique for [http://en.wikipedia.org/wiki/Critical_section critical sections] in order to avoid [http://en.wikipedia.org/wiki/Race_condition 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.		However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism or other parallel technique for [http://en.wikipedia.org/wiki/Critical_section critical sections] in order to avoid [http://en.wikipedia.org/wiki/Race_condition 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.

Remcelfr: /* Introduction to Linked-List Parallel Programming */

2014-03-04T02:23:53Z

Introduction to Linked-List Parallel Programming

← Older revision		Revision as of 02:23, 4 March 2014
Line 18:		Line 18:

	The basic process for copy-scan would be to:		The basic process for copy-scan would be to:
	~~Step 1)~~ Copy the row 1 array to row 2.		# 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.		# 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.		# 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.).		# Perform the parallel operations to generate the desired result (reduction for sum, etc.).

	[[File:CopyScan.gif]]		[[File:CopyScan.gif]]
Line 29:		Line 29:
	With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.[[#References\|<sup>[1]</sup>]]		With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.[[#References\|<sup>[1]</sup>]]

	~~Step 1)~~ Each processor will make a copy of the pointer it holds to its neighbor.		# Each processor will make a copy of the pointer it holds to its neighbor.
	~~Step 2)~~ Next, each processor will make a pointer to the processor 2 steps away.		# 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.		# 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.		# Perform the parallel operations to generate the desired result.

	One algorithm that pointer doubling can be used for is to perform partial sums of a linked list. The way in which this is accomplished is by adding the value held by the node with the value stored in the node it is pointing to. This is repeated until all pointers have reached the end of the list. The result is a linked list which contains the sum of the node and all preceding nodes. Below shows an example of this algorithm in action.		One algorithm that pointer doubling can be used for is to perform partial sums of a linked list. The way in which this is accomplished is by adding the value held by the node with the value stored in the node it is pointing to. This is repeated until all pointers have reached the end of the list. The result is a linked list which contains the sum of the node and all preceding nodes. Below shows an example of this algorithm in action.
Line 44:		Line 44:
	[[File:PartialSums4.png]]		[[File:PartialSums4.png]]

			The advantages of pointer doubling aren't just for single linked lists. This algorithm can also be used for finding the roots of trees, which we will talk more about in the next section. The way in which this algorithm is used, is similar to the previous example. Each node will point to the next node until it reaches the end. The result is that every node will have a pointer to the root of the tree. Below is an example of this process.[[#References]<sup>[22]</sup]]

			[[File:Pointer_Jumping_Example.svg]]

	However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism or other parallel technique for [http://en.wikipedia.org/wiki/Critical_section critical sections] in order to avoid [http://en.wikipedia.org/wiki/Race_condition 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.		However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism or other parallel technique for [http://en.wikipedia.org/wiki/Critical_section critical sections] in order to avoid [http://en.wikipedia.org/wiki/Race_condition 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.

Remcelfr: /* Introduction to Linked-List Parallel Programming */

2014-03-04T02:07:55Z

Introduction to Linked-List Parallel Programming

← Older revision		Revision as of 02:07, 4 March 2014
Line 34:		Line 34:
	Step 4) Perform the parallel operations to generate the desired result.		Step 4) Perform the parallel operations to generate the desired result.

	One ~~of the uses of~~ pointer doubling is to perform partial sums of a linked list. The way in which this is accomplished is by adding the value held by the node with the value stored in the node it is pointing to. This is repeated until all pointers have reached the end of the list. The result is a linked list which contains the sum of the node and all preceding nodes. Below shows an example of this ~~operation~~ in action.		One algorithm that pointer doubling can be used for is to perform partial sums of a linked list. The way in which this is accomplished is by adding the value held by the node with the value stored in the node it is pointing to. This is repeated until all pointers have reached the end of the list. The result is a linked list which contains the sum of the node and all preceding nodes. Below shows an example of this algorithm in action.

	[[File:PartialSums1.png]]		[[File:PartialSums1.png]]

Remcelfr: /* Parallel Solution */

2014-03-04T02:00:02Z

Parallel Solution

← Older revision		Revision as of 02:00, 4 March 2014
Line 223:		Line 223:
	A [http://www.cs.bu.edu/teaching/c/tree/breadth-first/ Breadth-First traversal] is somewhat more complicated to implement as a		A [http://www.cs.bu.edu/teaching/c/tree/breadth-first/ Breadth-First traversal] is somewhat more complicated to implement as a
	parallel system because at each level, it must access nodes from all of the parallel		parallel system because at each level, it must access nodes from all of the parallel
	processors. Theoretically, a Breadth-First traversal can achieve complete parallelization of Pre-, In-, and Post-Order traversals. ~~However~~, the amount of processor-to-processor data transmission adds in a greater potential for delays, thus slowing		processors. Theoretically, a Breadth-First traversal can achieve complete parallelization of Pre-, In-, and Post-Order traversals. As the degree of parallelism is increased, the speed up increases as per Amdahl's law. One thing to remember in the parllelization though, is that the amount of processor-to-processor data transmission adds in a greater potential for delays, thus slowing
	down the algorithm. Nevertheless, as the size of the tree increases the size of the		down the algorithm. Nevertheless, as the size of the tree increases the size of the
	generations grows at the rate of 2n while the number of synchronizations grows at a		generations grows at the rate of 2n while the number of synchronizations grows at a

Remcelfr: /* Serial Code Example */

2014-03-04T01:54:19Z

Serial Code Example

← Older revision		Revision as of 01:54, 4 March 2014
Line 61:		Line 61:
	=== Serial Code Example ===		=== Serial Code Example ===

	In this section, we will begin by showing a serial tree traversal algorithm using the tree shown below.[[#References\|<sup>[8]</sup>]]		In this section, we will begin by showing different serial tree traversal algorithm using the tree shown below.[[#References\|<sup>[8]</sup>]] The four ordering algorithms that we will cover are pre-order, in-order, post-order, and level order.

	[[File: tree.PNG]]		[[File: tree.PNG]]

Remcelfr: /* Parallel Solution */

2014-03-04T01:51:20Z

Parallel Solution

← Older revision		Revision as of 01:51, 4 March 2014
Line 202:		Line 202:

	=== Parallel Solution ===		=== Parallel Solution ===
	In many ways, a tree is the perfect candidate for parallelism. In a tree, each		Now that we have seen what a standard parallel tree traversal is, we will look at how trees can be parallelized. In many ways, a tree is the perfect candidate for parallelism. In a tree, each
	node/subtree is independent. As a result, we can split up a large tree into 2, 4, 8, or		node/subtree is independent. As a result, we can split up a large tree into 2, 4, 8, or
	more subtrees and hold subtree on each processor. Then, the only duplicated data		more subtrees and hold subtree on each processor. Then, the only duplicated data