M3C 2017 Homework 3

Due date/time: 30/11/2017, 23:59 GMT

Getting Started: If needed, update your local copy of the course repo (sync and pull). The homework/hw3/ directory contains the files, hw3_template.py, hw3_template.f90, and hw3_main.f90. Make a new directory outside of the course repo, and place dev copies of the template files named in this new directory. Ultimately, the final files that you submit should be titled hw3.py and hw3.f90. Browse through the three files provided; the template files contain a number of function/subroutine headers, and you will have to add code as described below. First, however, you should add your name and 8-digit college id to the docstring/comment at the top of each file.

In this assignment, we will consider a modified version of the random network model implemented in HW1. We now consider random walks in d dimensions as follows. A seed node is placed at \(x^{(i)}=0\), \(i=1,2,...,d\). A new node is introduced at \(x^{(d)}=H\) with \(x^{(i)}=0\), \(i=1,2,...,d-1\), and this node then undergoes a random walk with each step governed by:

\[X^{(i)}_{j+1} = X^{(i)}_j + \mathcal{P}^{(i)}_j, ~ i=1,2,...,d,\]

where \(\mathcal{P}^{(i)}_j\) are random numbers (independent for all values of i and j considered). For \(i<d\), \(\mathcal{P}^{(i)}_j\) takes on the values -1 or 1 with equal probability. For i=d, \(\mathcal{P}^{(d)}_j\) is either -1 or 0 with equal probability. A random walk terminates when either 1) a node reaches \(x^{(d)}=0\) or 2) the new node is sufficiently close to one or more “old” nodes such that: \(\min(\Delta X) \leq 1\) where \(\Delta X = \{|X^{(1)}-Y^{(1)}|, |X^{(2)}-Y^{(2)}|, ..., |X^{(d)}-Y^{(d)}|\}\), \(X^{(i)}\) is the position of the new node and \(Y^{(i)}\) is the position of a node that has already been added to the network. New nodes continue to be introduced (after the previous node has been added to the network) until there are a total of N nodes in the network. The height of a network corresponds to the largest value of \(X^{(d)}\) in the network.

Note: As you work through the tasks below, you may add module variables and additional subroutines and functions as needed. Do not remove module variables or modify input/output of existing complete routines without first asking for permission.

1.(20 pts) Performance You have been provided with Python and Fortran routines named rwnet that implement the model described above. Complete the function performance1 in hw3_dev.py so that it analyzes how the model simulation time varies with the total number of nodes in the network. You may keep H fixed and constrain d to be 2 and 3 (though you can examine a broader parameter space if desired). You should also compare the performance of the Fortran and Python routines. The function should create one or more figures illustrating the most important trends, and these trends should be concisely discussed and analyzed in the function docstring.

2. (35 pts) Ensemble averages and parallel performance i) You will now develop a Fortran subroutine parallelized with OpenMP which simulates m realizations of a network for a given set of input parameters. The routine should output: 1) the node coordinates for all m networks, 2) The maximum and 3) minimum network heights and 4) the average height of the m networks. The subroutine should be carefully parallelized with OpenMP. You should avoid generating nested parallel regions, but otherwise, your OpenMP implementation should be both sensible and thorough. The number of threads used within any parallel regions should correspond to the input variable, numthreads. Add a comment below the subroutine header concisely explaining your approach to parallelization.

ii) Analyze the parallel performance of simulate_m for the case H=600, d=2. Add code to performance2 in hw3_dev.py which assesses the speedup and makes one or more figures illustrating the most important trends. Clearly and concisely discuss and explain these trends in the docstring of the function. You are not required to run calculations with more than 2 threads.

3. (30 pts) Network analysis i) Analyze the dependence of the network height on the total number of nodes. Add code to analyze1 in hw3_dev.py which generates one or more figures illustrating the most important trends. Clearly and concisely discuss and explain these trends in the docstring of the function. You should consider both d=2, H=200 and d=3,H=100.

ii) You will now compute the fractal dimensions of simulated networks. The fractal dimension, \(\delta_f\), can be defined as follows for networks with N total nodes. Let \(N_\epsilon\) denote the total number of pairs of nodes within a distance, \(\epsilon\), of each other. Then \(C(\epsilon) \sim \epsilon^{\delta_f}\) where \(C(\epsilon) = lim_{N\rightarrow \infty}\frac{N_\epsilon}{N^2}\), . Complete analyze2 in hw3_dev.py so that it estimates \(\delta_f\) for d=2, H=400 and d=3,H=100. You may base your estimate on a single network (for each d) with sufficiently large N. For a given network, you should allow \(\epsilon\) to vary between 2 and half of the network height. The function should return your estimates for \(\delta_f\) in a 2-element tuple. The function should also generate one or more figures illustrating how well the simulation data fits the assumed form for \(C(\epsilon)\).

4. (15 pts) Visualization Complete the function visualize in hw3_dev.py so that it generates an animation illustrating the generation of a network. It is sufficient to consider the case H=200, N=500, d=2, but feel free to explore larger networks and d=3. Submit your animation file with the filename hw3movie.xxx with xxx replaced as appropriate (e.g. mp4).

You also have the option of entering a movie in the 1st annual M3C animation festival. The class will vote on a winner who will receive a non-lucrative prize, and the top vote-getters and the instructor will have their movies shown during the final lecture this term.


1. All figures created by your code should be well-made and properly labeled. The title of each figure should include your name and the name of the function which created it. Submit figures files corresponding to all of the figures generated by the *performance* and *analyze* functions with your codes. If you are submitting more than 10 figures in total, please think carefully about presenting your results more concisely.

2. It is expected that your python functions will take several minutes to run. It is suggested that you start out with smaller problem sizes and then move to larger sizes as your code develeops and as you prepare to generate your final figures. If a function is taking more than an hour to run, check with the instructor to see if this is ok.

3. Your Fortran codes should run to double-precision accuracy.

4. The code in the name==main section of your python script should call your performance and analyze functions and generate the figures you are submitting.

5. You may use any python routines in numpy, scipy, matplotlib, and time. Check first if you would like to utilize other modules.

Submitting the assignment

To submit the assignment for assessment, go to the course blackboard page, and click on the “Assignments” link on the left-hand side of the page, and then click on Homework 3. Click on “Write Submission” and add the statement: “This is all my own unaided work unless stated otherwise.”

Click on “Browse My Computer” and upload your final files, hw3.f90, hw3.py, hw3xx.png, and hw3movie.xxx. Finally, click “Submit”.