Performance of Parallel Programs

Scenario: A program takes 100 seconds total.
  - Sequential (unavoidable) work: 25 + 25 = 50 seconds
  - Parallelisable work:                    50 seconds
  - p = 50/100 = 0.50   (50% parallelisable)

With 5 threads (N = 5):
  new_time = (1 - p) * T + (p * T) / N
           = 0.50 * 100 + 0.50 * 100 / 5
           = 50 + 10
           = 60 seconds

  Speedup = old_time / new_time = 100 / 60 = 1.67x

With infinite threads (theoretical max):
  max_speedup = 1 / (1 - p) = 1 / 0.50 = 2.0x

Even with unlimited processors, this program can never run faster
than 50 seconds, because 50 seconds is the serial portion.

Example 2 (from lecture): p = 0.75, N = 8 threads
  Speedup = 1 / ((1 - 0.75) + 0.75/8)
          = 1 / (0.25 + 0.09375)
          = 1 / 0.34375
          = 2.91x

  Theoretical max (N → ∞):
  max_speedup = 1 / (1 - 0.75) = 1 / 0.25 = 4.0x

Efficiency (N=8, p=0.75):
  Efficiency = Speedup / N = 2.91 / 8 = 0.36
  (Only 36% of the additional hardware is used effectively)

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

#define ARRAY_SIZE  (16 * 1024 * 1024)  /* 16 million elements */
#define MAX_THREADS 8
#define CACHE_LINE  64

/* --- Padded struct: each thread's partial sum on its own cache line --- */
struct padded_sum {
    unsigned long long value;
    char padding[CACHE_LINE - sizeof(unsigned long long)];  /* 56 bytes */
} private_sum[MAX_THREADS];

static unsigned char array[ARRAY_SIZE];
static int num_threads;

typedef struct { int id; int start; int end; } thread_arg_t;

/* Each thread accumulates its slice into its own private_sum */
void *sum_worker(void *arg) {
    thread_arg_t *a = (thread_arg_t *)arg;
    unsigned long long local = 0;
    for (int i = a->start; i < a->end; i++)
        local += array[i];
    private_sum[a->id].value = local;
    return NULL;
}

int main(int argc, char **argv) {
    num_threads = (argc > 1) ? atoi(argv[1]) : 4;

    /* Initialise array */
    for (int i = 0; i < ARRAY_SIZE; i++) array[i] = (unsigned char)(i % 256);

    /* --- Sequential baseline --- */
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    unsigned long long seq_sum = 0;
    for (int i = 0; i < ARRAY_SIZE; i++) seq_sum += array[i];
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double seq_time = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) * 1e-9;

    /* --- Parallel version --- */
    pthread_t threads[MAX_THREADS];
    thread_arg_t args[MAX_THREADS];
    int chunk = ARRAY_SIZE / num_threads;

    for (int i = 0; i < num_threads; i++) {
        args[i].id    = i;
        args[i].start = i * chunk;
        args[i].end   = (i == num_threads - 1) ? ARRAY_SIZE : args[i].start + chunk;
        private_sum[i].value = 0;
    }

    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (int i = 0; i < num_threads; i++)
        pthread_create(&threads[i], NULL, sum_worker, &args[i]);
    for (int i = 0; i < num_threads; i++)
        pthread_join(threads[i], NULL);

    unsigned long long par_sum = 0;
    for (int i = 0; i < num_threads; i++) par_sum += private_sum[i].value;
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double par_time = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) * 1e-9;

    printf("Sequential: %.4f s  (sum = %llu)\n", seq_time, seq_sum);
    printf("Parallel (%d threads): %.4f s  (sum = %llu)\n", num_threads, par_time, par_sum);
    printf("Speedup: %.2fx  Efficiency: %.2f\n",
           seq_time / par_time, (seq_time / par_time) / num_threads);
    return 0;
}

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

#define ITERS       100000000ULL
#define NUM_THREADS 4
#define CACHE_LINE  64

/* Version A: False sharing — all counters on one cache line */
unsigned long long counters_bad[NUM_THREADS];

/* Version B: Padded — each counter on its own cache line */
struct { unsigned long long v; char pad[CACHE_LINE - 8]; } counters_good[NUM_THREADS];

void *inc_bad(void *arg)  { int id = *(int*)arg; for (unsigned long long i=0;i<ITERS;i++) counters_bad[id]++;  return NULL; }
void *inc_good(void *arg) { int id = *(int*)arg; for (unsigned long long i=0;i<ITERS;i++) counters_good[id].v++; return NULL; }

double run_threads(void *(*fn)(void*)) {
    pthread_t t[NUM_THREADS]; int ids[NUM_THREADS];
    struct timespec s, e;
    clock_gettime(CLOCK_MONOTONIC, &s);
    for (int i=0;i<NUM_THREADS;i++) { ids[i]=i; pthread_create(&t[i],NULL,fn,&ids[i]); }
    for (int i=0;i<NUM_THREADS;i++) pthread_join(t[i],NULL);
    clock_gettime(CLOCK_MONOTONIC, &e);
    return (e.tv_sec - s.tv_sec) + (e.tv_nsec - s.tv_nsec)*1e-9;
}

int main(void) {
    printf("False sharing:  %.3f s\n", run_threads(inc_bad));
    printf("Padded (fixed): %.3f s\n", run_threads(inc_good));
    return 0;
}