Parallel Sorting

Loading...

來自 École Polytechnique Fédérale de Lausanne 的課程

并行编程

1485 個評分

瀏覽相關視頻

您將在 Coursera 發現全球最優質的課程。以下是為我們為您提供的部分個性化建議

École Polytechnique Fédérale de Lausanne

并行编程

1485 個評分

課程 3（共 5 門，Specialization Functional Programming in Scala）

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.

從本節課中

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.

Parallel Sorting7:07

Data Operations and Parallel Mapping18:50

Parallel Fold (Reduce) Operation18:06

Associativity I14:16

Associativity II17:37

Parallel Scan (Prefix Sum) Operation24:07

與講師見面

Prof. Viktor Kuncak
Associate Professor
School of Computer and Communication Sciences
Dr. Aleksandar Prokopec
Principal 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.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取