README.md 2.44 KB
Newer Older
Ivo Roghair's avatar
Ivo Roghair committed
1
# Summations 
Ivo Roghair's avatar
Ivo Roghair committed
2

Ivo Roghair's avatar
Ivo Roghair committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
## Intro
It has been found that a parallel implementation of the DPM did not provide
the same (exact) results as its serial counterpart. We suspected that the 
addition of finite precision floating point numbers would be the root cause.
The (serial) DPM model loops over all the Lagrangian particles in sequence 
to account for their contribution to various field variables, e.g. porosity, 
pressure, momentum exchange etc. The parallel code adds these contributions
in a different order, and this accounts for a numerical error that perturbs
the simulation so that the results are not exactly identical compared to the
serial code. As a matter of fact, multiple runs of the same simulation may
yield slightly different results due to different scheduling.

## Components
* Python script `generateBinaryPositions.py`: Generates a binary file that 
contains the number of particles (1 integer) and consequently their (x,y,z) 
positions.
19
20
* Binary file `example.bin`: file containing the integer 10 000 000, followed
by 30 000 000 binary doubles (i.e. 10M (x y z) positions).
Ivo Roghair's avatar
Ivo Roghair committed
21
22
23
* A main file `main.cpp` that loads the binary file into an N x 3 array, and
proceeds to sum all the positions to a single summation:
```math
Ivo Roghair's avatar
Ivo Roghair committed
24
    s = \sum_{n=0}^{N_\mathrm{part}} x_n + y_n + z_n
Ivo Roghair's avatar
Ivo Roghair committed
25
26
27
28
29
```
It accounts for a summation using OpenMP parallelization, a serial summation
(counting from 0 up to npart), another serial (counting down from npart to 0) 
and finally a sum that accounts for minimizing the numerical error using the
 [Kahan summation algorithm](https://en.wikipedia.org/wiki/Kahan_summation_algorithm)
30
31
32
The program also performs a quad-precision summation which is printed first, 
and the differences between the 4 double-precision summation techniques are 
provided behind the results.
Ivo Roghair's avatar
Ivo Roghair committed
33
34
35
36

## Sample output
The program loads an input file given as argument to the program:
```
37
$ ./summation example.bin
Ivo Roghair's avatar
Ivo Roghair committed
38
39
Trying to open file example.bin ...
Trying to read 10000000 positions from file...
40
41
42
43
44
45
46
The truth, and nothing but the truth (i.e. quad precision):
                         1.499928871027937014807207560807e+07
Four different summations with double:
 OpenMP:                1.4999288710279474e+07 (delta: -1.0430812835693359e-07)
 Serial 0->nparts:      1.4999288710278464e+07 (delta: +9.0524554252624512e-07)
 Serial nparts-->0:     1.4999288710281001e+07 (delta: -1.6316771507263184e-06)
 Kahan:                 1.4999288710279370e+07 (delta: +0.0000000000000000e+00)
Ivo Roghair's avatar
Ivo Roghair committed
47
48
49
50
Exiting normally...
```

## To do