CSC/ECE 506 Spring 2015/5a vv - Revision history

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

2015-03-18T00:33:19Z

Introduction to Linked-List Parallel Programming

← Older revision		Revision as of 00:33, 18 March 2015
Line 43:		Line 43:
	[[File:PartialSums4.png]]		[[File:PartialSums4.png]]

	The advantages of ~~Pointer~~ jumping<ref>http://en.wikipedia.org/wiki/Pointer_jumping</ref> aren't just for single linked lists. This algorithm can also be used to find the root of a tree (this will be discussed in detail in the later 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 diagram shows an example which illustrates the algorithm discussed.<ref>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</ref>		The advantages of pointer jumping<ref>http://en.wikipedia.org/wiki/Pointer_jumping</ref> aren't just for single linked lists. This algorithm can also be used to find the root of a tree (this will be discussed in detail in the later 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 diagram shows an example which illustrates the algorithm discussed.<ref>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</ref>

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

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

2015-03-18T00:31:01Z

Introduction to Linked-List Parallel Programming

← Older revision		Revision as of 00:31, 18 March 2015
Line 11:		Line 11:
	= Introduction to Linked-List Parallel Programming =		= Introduction to Linked-List Parallel Programming =

	A [http://en.wikipedia.org/wiki/Linked_list linked ~~lists~~] is a data structure which contains a set of nodes. Nodes in linked list are composed of data and references to next node. It is the simplest form of linked data structures. Other linked data structures include Trees, Hash Tables and Graphs. One component that tends to link together various linked data structures is their dependence at some level on an internal pointer-based linked list. For example, hash tables have linked lists to support chained links to a given bucket in order to resolve collisions, trees have linked lists with left and right tree node paths, and graphs have linked lists to determine the paths.		A [http://en.wikipedia.org/wiki/Linked_list linked list] is a data structure which contains a set of nodes. Nodes in linked list are composed of data and references to next node. It is the simplest form of linked data structures. Other linked data structures include Trees, Hash Tables and Graphs. One component that tends to link together various linked data structures is their dependence at some level on an internal pointer-based linked list. For example, hash tables have linked lists to support chained links to a given bucket in order to resolve collisions, trees have linked lists with left and right tree node paths, and graphs have linked lists to determine the paths.

	To understand how parallelization techniques are applied to linked data structures, a copy-scan technique is illustrated in brief, which is further extended to a partial sum computation in a linked list.		To understand how parallelization techniques are applied to linked data structures, a copy-scan technique is illustrated in brief, which is further extended to a partial sum computation in a linked list.

Vareti: /* Graphs */

2015-03-05T17:31:45Z

Graphs

← Older revision		Revision as of 17:31, 5 March 2015
Line 453:		Line 453:
	A graph data structure<ref>http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29</ref> is another type of linked-list structure that focuses on data relationships and the most efficient ways to traverse from one node to another. 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.		A graph data structure<ref>http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29</ref> is another type of linked-list structure that focuses on data relationships and the most efficient ways to traverse from one node to another. 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.

	[[File:250px-6n-graf.svg.png~~\|thumb\|upright\|~~]]		[[File:250px-6n-graf.svg.png]]

	=== Opportunities for Parallelization ===		=== Opportunities for Parallelization ===

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

2015-03-05T17:20:21Z

Introduction to Linked-List Parallel Programming

← Older revision		Revision as of 17:20, 5 March 2015
Line 11:		Line 11:
	= Introduction to Linked-List Parallel Programming =		= Introduction to Linked-List Parallel Programming =

	One component that tends to link together various data structures is their dependence at some level on an internal pointer-based linked list. For example, hash tables have linked lists to support chained links to a given bucket in order to resolve collisions, trees have linked lists with left and right tree node paths, and graphs have linked lists to determine ~~shortest path algorithms~~.		A [http://en.wikipedia.org/wiki/Linked_list linked lists] is a data structure which contains a set of nodes. Nodes in linked list are composed of data and references to next node. It is the simplest form of linked data structures. Other linked data structures include Trees, Hash Tables and Graphs. One component that tends to link together various linked data structures is their dependence at some level on an internal pointer-based linked list. For example, hash tables have linked lists to support chained links to a given bucket in order to resolve collisions, trees have linked lists with left and right tree node paths, and graphs have linked lists to determine the paths.

	To understand how parallelization techniques are applied to linked data structures, a copy-scan technique is illustrated in brief, which is further extended to a partial sum computation in a linked list.		To understand how parallelization techniques are applied to linked data structures, a copy-scan technique is illustrated in brief, which is further extended to a partial sum computation in a linked list.

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

2015-03-05T17:16:40Z

Introduction to Linked-List Parallel Programming

← Older revision		Revision as of 17:16, 5 March 2015
Line 26:		Line 26:
	[[File:CopyScan.gif]]		[[File:CopyScan.gif]]

	With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.<ref>http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html</ref>		With [http://en.wikipedia.org/wiki/Linked_list linked lists], there is a concept called pointer doubling, which works in a very similar manner to copy-scan.<ref>http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html</ref>

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

Vareti: /* Parallel Solution */

2015-03-05T17:07:47Z

Parallel Solution

← Older revision		Revision as of 17:07, 5 March 2015
Line 270:		Line 270:


	<~~code~~>		<pre>
	Algorithm GEN-COMP-NEXT:		Algorithm GEN-COMP-NEXT:
	for all Pi, 1<=i<=n, do		for all Pi, 1<=i<=n, do
Line 277:		Line 277:
	Step 2: Processor Pi builds node i's last fiend whose array index is (n+1)		Step 2: Processor Pi builds node i's last fiend whose array index is (n+1)
	parallel end		parallel end
	</~~code~~>		</pre>

Vareti: /* Parallel Solution */

2015-03-05T16:55:29Z

Parallel Solution

← Older revision		Revision as of 16:55, 5 March 2015
Line 272:		Line 272:
	<code>		<code>
	Algorithm GEN-COMP-NEXT:		Algorithm GEN-COMP-NEXT:
	:for all Pi, 1<=i<=n, do		for all Pi, 1<=i<=n, do
	::parallel begin		parallel begin
	~~:::~~Step 1: Processor Pi builds the jth field of i's parent node if i is the jth child of its parent. The jth field (if it is not the last field) is stored in the ith index of array SUPERNODE.		Step 1: Processor Pi builds the jth field of i's parent node if i is the jth child of its parent. The jth field (if it is not the last field) is stored in the ith index of array SUPERNODE.
	~~:::~~Step 2: Processor Pi builds node i's last fiend whose array index is (n+1)		Step 2: Processor Pi builds node i's last fiend whose array index is (n+1)
	::parallel end		parallel end
	</code>		</code>

Line 283:		Line 283:


	<~~code~~>		<pre>
	Algorithm BF-TRAVERSAL (bfank, level, preorder-list)		Algorithm BF-TRAVERSAL (bfank, level, preorder-list)
	:Step 1. Divide the preorder-list into p blocks. Each processor builds partial lists from the nodes in the block. The header and the taller arrays for the lists built by processor i are denoted by hd[,i] and tl[,i], respectively.		Step 1. Divide the preorder-list into p blocks. Each processor builds partial lists from the nodes in the block. The header and the taller arrays for the lists built by processor i are denoted by hd[,i] and tl[,i], respectively.
	:for all Pi, 1<=i<=p do		for all Pi, 1<=i<=p do
	::parbegin		parbegin
	~~:::~~Pi works on nodes pre-order-list[k], where (i-1)(n/p) <= k < (in/p)		Pi works on nodes pre-order-list[k], where (i-1)(n/p) <= k < (in/p)
	~~:::~~Pi initializes list[k] to zreo /* the successor of k-th input in a partial list */		Pi initializes list[k] to zreo /* the successor of k-th input in a partial list */
	~~:::~~/* Phase 1. Pi initializes entries in hd[,i] and tl[,i] that are used and entries in hdflag */		/* Phase 1. Pi initializes entries in hd[,i] and tl[,i] that are used and entries in hdflag */
	~~:::~~hd[level[preorder-list[k]], i] := 0; tl[level[preorder-list[k]], i] := 0; hdflag[k] := 0;		hd[level[preorder-list[k]], i] := 0; tl[level[preorder-list[k]], i] := 0; hdflag[k] := 0;
	~~:::~~/* Phase 2. Build partial lists */		/* Phase 2. Build partial lists */
	~~:::~~Pi adds each of the n/p nodes to the partial list for the level of that node and updates hd[,i], tl[, i], and list [*] accordingly.		Pi adds each of the n/p nodes to the partial list for the level of that node and updates hd[,i], tl[, i], and list [*] accordingly.
	::parend;		parend;
	:Step 2. Link up partial lists.		Step 2. Link up partial lists.
	::/* Phase 1. Initialize header and tailer for the global lists */		/* Phase 1. Initialize header and tailer for the global lists */
	::for all Pi, 1 <= i <= p, do		for all Pi, 1 <= i <= p, do
	~~:::~~initialize head[k] and tail[k] to zero, for (i-1)n/p <= k < (in/p)		initialize head[k] and tail[k] to zero, for (i-1)n/p <= k < (in/p)
	::P1 sets head[n+1] and tail[n+1] to zero;		P1 sets head[n+1] and tail[n+1] to zero;
	::/* Phase 2. Link partial lists to form a list for each level */		/* Phase 2. Link partial lists to form a list for each level */
	::for each of the p blocks do		for each of the p blocks do
	~~:::~~for all Pi, 1 <= i <= p, do /* all processors work on the same block */		for all Pi, 1 <= i <= p, do /* all processors work on the same block */
	~~:::~~parbegin		parbegin
	~~::::~~for i := 1 to (n/p^2) do		for i := 1 to (n/p^2) do
	~~::::~~begin		begin
	~~:::::~~Pi is given at most a node mi in each iteration.		Pi is given at most a node mi in each iteration.
	~~:::::~~if hdflag[mi] = 1 /* The first element in its partial list */		if hdflag[mi] = 1 /* The first element in its partial list */
	~~:::::~~then		then
	~~::::::~~if the global list for the level of node mi is empty		if the global list for the level of node mi is empty
	~~::::::~~then let head[level[mi]] and tail[level[mi]] point to mi		then
	~~::::::~~else list[tail[level[mi]]] := mi and update tail[level[mi]] to be the tail of the partial list for mi.		let head[level[mi]] and tail[level[mi]] point to mi
	~~::::::~~end;		else
	~~:::~~parend;		list[tail[level[mi]]] := mi and update tail[level[mi]] to be the tail of the partial list for mi.
	:Step 3. Create a linked list to implement the NEXT function		end;
	::for all Pi, 1 <= i <= p, do		parend;
	~~:::~~parbegin		Step 3. Create a linked list to implement the NEXT function
	~~::::~~for k := (i-1)(n/p)+1 to (in/p) do		for all Pi, 1 <= i <= p, do
	~~:::::~~if(head[k] != 0 and head[k+1] != 0) then list[tail[k]] := head[k+1];		parbegin
	~~:::~~parend;		for k := (i-1)(n/p)+1 to (in/p) do
	:Step 4. Obtain ranking		if(head[k] != 0 and head[k+1] != 0) then list[tail[k]] := head[k+1];
	::LINKED-LIST-RANKING(list, tmp-rank, n);		parend;
	:Step 5. Output the result		Step 4. Obtain ranking
	::for all Pi, 1 <= i <= p, do		LINKED-LIST-RANKING(list, tmp-rank, n);
	~~:::~~parbegin		Step 5. Output the result
	~~::::~~for k := (i-1)(n/p)+1 to (in/p) do bfrank[preorder-list[k]] := tmp-rank[k];		for all Pi, 1 <= i <= p, do
	~~:::~~parend;		parbegin
	</~~code~~>		for k := (i-1)(n/p)+1 to (in/p) do bfrank[preorder-list[k]] := tmp-rank[k];
			parend;
			</pre>

Vareti: /* Parallel Solution */

2015-03-05T16:51:23Z

Parallel Solution

← Older revision		Revision as of 16:51, 5 March 2015
Line 515:		Line 515:


	<~~code~~>		<pre>
	:for all vertices u at level d in parallel do		for all vertices u at level d in parallel do
	::for all adjacencies v of u in parallel do		for all adjacencies v of u in parallel do
	::dv = D[v];		dv = D[v];
	::if(dv < 0) // v is visited for the first time		if(dv < 0) // v is visited for the first time
	~~:::~~vis = fetch_and_add(&Visited[v], 1); '''LOCK'''		vis = fetch_and_add(&Visited[v], 1); '''LOCK'''
	~~:::~~if(vis == 0) // v is added to a stack only once		if(vis == 0) // v is added to a stack only once
	~~::::~~D[v] = d+1;		D[v] = d+1;
	~~::::~~pS[count++] = v; // Add v to local thread stack		pS[count++] = v; // Add v to local thread stack
	~~:::~~fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''		fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
	~~:::~~fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''		fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''
	::if(dv == d + 1)		if(dv == d + 1)
	~~:::~~fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''		fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
	~~:::~~fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''		fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''
	</~~code~~>		</pre>

Vareti: /* Serial Code Examples */

2015-03-05T16:50:14Z

Serial Code Examples

← Older revision		Revision as of 16:50, 5 March 2015
Line 476:		Line 476:


	<~~code~~>		<pre>
	public void search(Graph g)		public void search(Graph g)
	{		{
	:g.paint(Color.white); // paint all the graph vertices with white		g.paint(Color.white); // paint all the graph vertices with white
	:g.mark(false); // unmark the whole graph		g.mark(false); // unmark the whole graph
	:refresh(null); // and redraw it		refresh(null); // and redraw it
	:Vertex r = g.root(); // the root is painted grey		Vertex r = g.root(); // the root is painted grey
	:g.paint(r, Color.gray); refresh(g.box(r));		g.paint(r, Color.gray); refresh(g.box(r));
	:java.util.Vector queue = new java.util.Vector();		java.util.Vector queue = new java.util.Vector();
	:queue.addElement(r); // and put in a queue		queue.addElement(r); // and put in a queue

	:while(!queue.isEmpty())		while(!queue.isEmpty())
	:{		{
	::Vertex u = (Vertex) queue.firstElement();		Vertex u = (Vertex) queue.firstElement();
	::queue.removeElement(u); // extract a vertex from the queue		queue.removeElement(u); // extract a vertex from the queue
	::g.mark(u, true); refresh(g.box(u));		g.mark(u, true); refresh(g.box(u));
	::int dp = g.degreePlus(u);		int dp = g.degreePlus(u);
	::for(int i = 0; i < dp; i++) // look at its successors		for(int i = 0; i < dp; i++) // look at its successors
	::{		{
	~~:::~~Vertex v = g.ithSucc(i, u);		Vertex v = g.ithSucc(i, u);
	~~:::~~if(Color.white == g.color(v))		if(Color.white == g.color(v))
	~~:::~~{		{
	~~::::~~queue.addElement(v);		queue.addElement(v);
	~~::::~~g.paint(v, Color.gray); refresh(g.box(v));		g.paint(v, Color.gray); refresh(g.box(v));
	~~:::~~}		}
	::}		}
	::g.paint(u, Color.black); refresh(g.box(u));		g.paint(u, Color.black); refresh(g.box(u));
	::g.mark(u, false); refresh(g.box(u));		g.mark(u, false); refresh(g.box(u));
	:}		}
	}		}
	</~~code~~>		</pre>

	=== Parallel Solution ===		=== Parallel Solution ===

Vareti: /* Parallel Solution */

2015-03-05T16:48:30Z

Parallel Solution

← Older revision		Revision as of 16:48, 5 March 2015
Line 436:		Line 436:

	<pre>		<pre>
	Map m = new ConcurrentHashMap();		Map m = new ConcurrentHashMap();
	Set s = m.keySet(); // set of keys in hashmap		Set s = m.keySet(); // set of keys in hashmap
	Iterator i = s.iterator(); // Must be in synchronized block		Iterator i = s.iterator(); // Must be in synchronized block
	while (i.hasNext())		while (i.hasNext())
	foo(i.next());		foo(i.next());
	</pre>		</pre>