Question in files
Plymouth University MODULE CODE: MATH2607 TITLE OF PAPER: Mathematical Programming TIME ALLOWED DEADLINE Thu 18th January, 16:00 TIME FACULTY SCIENCE AND ENGINEERING SCHOOL COMPUTING, ELECTRONICS ANDMATHEMATICS ACADEMIC YEAR 2017/2018 STAGE 2 INSTRUCTIONS TO CANDIDATES: TOTAL NUMBER of marks for this coursework is 100. QUESTIONS Answer ALL the questions. The coursework should be submitted via the online submission system in the DLE. The coursework should be done according to the group discussed in class. The submitted documents will be run through originality checking software Turnitin http://ilsselfhelp.plymouth.ac.uk/novo/default.asp?id=1032&Lang=1 to ensure that the material is original. • The written answers to the questions should be submitted in a format such as pdf. • This coursework contains two programming exercises which must be completed using the Python language. The programmes should be submitted. They should contains comments. • plots and animations should be submitted The anonymous marking policy of the University requires that you include the student IDs of ALL group members of submitted materials, but not your names. Release to library? NO Second coursework MATH2607 – 2017/2018 Page 1 of 6 QUESTIONS Please provide python codes and the output of a few examples that demonstrates that your code is running properly. Your code should return informative error messages, if it fails to run. Please make comments in your code, and make the output of the print statement clear. For instance instructions like : print(rank,N, size) are not recommanded, and should be replaced by statement like: print(’process [’,rank,’] has variable X=’,X,’before Send statement’) Q1. Message latency and bandwidth The goal of this exercise is to estimate the communication rate between two tasks using the Message Passing Interface framework (the bandwidth) and the overhead associated with sending a zero-byte message between two MPI tasks. Two cases are considered: communication between two tasks on a single computer and communication between two tasks on two different nodes. • Write a function that generate a random array of integer of length nint.(5 Marks) • Write a program such that the process 0 send N times an array of length nint generated using the previous function to process 1. (5 Marks) • Add time measurements to estimate the average time to send one array of length nint. The timings need to be averaged over a number N of Send/Receive instructions to be less sensitive to fluctuations. (10 Marks) • Run your code to plot the timings for large range of message size. Consider the two cases where the two processes are located on two cores on the same node or on two different nodes. (5 Marks) • Give an estimate of the bandwidth in mbps (megabits per second) and MB/s (megabytes per second) and of the latency. What do you observe ? Propose an explanation.(Hint:you can find the number of bytes occupied by an object X using X.nbytes. The number of bits is 8 times the number of bytes.).(5 Marks) (30 Marks) MATH2607 – 2017/2018 Page 2 of 6 Q2. On fractals In this exercise we study the parallelisation of two simple programs that are designed to draw some fractal shapes. Fractals are geometrical self-similar figures which are studied extensively by mathematicians and some fractal shapes are observed in nature. The first part of the exercise focus on the the Mandelbrot set and the second part on random walks. Both scalar programs are provided and required minimal modification to be parallellised. The Mandelbrot set is defined as the of complex number c such that the sequence zn+1 = z 2 n + c starting from z0 = 0 is bounded. It can be shown that a point c belongs to the Mandelbrot set if and only if zn ≤ 2 for all n ≥ 0. Figure Q2 (1): The Mandelbrot set. The x-axis is the real axis and the y axis in the imaginary axis. A program that scans the complex plane on a given range of values for c and compute MATH2607 – 2017/2018 Page 3 of 6 zn for n = nitermax is provided. Since we are only interested in the domain of convergence of the sequence for a given c, the program return 1 when the sequence converge and 0 otherwise. After having read and understood the program, answer to the following questions: • Parallelelise the program by slicing the scanned domain, and check again the scalar code provided that you can reproduce the Mandelbrot set. (10 Marks) • In parallel computing how would you call such a problem ? Do you expect good scaling properties ?(2 Marks) A random walk is a random process that describes a path that consists of a succession of random steps. Their mathematical study has been extensive and has application in physics, chemistry, finance, ecology... For simplicity we consider here a particle originaly positionned in the origin (0, 0) moving on a 2-dimensional grid of points spaced of a distance a. At each time step, the particle has a probability 1/4 to hop in each direction (up,down,left or right). A question of interest is to know what is the average distance traveled by the particle from the origin O in a number of time steps n. We call this distance d(n). The problem can be solve analytically and it can be shown that d(t = n) =√ 4Dn where D = a 2 2π - a famous relation established by Einstein studying Brownian motion in 1905. 0.10 0.08 0.06 0.04 0.02 0.02 0.04 0.06 0.08 0.10 0.10 0.08 0.06 0.04 0.02 0.02 0.04 0.06 0.08 0.10 O= (0, 0) a a d( n= 10 ) Figure Q2 (2): Random walk (in red) on a lattice of spacing a = 0.02. A program that simulate such a random process for npart independent particles is MATH2607 – 2017/2018 Page 4 of 6 provided. • Parallelelise the program, in a way that each process simulates npart trajectories. (10 Marks) • Modify the code to plot a few sample trajectories on a single plot and for a number of at least 10000 steps. (3 Marks) • Run the parallel program on a large number of particles∼ 1000 and plot the average distance to the orgin as a function of the number of steps n. Compare to the theoretical prediction by ploting the theoretical curve.(3 Marks) • In parallel computing how would you call such a problem ? Do you expect good scaling properties ?(2 Marks) (30 Marks) Q3. Heat equation in 2 dimension The goal of this question is to explore some aspects of the parallelization of a partial differential equation solver. The two-dimensional heat equation for an homogeneous material reads: ∂T ∂t = C ( ∂2T ∂x2 + ∂2T ∂y2 ) (1) where T = T (x, y, t) is the temperature at a given position (x, y) and time t. The coefficent C is a parameter which depends of the material, called the thermal diffusivity. For simplicity we will consider a rectangular piece of material, whose borders are maintained at a temperature of 0◦ C. The heat equation can be shown to have a unique solution once T (x, y, 0) - the so-called initial condition - is fixed. To obtained a numerical solution, the problem is discretised on a regular grid of spacing a. The number of points in each direction is denoted nx in the x-direction and ny in the y-direction. Using discretised derivative is can be shown, that the solution of the heat equation T (x, y, t + dt) for all x and y,given the solution at T (x, y, t) reads: T (x, y, t+ dt) = T (x, y, t)+ + r { T (x+ a, y, t) + T (x− a, y, t) (2) + T (x, y + a, t) + T (x, y − a, t)− 4T (x, y, t) } where r = Cdt/a2. A program solving this equation in parallel is provided. • Write a serial version of the program and demonstrate that it works. (10 Marks) • Add comments to the parallel code. In particular, the types of the main variables should be added in a comment when declared (for instance : “array of floats of size ...”). The role and usage of the functions should be commented. Do not comment the plotting part of the program. (5 Marks) MATH2607 – 2017/2018 Page 5 of 6 • Explain how the code is parallelised, in particular how the data are splitted and what need to be communicated. Use a a sketch for instance nx = ny = 6 to illustrate your statements. (10 Marks) • Write a python code to plot the speedup versus the number of processes and include on the graph the theoretical expectation from Amdahls law. (5 Marks) • Write a python code to plot the strong and weak scaling efficiencies from 1 to 16 processes (the total number of processors available in the cluster). What can you say about the performance of the code ? (5 Marks) • Modify the code so that the process 0 gather the value of the temperature for a range of value and make an animation (3d or color level) of the results for nx = ny = 512 and for a number of steps such that the code run in a few minutes. Use for instance a random initial configuration by setting: init_type=’random’.(5 Marks) (40 Marks) END OF QUESTIONS END OF COURSEWORK MATH2607 – 2017/2018 Page 6 of 6