// Companion code for Chapter 15: Parallel Computing // Computational Physics: From Equations to Simulation // // FIRST STEPS WITH OPENMP (C++11): serial sum, parallel reduction, timing. // // Compile with an OpenMP-capable compiler, for example GNU C++: // g++ -std=c++11 -O2 -fopenmp ch15_parallel_reduction.cpp -o ch15_parallel_reduction // ./ch15_parallel_reduction // On macOS, Apple's default clang++ may need a separately installed OpenMP // runtime/compiler. C++11 alone does not supply OpenMP. // // Problem: S = sum [sin(x_i) + sqrt(x_i)] for x_i > x_cut, // where x_i = i/N, i = 1,...,N. // Then h*S approximates the integral from x_cut to 1, h = 1/N. // No large arrays are allocated: each thread calculates its own x_i. // // reduction(+:sum) creates private partial sums and safely combines them. // schedule(static,chunk_size) spreads useful work among threads even when // a threshold discards a contiguous portion of the iteration range. // // Change the settings below. Optional teaching demonstrations are OFF. // Reported speedups depend on the CPU, compiler, and other system activity. #include #include #include #include #include #include #include #include // ---- Editable example settings ---- const int n_terms = 50000000; const int repetitions = 5; const int maximum_threads = 4; const int chunk_size = 4096; const double x_cut = 0.5; const bool show_schedule_demo = false; const bool show_race_demo = false; // These routines can be reused with a different N or cutoff. double serial_sum(int n, double cut) { const double h = 1.0 / static_cast(n); double sum = 0.0; for (int i = 1; i <= n; ++i) { const double x = static_cast(i) * h; if (x > cut) { const double term = std::sin(x) + std::sqrt(x); sum += term; } } return sum; } double omp_sum(int n, double cut, int threads) { const double h = 1.0 / static_cast(n); double sum = 0.0; // Round-robin chunks: threads share the costly part after x_cut. #pragma omp parallel for schedule(static,chunk_size) reduction(+:sum) num_threads(threads) for (int i = 1; i <= n; ++i) { const double x = static_cast(i) * h; if (x > cut) { const double term = std::sin(x) + std::sqrt(x); sum += term; } } return sum; } double contiguous_sum(int n, double cut, int threads) { const double h = 1.0 / static_cast(n); double sum = 0.0; // Optional contrast: contiguous chunks have very unequal useful work. #pragma omp parallel for schedule(static) reduction(+:sum) num_threads(threads) for (int i = 1; i <= n; ++i) { const double x = static_cast(i) * h; if (x > cut) { const double term = std::sin(x) + std::sqrt(x); sum += term; } } return sum; } // IMPORTANT: This function intentionally contains a C++ data race. // It is undefined behavior. Run only as an optional teaching demonstration. double unsafe_sum(int n, double cut, int threads) { const double h = 1.0 / static_cast(n); double sum = 0.0; #pragma omp parallel for schedule(static,chunk_size) num_threads(threads) for (int i = 1; i <= n; ++i) { const double x = static_cast(i) * h; if (x > cut) { const double term = std::sin(x) + std::sqrt(x); sum += term; // WRONG: updates can overlap or be lost. } } return sum; } double atomic_sum(int n, double cut, int threads) { const double h = 1.0 / static_cast(n); double sum = 0.0; #pragma omp parallel for schedule(static,chunk_size) num_threads(threads) for (int i = 1; i <= n; ++i) { const double x = static_cast(i) * h; if (x > cut) { const double term = std::sin(x) + std::sqrt(x); #pragma omp atomic sum += term; // Correct, but each shared addition is synchronized. } } return sum; } double median(std::vector values) { std::sort(values.begin(), values.end()); const std::size_t count = values.size(); if (count % 2 == 1) return values[count / 2]; return 0.5 * (values[count / 2 - 1] + values[count / 2]); } int actual_team_size(int requested) { int actual = 1; #pragma omp parallel num_threads(requested) { #pragma omp single actual = omp_get_num_threads(); } return actual; } int main() { if (n_terms < 1 || repetitions < 1 || maximum_threads < 1 || chunk_size < 1) { std::cerr << "Error: N, repetitions, maximum_threads, and chunk_size must be positive.\n"; return EXIT_FAILURE; } if (!std::isfinite(x_cut) || x_cut < 0.0 || x_cut >= 1.0) { std::cerr << "Error: x_cut must satisfy 0 <= x_cut < 1.\n"; return EXIT_FAILURE; } omp_set_dynamic(0); // Request the chosen thread counts, if permitted. const int available = omp_get_num_procs(); // May include logical CPUs. const int max_p = std::min(maximum_threads, available); const double h = 1.0 / static_cast(n_terms); const double exact = std::cos(x_cut) - std::cos(1.0) + (2.0 / 3.0) * (1.0 - std::pow(x_cut, 1.5)); std::cout << "Chapter 15: first steps with OpenMP reductions (C++)\n" << "Number of terms N: " << n_terms << '\n' << "Threshold x_cut: " << x_cut << '\n' << "Timing repetitions: " << repetitions << '\n' << "OpenMP available processors (may include logical CPUs): " << available << '\n' << "Maximum threads requested: " << maximum_threads << '\n' << "Testing up to this many threads: " << max_p << '\n' << "Round-robin static chunk size: " << chunk_size << '\n' << "Indices are generated inside the loop (no stored array).\n"; // Untimed warm-ups, then repeated wall-clock measurements. double reference = serial_sum(n_terms, x_cut); double parallel_value = omp_sum(n_terms, x_cut, 1); std::vector times; times.reserve(repetitions); for (int r = 0; r < repetitions; ++r) { const double start = omp_get_wtime(); reference = serial_sum(n_terms, x_cut); times.push_back(omp_get_wtime() - start); } const double serial_median = median(times); std::cout << std::scientific << std::setprecision(15) << "Serial sum S: " << reference << '\n' << "Integral h*S: " << h * reference << '\n' << "Exact integral: " << exact << '\n' << "Quadrature error: " << std::fabs(h * reference - exact) << '\n'; // Leading signed right-endpoint error if x_cut is exactly on the grid. const double grid_cut = static_cast(n_terms) * x_cut; if (std::fabs(grid_cut - std::round(grid_cut)) <= 1.0e-9) { const double leading_error = 0.5 * h * (std::sin(1.0) + 1.0 - std::sin(x_cut) - std::sqrt(x_cut)); std::cout << "Leading right-rule error (signed): " << leading_error << '\n'; } else { std::cout << "Cutoff is between grid points; a partial cell also affects the error.\n"; } std::cout << std::fixed << std::setprecision(5) << "Serial median time: " << serial_median << " seconds\n\n" << " Threads Actual Relative sum difference Median (s) Speedup\n"; std::vector chunked_medians(max_p + 1, 0.0); for (int p = 1; p <= max_p; ++p) { const int actual = actual_team_size(p); parallel_value = omp_sum(n_terms, x_cut, p); // Untimed warm-up. times.clear(); for (int r = 0; r < repetitions; ++r) { const double start = omp_get_wtime(); parallel_value = omp_sum(n_terms, x_cut, p); times.push_back(omp_get_wtime() - start); } const double t = median(times); chunked_medians[p] = t; const double difference = std::fabs(parallel_value - reference) / std::max(std::numeric_limits::min(), std::fabs(reference)); std::cout << std::setw(8) << p << " " << std::setw(6) << actual << " " << std::scientific << std::setprecision(4) << std::setw(12) << difference << " " << std::fixed << std::setprecision(5) << std::setw(9) << t << " " << std::setprecision(3) << std::setw(8) << serial_median / t << '\n'; if (difference > 1.0e-10) { std::cout << "WARNING: parallel and serial sums differ more than expected.\n"; } } std::cout << "\nSpeedup compares with the optimized serial routine.\n" << "Overhead, imbalance, thermal limits, and other activity affect timing.\n" << "A measured speedup above the available core count may be noise.\n" << "Parallel sums can differ slightly because floating-point addition\n" << "depends on the order of partial sums.\n"; if (show_schedule_demo) { std::cout << "\nOPTIONAL: contiguous versus chunked scheduling\n"; if (max_p < 2) { std::cout << "Need at least two available threads.\n"; } else { parallel_value = contiguous_sum(n_terms, x_cut, max_p); // Warm-up. times.clear(); for (int r = 0; r < repetitions; ++r) { const double start = omp_get_wtime(); parallel_value = contiguous_sum(n_terms, x_cut, max_p); times.push_back(omp_get_wtime() - start); } const double difference = std::fabs(parallel_value - reference) / std::max(std::numeric_limits::min(), std::fabs(reference)); std::cout << "Requested threads: " << max_p << '\n' << "Contiguous schedule(static) median (s): " << median(times) << '\n' << "Chunked schedule(static,chunk_size) median (s): " << chunked_medians[max_p] << '\n' << "Contiguous sum relative difference: " << std::scientific << difference << std::fixed << '\n' << "Equal iteration counts need not mean equal useful work.\n"; } } if (show_race_demo) { std::cout << "\nOPTIONAL: unsafe shared sum versus atomic accumulation\n"; if (max_p < 2) { std::cout << "Need at least two available threads.\n"; } else { const int n_demo = std::min(n_terms, 200000); std::cout << "Terms: " << n_demo << ", threads requested: " << max_p << '\n' << std::scientific << std::setprecision(15) << "Serial reference: " << serial_sum(n_demo, x_cut) << '\n'; for (int r = 1; r <= 3; ++r) { const double bad = unsafe_sum(n_demo, x_cut, max_p); const double safe = atomic_sum(n_demo, x_cut, max_p); std::cout << "Run " << r << ": UNSAFE = " << bad << " atomic = " << safe << '\n'; } std::cout << "UNSAFE has a C++ data race and undefined behavior; even a\n" << "correct-looking result proves nothing. Atomic protects each\n" << "addition but can be slow; its last digits can vary by run.\n"; } } return EXIT_SUCCESS; }