Monte Carlo Method to Estimate Pi

Loading...

En provenance du cours de École Polytechnique Fédérale de Lausanne

Parallel programming

1385 notes

École Polytechnique Fédérale de Lausanne

Parallel programming

1385 notes

Cours 3 sur 5 dans 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.

À partir de la leçon

Parallel Programming

We motivate parallel programming and introduce the basic constructs for building parallel programs on JVM and Scala. Examples such as array norm and Monte Carlo computations illustrate these concepts. We show how to estimate work and depth of parallel programs as well as how to benchmark the implementations.

Course Overview2:04

Introduction to Parallel Computing15:04

Parallelism on the JVM I13:13

Parallelism on the JVM II8:50

Running Computations in Parallel13:01

Monte Carlo Method to Estimate Pi4:27

First-Class Tasks7:18

How Fast are Parallel Programs?24:41

Benchmarking Parallel Programs17:02

Rencontrer les enseignants

Prof. Viktor Kuncak
Associate Professor
School of Computer and Communication Sciences
Dr. Aleksandar Prokopec
Principal Researcher
Oracle Labs

Let's look at the method to estimate the value of pi.

Here, I have a square and inside it I have a circle.

Suppose that the radius of the circle is one, now that makes the surface of

the circle in total 1 squared pi.

And the side of the square is then 2 so

the surface of the square itself is two square.

Now, we can look also at one quarter of this entire picture.

And then the surface of the quarter of the circle is one quarter and

the quarter of the square is also one quarter.

So, if we compute the ratio between these two, between the fraction of a circle and

the fraction of a square, we get pi over four.

Sp.

let me denote this value by lambda.

Suppose we want to estimate the lambda.

What we can do is to randomly sample points inside

the entire square, and then see what fraction belongs to the circle.

Or alternatively, we can randomly sample points inside one quarter

of a square and see what fraction falls into that quarter of a circle.

In any case, we will be obtaining an estimate of this value lambda.

So if you want to get an estimate of pi,

we just need to multiply that estimate by four.

Here's sequential code that implements this idea.

Here we use pseudo random generators from the Scala Library

in order to implement sampling of points.

Given two instances of random class, we can use the method

nextDouble to obtain a floating point in the intervals 0, 1.

If we get two such floating point numbers,

it'll be getting points inside the quarter on the square we considered.

And then to test whether these two points, these two coordinates correspond

to a point inside the circle, we just check whether this condition holds.

Whether their distance to the origin is less than 1.

If this is the case, we are going to increase the counter.

So you have some total number of attempts, denoted here by iter.

We're going to compute how many times we ended up inside the circle.

So given this ratio, the number of times inside the circle divided by the total

number of attempts, we get our estimates for the lambda from previous slide.

And then if you multiply it by four, we get our estimate for pi.

Now, let's look how we would parallelize this kind of code.

Here's the parallel version of computing the same estimate.

Here, I'm using the parallel construct to simultaneously

count these estimates for one quarter of iterations.

Once I get these counts, I can simply add them up and divide them

by the total number of iterations that I had, and multiply the value by four.

In this case, all these four computations are proceeding in parallel.

And in fact, they do not really have much of shared resource

since they are all proceeding independently doing this computation.

So this is a nice example because we do not have a shared resource and

also because the amount of work can be easily subdivided into four,

approximately, equal parts.

This is because the computation itself is such that

even the value of the parameter we can easily estimate the amount of work.

In this case, it's in fact linear in this parameter, the number of iteration.

Unfortunately, not all parallel computations have

this property which means that it can be difficult

to ensure that different parallel computations are balanced.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play