CSC/ECE 506 Spring 2012/ch5a ja - Revision history

Ksharida: /* References */

2013-02-27T19:59:57Z

References

← Older revision		Revision as of 19:59, 27 February 2013
Line 388:		Line 388:
	#http://en.wikipedia.org/wiki/Breadth-first_search		#http://en.wikipedia.org/wiki/Breadth-first_search
	#http://code.wikia.com/wiki/Hashmap		#http://code.wikia.com/wiki/Hashmap
			#http://code.wikia.com/wiki/Hashmap
			#http://www.shodor.org/petascale/materials/UPModules/Binary_Tree_Traversal

Japlemmo: /* Opportunities for Parallelization */

2012-03-05T20:16:07Z

Opportunities for Parallelization

← Older revision		Revision as of 20:16, 5 March 2012
Line 202:		Line 202:
	This would, however, involve a good bit of synchronization, as each processor would need to wait in case a lock was being placed on a specific bucket in the cache hashmap. Unfortunately, traditional locking would be a bad solution to this problem as processors need to run very quickly. Having to wait for locks would destroy the application processing time. The need for a non-locking solution is critical to performance.		This would, however, involve a good bit of synchronization, as each processor would need to wait in case a lock was being placed on a specific bucket in the cache hashmap. Unfortunately, traditional locking would be a bad solution to this problem as processors need to run very quickly. Having to wait for locks would destroy the application processing time. The need for a non-locking solution is critical to performance.

	In Java, the standard class utilized for hashing is the HashMap class. This class has a fundamental weakness though in that the entire map requires synchronization prior to each access. This causes a lot of contention and many bottlenecks on a parallel machine.		In Java, the standard class utilized for hashing is the HashMap[[#References\|<sup>[17]</sup>]] class. This class has a fundamental weakness though in that the entire map requires synchronization prior to each access. This causes a lot of contention and many bottlenecks on a parallel machine.

	Below, I will present a Java-based solution to this problem by using a ConcurrentHashMap class. This class only requires a portion of the map to be locked and reads can generally occur with no locking whatsoever.		Below, I will present a Java-based solution to this problem by using a ConcurrentHashMap class. This class only requires a portion of the map to be locked and reads can generally occur with no locking whatsoever.

Japlemmo: /* References */

2012-03-05T20:15:32Z

References

← Older revision		Revision as of 20:15, 5 March 2012
Line 387:		Line 387:
	#http://www.facebook.com/press/info.php?statistics		#http://www.facebook.com/press/info.php?statistics
	#http://en.wikipedia.org/wiki/Breadth-first_search		#http://en.wikipedia.org/wiki/Breadth-first_search
			#http://code.wikia.com/wiki/Hashmap

Japlemmo: /* Parallel Code Solution */

2012-03-05T20:12:59Z

Parallel Code Solution

← Older revision		Revision as of 20:12, 5 March 2012
Line 158:		Line 158:
	=== Parallel Code Solution ===		=== Parallel Code Solution ===

	This part we implement a parallel algorithm with the same ~~definition of~~ traversal.		This part we implement a parallel algorithm with the same functionality as the serial 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		First, we define 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]]		[[File: para_tree1.PNG]]

Japlemmo: /* Opportunities for Parallelization */

2012-03-05T20:11:30Z

Opportunities for Parallelization

← Older revision		Revision as of 20:11, 5 March 2012
Line 42:		Line 42:
	=== Opportunities for Parallelization ===		=== Opportunities for Parallelization ===

	One potential slowdown in a tree data structure could occur during the traversal process. Even though search/update/insert can occur in a logarithmic fashion, traversal operations such as in-order, pre-order, post-order traversals can still require a full sequence of the list to generate all output. This gives an opportunity to generate parallel code.		One potential slowdown in a tree data structure could occur during the traversal process. Even though search/update/insert can occur in a logarithmic fashion, traversal operations such as in-order, pre-order, post-order traversals can still require a full sequence of the list to generate all output. This gives an opportunity to generate parallel code by having various portions of the traversal occur on different processors.

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

Japlemmo: /* Trees */

2012-03-05T20:09:59Z

Trees

← Older revision		Revision as of 20:09, 5 March 2012
Line 35:		Line 35:

	== Trees ==		== Trees ==

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

	=== Tree Intro ===		=== Tree Intro ===

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

2012-03-05T20:09:38Z

Introduction to Linked-List Parallel Programming

← Older revision		Revision as of 20:09, 5 March 2012
Line 32:		Line 32:
	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 critical sections in order 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.		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 critical sections in order 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.		In this chapter, we will explore 3 linked-list based data structures and the parallelization opportunities as well as the concurrency issues they present: hash tables, trees, and graphs.

	== Trees ==		== Trees ==

Japlemmo: /* Chapter 5a CSC/ECE 506 Spring 2012 / ch5a */

2012-03-05T20:08:48Z

Chapter 5a CSC/ECE 506 Spring 2012 / ch5a

← Older revision		Revision as of 20:08, 5 March 2012
Line 1:		Line 1:
	== Chapter 5a CSC/ECE 506 Spring 2012 / ch5a ==		== 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.		An exploration and summary of parallel optimization and 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 =		= Introduction to Linked-List Parallel Programming =

Japlemmo: /* Opportunities for Parallelization */

2012-03-05T20:05:32Z

Opportunities for Parallelization

← Older revision		Revision as of 20:05, 5 March 2012
Line 282:		Line 282:
	Certainly though, the need for parallel processing becomes critical when you consider, for example, that social networking has become such a major proponent of graph algorithms. Facebook now has roughly a billion users[[#References\|<sup>[15]</sup>]] and each user has series of friend links that must be analyzed and examined. This list just keeps growing and growing.		Certainly though, the need for parallel processing becomes critical when you consider, for example, that social networking has become such a major proponent of graph algorithms. Facebook now has roughly a billion users[[#References\|<sup>[15]</sup>]] and each user has series of friend links that must be analyzed and examined. This list just keeps growing and growing.

	One of the most significant opportunities for a parallel algorithm with a graph data structure is with the traversal algorithms. We can use Breadth-First search as an example of this, starting from an initial node and expanding outwards until reaching the destination node.		One of the most significant opportunities for a parallel algorithm with a graph data structure is with the traversal algorithms. We can use Breadth-First search[[#References\|<sup>[16]</sup>]] as an example of this, starting from an initial node and expanding outwards until reaching the destination node.

	=== Breadth First Search - Serial Version ===		=== Breadth First Search - Serial Version ===

Japlemmo: /* References */

2012-03-05T20:05:02Z

References

← Older revision		Revision as of 20:05, 5 March 2012
Line 388:		Line 388:
	#http://sc05.supercomputing.org/schedule/pdf/pap346.pdf		#http://sc05.supercomputing.org/schedule/pdf/pap346.pdf
	#http://www.facebook.com/press/info.php?statistics		#http://www.facebook.com/press/info.php?statistics
			#http://en.wikipedia.org/wiki/Breadth-first_search