CSC/ECE 506 Spring 2015/5b SA

Introduction

Parallelization of computations in the presence of dynamic data structures has shown immense potential. Here we discuss how can we parallelize linked data structures. Efficiently exploiting parallelism is fundamental in parallel computing even in the context of dynamic data structures. Some amount of speculation is needed to figure out how to exploit it the best. The idea is to introduce concurrency in the existing data structures to enable multi-threading and hence parallelism. We discuss the major steps in parallelizing data structures and then discuss some techniques and algorithms existing in the literature to gain more insight into the process.

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.

[1]

Linked Data Structure parallelization

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

As mentioned before, a linked list data structure consists of a set of nodes such that each node points to another node in the set. A special node in this set is considered to be the head of the linked list. We consider connected linked lists without loops, which means every node can be reached from the head, no two nodes point to the same node and no node points at the root.

Example 1 Parallelize Linked List

The following code snippet shows a parallelized linked list.

74 class Invocation[T](xs: List[T]) { 75 @volatile var stack = xs 76 def READ = unsafe.getObjectVolatile(this, OFFSET) 77 def CAS(ov: List[T], nv: List[T]) = unsafe.compareAndSwapObject(this, OFFSET, ov, nv) 78 } 79 80 abstract class ListTask[T] extends RecursiveTask[T] { 81 val inv: Invocation[T] 82 def workOn(elem: T): Unit 83 def compute() { 84 val stack = inv.READ 85 stack match { 86 case Nil => 87 // no more work 88 case head :: tail => 89 if (inv.CAS(stack, tail)) workOn(stack) 90 compute() 91 } 92 } 93 } 94 95 class ListForeach[T, U](f: T => U, val inv: Invocation[T]) extends ListTask[T] { 96 def workOn(elem: T) = f(elem) 97 } 98 99 implicit class ListOps[T](val par: Par[List[T]]) { 100 def foreach[U](f: T => U) = { 101 val inv = new Invocation(par.seq) 102 val tasks = for (i <- 0 until P) yield new ListForeach[T](f, inv) 103 for (t <- tasks) t.fork() 104 for (t <- tasks) t.join() 105 } 106 }

Example 2 Parallelized Queue Linked List

Now, lets consider the queue data structure based on single linked list. The following code snippet explains the same.

Algorithms

One algorithm to perform parallelization of data structures is PLDS.

References

1. http://idb.csie.ncku.edu.tw/tsengsm/COURSE/Java/Slides/Java-15-Linked_Data_Structure.pdf