Parallel histogram implementations

This project compares five strategies for constructing a histogram from uniformly generated integer samples:

1. a sequential baseline;
2. one global mutex;
3. one mutex per bucket;
4. atomic bucket counters; and
5. thread-local histograms followed by a reduction.

The programs use the same command-line interface and deterministic random-number streams, making synchronization overhead and scalability easier to compare.

Implementations

Source file	Strategy
histogram.cpp	Sequential baseline
histogram-mutex.cpp	One mutex protecting the entire histogram
histogram-mutex-per-bucket.cpp	One mutex per bucket
histogram-atomic.cpp	Relaxed atomic increment per bucket
histogram-best.cpp	Private histogram per thread followed by reduction

histogram-common.hpp contains shared argument parsing, deterministic sample generation, work partitioning, timing, and result reporting.

Requirements

• A C++17 compiler
• POSIX threads
• GNU Make
• Optional: Slurm for cluster benchmarks

Build and verify

make
make test

The executables are written to build/. The smoke test checks that every strategy processes the requested number of samples.

Run one implementation

./build/histogram-atomic \
  --N 255 \
  --sample-size 30000000 \
  --num-threads 8 \
  --seed 1 \
  --print-level 2

--N is the largest generated integer, so the histogram contains N + 1 buckets. Print level 0 emits only elapsed seconds; level 1 also emits the histogram and total; level 2 additionally emits the run configuration.

The sequential executable accepts only --num-threads 1.

Benchmark sweep

runall.sh sweeps bucket and thread counts and writes structured CSV output:

./runall.sh ./build/histogram-atomic atomic-results.csv

The defaults can be overridden through environment variables:

SAMPLE_SIZE=10000000 \
REPETITIONS=5 \
THREAD_COUNTS="1 2 4 8" \
MAX_VALUES="10 100 1000" \
./runall.sh ./build/histogram-best local-results.csv

Each configuration is measured three times by default. Set REPETITIONS to change this value.

When run inside an allocated Slurm job, the script launches each measurement with srun and requests one task with the corresponding number of CPUs. Otherwise, it runs locally.

Measurement scope

The timed section includes random-number generation and histogram construction. For the thread-local strategy, it also includes the final reduction. Allocation, argument parsing, and output are excluded.

Each worker receives a distinct but deterministic random-number stream derived from the base seed and thread index. All implementations therefore process equivalent streams for a fixed seed and thread count.