-
When equal iterations are not equal work
Level: Foundation · Program: parallel_reduction (Fortran or C++)
Start from the supplied default sum with
N = 50,000,000 and x_cut = 0.5. Enable the optional scheduling comparison
(show_schedule_demo in Fortran; see the corresponding
setting in C++). Run with two threads, if available, and compare
contiguous schedule(static) with
schedule(static,4096). Repeat each timing at least five
times and report medians. Explain why half the contiguous iteration
range contributes almost no expensive work.
Validation: Both properly reduced sums must agree with
the serial result to floating-point rounding. Their right-endpoint
integration errors should agree with the printed leading-error
prediction. Faster execution is not a correctness check.
Extension: try x_cut = 0.1 and
0.9. How does the amount and distribution of useful
work change? With two physical cores, the contiguous schedule
often gives speedup near 1, whereas chunked scheduling may
approach 2; actual timings depend on the machine. If at least
two threads are available, try the
explicitly unsafe accumulation option and compare it with the
correct reduction and atomic versions. A race need not produce
an incorrect value on every run.
-
When is parallel execution worthwhile?
Level: Foundation · Program: parallel_reduction
Use N = 500,000, 5,000,000, and
50,000,000, keeping x_cut = 0.5 and the
same compilation options. For each size, record the optimized
serial median and parallel medians with one, two, and four
threads or workers, limited by the hardware available. Compute
speedup S = T_serial/T_parallel and efficiency
E = S/P, where P is the actual number
of workers used.
Validation: Check the numerical sum before comparing
timings. Keep problem size fixed across worker counts within
each strong-scaling experiment. If no speedup occurs, report
that result rather than changing the comparison baseline.
Extension: estimate the effective serial fraction for
P > 1 as
e = (1/S − 1/P)/(1 − 1/P).
Explain why overhead and measurement noise mean this is not a
direct measurement of a fixed serial portion of the code.
-
Parallel heat diffusion: correctness before speed
Level: Intermediate · Program: heat_diffusion_2d (Fortran, C++, or Python)
Keep the Fourier-mode initial condition, alpha = 1,
and r = 0.20. Run the grids
128 × 128, 256 × 256, and
512 × 512 for 50, 200, and 800 steps,
respectively. Since dt = r/(alpha N2),
these choices have the same final physical time. Record maximum
error against the exact discrete mode and analytical PDE
solution, mean-temperature change, and serial/parallel field
difference.
Validation: The discrete-mode error and the parallel-field
difference should remain near floating-point rounding. The
analytical PDE error should decrease as the grid is refined;
doubling resolution with four times as many steps should give
approximately second-order convergence while the leading error
dominates. For these settings, representative PDE errors are
about 7.23 × 10−4,
1.80 × 10−4, and
4.49 × 10−5;
successive error ratios should be close to 4. Keep the
prescribed stable r ≤ 0.25.
Extension (Fortran or C++): activate the supplied
incorrect in-place update demonstration on a small grid. Observe both the field error and
the change in mean temperature. Do not use this update for a
production calculation.
-
Reproducibility is not the same as statistical accuracy
Level: Intermediate · Program: parallel_monte_carlo
Keep 100,000 samples per batch and use 30, 120,
and 480 batches (3, 12, and 48 million points) to estimate
π. For each size, use the same fixed seed or seed pair and
compare serial and parallel hit counts with one, two, and four
workers where supported. Record the estimated standard error
and |pi_estimate − pi|/SE.
Validation: The integer hit counts should match exactly
across worker counts for each fixed setup; different languages
are not expected to generate the same points. The estimated
standard error should decrease approximately as
1/sqrt(N). One estimate need not get closer to
π every time the sample count increases.
Extension: repeat for ten recorded seeds and count how
many estimates lie within two standard errors of π.
For independent experiments with approximately normal errors,
the theoretical coverage is about 95%; with ten seeds,
typically 9 or 10 estimates will fall inside, though any
particular run may differ. For one language, also compare strong scaling with weak scaling;
remember that the supplied weak runs reuse earlier batches and
their estimates are correlated.
-
Task parallelism in MATLAB: four or twelve simulations?
Level: Intermediate · MATLAB with Parallel Computing Toolbox
In ch15_heat_diffusion_2d.m, run the four-diffusivity
default, then set run_twelve_case_experiment = true
and run twelve independent cases. Keep the same grid and time
steps for both experiments. For each, record its own optimized
serial median, the parfor median with each available
worker limit, and the speedup. Do not compare the twelve-case
elapsed time directly with the four-case elapsed time.
Validation: Every parallel final field should agree with
its serial counterpart, and the mean temperature and exact
discrete mode should pass their checks. Explain why more
independent tasks do not guarantee a higher speedup: MATLAB's
vectorized serial operations may already use multiple cores,
while workers compete for processing and memory resources.
Extension: also time the same serial calculation with
MATLAB limited to one computational thread. Where supported,
save the original thread setting using
old_threads = maxNumCompThreads(1), run the serial
calculation, and then restore it with
maxNumCompThreads(old_threads). Recompute speedup
against this explicitly single-threaded baseline, and distinguish
it from speedup against MATLAB's optimized default serial run.
As another experiment, use a smaller grid and compare the
performance pattern; neither test alone proves a specific
hardware bottleneck.
-
Compute-bound or memory-bound?
Level: Intermediate · Programs: parallel_reduction and heat_diffusion_2d (Fortran or C++)
Using the same compiler, optimization options, and available
thread counts, compare the strong-scaling behavior of the
reduction and heat-diffusion programs. Then try heat grids of
256 × 256, 1024 × 1024,
and 4096 × 4096, if memory permits. Adjust
the time-step count so timed runs are long enough for reliable
medians; keep the stable stencil coefficient unchanged.
Estimate the storage for two double-precision temperature
grids: approximately 16 bytes per point, or 256 MiB at
4096 × 4096. The complete program uses
additional grids and temporary storage, so allow considerably
more RAM. Compare working-set sizes with your processor's caches.
Validation: the serial and parallel sums or fields,
the heat-conservation check, and the discrete-mode check must
pass before timing comparisons. Explain why the reduction
performs relatively expensive arithmetic per accepted term,
while a heat stencil reads and writes many neighboring values.
Cache, memory bandwidth, and CPU architecture may influence
scaling, so a specific crossover is not guaranteed.
Extension: with GCC, build the heat program using
-O2 and -O3 and add
-fopt-info-vec-optimized to inspect vectorization
reports. Which stencil loops are vectorized? Compare the
optimized serial time with the one-thread OpenMP time for
each build. Compiler behavior may differ by version.