With every smartphone and computer now boasting multiple processors, the use of functional ideas to facilitate parallel programming is becoming increasingly widespread. In this course, you'll learn the fundamentals of parallel programming, from task parallelism to data parallelism. In particular, you'll see how many familiar ideas from functional programming map perfectly to to the data parallel paradigm. We'll start the nuts and bolts how to effectively parallelize familiar collections operations, and we'll build up to parallel collections, a production-ready data parallel collections library available in the Scala standard library. Throughout, we'll apply these concepts through several hands-on examples that analyze real-world data, such as popular algorithms like k-means clustering. Learning Outcomes. By the end of this course you will be able to: - reason about task and data parallel programs, - express common algorithms in a functional style and solve them in parallel, - competently microbenchmark parallel code, - write programs that effectively use parallel collections to achieve performance Recommended background: You should have at least one year programming experience. Proficiency with Java or C# is ideal, but experience with other languages such as C/C++, Python, Javascript or Ruby is also sufficient. You should have some familiarity using the command line. This course is intended to be taken after Functional Program Design in Scala: https://www.coursera.org/learn/progfun2.
Parallel Sorting
Loading...
來自 École Polytechnique Fédérale de Lausanne 的課程
并行编程
1283 個評分
École Polytechnique Fédérale de Lausanne
1283 個評分
課程 3（共 5 門，Specialization Functional Programming in Scala）
從本節課中
Basic Task Parallel Algorithms
We continue with examples of parallel algorithms by presenting a parallel merge sort. We then explain how operations such as map, reduce, and scan can be computed in parallel. We present associativity as the key condition enabling parallel implementation of reduce and scan.
與講師見面
Prof. Viktor KuncakAssociate Professor
School of Computer and Communication Sciences
Dr. Aleksandar ProkopecPrincipal Researcher
Oracle Labs
Sorting is a fundamental algorithm, so
let's see how can we do sorting in parallel.
We're going to implement a parallel version of merge sort.
Merge sort recursively sorts two halves of an array, and
we are going to do this thing in parallel.
And then we need to merge the two sorted arrays into one larger sorted array.
In order to do that we're going to use two arrays,
one of which is going to be a temporary array.
And we are going to be copying elements between the temporary and
the original array.
We will implement parMergeSort as the parMergeSort method which takes an array
and a maximum depth that determines how much parallelization we will use and
it's going to have the side effect of making the given array sorted.
We will start by allocating an intermediate array.
We will call this array ys.
Whereas the original array was xs.
And in order to use this auxilliary storage efficiently we will alternate
between using xs versus YS as the array whenever we do the work.
The shape of parallel merge sort is similar to the shape of many other
divide and conquer parallel algorithms that we have seen.
In the base case, we are just going to invoke the sequential sorting algorithm.
In this case, this will be a quick sort.
Previously we have to go this base case
when the segment length was sufficiently small.
In this case, this is controlled using this depth parameter and
we will stop paralyzation when the depth tree the maximum depth.
In this case we are making use of the fact that there is no point to do for
the parallelization once we have
saturated the parallel resources that we have on a given machine.
The interesting part is when we have not reached yet the base case,
we are going to then split the array in middle, computing the middle point.
And then we are going to recursively sort the first half of the array and
the second half of the array.
We are of course updating the depth as we proceed to smaller array segments.
These two sorts are taking place in parallel.
Each of the sub routines calls to sort their recurring locations is going
to ensure that the appropriate segment of DRA is sorted.
So, we will have two, these joined segments of the array,
each of which contains assorted list of some elements.
Now, we will just like to merge these two segments into
one larger segment that is still sorted.
We will do this merge using the call to merge.
What merge needs to do Is
to copy the elements from the original segments into a new one.
For that, we will use the auxiliary storage.
Whether xs or ys is auxiliary storage is determined by
whether the current difference between maxDepth and depth is even or odd.
The flip Boolean variable determines whether this is the case.
According to the value of flip, source and
destination will either be ys and xs or the other way around.
So this is the definition of sort that takes the segments.
Beginning and the end.
In order to sort an array, we simply invoke this version of sort,
starting from 0 and going to the entire length of the array.
Merging of the array can be done sequentially,
this is a function that takes one array.
Which is the source and then destination and
it's going to take two sorted intervals in the source array and these intervals
are given with the points the beginning, the middle point, and the end point.
And it's going to write the resulting merged array into the destination.
The version of merge that we are using in this implementation is sequential, so
you can do it as you would do in usual merge sort.
It is nonetheless an interesting exercise
to think how one would implement merge in parallel.
A simple operation is to copy one array,
given by source in this function, into the target.
How could we parallelize this?
Let's assume that the beginning of this segment that we wish to copy is
given by the from, and the end by until.
And that we are willing to do parallization with the depth.
In the base case, when the depth is equal to maximum depth,
we are simply going to invoke a sequential array copy function.
Otherwise, we are going to divide our
current array segment into two sub-segments.
And then we are going to invoke recursively our own function.
By copying the two smaller segments, from middle to until, and
from beginning until middle.
At each step, we are increasing depth by one, so
that at some point we will reach the maximum depth.
We can now compare the performance of parMergeSort and
the performance of the sequential quicksort.
Here, I have the implementation of parallel MergeSort in the Scala prompt
as well as code that is going to use Scala meter to compare the sequential and
parallel execution.
Let's run the benchmarking and
see what the relative performance of these two versions is.
We can see that we have obtained over two fold speed up for
the array sizes that we have considered on this machine.
So we have seen the main part of merge sort,
how to recursively sort the two halves of the array in parallel.
Then we have seen the merging part,
which is also the fundamental component of the algorithm.
For that we have used a temporary array.
And finally, we have seen a simple parallel copy operation on the right
that allows us to copy the temporary array back into the original array.
Together this gives us our parMergeSort operation and we can see that it can,
in fact, achieve speed-ups in practice.
