Pi

Benchmark

dabovila@macneill:~/concurrent$ cat sample3.run 
1 thread(s): 524.11s
2 thread(s): 275.00s
3 thread(s): 192.64s
4 thread(s): 150.11s
5 thread(s): 122.52s
6 thread(s): 104.51s
7 thread(s): 97.71s
8 thread(s): 88.17s
9 thread(s): 75.76s
10 thread(s): 69.57s
11 thread(s): 51.63s
12 thread(s): 47.46s
13 thread(s): 42.83s
14 thread(s): 42.06s
15 thread(s): 37.13s
16 thread(s): 34.81s
17 thread(s): 32.80s
18 thread(s): 30.95s
19 thread(s): 29.33s
20 thread(s): 27.86s
21 thread(s): 26.54s
22 thread(s): 25.34s
23 thread(s): 24.24s
24 thread(s): 23.23s
25 thread(s): 22.32s
26 thread(s): 23.42s
27 thread(s): 20.84s
28 thread(s): 19.95s
29 thread(s): 19.49s
30 thread(s): 18.63s
31 thread(s): 18.03s
32 thread(s): 17.50s
33 thread(s): 31.17s
34 thread(s): 35.47s
35 thread(s): 25.45s
36 thread(s): 25.25s
37 thread(s): 25.95s
38 thread(s): 23.93s
39 thread(s): 22.26s
40 thread(s): 21.43s
41 thread(s): 21.15s
42 thread(s): 20.54s
43 thread(s): 20.05s
44 thread(s): 20.68s
45 thread(s): 22.91s
46 thread(s): 28.85s
47 thread(s): 31.49s
48 thread(s): 30.48s
49 thread(s): 31.49s
50 thread(s): 31.56s
51 thread(s): 33.95s
52 thread(s): 36.24s
53 thread(s): 32.33s
54 thread(s): 29.24s
55 thread(s): 29.48s
56 thread(s): 30.34s
57 thread(s): 26.71s
58 thread(s): 31.10s
59 thread(s): 29.61s
60 thread(s): 27.59s
61 thread(s): 31.96s
62 thread(s): 31.52s
63 thread(s): 28.20s
64 thread(s): 18.73s
65 thread(s): 27.19s
66 thread(s): 27.92s
67 thread(s): 29.77s
68 thread(s): 29.40s
69 thread(s): 31.00s
70 thread(s): 30.68s
71 thread(s): 32.92s
72 thread(s): 31.36s
73 thread(s): 27.45s
74 thread(s): 30.40s
75 thread(s): 29.35s
76 thread(s): 32.98s
77 thread(s): 29.71s
78 thread(s): 27.64s
79 thread(s): 28.84s
80 thread(s): 30.94s
81 thread(s): 28.54s
82 thread(s): 31.37s
83 thread(s): 29.23s
84 thread(s): 28.38s
85 thread(s): 28.27s
86 thread(s): 31.99s
87 thread(s): 26.70s
88 thread(s): 28.35s
89 thread(s): 29.09s
90 thread(s): 29.59s
91 thread(s): 29.54s
92 thread(s): 29.76s
93 thread(s): 29.62s
94 thread(s): 25.77s
95 thread(s): 27.66s
96 thread(s): 22.18s

pi.c

#include <pthread.h>
#include <stdio.h>

//#define THREADS 2 // number of threads to use
//#define ITERATIONS (1<<30) // total number of iterations
//#define NRUNS 5 // how many time we compute pi?

typedef struct {
    unsigned min;
    unsigned iterations;
    double res;
} pi_arg_t;

void* madhava_series(void *arg) {
    /* arg should be a pi_arg_t*
     *
     * compute the series:
     * \sum_{k=arg->min}^{arg->min + arg->iterations - 1} \frac{(-1)^k}{2k + 1}
     *
     * (IMPORTANT: does not multiply the result by 4)
     */

    pi_arg_t *v = (pi_arg_t*)arg;
    double res = 0.;

    for(unsigned k = v->min, max = k + v->iterations; k < max; ++k) {
        /* check if the power k is even or not,
         * more efficient than raising to the power k
         * as in the *true* formula
         */
        res += (k & 1 ? -1. : 1.) / ((k << 1) + 1);
    }

    v->res = res;
}

int main(int argc, char *argv[]) {
    /* Compute & print PI NRUNS times 
     *
     * Compile & run with:
     * $ gcc pi.c -Ofast -lpthread -std=c99 -D THREADS=4 -D ITERATIONS=(1<<30)\
     *   -D NRUNS 5
     * $ ./a.out
     */
    for(unsigned tmp = 0; tmp < NRUNS; ++tmp) {
        /* Compute & print PI using the Madhava's series:
         * pi = 4 \sum_{k=0}^{\infty} \frac{(-1)^k}{2k + 1}
         */
        double res = 0.;

        pthread_t threads[THREADS];
        pi_arg_t args[THREADS];

        /* create threads */
        for(unsigned i = 0; i < THREADS; ++i) {
            args[i].iterations = ITERATIONS / THREADS;
            args[i].min = i * args[i].iterations;

            if(i == THREADS - 1) {
                args[i].iterations += ITERATIONS % THREADS;
            }

            pthread_create(&threads[i], NULL, madhava_series, &args[i]);
        }

        /* wait for them to exit */
        for(unsigned i = 0; i < THREADS; ++i) {
            pthread_join(threads[i], NULL);
            res += args[i].res;
        }

        /* see Madhava's series */
        res *= 4.;

        printf("pi = %.10f\n", res);
    }

    return 0;
}

Processed

dabovila@macneill:~/concurrent$ cat sample3.run | cut -d : -f 2 | tr -d ' s' | sed 's/\./,/'
524,11
275,00
192,64
150,11
122,52
104,51
97,71
88,17
75,76
69,57
51,63
47,46
42,83
42,06
37,13
34,81
32,80
30,95
29,33
27,86
26,54
25,34
24,24
23,23
22,32
23,42
20,84
19,95
19,49
18,63
18,03
17,50
31,17
35,47
25,45
25,25
25,95
23,93
22,26
21,43
21,15
20,54
20,05
20,68
22,91
28,85
31,49
30,48
31,49
31,56
33,95
36,24
32,33
29,24
29,48
30,34
26,71
31,10
29,61
27,59
31,96
31,52
28,20
18,73
27,19
27,92
29,77
29,40
31,00
30,68
32,92
31,36
27,45
30,40
29,35
32,98
29,71
27,64
28,84
30,94
28,54
31,37
29,23
28,38
28,27
31,99
26,70
28,35
29,09
29,59
29,54
29,76
29,62
25,77
27,66
22,18

run.sh

#!/usr/bin/env bash

iterations='(1<<30)'
nruns=50 # number of time we run the executable

for n in {1..96} # go up to 96 to (hopefully) show the cost of context switches
do
    # compile with $n threads and $iterations
    gcc pi.c -O3 -lpthread -std=c99 -D THREADS=$n -D ITERATIONS=$iterations -D NRUNS=$nruns
    /usr/bin/time -f "$n thread(s): %es" ./a.out > /dev/null
done