Line data Source code
1 : /**
2 : * @file linear_solver_bicgstab_omp.c
3 : * @brief BiCGSTAB solver - OpenMP parallelized implementation
4 : *
5 : * Same algorithm as scalar BiCGSTAB (van der Vorst, 1992) but with the vector
6 : * primitives (dot products, axpy, Laplacian, and the per-iteration vector
7 : * updates) parallelized across OpenMP threads. The high-level solve loop and
8 : * all breakdown checks are identical to the scalar reference — only the
9 : * primitives differ, per the algorithm/primitive separation rule.
10 : *
11 : * Each interior element is computed independently and identically regardless of
12 : * thread count; only the dot-product reductions accumulate in a different order,
13 : * so OMP results agree with scalar to within reduction rounding.
14 : */
15 :
16 : #include "../linear_solver_internal.h"
17 :
18 : #include "cfd/core/indexing.h"
19 : #include "cfd/core/logging.h"
20 : #include "cfd/core/memory.h"
21 :
22 : #include <math.h>
23 :
24 : #ifdef CFD_ENABLE_OPENMP
25 :
26 : #include <omp.h>
27 :
28 : #include "linear_solver_primitives_omp.h"
29 :
30 : /* ============================================================================
31 : * BICGSTAB CONTEXT
32 : * ============================================================================ */
33 :
34 : typedef struct {
35 : double dx2; /* dx^2 */
36 : double dy2; /* dy^2 */
37 : double inv_dz2; /* 1/dz^2 (0 for 2D) */
38 :
39 : size_t stride_z; /* nx*ny for 3D, 0 for 2D */
40 : size_t k_start; /* first interior k index */
41 : size_t k_end; /* one-past-last interior k index */
42 :
43 : /* BiCGSTAB working vectors (allocated during init) */
44 : double* r; /* Residual vector */
45 : double* r_hat; /* Shadow residual (typically r_0) */
46 : double* p; /* Search direction */
47 : double* v; /* A * p */
48 : double* s; /* Intermediate residual */
49 : double* t; /* A * s */
50 :
51 : int initialized;
52 : } bicgstab_omp_context_t;
53 :
54 : /* ============================================================================
55 : * OMP-PARALLELIZED PRIMITIVES
56 : *
57 : * dot_product_omp, axpy_omp, apply_laplacian_omp, compute_residual_omp and
58 : * copy_vector_omp come from linear_solver_primitives_omp.h (shared with CG and
59 : * GMRES OMP).
60 : * ============================================================================ */
61 :
62 : /* v = 0 (interior points only) */
63 12 : static void zero_vector_omp(double* v, size_t nx, size_t ny,
64 : size_t k_start, size_t k_end, size_t stride_z) {
65 12 : int ny_int = poisson_solver_size_to_int(ny);
66 12 : int nx_int = poisson_solver_size_to_int(nx);
67 :
68 24 : for (size_t k = k_start; k < k_end; k++) {
69 12 : int j;
70 12 : #pragma omp parallel for schedule(static)
71 : for (j = 1; j < ny_int - 1; j++) {
72 : for (int i = 1; i < nx_int - 1; i++) {
73 : size_t idx = k * stride_z + IDX_2D((size_t)i, (size_t)j, nx);
74 : v[idx] = 0.0;
75 : }
76 : }
77 : }
78 12 : }
79 :
80 : /*
81 : * Fused per-iteration vector updates. Each preserves the scalar reference's
82 : * exact per-element floating-point operation order (only the dot-product
83 : * reductions differ across threads), so OMP and scalar agree tightly.
84 : */
85 :
86 : /* p = r + beta * (p - omega * v) */
87 138 : static void update_p_omp(double* p, const double* r, const double* v,
88 : double beta, double omega,
89 : size_t nx, size_t ny,
90 : size_t k_start, size_t k_end, size_t stride_z) {
91 138 : int ny_int = poisson_solver_size_to_int(ny);
92 138 : int nx_int = poisson_solver_size_to_int(nx);
93 :
94 276 : for (size_t k = k_start; k < k_end; k++) {
95 138 : int j;
96 138 : #pragma omp parallel for schedule(static)
97 : for (j = 1; j < ny_int - 1; j++) {
98 : for (int i = 1; i < nx_int - 1; i++) {
99 : size_t idx = k * stride_z + IDX_2D((size_t)i, (size_t)j, nx);
100 : p[idx] = r[idx] + beta * (p[idx] - omega * v[idx]);
101 : }
102 : }
103 : }
104 138 : }
105 :
106 : /* s = r - alpha * v */
107 138 : static void update_s_omp(double* s, const double* r, const double* v,
108 : double alpha,
109 : size_t nx, size_t ny,
110 : size_t k_start, size_t k_end, size_t stride_z) {
111 138 : int ny_int = poisson_solver_size_to_int(ny);
112 138 : int nx_int = poisson_solver_size_to_int(nx);
113 :
114 276 : for (size_t k = k_start; k < k_end; k++) {
115 138 : int j;
116 138 : #pragma omp parallel for schedule(static)
117 : for (j = 1; j < ny_int - 1; j++) {
118 : for (int i = 1; i < nx_int - 1; i++) {
119 : size_t idx = k * stride_z + IDX_2D((size_t)i, (size_t)j, nx);
120 : s[idx] = r[idx] - alpha * v[idx];
121 : }
122 : }
123 : }
124 138 : }
125 :
126 : /* x = x + alpha * p + omega * s */
127 136 : static void update_x_omp(double* x, const double* p, const double* s,
128 : double alpha, double omega,
129 : size_t nx, size_t ny,
130 : size_t k_start, size_t k_end, size_t stride_z) {
131 136 : int ny_int = poisson_solver_size_to_int(ny);
132 136 : int nx_int = poisson_solver_size_to_int(nx);
133 :
134 272 : for (size_t k = k_start; k < k_end; k++) {
135 136 : int j;
136 136 : #pragma omp parallel for schedule(static)
137 : for (j = 1; j < ny_int - 1; j++) {
138 : for (int i = 1; i < nx_int - 1; i++) {
139 : size_t idx = k * stride_z + IDX_2D((size_t)i, (size_t)j, nx);
140 : x[idx] += alpha * p[idx] + omega * s[idx];
141 : }
142 : }
143 : }
144 136 : }
145 :
146 : /* r = s - omega * t */
147 136 : static void update_r_omp(double* r, const double* s, const double* t,
148 : double omega,
149 : size_t nx, size_t ny,
150 : size_t k_start, size_t k_end, size_t stride_z) {
151 136 : int ny_int = poisson_solver_size_to_int(ny);
152 136 : int nx_int = poisson_solver_size_to_int(nx);
153 :
154 272 : for (size_t k = k_start; k < k_end; k++) {
155 136 : int j;
156 136 : #pragma omp parallel for schedule(static)
157 : for (j = 1; j < ny_int - 1; j++) {
158 : for (int i = 1; i < nx_int - 1; i++) {
159 : size_t idx = k * stride_z + IDX_2D((size_t)i, (size_t)j, nx);
160 : r[idx] = s[idx] - omega * t[idx];
161 : }
162 : }
163 : }
164 136 : }
165 :
166 : /* ============================================================================
167 : * BICGSTAB OMP IMPLEMENTATION
168 : * ============================================================================ */
169 :
170 10 : static cfd_status_t bicgstab_omp_init(
171 : poisson_solver_t* solver,
172 : size_t nx, size_t ny, size_t nz,
173 : double dx, double dy, double dz,
174 : const poisson_solver_params_t* params)
175 : {
176 10 : (void)params;
177 :
178 : /* The shared primitives loop over int bounds, which collapse to empty loops
179 : * for oversized dimensions; reject those grids before allocating. */
180 10 : size_t n = 0;
181 10 : cfd_status_t size_status = poisson_solver_validate_grid_size(nx, ny, nz, 1, &n);
182 10 : if (size_status != CFD_SUCCESS) {
183 : return size_status;
184 : }
185 :
186 7 : bicgstab_omp_context_t* ctx = (bicgstab_omp_context_t*)cfd_calloc(1, sizeof(bicgstab_omp_context_t));
187 7 : if (!ctx) {
188 : return CFD_ERROR_NOMEM;
189 : }
190 :
191 7 : ctx->dx2 = dx * dx;
192 7 : ctx->dy2 = dy * dy;
193 7 : ctx->inv_dz2 = poisson_solver_compute_inv_dz2(dz);
194 7 : poisson_solver_compute_3d_bounds(nz, nx, ny, &ctx->stride_z, &ctx->k_start, &ctx->k_end);
195 :
196 : /* Allocate working vectors */
197 7 : ctx->r = (double*)cfd_calloc(n, sizeof(double));
198 7 : ctx->r_hat = (double*)cfd_calloc(n, sizeof(double));
199 7 : ctx->p = (double*)cfd_calloc(n, sizeof(double));
200 7 : ctx->v = (double*)cfd_calloc(n, sizeof(double));
201 7 : ctx->s = (double*)cfd_calloc(n, sizeof(double));
202 7 : ctx->t = (double*)cfd_calloc(n, sizeof(double));
203 :
204 7 : if (!ctx->r || !ctx->r_hat || !ctx->p || !ctx->v || !ctx->s || !ctx->t) {
205 0 : cfd_free(ctx->r);
206 0 : cfd_free(ctx->r_hat);
207 0 : cfd_free(ctx->p);
208 0 : cfd_free(ctx->v);
209 0 : cfd_free(ctx->s);
210 0 : cfd_free(ctx->t);
211 0 : cfd_free(ctx);
212 0 : return CFD_ERROR_NOMEM;
213 : }
214 :
215 7 : ctx->initialized = 1;
216 7 : solver->context = ctx;
217 7 : return CFD_SUCCESS;
218 : }
219 :
220 13 : static void bicgstab_omp_destroy(poisson_solver_t* solver) {
221 13 : if (solver && solver->context) {
222 7 : bicgstab_omp_context_t* ctx = (bicgstab_omp_context_t*)solver->context;
223 7 : cfd_free(ctx->r);
224 7 : cfd_free(ctx->r_hat);
225 7 : cfd_free(ctx->p);
226 7 : cfd_free(ctx->v);
227 7 : cfd_free(ctx->s);
228 7 : cfd_free(ctx->t);
229 7 : cfd_free(ctx);
230 7 : solver->context = NULL;
231 : }
232 13 : }
233 :
234 : /*
235 : * BiCGSTAB solve loop — structurally identical to the scalar reference. It uses
236 : * its own solve function because it maintains complex state across iterations
237 : * (rho, omega, alpha), has two convergence checks per iteration, and requires
238 : * two matrix-vector products per iteration.
239 : */
240 6 : static cfd_status_t bicgstab_omp_solve(
241 : poisson_solver_t* solver,
242 : double* x,
243 : double* x_temp,
244 : const double* rhs,
245 : poisson_solver_stats_t* stats)
246 : {
247 6 : (void)x_temp; /* BiCGSTAB doesn't use the temp buffer */
248 :
249 6 : bicgstab_omp_context_t* ctx = (bicgstab_omp_context_t*)solver->context;
250 6 : size_t nx = solver->nx;
251 6 : size_t ny = solver->ny;
252 6 : double dx2 = ctx->dx2;
253 6 : double dy2 = ctx->dy2;
254 6 : double inv_dz2 = ctx->inv_dz2;
255 6 : size_t stride_z = ctx->stride_z;
256 6 : size_t k_start = ctx->k_start;
257 6 : size_t k_end = ctx->k_end;
258 :
259 6 : double* r = ctx->r;
260 6 : double* r_hat = ctx->r_hat;
261 6 : double* p = ctx->p;
262 6 : double* v = ctx->v;
263 6 : double* s = ctx->s;
264 6 : double* t = ctx->t;
265 :
266 6 : poisson_solver_params_t* params = &solver->params;
267 6 : double start_time = poisson_solver_get_time_ms();
268 :
269 : /* Not poisson_solver_apply_bc: the initial residual has to see the same walls
270 : * the iteration below inverts. See poisson_solver_krylov_apply_bc. */
271 6 : poisson_solver_krylov_apply_bc(solver, x);
272 :
273 : /* Compute initial residual: r_0 = b - A*x_0 */
274 6 : compute_residual_omp(x, rhs, r, nx, ny, dx2, dy2, inv_dz2, k_start, k_end, stride_z);
275 :
276 : /* r_hat = r_0 (shadow residual) */
277 6 : copy_vector_omp(r, r_hat, nx, ny, k_start, k_end, stride_z);
278 :
279 : /* Initialize: rho = alpha = omega = 1, v = p = 0 */
280 6 : double rho = 1.0;
281 6 : double alpha = 1.0;
282 6 : double omega = 1.0;
283 6 : zero_vector_omp(v, nx, ny, k_start, k_end, stride_z);
284 6 : zero_vector_omp(p, nx, ny, k_start, k_end, stride_z);
285 :
286 : /* Compute initial residual norm */
287 6 : double r_dot_r = dot_product_omp(r, r, nx, ny, k_start, k_end, stride_z);
288 6 : double initial_res = sqrt(r_dot_r);
289 :
290 6 : if (stats) {
291 6 : stats->initial_residual = initial_res;
292 : }
293 :
294 : /* Check if already converged */
295 : /* Never below the round-off floor of the residual at the initial guess:
296 : * a warm start near steady state begins there (poisson_solver_residual_floor) */
297 6 : double floor_res = poisson_solver_residual_floor(solver, x, POISSON_NORM_L2);
298 6 : double tolerance = poisson_solver_stop_target(params, initial_res, floor_res);
299 :
300 11 : if (initial_res < poisson_solver_done_target(params, floor_res)) {
301 1 : if (stats) {
302 1 : stats->status = POISSON_CONVERGED;
303 1 : stats->iterations = 0;
304 1 : stats->final_residual = initial_res;
305 1 : stats->elapsed_time_ms = poisson_solver_get_time_ms() - start_time;
306 : }
307 1 : return CFD_SUCCESS;
308 : }
309 :
310 138 : int converged = 0;
311 : int iter;
312 : double res_norm = initial_res;
313 :
314 138 : for (iter = 0; iter < params->max_iterations; iter++) {
315 : /* rho_new = (r_hat, r) */
316 138 : double rho_new = dot_product_omp(r_hat, r, nx, ny, k_start, k_end, stride_z);
317 :
318 : /* Check for breakdown */
319 138 : if (fabs(rho_new) < BICGSTAB_BREAKDOWN_THRESHOLD) {
320 0 : if (stats) {
321 0 : stats->status = POISSON_STAGNATED;
322 0 : stats->iterations = iter + 1;
323 0 : stats->final_residual = res_norm;
324 0 : stats->elapsed_time_ms = poisson_solver_get_time_ms() - start_time;
325 : }
326 0 : return CFD_ERROR_MAX_ITER;
327 : }
328 :
329 : /* beta = (rho_new / rho) * (alpha / omega) */
330 138 : double beta = (rho_new / rho) * (alpha / omega);
331 :
332 : /* p = r + beta * (p - omega * v) */
333 138 : update_p_omp(p, r, v, beta, omega, nx, ny, k_start, k_end, stride_z);
334 :
335 : /* v = A * p */
336 : /* Homogeneous boundary condition on the direction: this is what makes the
337 : * apply below the operator the walls describe, and the direction is rebuilt
338 : * from interior-only updates, so it is stale otherwise. */
339 138 : poisson_solver_krylov_apply_bc_homogeneous(solver, p);
340 138 : apply_laplacian_omp(p, v, nx, ny, dx2, dy2, inv_dz2, k_start, k_end, stride_z);
341 :
342 : /* alpha = rho_new / (r_hat, v) */
343 138 : double r_hat_dot_v = dot_product_omp(r_hat, v, nx, ny, k_start, k_end, stride_z);
344 :
345 : /* Check for breakdown */
346 138 : if (fabs(r_hat_dot_v) < BICGSTAB_BREAKDOWN_THRESHOLD) {
347 0 : if (stats) {
348 0 : stats->status = POISSON_STAGNATED;
349 0 : stats->iterations = iter + 1;
350 0 : stats->final_residual = res_norm;
351 0 : stats->elapsed_time_ms = poisson_solver_get_time_ms() - start_time;
352 : }
353 0 : return CFD_ERROR_MAX_ITER;
354 : }
355 :
356 138 : alpha = rho_new / r_hat_dot_v;
357 :
358 : /* s = r - alpha * v */
359 138 : update_s_omp(s, r, v, alpha, nx, ny, k_start, k_end, stride_z);
360 :
361 : /* Check for early convergence on s */
362 138 : double s_norm = sqrt(dot_product_omp(s, s, nx, ny, k_start, k_end, stride_z));
363 138 : if (s_norm < tolerance || s_norm < params->absolute_tolerance) {
364 : /* Update x and return */
365 2 : axpy_omp(alpha, p, x, nx, ny, k_start, k_end, stride_z);
366 2 : res_norm = s_norm;
367 2 : converged = 1;
368 2 : break;
369 : }
370 :
371 : /* t = A * s */
372 136 : poisson_solver_krylov_apply_bc_homogeneous(solver, s);
373 136 : apply_laplacian_omp(s, t, nx, ny, dx2, dy2, inv_dz2, k_start, k_end, stride_z);
374 :
375 : /* omega = (t, s) / (t, t) */
376 136 : double t_dot_s = dot_product_omp(t, s, nx, ny, k_start, k_end, stride_z);
377 136 : double t_dot_t = dot_product_omp(t, t, nx, ny, k_start, k_end, stride_z);
378 :
379 : /* Check for breakdown */
380 136 : if (fabs(t_dot_t) < BICGSTAB_BREAKDOWN_THRESHOLD) {
381 : /* Update x with available progress */
382 0 : axpy_omp(alpha, p, x, nx, ny, k_start, k_end, stride_z);
383 0 : if (stats) {
384 0 : stats->status = POISSON_STAGNATED;
385 0 : stats->iterations = iter + 1;
386 0 : stats->final_residual = s_norm;
387 0 : stats->elapsed_time_ms = poisson_solver_get_time_ms() - start_time;
388 : }
389 0 : return CFD_ERROR_MAX_ITER;
390 : }
391 :
392 136 : omega = t_dot_s / t_dot_t;
393 :
394 : /* x = x + alpha * p + omega * s */
395 136 : update_x_omp(x, p, s, alpha, omega, nx, ny, k_start, k_end, stride_z);
396 :
397 : /* r = s - omega * t */
398 136 : update_r_omp(r, s, t, omega, nx, ny, k_start, k_end, stride_z);
399 :
400 : /* Update rho for next iteration */
401 136 : rho = rho_new;
402 :
403 : /* Compute residual norm */
404 136 : res_norm = sqrt(dot_product_omp(r, r, nx, ny, k_start, k_end, stride_z));
405 :
406 : /* Check convergence at intervals */
407 136 : if (iter % params->check_interval == 0) {
408 136 : if (params->verbose) {
409 0 : CFD_LOG_DEBUG("poisson", "BiCGSTAB-OMP Iter %d: residual = %.6e", iter, res_norm);
410 : }
411 :
412 136 : if (res_norm < tolerance || res_norm < params->absolute_tolerance) {
413 : converged = 1;
414 : break;
415 : }
416 : }
417 :
418 : /* Check for omega breakdown (would cause division by zero next iteration) */
419 133 : if (fabs(omega) < BICGSTAB_BREAKDOWN_THRESHOLD) {
420 0 : if (stats) {
421 0 : stats->status = POISSON_STAGNATED;
422 0 : stats->iterations = iter + 1;
423 0 : stats->final_residual = res_norm;
424 0 : stats->elapsed_time_ms = poisson_solver_get_time_ms() - start_time;
425 : }
426 0 : return CFD_ERROR_MAX_ITER;
427 : }
428 : }
429 :
430 : /* Final convergence check */
431 5 : if (!converged && (res_norm < tolerance || res_norm < params->absolute_tolerance)) {
432 3 : converged = 1;
433 : }
434 :
435 : /* Apply final boundary conditions */
436 5 : poisson_solver_apply_bc(solver, x);
437 :
438 5 : double end_time = poisson_solver_get_time_ms();
439 :
440 5 : if (stats) {
441 5 : stats->iterations = (iter < params->max_iterations) ? (iter + 1) : iter;
442 5 : stats->final_residual = res_norm;
443 5 : stats->elapsed_time_ms = end_time - start_time;
444 5 : stats->status = converged ? POISSON_CONVERGED : POISSON_MAX_ITER;
445 : }
446 :
447 5 : return converged ? CFD_SUCCESS : CFD_ERROR_MAX_ITER;
448 : }
449 :
450 : /*
451 : * Single iteration is not well-defined for BiCGSTAB (it maintains internal
452 : * state). Provide a minimal implementation that returns the current residual.
453 : */
454 0 : static cfd_status_t bicgstab_omp_iterate(
455 : poisson_solver_t* solver,
456 : double* x,
457 : double* x_temp,
458 : const double* rhs,
459 : double* residual)
460 : {
461 0 : (void)x_temp;
462 :
463 0 : if (residual) {
464 0 : *residual = poisson_solver_compute_residual(solver, x, rhs);
465 : }
466 0 : return CFD_SUCCESS;
467 : }
468 :
469 : /* ============================================================================
470 : * FACTORY FUNCTION
471 : * ============================================================================ */
472 :
473 13 : poisson_solver_t* create_bicgstab_omp_solver(void) {
474 13 : poisson_solver_t* solver = (poisson_solver_t*)cfd_calloc(1, sizeof(poisson_solver_t));
475 13 : if (!solver) {
476 : return NULL;
477 : }
478 :
479 13 : solver->name = POISSON_SOLVER_TYPE_BICGSTAB_OMP;
480 13 : solver->description = "BiCGSTAB (OpenMP)";
481 13 : solver->method = POISSON_METHOD_BICGSTAB;
482 13 : solver->backend = POISSON_BACKEND_OMP;
483 13 : solver->params = poisson_solver_params_default();
484 :
485 13 : solver->init = bicgstab_omp_init;
486 13 : solver->destroy = bicgstab_omp_destroy;
487 13 : solver->solve = bicgstab_omp_solve; /* BiCGSTAB uses custom solve loop */
488 13 : solver->iterate = bicgstab_omp_iterate;
489 13 : solver->apply_bc = NULL; /* Use default Neumann */
490 :
491 13 : return solver;
492 : }
493 :
494 : #endif /* CFD_ENABLE_OPENMP */
|