M3C 2017 Homework 3 solution

The complete Python script, hw3soln.py:

and the Fortran module, hw3soln.f90:

  1. (20 pts) Importing the module in a Python terminal, and running rw2d:

From the walltimes, we see that both the Fortran and Python implementations show a simple, monotonic reduction in speed as the number of nodes increases. This is unsurprising.


Comparing the ratios of the Python and Fortran codes in the figure below, we see that the Fortran implementation is exceptionally fast for small problem size indicating that compiler optimizations are more effective when working with smaller arrays As noted above, the “slowdown” for the Fortran code is larger as problem size increases, so for the largest networks shown, the Fortran subroutine is “only” ~10 times faster than the Python function. The linear fits shown on the figure above indicate that the Python algorithm is more efficient than the Fortran implementation (the distance calculations are not implemented in the same way) which is why the Python code “catches up” to the Fortran routine as the problem size increases.


2. i) (20 pts) The outer “m-loop” should be parallelized in simulate_m, and the hmean, hmax, and hmin calculations should all be reductions.

  1. (15 pts)
../_images/hw321soln.png ../_images/hw322soln.png

For small problem sizes, the one-thread calculation is actually faster than the two-thread one as overhead associated with forking/joining the two threads is tangible and cancels out gains from parallelization. However, as the problem size increases (increasing N and/or increasing M), the fraction of the workload that is parallelizable increases, and from Amdahl’s law, we expect speedup to increase towards the theoretical maximum which is two for the results shown.

3. i) (15 pts) The dependence of the average network height on the number of nodes in the network is essentially equivalent to the trends observed in hw1 for the (ensemble-averaged) rate of increase of the network height during a single simulation. Height depends linearly on the number of nodes for small and intermediate network sizes, but for larger sizes, where a dominant vertical branch emerges, the growth accelerates as seen in the figures below. The solution code calls simulate_m several times (with varying N), but really, we could just call it a single time with large N, and extract average heights from the returned X coordinates.

../_images/hw331soln.png ../_images/hw332soln.png
  1. (15 pts)

Since the correlation function \(C(\epsilon) \sim \epsilon^{\delta_c}\), the slope of a log-log plot of \(C\) vs \(\epsilon\) provides an estimate of the correlation dimension. A linear least-squares fit is computed using np.polyfit and the fits and slopes are shown in the figure above. We have to be careful when interpreting \(N \rightarrow \infty\) in the definition of C since as N increases, at some point nodes start accumulating at (0,H) and C will simply trend towards zero. Fortunately, the analysis from question i) provides guidance on how to choose N so that this problem is avoided.

  1. (15 pts)

Any reasonable working animation/movie is fine.