The purpose of this exercise is to write a program that demonstrates the need for parallel computing. In a basic particle simulation, with calculations of distance from each particle to every other particle, the problem is O(N^2). This naive, unparallel program simply nests one loop over the set of particles inside another.
The program can be downloaded here.
The program computes the mean of all of the particles, and the variance from the mean. These calculations are O(N). After computing all of the distances, the program computes the mean distance and the variance, as well as the mean inverse squared distance and its variance.
Because the program randomly generates the particles, it is expected that the means will converge to (0,0) with larger numbers of particles. The variance, with a radius of 1, is expected to converge to 0.333... for the square shape, and 0.250 for the disk shape, as the disk shape is smaller in surface area than the square.
RESULTS
numParticles 1000
shape square
radius 1.000000
xMean 0.003013
yMean -0.006152
xVariance 0.347908
yVariance 0.335383
distanceMean 1.055987
distanceVariance 1.367950
distanceInverseSquaredMean 10.803389
distanceInverseSquaredVariance 911364.212702
shape square radius 1 numParticles 1000 timeElapsed 0.16s
The values are mostly as expected, though the Inverse Squared Distance variance is a very large number that is hard to intuitively verify.
Doubling the problem size does in fact quadruple (2^2) the runtime, as shown for numParticles = 2000:
numParticles 2000
shape square
radius 1.000000
xMean -0.008348
yMean -0.011882
xVariance 0.341173
yVariance 0.339286
distanceMean 1.053602
distanceVariance 1.361599
distanceInverseSquaredMean 16.772375
distanceInverseSquaredVariance 59622542.750757
shape square radius 1 numParticles 2000 timeElapsed 0.66s
Again, values are as expected, and the variance has dropped slightly. Doubling the problem size to 4000:
numParticles 4000
shape square
radius 1.000000
xMean -0.004678
yMean -0.009344
xVariance 0.334032
yVariance 0.334881
distanceMean 1.044886
distanceVariance 1.338162
distanceInverseSquaredMean 13.926066
distanceInverseSquaredVariance 22747124.295431
shape square radius 1 numParticles 4000 timeElapsed 2.63s
At this point, the mean and variance are clearly converging. Doubling again to 8000:
numParticles 8000
shape square
radius 1.000000
xMean 0.000013
yMean -0.005476
xVariance 0.329461
yVariance 0.333698
distanceMean 1.040121
distanceVariance 1.326485
distanceInverseSquaredMean 14.022405
distanceInverseSquaredVariance 67923729.057555
shape square radius 1 numParticles 8000 timeElapsed 10.5s
With the disk shape, we see similar results, but the variances are smaller:
numParticles 2000
shape disk
radius 1.000000
xMean -0.013676
yMean 0.003475
xVariance 0.255792
yVariance 0.248521
distanceMean 0.909900
distanceVariance 1.009132
distanceInverseSquaredMean 18.541516
distanceInverseSquaredVariance 57242207.267090
shape disk radius 1 numParticles 2000 timeElapsed 0.66s
The runtime with the disk shape is not significantly different from the runtime with the square, as the distance computation dominates the particle generation and discarding of 'invalid' particles.
The full set of timing results for disk show the O(N^2) growth of the problem:
shape disk radius 1 numParticles 1000 timeElapsed 0.16s
shape disk radius 1 numParticles 2000 timeElapsed 0.66s
shape disk radius 1 numParticles 3000 timeElapsed 1.47s
shape disk radius 1 numParticles 4000 timeElapsed 2.63s
shape disk radius 1 numParticles 5000 timeElapsed 4.09s
shape disk radius 1 numParticles 6000 timeElapsed 5.92s
shape disk radius 1 numParticles 7000 timeElapsed 8.04s
shape disk radius 1 numParticles 8000 timeElapsed 10.48s