// Companion code for Chapter 15: Parallel Computing // Computational Physics: From Equations to Simulation // FIRST STEPS WITH OPENMP: two-dimensional periodic heat diffusion. // Build: g++ -std=c++11 -O3 -fopenmp ch15_heat_diffusion_2d.cpp -o ch15_heat_diffusion_2d // Run: ./ch15_heat_diffusion_2d // C++11 and OpenMP required; no third-party libraries. // // PDE: u_t = alpha*(u_xx+u_yy), on [0,1)^2 with periodic edges. // Explicit five-point update, r=alpha*dt/dx^2 <= 1/4 (dx=dy). // Each point reads OLD and writes NEW; in-place updates are wrong. // OpenMP distributes equal-work rows with schedule(static), unlike the // thresholded reduction example where contiguous chunks were imbalanced. // Ghost-edge copies and a barrier at each step are included in the timings. // At -O3 inspect SIMD reports if interested: -fopt-info-vec-optimized. // A single periodic cosine mode has both a known PDE decay and an EXACT // discrete finite-difference decay factor. Total heat is conserved. #include #include #include #include #include #include #include #include #include #include #include // ---- Editable example settings ---- static const int n_side = 768, time_steps = 500, repetitions = 3; static const int maximum_threads = 4; static const double diffusivity = 1.0, step_factor = 0.20, amplitude = 0.25; static const int mode_x = 8, mode_y = 6; static const bool show_inplace_demo = false; using Grid = std::vector; inline size_t at(int i, int j, int stride) { return static_cast(j) * static_cast(stride) + static_cast(i); } void periodic_edges(Grid& a, int n) { const int ld = n + 2; // Corner ghosts are unnecessary for a five-point stencil. for (int j=1; j<=n; ++j) { a[at(0,j,ld)] = a[at(n,j,ld)]; a[at(n+1,j,ld)] = a[at(1,j,ld)]; } for (int i=1; i<=n; ++i) { a[at(i,0,ld)] = a[at(i,n,ld)]; a[at(i,n+1,ld)] = a[at(i,1,ld)]; } } void heat_step(const Grid& old, Grid& next, int n, double r, int threads, bool parallel) { const int ld=n+2; // Same arithmetic in both paths; rows are equal work, so static is balanced. if (parallel) { #pragma omp parallel for schedule(static) num_threads(threads) for (int j=1;j<=n;++j) { for (int i=1;i<=n;++i) { size_t k=at(i,j,ld); next[k] = old[k] + r*(old[k-1]+old[k+1]+old[k-ld]+old[k+ld]-4.0*old[k]); } } } else { for (int j=1;j<=n;++j) { for (int i=1;i<=n;++i) { size_t k=at(i,j,ld); next[k] = old[k] + r*(old[k-1]+old[k+1]+old[k-ld]+old[k+ld]-4.0*old[k]); } } } } // Swapping pointers avoids an O(n^2) full-grid copy after every update. // Returns the buffer holding the final field (may be a or b). const Grid& evolve(Grid& a, Grid& b, int n, int steps, double r, int threads, bool parallel) { Grid* old=&a; Grid* next=&b; for (int step=0;step(ld)*ld,0.0); const double pi=std::acos(-1.0); for (int j=1;j<=n;++j) for (int i=1;i<=n;++i) a[at(i,j,ld)] = 1.0+amp*std::cos(2*pi*kx*i/n)*std::cos(2*pi*ky*j/n); return a; } double mean_interior(const Grid& a,int n) { const int ld=n+2; double s=0.0; for (int j=1;j<=n;++j) for (int i=1;i<=n;++i) s+=a[at(i,j,ld)]; return s/(static_cast(n)*n); } double max_difference(const Grid& a,const Grid& b,int n) { const int ld=n+2; double err=0.0; for (int j=1;j<=n;++j) for (int i=1;i<=n;++i) err=std::max(err,std::abs(a[at(i,j,ld)]-b[at(i,j,ld)])); return err; } double median(std::vector x) { std::sort(x.begin(),x.end()); size_t m=x.size()/2; return x.size()%2 ? x[m] : 0.5*(x[m-1]+x[m]); } int actual_team_size(int wanted) { int actual=1; #pragma omp parallel num_threads(wanted) { #pragma omp single actual=omp_get_num_threads(); } return actual; } void wrong_update_demo() { const int n=64,steps=40,ld=n+2; Grid initial=make_initial(n,4,3,0.25),a=initial,b(initial.size(),0.0),bad=initial; const Grid& good=evolve(a,b,n,steps,0.20,1,false); for (int step=0;step= 16 and steps/repetitions/threads >= 1 required"); if (mode_x<1 || mode_y<1 || 2LL*mode_x>=n_side || 2LL*mode_y>=n_side) throw std::runtime_error("wave numbers must be positive and below Nyquist limit"); if (!(diffusivity>0.0) || !(step_factor>0.0) || std::abs(amplitude)>1.0) throw std::runtime_error("diffusivity and step_factor > 0, |amplitude| <= 1 required"); double dx=1.0/n_side, dt=step_factor*dx*dx,r=diffusivity*dt/(dx*dx); if (!(r>0.0 && r<=0.25)) throw std::runtime_error("unstable r: require 0 < r <= 0.25"); if (static_cast(n_side+2)>std::numeric_limits::max()/static_cast(n_side+2)) throw std::runtime_error("grid dimensions overflow addressable size"); const double pi=std::acos(-1.0),final_time=time_steps*dt; const double decay_discrete=std::pow(1.0-4*r*(std::pow(std::sin(pi*mode_x/n_side),2)+ std::pow(std::sin(pi*mode_y/n_side),2)),time_steps); const double decay_pde=std::exp(-4*pi*pi*diffusivity*(static_cast(mode_x)*mode_x+ static_cast(mode_y)*mode_y)*final_time); const double predicted_error=std::abs(amplitude)*std::abs(decay_discrete-decay_pde); omp_set_dynamic(0); int max_p=std::min(maximum_threads,omp_get_num_procs()); Grid initial=make_initial(n_side,mode_x,mode_y,amplitude),a=initial,b(a.size(),0.0); std::cout << std::setprecision(10) << std::scientific; std::cout << "Chapter 15: first steps with C++ OpenMP heat diffusion\n" << "Grid: " << n_side << " x " << n_side << ", steps: " << time_steps << "\n" << "Approx. three-grid allocation: " << 3.0*8.0*(n_side+2.0)*(n_side+2.0)/1048576.0 << " MiB\n" << "Diffusivity alpha: " << diffusivity << ", dt: " << dt << ", r: " << r << " (<=0.25)\n" << "Final time: " << final_time << "; mode: (" << mode_x << "," << mode_y << ")\n" << "Timing repetitions: " << repetitions << "\n" << "OpenMP logical processors: " << omp_get_num_procs() << ", maximum threads requested: " << maximum_threads << ", testing up to: " << max_p << "\n" << "Ghost edges and step synchronization are included in timings.\n"; const double initial_mean=mean_interior(initial,n_side); (void)evolve(a,b,n_side,time_steps,r,1,false); // untimed warm-up std::vector secs; for (int rep=0;rep(std::chrono::steady_clock::now()-t0).count()); } const double serial_median=median(secs); // Last timed run is a valid reference (a for even steps, b for odd). const Grid serial_ref=(time_steps%2==0 ? a : b); const double serial_mean=mean_interior(serial_ref,n_side); double err_discrete=0.0,err_pde=0.0; for (int j=1;j<=n_side;++j) for (int i=1;i<=n_side;++i) { double mode=amplitude*std::cos(2*pi*mode_x*i/n_side)*std::cos(2*pi*mode_y*j/n_side); const double val=serial_ref[at(i,j,n_side+2)]; err_discrete=std::max(err_discrete,std::abs(val-(1.0+decay_discrete*mode))); err_pde=std::max(err_pde,std::abs(val-(1.0+decay_pde*mode))); } std::cout << "Initial mean: " << initial_mean << ", final mean: " << serial_mean << ", absolute change: " << std::abs(serial_mean-initial_mean) << "\n" << "Exact discrete decay factor: " << decay_discrete << "\n" << "Analytical PDE decay factor: " << decay_pde << "\n" << "Max error vs exact discrete solution: " << err_discrete << "\n" << "Max error vs analytical PDE solution: " << err_pde << "\n" << "Predicted max PDE discretization error: " << predicted_error << "\n" << "Optimized serial median: " << serial_median << " seconds\n"; if (err_discrete>1e-9 || std::abs(serial_mean-initial_mean)>1e-9) std::cerr << "WARNING: serial validation failed.\n"; std::cout << "\nThreads Actual Max field difference Mean change Median (s) Speedup\n"; for (int p=1;p<=max_p;++p) { int actual=actual_team_size(p); a=initial;std::fill(b.begin(),b.end(),0.0); (void)evolve(a,b,n_side,time_steps,r,p,true); // warm-up secs.clear(); for (int rep=0;rep(std::chrono::steady_clock::now()-t0).count()); } const Grid& result=(time_steps%2==0 ? a : b); double diff=max_difference(result,serial_ref,n_side); double change=std::abs(mean_interior(result,n_side)-initial_mean); double elapsed=median(secs); std::cout << std::setw(7) << p << " " << std::setw(6) << actual << " " << diff << " " << change << " " << elapsed << " " << serial_median/elapsed << "\n"; if (diff>1e-12) std::cerr << "WARNING: parallel field differs from serial.\n"; } std::cout << "\nEach point reads an OLD grid and writes a distinct NEW-grid value.\n" << "The field should match bit-for-bit here; aggregate sums may round differently.\n" << "This small grid may fit in cache; try 4096 x 4096 with ample RAM to study bandwidth.\n" << "Speedup uses optimized serial code. A speedup is not guaranteed.\n"; if (show_inplace_demo) wrong_update_demo(); } catch (const std::exception& ex) { std::cerr << "ERROR: " << ex.what() << "\n"; return EXIT_FAILURE; } }