! Companion code for Chapter 15: Parallel Computing ! Computational Physics: From Equations to Simulation ! ! FIRST STEPS WITH OPENMP: parallel Monte Carlo, reproducible batches, ! statistical uncertainty, strong scaling, and weak scaling. ! ! Build with GNU Fortran (Fortran 95 syntax plus OpenMP extension): ! gfortran -std=f95 -Wall -Wextra -pedantic -O3 -fopenmp & ! ch15_parallel_monte_carlo.f95 -o ch15_parallel_monte_carlo ! ./ch15_parallel_monte_carlo ! ! Estimate pi by throwing random points uniformly into the unit square. ! A point is a hit if x*x+y*y <= 1 (quarter unit disk). ! The estimate is pi_hat = 4*hits/samples. Its estimated standard error is ! SE = 4*sqrt(p_hat*(1-p_hat)/samples), p_hat=hits/samples. ! A deviation of several SE is possible by chance; it does not by itself ! demonstrate a parallel-programming error. ! ! Each batch has a fixed stream of pseudo-random numbers. The streams are ! contiguous, nonoverlapping positions in a combined two-component ! L'Ecuyer (1988) multiplicative generator, located by modular jump-ahead. ! A batch gives the same hit count no matter which OpenMP thread performs ! it. Serial and parallel integer counts can therefore agree exactly. ! The combined period is approximately 2.3e18 draws, vastly longer than ! the period of the elementary Park-Miller generator used in the first draft. ! IMPORTANT: this educational generator is not suitable for cryptography. ! For demanding research simulations, use a validated parallel RNG library. ! ! Change settings below. The fixed seed is active by default. ! To use a fresh seed, see the commented alternative in the settings. ! No plotting, MPI, or additional numerical libraries are needed. ! ! Strong scaling: fixed number of batches for all thread counts. ! Weak scaling: fixed number of batches per thread, so work grows with p. ! Timings are wall-clock times, with warm-up and repeated measurements. ! Thread creation/scheduling are included; printing and validation are not. program ch15_parallel_monte_carlo use omp_lib implicit none integer, parameter :: dp = selected_real_kind(15,300) integer, parameter :: i8 = selected_int_kind(18) ! Combined multiplicative RNG: two independently advanced components. ! Each modular product fits within signed 64-bit integer arithmetic. integer(i8), parameter :: m1=2147483563_i8, a1=40014_i8 integer(i8), parameter :: m2=2147483399_i8, a2=40692_i8 ! ---- Editable example settings ---- integer, parameter :: samples_per_batch = 100000 integer, parameter :: strong_batches = 240 ! 24 million samples integer, parameter :: weak_batches_per_thread = 240 integer, parameter :: repetitions = 3 integer, parameter :: maximum_threads = 4 integer(i8), parameter :: base_seed1 = 13579_i8 integer(i8), parameter :: base_seed2 = 24680_i8 logical, parameter :: use_clock_seed = .false. ! Set use_clock_seed = .true. for a fresh clock-derived seed. ! Keep .false. for reproducible comparisons. integer :: p, max_p, rep, batches, actual_threads, clock_tick integer(i8) :: serial_hits, parallel_hits, weak_hits, weak_serial_hits integer(i8) :: seed1_used, seed2_used, n_samples real(dp) :: serial_times(repetitions), parallel_times(repetitions) real(dp) :: weak_times(repetitions), reference_seconds, parallel_seconds real(dp) :: weak_seconds, pi_value, pi_exact, se, t0 real(dp) :: strong_speedup, weak_reference_time if (samples_per_batch < 1 .or. strong_batches < 1 .or. & weak_batches_per_thread < 1 .or. repetitions < 1 .or. & maximum_threads < 1) then print '(a)', 'Error: sample, batch, repetition and thread settings must be positive.' stop 1 end if if (base_seed1 < 1_i8 .or. base_seed1 >= m1 .or. & base_seed2 < 1_i8 .or. base_seed2 >= m2) then print '(a)', 'Error: seeds must be positive and below their respective moduli.' stop 1 end if ! TWO random draws per sample. Check integer jump calculations and keep ! total work far below the very long combined period (~2.3e18 draws). if (2_i8*int(samples_per_batch,i8)* & max(int(strong_batches,i8), & int(weak_batches_per_thread,i8)*int(maximum_threads,i8)) & > 1000000000000000_i8) then print '(a)', 'Error: requested RNG draws exceed the conservative teaching limit.' stop 1 end if seed1_used=base_seed1 seed2_used=base_seed2 if (use_clock_seed) then call system_clock(count=clock_tick) seed1_used=1_i8+mod(abs(int(clock_tick,i8)),m1-1_i8) seed2_used=1_i8+mod(abs(int(clock_tick,i8)+104729_i8),m2-1_i8) end if call omp_set_dynamic(.false.) max_p = min(maximum_threads,omp_get_num_procs()) pi_exact = acos(-1.0_dp) n_samples = int(strong_batches,i8)*int(samples_per_batch,i8) print '(a)', 'Chapter 15: first steps with OpenMP Monte Carlo' print '(a)', 'Quarter-circle area estimate of pi, using batch-specific streams.' print '(a,2(i0,1x))', 'Random component seeds: ',seed1_used,seed2_used print '(a,i0)', 'Samples per batch: ',samples_per_batch print '(a,i0)', 'Strong-scaling batches: ',strong_batches print '(a,i0)', 'Strong-scaling samples: ',n_samples print '(a,i0)', 'Weak-scaling batches per thread: ',weak_batches_per_thread print '(a,i0)', 'Available OpenMP processors (logical CPUs possible): ',omp_get_num_procs() print '(a,i0)', 'Maximum threads requested: ',maximum_threads print '(a,i0)', 'Threads tested: 1 through ',max_p print '(a,i0)', 'Timing repetitions: ',repetitions print '(a)', '' ! Warm up both paths before timing. serial_hits = serial_count(1, strong_batches, samples_per_batch, seed1_used,seed2_used) parallel_hits = parallel_count(strong_batches,samples_per_batch,seed1_used,seed2_used,1) if (serial_hits /= parallel_hits) then print '(a)', 'ERROR: serial and 1-thread counts disagree.' stop 2 end if do rep=1,repetitions t0 = omp_get_wtime() serial_hits = serial_count(1,strong_batches,samples_per_batch,seed1_used,seed2_used) serial_times(rep) = omp_get_wtime()-t0 end do reference_seconds = median(serial_times) call report_statistics('Strong-scaling serial',serial_hits,n_samples,pi_exact) print '(a,f10.5,a)', 'Serial median time: ',reference_seconds,' seconds' print '(a)', 'Strong scaling: SAME total sample count for every thread count.' print '(a)', ' Threads Actual Hits Median (s) Speedup' do p=1,max_p call determine_threads(p,actual_threads) parallel_hits = parallel_count(strong_batches,samples_per_batch,seed1_used,seed2_used,p) do rep=1,repetitions t0=omp_get_wtime() parallel_hits=parallel_count(strong_batches,samples_per_batch,seed1_used,seed2_used,p) parallel_times(rep)=omp_get_wtime()-t0 end do parallel_seconds=median(parallel_times) strong_speedup=reference_seconds/max(parallel_seconds,tiny(1.0_dp)) if (parallel_hits /= serial_hits) then print '(a,i0)', 'ERROR: parallel hit count differs at threads=',p stop 3 end if print '(2i8,3x,i14,3x,f10.5,3x,f8.3)', & p,actual_threads,parallel_hits,parallel_seconds,strong_speedup end do print '(a)', '' ! The weak-scaling reference is one thread processing its fixed work. ! At p threads, total batches = p*weak_batches_per_thread. batches=weak_batches_per_thread weak_hits=parallel_count(batches,samples_per_batch,seed1_used,seed2_used,1) do rep=1,repetitions t0=omp_get_wtime() weak_hits=parallel_count(batches,samples_per_batch,seed1_used,seed2_used,1) weak_times(rep)=omp_get_wtime()-t0 end do weak_reference_time=median(weak_times) print '(a)', 'Weak scaling: SAME number of batches per requested thread.' print '(a,f9.5,a)', 'One-thread weak-reference time: ',weak_reference_time,' seconds' print '(a)', ' Threads Samples Pi estimate SE Median (s) Efficiency' do p=1,max_p batches=p*weak_batches_per_thread n_samples=int(batches,i8)*int(samples_per_batch,i8) call determine_threads(p,actual_threads) weak_hits=parallel_count(batches,samples_per_batch,seed1_used,seed2_used,p) ! Independent correctness check: serial processing of the SAME batches. weak_serial_hits=serial_count(1,batches,samples_per_batch,seed1_used,seed2_used) if (weak_hits /= weak_serial_hits) then print '(a,i0)', 'ERROR: weak-scaling hit count differs at threads=',p stop 4 end if do rep=1,repetitions t0=omp_get_wtime() weak_hits=parallel_count(batches,samples_per_batch,seed1_used,seed2_used,p) weak_times(rep)=omp_get_wtime()-t0 end do weak_seconds=median(weak_times) pi_value=4.0_dp*real(weak_hits,dp)/real(n_samples,dp) se=4.0_dp*sqrt((pi_value/4.0_dp)*(1.0_dp-pi_value/4.0_dp) / & real(n_samples,dp)) print '(i8,1x,i12,3x,f13.8,3x,es9.2,3x,f10.5,3x,f9.3)', & p,n_samples,pi_value,se,weak_seconds, & weak_reference_time/max(weak_seconds,tiny(1.0_dp)) end do print '(a)', '' print '(a)', 'Weak-scaling efficiency = T(1 thread, fixed work) / T(p threads, p*work).' print '(a)', 'Ideal weak-scaling efficiency is near 1; overhead may reduce it.' print '(a)', 'Rows use nested samples: larger runs include earlier batches, so' print '(a)', 'their pi estimates are statistically correlated, not independent.' print '(a)', 'Laptop clocks may decrease with more active cores, reducing efficiency.' print '(a)', 'Strong scaling measures speedup for fixed work, weak scaling for growing work.' print '(a)', 'Exact integer hit agreement checks parallel bookkeeping, not RNG quality.' print '(a)', 'Monte Carlo error decreases approximately as 1/sqrt(number of samples).' print '(a)', 'Timing values are machine-dependent; speedup is not guaranteed.' contains function next_random(state1,state2) result(u) integer(i8), intent(inout) :: state1,state2 integer(i8) :: z real(dp) :: u state1=mod(a1*state1,m1) state2=mod(a2*state2,m2) z=state1-state2 if (z < 1_i8) z=z+(m1-1_i8) u=real(z,dp)/real(m1,dp) end function next_random function mod_power(base,exponent,m) result(value) integer(i8), intent(in) :: base,exponent,m integer(i8) :: value,b,e value=1_i8 b=mod(base,m) e=exponent do while (e>0_i8) if (mod(e,2_i8)==1_i8) value=mod(value*b,m) b=mod(b*b,m) e=e/2_i8 end do end function mod_power function batch_count(batch_id,n_per_batch,seed1,seed2) result(hits) integer, intent(in) :: batch_id,n_per_batch integer(i8), intent(in) :: seed1,seed2 integer(i8) :: hits,state1,state2,jump integer :: i real(dp) :: x,y ! First random draw for batch k follows the first 2*n*(k-1) draws. jump=2_i8*int(n_per_batch,i8)*int(batch_id-1,i8) state1=mod(seed1*mod_power(a1,jump,m1),m1) state2=mod(seed2*mod_power(a2,jump,m2),m2) hits=0_i8 do i=1,n_per_batch x=next_random(state1,state2) y=next_random(state1,state2) if (x*x+y*y <= 1.0_dp) hits=hits+1_i8 end do end function batch_count function serial_count(first,last,n_per_batch,seed1,seed2) result(total) integer, intent(in) :: first,last,n_per_batch integer(i8), intent(in) :: seed1,seed2 integer(i8) :: total integer :: b total=0_i8 do b=first,last total=total+batch_count(b,n_per_batch,seed1,seed2) end do end function serial_count function parallel_count(n_batches,n_per_batch,seed1,seed2,threads) result(total) integer, intent(in) :: n_batches,n_per_batch,threads integer(i8), intent(in) :: seed1,seed2 integer(i8) :: total integer :: b total=0_i8 !$omp parallel do default(shared) private(b) reduction(+:total) & !$omp& schedule(static) num_threads(threads) do b=1,n_batches total=total+batch_count(b,n_per_batch,seed1,seed2) end do !$omp end parallel do end function parallel_count subroutine report_statistics(label,hits,samples,exact) character(len=*), intent(in) :: label integer(i8), intent(in) :: hits,samples real(dp), intent(in) :: exact real(dp) :: phat,pi_hat,standard_error,z phat=real(hits,dp)/real(samples,dp) pi_hat=4.0_dp*phat standard_error=4.0_dp*sqrt(phat*(1.0_dp-phat)/real(samples,dp)) z=abs(pi_hat-exact)/max(standard_error,tiny(1.0_dp)) print '(a)',trim(label) print '(a,i0)', ' Hits: ',hits print '(a,f14.9)', ' Pi estimate: ',pi_hat print '(a,f14.9)', ' Reference pi: ',exact print '(a,es12.4)', ' Estimated standard error: ',standard_error print '(a,f9.3)', ' Absolute discrepancy / SE: ',z if (z>4.0_dp) then print '(a)', ' Note: deviation exceeds 4 estimated SE; investigate if persistent.' end if end subroutine report_statistics subroutine determine_threads(requested,observed) integer, intent(in) :: requested integer, intent(out) :: observed observed=0 !$omp parallel num_threads(requested) shared(observed) !$omp single observed=omp_get_num_threads() !$omp end single !$omp end parallel end subroutine determine_threads function median(values) result(m) real(dp), intent(in) :: values(:) real(dp) :: m,temp,work(size(values)) integer :: i,j work=values do i=2,size(work) temp=work(i) j=i-1 do while(j>=1) if (work(j)<=temp) exit work(j+1)=work(j) j=j-1 end do work(j+1)=temp end do i=size(work) if (mod(i,2)==1) then m=work((i+1)/2) else m=0.5_dp*(work(i/2)+work(i/2+1)) end if end function median end program ch15_parallel_monte_carlo