CSC/ECE 506 Spring 2015/5b SA - Revision history

Admin: /* Linked Data Structure parallelization */

2015-03-18T00:52:10Z

Linked Data Structure parallelization

← Older revision		Revision as of 00:52, 18 March 2015
Line 32:		Line 32:

	Unlike data structures like arrays, linked lists are unsuitable for naive parallelization methods which employ divide and		Unlike data structures like arrays, linked lists are unsuitable for naive parallelization methods which employ divide and
	conquer policy~~, they~~ split the input and assign them to multiple workers for parallel processing. Splitting an arbitrary linked list requires traversing half of its elements. For too many operation instances such an O(n) splitting is		conquer policy. They split the input and assign them to multiple workers for parallel processing. Splitting an arbitrary linked list requires traversing half of its elements. For too many operation instances such an O(n) splitting is
	unacceptable. Hence, intuitively, it is more efficient to convert the linked list into an array and then use splitters		unacceptable. Hence, intuitively, it is more efficient to convert the linked list into an array and then use splitters
	on the array. One thing to be noticed is that these data structures does not retain information about the relative order of elements, hence the operators applied to their data-parallel operations need to be '''commutative'''.		on the array. One thing to be noticed is that these data structures does not retain information about the relative order of elements, hence the operators applied to their data-parallel operations need to be '''commutative'''.

Admin: /* Linearizability */

2015-03-18T00:49:35Z

Linearizability

← Older revision		Revision as of 00:49, 18 March 2015
Line 18:		Line 18:

	Linearizability is an important property of operations that may be executed concurrently		Linearizability is an important property of operations that may be executed concurrently
	[Herlihy and Wing(1990)][[#References\|<sup>[3]</sup>]][http://dl.acm.org/citation.cfm?id=78972]. An operation is linearizable if the rest of the system observes the corresponding system state change as if it occurred		[Herlihy and Wing (1990)][[#References\|<sup>[3]</sup>]][http://dl.acm.org/citation.cfm?id=78972]. An operation is linearizable if the rest of the system observes the corresponding system state change as if it occurred
	instantaneously at a single point in time after the operation started and before it ﬁnished.		instantaneously at a single point in time after the operation started and before it ﬁnished.
	This property ensures that all the linearizable operations in the program have a mutual		This property ensures that all the linearizable operations in the program have a mutual

Admin: /* Overview */

2015-03-18T00:49:18Z

Overview

← Older revision		Revision as of 00:49, 18 March 2015
Line 9:		Line 9:
	==Overview==		==Overview==

	The simplest linked data structure we can think of is a linked list. A single linked list with one pointer pointing to the next node in the list or double linked list where nodes have two pointers pointing to the adjacent nodes to its left and right in the linked list are the most commonly used linked data structures. Following figures are some examples of the same. The first shows the head node to a singly linked list and the second shows a ~~double~~ linked list.		The simplest linked data structure we can think of is a linked list. A single linked list with one pointer pointing to the next node in the list or double linked list where nodes have two pointers pointing to the adjacent nodes to its left and right in the linked list are the most commonly used linked data structures. Following figures are some examples of the same. The first shows the head node to a singly linked list and the second shows a doubly linked list.

	[[File:linked-list2.jpg\|thumbnail\|left\|upright=1.9\|600px\|A linked List]] [http://idb.csie.ncku.edu.tw/tsengsm/COURSE/Java/Slides/Java-15-Linked_Data_Structure.pdf] [[File:linked-list1.jpg\|thumbnail\|center\|Linked List Traversal]]		[[File:linked-list2.jpg\|thumbnail\|left\|upright=1.9\|600px\|A linked List]] [http://idb.csie.ncku.edu.tw/tsengsm/COURSE/Java/Slides/Java-15-Linked_Data_Structure.pdf] [[File:linked-list1.jpg\|thumbnail\|center\|Linked List Traversal]]

Spkanung: /* Overview */

2015-03-03T05:04:52Z

Overview

← Older revision		Revision as of 05:04, 3 March 2015
Line 11:		Line 11:
	The simplest linked data structure we can think of is a linked list. A single linked list with one pointer pointing to the next node in the list or double linked list where nodes have two pointers pointing to the adjacent nodes to its left and right in the linked list are the most commonly used linked data structures. Following figures are some examples of the same. The first shows the head node to a singly linked list and the second shows a double linked list.		The simplest linked data structure we can think of is a linked list. A single linked list with one pointer pointing to the next node in the list or double linked list where nodes have two pointers pointing to the adjacent nodes to its left and right in the linked list are the most commonly used linked data structures. Following figures are some examples of the same. The first shows the head node to a singly linked list and the second shows a double linked list.

	[[File:linked-list2.jpg~~]] [[File:~~linked~~-list1.jpg~~]] [http://idb.csie.ncku.edu.tw/tsengsm/COURSE/Java/Slides/Java-15-Linked_Data_Structure.pdf]		[[File:linked-list2.jpg\|thumbnail\|left\|upright=1.9\|600px\|A linked List]] [http://idb.csie.ncku.edu.tw/tsengsm/COURSE/Java/Slides/Java-15-Linked_Data_Structure.pdf] [[File:linked-list1.jpg\|thumbnail\|center\|Linked List Traversal]]

Spkanung: /* References */

2015-03-03T04:39:51Z

References

← Older revision		Revision as of 04:39, 3 March 2015
Line 586:		Line 586:

	16. http://www.cs.toronto.edu/~christoff/files/Linearizability-ACorrectnessConditionForConcurrentObjects.pdf		16. http://www.cs.toronto.edu/~christoff/files/Linearizability-ACorrectnessConditionForConcurrentObjects.pdf

			17. http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=876120

Spkanung: /* Algorithms */

2015-03-03T04:39:18Z

Algorithms

← Older revision		Revision as of 04:39, 3 March 2015
Line 311:		Line 311:


	[[File:codexy.PNG\|thumbnail\|600px\|left\|Transformation of a Simple Loop Traversal to Parallel Loop Traversal[http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=876120]]] '''Implementation'''		[[File:codexy.PNG\|thumbnail\|600px\|left\|Transformation of a Simple Loop Traversal to Parallel Loop Traversal[http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=876120]]] '''Implementation'''[[#References\|<sup>[17]</sup>]][http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=876120]

	Now let us have a look at the implementation of Parallelism of Cyclic Graphs from a higher level language perspective. The code given below transforms a Simple Loop traversal of a data structure to a Parallel Loop traversal which can be implemented by several threads.		Now let us have a look at the implementation of Parallelism of Cyclic Graphs from a higher level language perspective. The code given below transforms a Simple Loop traversal of a data structure to a Parallel Loop traversal which can be implemented by several threads.

Spkanung: /* Algorithms */

2015-03-03T04:34:16Z

Algorithms

← Older revision		Revision as of 04:34, 3 March 2015
Line 320:		Line 320:

	Now, each thread can enter the '''do while''' loop in parallel to others and execute the required operation '''call proc''' on its assigned node. So, we see that knowing the traversal pattern in advance helps us in achieving parallelism. Here, the lock and unlock sections are present inside the loop so as the first thread that completes its task can now update its '''plocal''' to the next available '''p''' inside a critical section.		Now, each thread can enter the '''do while''' loop in parallel to others and execute the required operation '''call proc''' on its assigned node. So, we see that knowing the traversal pattern in advance helps us in achieving parallelism. Here, the lock and unlock sections are present inside the loop so as the first thread that completes its task can now update its '''plocal''' to the next available '''p''' inside a critical section.

Spkanung: /* Algorithms */

2015-03-03T04:34:00Z

Algorithms

← Older revision		Revision as of 04:34, 3 March 2015
Line 320:		Line 320:

	Now, each thread can enter the '''do while''' loop in parallel to others and execute the required operation '''call proc''' on its assigned node. So, we see that knowing the traversal pattern in advance helps us in achieving parallelism. Here, the lock and unlock sections are present inside the loop so as the first thread that completes its task can now update its '''plocal''' to the next available '''p''' inside a critical section.		Now, each thread can enter the '''do while''' loop in parallel to others and execute the required operation '''call proc''' on its assigned node. So, we see that knowing the traversal pattern in advance helps us in achieving parallelism. Here, the lock and unlock sections are present inside the loop so as the first thread that completes its task can now update its '''plocal''' to the next available '''p''' inside a critical section.




















	===Hash Tables===		===Hash Tables===

Spkanung: /* The Cyclic Graph Parallelization */

2015-03-03T04:32:57Z

The Cyclic Graph Parallelization

← Older revision		Revision as of 04:32, 3 March 2015
Line 320:		Line 320:

	Now, each thread can enter the '''do while''' loop in parallel to others and execute the required operation '''call proc''' on its assigned node. So, we see that knowing the traversal pattern in advance helps us in achieving parallelism. Here, the lock and unlock sections are present inside the loop so as the first thread that completes its task can now update its '''plocal''' to the next available '''p''' inside a critical section.		Now, each thread can enter the '''do while''' loop in parallel to others and execute the required operation '''call proc''' on its assigned node. So, we see that knowing the traversal pattern in advance helps us in achieving parallelism. Here, the lock and unlock sections are present inside the loop so as the first thread that completes its task can now update its '''plocal''' to the next available '''p''' inside a critical section.

















	===Hash Tables===		===Hash Tables===

Spkanung: /* Algorithms */

2015-03-03T04:32:28Z

Algorithms

← Older revision		Revision as of 04:32, 3 March 2015
Line 320:		Line 320:

	Now, each thread can enter the '''do while''' loop in parallel to others and execute the required operation '''call proc''' on its assigned node. So, we see that knowing the traversal pattern in advance helps us in achieving parallelism. Here, the lock and unlock sections are present inside the loop so as the first thread that completes its task can now update its '''plocal''' to the next available '''p''' inside a critical section.		Now, each thread can enter the '''do while''' loop in parallel to others and execute the required operation '''call proc''' on its assigned node. So, we see that knowing the traversal pattern in advance helps us in achieving parallelism. Here, the lock and unlock sections are present inside the loop so as the first thread that completes its task can now update its '''plocal''' to the next available '''p''' inside a critical section.

















	===Hash Tables===		===Hash Tables===