159.735编程代写、代做program程序设计、C++语言编程调试

日期：2020-11-01 11:27

159.735 Assignment 1

Parellel Random Number Generation

Monte Carlo methods using random numbers are used extensively in numerical

computation and analysis. For this assignment, write an MPI program

to implement the parallel computation of the value of π by simulating the

throwing of darts on an imaginary dartboard. Evaluate the performance of

your program by trying it on a range of available nodes and processors.

Consider a unit circle, ie of radius 1, and the smallest bounding box that

fully encloses the circle with (x, y) values each ranging from -1 to +1. Use

a suitable random number generator to sample random (x, y) values in this

range, and count the number of times the coordinates fall within the circle.

The ratio of this count to the total number of random positions that were

used is equal to the ratio of the area of the circle to the area of the box—from

whence the value of π can be calculated.

The following linear congruential generator is a suitable random number

generator:

ni+1 = (ani + c) mod m

where a = 1664525, m = 232, and c = 1013904223. Your program MUST

make use of the full range of random numbers that are available.

You will need to decide upon a strategy for generating random numbers and

to ensure that all processes get their random numbers from the same pool.

Doing this in a parallel computation environment is the main purpose of this

exercise. You should use the “leapfrog” method as described in the lectures.

Submission

Please submit your C or C++ source code together with a brief report which

addresses the following.

• Give the results of your performance testing of your implementation

of the parallel π calculation. Present your results in such a way that

best demonstrates and tests Amdahl’s Law. Are the parallel speed-ups

what you would expect?

• Measure the interprocess communication times. Provide an estimate

of the amount of time your program will require if one implemented

a method where only the master generates the random numbers and

sends each to its appropriate slave.

Due date: August 2, 2019.

This assignment is worth 20% of your final grade