MPI-based embarrassingly parallel benchmark on a heterogeneous Raspberry Pi cluster
We estimated ฯ using the Monte Carlo method with MPI parallelization. Each rank independently generates random points and checks if they fall inside a unit circle. A single MPI_Reduce at the end combines results โ making this an embarrassingly parallel workload with minimal communication overhead.
We tested 6 core counts (1, 2, 4, 8, 16, 32) across 5 problem sizes (1M to 10B points), running each configuration 3โ5 times on an idle cluster with active fan cooling. Pi5 was excluded from compute โ all 32 cores are from 8ร Pi3 nodes (4 cores each).
Select problem size and view type. Charts replicate Prof. Baun's methodology from lecture slides.
| Cores | Mean Time (s) | Std Dev (s) | Speedup | Ideal | Efficiency | Runs |
|---|
Speedup at each core count across all problem sizes. Shows how larger problems approach ideal scaling.
Prof. Baun's key challenge: "Find the point where the program cannot be parallelized anymore." We systematically investigated where our cluster hits this limit and what causes it. Single runs were used for preliminary investigation across problem sizes from 1B to 25B.
At all problem sizes tested, 8 cores is the effective parallelization limit on our cluster. Beyond 8 cores, crossing from 2 to 4 physical nodes introduces MPI communication overhead that exceeds the compute gain โ exactly the serial fraction Amdahl's Law identifies. Adding more cores (16) provides no meaningful benefit, while 32 cores recovers by utilizing all 8 nodes symmetrically.
| Problem Size | 8 Cores (s) | 16 Cores (s) | 8โ16 Improvement | 32 Cores (s) | 16โ32 Improvement | Switch Topology |
|---|---|---|---|---|---|---|
| 1B | 25.46 | 25.37 | 0.4% โ | 12.57 | 50.4% โ | 2 switches |
| 5B | 126.42 | 124.98 | 1.1% โ | 62.31 | 50.1% โ | 2 switches |
| 7.5B | 189.87 | 186.95 | 1.5% โ | 93.74 | 49.8% โ | 2 switches |
| 10B | 252.96 | 250.17 | 1.1% โ | 125.02 | 50.0% โ | 2 switches |
| 10B (after switch rearrangement) | 256.23 | 249.34 | 2.7% โฌ๏ธ | 124.18 | 50.2% โ | 1+1 switches |
| 25B | 640 | 624 | 2.5% โ | 311.4 | 50.1% โ | 1+1 switches |
Switch 1: Pi5 + pi3-01 (2 devices)
Switch 2: pi3-02 to pi3-08 (7 devices)
Effect: ALL inter-Pi3 MPI communication crossed the inter-switch uplink
Ping latency pi3-01โpi3-06: 0.749ms (mdev: 0.205ms)
Switch 1: Pi5 + pi3-01 to pi3-06 (7 devices)
Switch 2: pi3-07, pi3-08 (2 devices)
Effect: Only 2 nodes cross the inter-switch boundary
Ping latency pi3-01โpi3-06: 0.433ms (mdev: 0.061ms) โ 42% faster, 3.4ร less jitter
Problem size effect: Increasing from 1B to 25B (25ร larger) improved 8โ16 core performance by only 0.4% โ 2.5% โ a marginal effect. To achieve clear 2ร improvement at 16 cores, problem sizes of ~500B+ would theoretically be needed, which is impractical on this hardware.
Switch topology effect: Rearranging switches improved latency by 42% and reduced jitter by 3.4ร, with slight improvement in 8โ16 performance (1.1% โ 2.7% at 10B). However the plateau persisted.
Final conclusion: The plateau is primarily a fundamental MPI communication topology effect when crossing from 2 to 4 physical nodes. A single switch connecting all 9 devices is the recommended next step to fully eliminate this bottleneck.
At 1B and 10B points, speedup tracks very closely to the ideal linear line: 2.00ร at 2 cores, ~3.95ร at 4 cores, ~7.87ร at 8 cores. Parallel efficiency exceeds 98% up to 8 cores โ the cluster hardware scales extremely well within node boundaries.
This directly answers Prof. Baun's challenge: "Find the point where the program cannot be parallelized anymore." On our cluster, the effective limit is 8 cores. Beyond this, MPI communication overhead at the 2โ4 node boundary exceeds the compute gain. This is Amdahl's Law made visible โ the serial fraction is the inter-node MPI_Reduce communication.
We tested problem sizes from 1B to 25B (25ร increase) to see if larger problems move the parallelization limit. Improvement at 8โ16 cores grew from 0.4% to only 2.5% โ the limit remains at 8 cores regardless. This confirms the limit is structural (network topology) not computational.
At 1M points: speedup degrades rapidly beyond 4 cores (communication dominates โ Amdahl's Law clearly visible). At 10B points: near-linear scaling to 8 cores, then the topology limit. This confirms Prof. Baun's lecture: "A sufficiently large problem can be parallelized efficiently."
Coefficient of variation < 0.5% for all 1B and 10B configurations across 3โ5 runs. This demonstrates the cluster operates stably under controlled conditions โ idle system, fan cooling, zombie process prevention. The consistency validates the results are real hardware behavior, not measurement noise.
Runtime (top row) and Speedup (bottom row) for each problem size. Values shown on bars. Color: green >85% efficiency, yellow 50โ85%, red <50% (parallelization limit).