1use std::any::Any;
8use std::collections::BTreeMap;
9use std::sync::Arc;
10
11use crate::algebra::bridge::BridgeScratch;
12use crate::algebra::scalar::{KrystScalar, S};
13use crate::error::KError;
14use crate::matrix::csr::CsrMatrix as PlanCsrMatrix;
15use crate::matrix::dist::csr_types::{DistRowCsr, LocalSquareCsr};
16use crate::matrix::dist::halo::{HaloIndexPlan, HaloPlan, HaloTuning};
17use crate::matrix::dist::spmv_dist::RowRanges;
18use crate::matrix::op::{ChangeIds, DistLayout, LinOp, StructureId, ValuesId};
19use crate::matrix::parcsr::ParCsrMatrix;
20use crate::matrix::sparse::CsrMatrix;
21use crate::matrix::spmv::plan::{self as spmv_plan, SpmvKernel, SpmvPlan, SpmvTuning};
22use crate::ops::klinop::KLinOp;
23use crate::parallel::{Comm, UniverseComm};
24#[cfg(all(feature = "backend-faer", not(feature = "complex")))]
25use faer::Mat;
26
27fn owner_of(j: usize, row_part: &[usize]) -> usize {
28 let mut lo = 0usize;
30 let mut hi = row_part.len() - 2;
31 while lo <= hi {
32 let mid = (lo + hi) / 2;
33 if j < row_part[mid + 1] {
34 if j >= row_part[mid] {
35 return mid;
36 }
37 if mid == 0 {
38 break;
39 }
40 hi = mid - 1;
41 } else {
42 lo = mid + 1;
43 }
44 }
45 lo
46}
47
48fn self_idx(plan: &HaloIndexPlan, gcol: usize) -> usize {
49 plan.n_local
50 + *plan
51 .ghost_index_of
52 .get(&gcol)
53 .expect("ghost column missing from halo plan")
54}
55
56pub struct DistCsrOp {
62 pub n_global: usize,
63 pub row_start: usize,
64 pub row_end: usize,
65 pub n_local: usize,
66 layout: DistLayout,
67 row_ptr: Vec<usize>,
68 col_idx: Vec<usize>,
69 vals: Vec<S>,
70 row_is_local: Vec<bool>,
71 #[cfg_attr(feature = "rayon", allow(dead_code))]
72 local_only: RowRanges,
73 border: RowRanges,
74 border_ghost_row_ranges: Vec<Option<std::ops::Range<usize>>>,
75 border_ghost_col_unified: Vec<usize>,
76 border_ghost_vals: Vec<S>,
77 local_diag_plan: SpmvPlan<S>,
78 plan_diagnostics: DistributedPlanDiagnostics,
79 halo: HaloPlan,
80 overlap_mode: HaloOverlapMode,
81 ids: ChangeIds,
82}
83
84#[derive(Debug, Clone, Copy, PartialEq, Eq)]
85pub enum HaloOverlapMode {
86 Disabled,
87 Interior,
88}
89
90#[derive(Debug, Clone, Copy, PartialEq, Eq)]
91pub enum DistLocalKernelStrategy {
92 RowSplitScalar,
93 LocalDiagSpmvPlan,
94}
95
96#[derive(Debug, Clone)]
97pub struct DistributedPlanMetrics {
98 pub n_local_rows: usize,
99 pub local_nnz: usize,
100 pub local_diag_nnz: usize,
101 pub ghost_nnz: usize,
102 pub local_only_rows: usize,
103 pub border_rows: usize,
104 pub halo_recv_volume: usize,
105 pub halo_send_volume: usize,
106}
107
108#[derive(Debug, Clone)]
109pub struct DistributedPlanDiagnostics {
110 pub overlap_mode: HaloOverlapMode,
111 pub kernel_strategy: DistLocalKernelStrategy,
112 pub local_spmv_kernel: Option<SpmvKernel>,
113 pub row_locality_ratio: f64,
114 pub border_ratio: f64,
115 pub halo_recv_volume: usize,
116 pub halo_send_volume: usize,
117 pub expected_communication_fraction: f64,
118 pub expected_computation_fraction: f64,
119}
120
121pub fn choose_distributed_plan(
122 metrics: &DistributedPlanMetrics,
123 local_spmv_kernel: Option<SpmvKernel>,
124) -> DistributedPlanDiagnostics {
125 let n_rows = metrics.n_local_rows.max(1) as f64;
126 let row_locality_ratio = (metrics.local_only_rows as f64 / n_rows).clamp(0.0, 1.0);
127 let border_ratio = (metrics.border_rows as f64 / n_rows).clamp(0.0, 1.0);
128 let halo_volume = metrics.halo_recv_volume + metrics.halo_send_volume;
129 let halo_per_row = halo_volume as f64 / n_rows;
130 let ghost_pressure = metrics.ghost_nnz as f64 / metrics.local_nnz.max(1) as f64;
131 let communication_pressure =
132 (0.5 * border_ratio + 0.3 * ghost_pressure + 0.2 * (halo_per_row / 8.0)).clamp(0.0, 1.0);
133
134 let overlap_mode = if communication_pressure >= 0.28 {
135 HaloOverlapMode::Interior
136 } else {
137 HaloOverlapMode::Disabled
138 };
139
140 let kernel_strategy = match local_spmv_kernel {
141 Some(_) if row_locality_ratio >= 0.55 || communication_pressure < 0.25 => {
142 DistLocalKernelStrategy::LocalDiagSpmvPlan
143 }
144 _ => DistLocalKernelStrategy::RowSplitScalar,
145 };
146
147 let mut expected_communication_fraction =
148 (0.55 * border_ratio + 0.45 * ghost_pressure + (halo_per_row / 32.0)).clamp(0.0, 0.95);
149 if overlap_mode == HaloOverlapMode::Interior {
150 expected_communication_fraction *= 0.82;
151 }
152 let expected_computation_fraction = (1.0 - expected_communication_fraction).clamp(0.05, 1.0);
153
154 DistributedPlanDiagnostics {
155 overlap_mode,
156 kernel_strategy,
157 local_spmv_kernel,
158 row_locality_ratio,
159 border_ratio,
160 halo_recv_volume: metrics.halo_recv_volume,
161 halo_send_volume: metrics.halo_send_volume,
162 expected_communication_fraction,
163 expected_computation_fraction,
164 }
165}
166
167impl DistCsrOp {
168 pub fn partition_rows_balanced(n_global: usize, comm: &UniverseComm) -> Vec<usize> {
173 let p = comm.size();
174 assert!(p > 0, "number of partitions must be positive");
175 let base = n_global / p;
176 let rem = n_global % p;
177 let mut starts = Vec::with_capacity(p + 1);
178 let mut s = 0usize;
179 for k in 0..p {
180 starts.push(s);
181 s += base + usize::from(k < rem);
182 }
183 starts.push(n_global);
184 starts
185 }
186
187 pub fn from_local_rows(
188 n_global: usize,
189 row_start: usize,
190 local_rows: &CsrMatrix<S>,
191 part_prefix: &[usize],
192 comm: UniverseComm,
193 ) -> Result<Self, KError> {
194 Self::from_local_rows_with_halo_tuning(
195 n_global,
196 row_start,
197 local_rows,
198 part_prefix,
199 comm,
200 HaloTuning::default(),
201 )
202 }
203
204 pub fn from_local_rows_with_halo_tuning(
205 n_global: usize,
206 row_start: usize,
207 local_rows: &CsrMatrix<S>,
208 part_prefix: &[usize],
209 comm: UniverseComm,
210 halo_tuning: HaloTuning,
211 ) -> Result<Self, KError> {
212 if part_prefix.len() != comm.size() + 1 {
213 return Err(KError::InvalidInput(
214 "partition vector length must be size + 1".into(),
215 ));
216 }
217 let row_end = row_start + local_rows.nrows();
218 let n_local = local_rows.nrows();
219 let rank = comm.rank();
220
221 let row_ptr = local_rows.row_ptr().to_vec();
222 let col_idx = local_rows.col_idx().to_vec();
223 let vals = local_rows.values().to_vec();
224
225 let mut recv_map: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
226 let mut row_is_local = vec![true; n_local];
227 for i in 0..n_local {
228 for idx in row_ptr[i]..row_ptr[i + 1] {
229 let gcol = col_idx[idx];
230 let owner = owner_of(gcol, part_prefix);
231 if owner != rank {
232 row_is_local[i] = false;
233 recv_map.entry(owner).or_default().push(gcol);
234 }
235 }
236 }
237
238 let halo = HaloPlan::new_with_tuning(
239 comm.clone(),
240 Arc::new(part_prefix.to_vec()),
241 row_start,
242 row_end,
243 recv_map,
244 halo_tuning,
245 )?;
246
247 let local_only = RowRanges::from_mask(&row_is_local, true);
248 let border = RowRanges::from_mask(&row_is_local, false);
249
250 let mut border_ghost_row_ranges = vec![None; n_local];
251 let mut border_ghost_col_unified = Vec::new();
252 let mut border_ghost_vals = Vec::new();
253 let mut local_diag_row_ptr = Vec::with_capacity(n_local + 1);
254 let mut local_diag_col_idx = Vec::new();
255 let mut local_diag_vals = Vec::new();
256 local_diag_row_ptr.push(0);
257 let mut local_diag_nnz = 0usize;
258 let mut ghost_nnz = 0usize;
259 let mut local_only_rows = 0usize;
260 for i in 0..n_local {
261 let start = border_ghost_col_unified.len();
262 for idx in row_ptr[i]..row_ptr[i + 1] {
263 let gcol = col_idx[idx];
264 let owner = owner_of(gcol, halo.index.row_part.as_ref());
265 if owner == rank {
266 local_diag_col_idx.push(gcol - row_start);
267 local_diag_vals.push(vals[idx]);
268 local_diag_nnz += 1;
269 } else {
270 border_ghost_col_unified.push(self_idx(&halo.index, gcol));
271 border_ghost_vals.push(vals[idx]);
272 ghost_nnz += 1;
273 }
274 }
275 local_diag_row_ptr.push(local_diag_col_idx.len());
276 let end = border_ghost_col_unified.len();
277 if end > start {
278 border_ghost_row_ranges[i] = Some(start..end);
279 } else {
280 local_only_rows += 1;
281 }
282 }
283 let local_diag = PlanCsrMatrix::new(
284 n_local,
285 n_local,
286 local_diag_row_ptr,
287 local_diag_col_idx,
288 local_diag_vals,
289 );
290 let local_diag_plan = spmv_plan::build(&local_diag, &SpmvTuning::default());
291 let metrics = DistributedPlanMetrics {
292 n_local_rows: n_local,
293 local_nnz: vals.len(),
294 local_diag_nnz,
295 ghost_nnz,
296 local_only_rows,
297 border_rows: n_local.saturating_sub(local_only_rows),
298 halo_recv_volume: halo.recv_volume(),
299 halo_send_volume: halo.send_volume(),
300 };
301 let plan_diagnostics = choose_distributed_plan(&metrics, Some(local_diag_plan.kernel));
302
303 let ids = ChangeIds::default();
304 ids.bump_structure();
305 ids.bump_values();
306
307 let layout = DistLayout {
308 global_rows: n_global,
309 global_cols: n_global,
310 row_start,
311 row_end,
312 col_start: row_start,
313 col_end: row_end,
314 };
315
316 Ok(Self {
317 n_global,
318 row_start,
319 row_end,
320 n_local,
321 layout,
322 row_ptr,
323 col_idx,
324 vals,
325 row_is_local,
326 local_only,
327 border,
328 border_ghost_row_ranges,
329 border_ghost_col_unified,
330 border_ghost_vals,
331 local_diag_plan,
332 plan_diagnostics: plan_diagnostics.clone(),
333 halo,
334 overlap_mode: plan_diagnostics.overlap_mode,
335 ids,
336 })
337 }
338
339 pub fn set_halo_overlap_mode(&mut self, mode: HaloOverlapMode) {
340 self.overlap_mode = mode;
341 self.plan_diagnostics.overlap_mode = mode;
342 }
343
344 pub fn plan_diagnostics(&self) -> &DistributedPlanDiagnostics {
345 &self.plan_diagnostics
346 }
347
348 pub fn from_parcsr(par: &ParCsrMatrix) -> Result<Self, KError> {
352 let n_global = par.global_m;
353 let local_rows = par.canonical_local_rows_csr()?;
354 let part_prefix = Self::partition_rows_balanced(n_global, &par.comm);
355
356 Self::from_local_rows(
357 n_global,
358 par.row_start,
359 &local_rows,
360 &part_prefix,
361 par.comm.clone(),
362 )
363 }
364
365 pub fn update_numeric(&mut self, new_vals: &[S]) -> Result<(), KError> {
366 if new_vals.len() != self.vals.len() {
367 return Err(KError::InvalidInput(
368 "value array has incorrect length".into(),
369 ));
370 }
371 self.vals.copy_from_slice(new_vals);
372 let local = self.local_block_csr();
373 let local_diag = PlanCsrMatrix::new(
374 local.nrows(),
375 local.ncols(),
376 local.row_ptr().to_vec(),
377 local.col_idx().to_vec(),
378 local.values().to_vec(),
379 );
380 self.local_diag_plan = spmv_plan::build(&local_diag, &SpmvTuning::default());
381 for row in 0..self.n_local {
382 if let Some(range) = &self.border_ghost_row_ranges[row] {
383 let mut slot = range.start;
384 for idx in self.row_ptr[row]..self.row_ptr[row + 1] {
385 let owner = owner_of(self.col_idx[idx], self.halo.index.row_part.as_ref());
386 if owner != self.halo.index.rank {
387 self.border_ghost_vals[slot] = self.vals[idx];
388 slot += 1;
389 }
390 }
391 }
392 }
393 self.ids.bump_values();
394 Ok(())
395 }
396
397 pub fn local_matrix(&self) -> CsrMatrix<S> {
398 CsrMatrix::from_csr(
399 self.n_local,
400 self.n_global,
401 self.row_ptr.clone(),
402 self.col_idx.clone(),
403 self.vals.clone(),
404 )
405 }
406
407 pub fn local_rows_csr(&self) -> DistRowCsr<S> {
409 DistRowCsr::new(self.local_matrix(), self.row_start, self.n_global)
410 .expect("DistCsrOp::local_matrix shape invariant violated")
411 }
412
413 pub fn local_block_csr(&self) -> CsrMatrix<S> {
415 let n = self.n_local;
416 let mut row_ptr = Vec::with_capacity(n + 1);
417 let mut col_idx = Vec::new();
418 let mut vals = Vec::new();
419 row_ptr.push(0);
420 for row in 0..n {
421 for idx in self.row_ptr[row]..self.row_ptr[row + 1] {
422 let gcol = self.col_idx[idx];
423 if gcol >= self.row_start && gcol < self.row_end {
424 col_idx.push(gcol - self.row_start);
425 vals.push(self.vals[idx]);
426 }
427 }
428 row_ptr.push(col_idx.len());
429 }
430 CsrMatrix::from_csr(n, n, row_ptr, col_idx, vals)
431 }
432
433 pub fn local_square_block(&self) -> LocalSquareCsr<S> {
435 LocalSquareCsr::try_from(self.local_block_csr())
436 .expect("DistCsrOp local block must be square by construction")
437 }
438
439 #[cfg(all(feature = "backend-faer", not(feature = "complex")))]
440 pub fn local_block_dense(&self) -> Mat<f64> {
442 let n = self.n_local;
443 let mut local = Mat::zeros(n, n);
444 for row in 0..n {
445 for idx in self.row_ptr[row]..self.row_ptr[row + 1] {
446 let gcol = self.col_idx[idx];
447 if gcol >= self.row_start && gcol < self.row_end {
448 local[(row, gcol - self.row_start)] = self.vals[idx];
449 }
450 }
451 }
452 local
453 }
454
455 pub fn local_row_offset(&self) -> usize {
457 self.row_start
458 }
459
460 pub fn row_partition(&self) -> Arc<Vec<usize>> {
462 self.halo.index.row_part.clone()
463 }
464
465 pub fn halo_index(&self) -> Arc<HaloIndexPlan> {
467 self.halo.index.clone()
468 }
469
470 pub fn local_nrows(&self) -> usize {
472 self.n_local
473 }
474
475 fn spmv_local_only(&self, x: &[S], y: &mut [S]) {
476 if self.plan_diagnostics.kernel_strategy == DistLocalKernelStrategy::LocalDiagSpmvPlan {
477 self.local_diag_plan.apply_scaled(S::one(), x, S::zero(), y);
478 return;
479 }
480 #[cfg(feature = "rayon")]
481 {
482 use rayon::prelude::*;
483 y.par_iter_mut()
484 .enumerate()
485 .filter(|(row, _)| self.row_is_local[*row])
486 .for_each(|(row, slot)| {
487 let mut acc = S::zero();
488 for idx in self.row_ptr[row]..self.row_ptr[row + 1] {
489 let col = self.col_idx[idx] - self.row_start;
490 acc = acc + self.vals[idx] * x[col];
491 }
492 *slot = acc;
493 });
494 }
495 #[cfg(not(feature = "rayon"))]
496 {
497 for span in &self.local_only.spans {
498 for row in span.clone() {
499 let mut acc = S::zero();
500 for idx in self.row_ptr[row]..self.row_ptr[row + 1] {
501 let col = self.col_idx[idx] - self.row_start;
502 acc = acc + self.vals[idx] * x[col];
503 }
504 y[row] = acc;
505 }
506 }
507 }
508 }
509
510 fn spmv_border(&self, y: &mut [S], ghost: &[S]) {
511 if self.border.is_empty() {
512 return;
513 }
514 #[cfg(feature = "rayon")]
515 {
516 use rayon::prelude::*;
517 y.par_iter_mut()
518 .enumerate()
519 .filter(|(row, _)| !self.row_is_local[*row])
520 .for_each(|(row, slot)| {
521 if let Some(range) = &self.border_ghost_row_ranges[row] {
522 let mut acc = S::zero();
523 for k in range.clone() {
524 let col = self.border_ghost_col_unified[k] - self.n_local;
525 let val = self.border_ghost_vals[k];
526 acc = acc + val * ghost[col];
527 }
528 *slot = *slot + acc;
529 }
530 });
531 }
532 #[cfg(not(feature = "rayon"))]
533 {
534 for span in &self.border.spans {
535 for row in span.clone() {
536 if let Some(range) = &self.border_ghost_row_ranges[row] {
537 let mut acc = S::zero();
538 for k in range.clone() {
539 let col = self.border_ghost_col_unified[k] - self.n_local;
540 let val = self.border_ghost_vals[k];
541 acc = acc + val * ghost[col];
542 }
543 y[row] = y[row] + acc;
544 }
545 }
546 }
547 }
548 }
549}
550
551impl KLinOp for DistCsrOp {
552 type Scalar = S;
553
554 fn dims(&self) -> (usize, usize) {
555 (self.n_local, self.n_local)
556 }
557
558 fn matvec_s(&self, x: &[S], y: &mut [S], _scratch: &mut BridgeScratch) {
559 assert_eq!(x.len(), self.n_local);
560 assert_eq!(y.len(), self.n_local);
561 for v in y.iter_mut() {
562 *v = S::zero();
563 }
564 match self.overlap_mode {
565 HaloOverlapMode::Disabled => {
566 let halo_req =
567 if self.halo.index.n_ghost > 0 || !self.halo.index.send_local_idx.is_empty() {
568 Some(self.halo.post_halo(x))
569 } else {
570 None
571 };
572 if let Some(req) = halo_req {
573 let ghost = self.halo.complete_halo(req);
574 self.spmv_local_only(x, y);
575 self.spmv_border(y, &ghost[..]);
576 } else {
577 self.spmv_local_only(x, y);
578 self.spmv_border(y, &[]);
579 }
580 }
581 HaloOverlapMode::Interior => {
582 let halo_req =
583 if self.halo.index.n_ghost > 0 || !self.halo.index.send_local_idx.is_empty() {
584 Some(self.halo.post_halo(x))
585 } else {
586 None
587 };
588
589 self.spmv_local_only(x, y);
590
591 if let Some(req) = halo_req {
592 let ghost = self.halo.complete_halo(req);
593 self.spmv_border(y, &ghost[..]);
594 } else {
595 self.spmv_border(y, &[]);
596 }
597 }
598 }
599 }
600}
601
602impl LinOp for DistCsrOp {
603 type S = S;
604
605 fn dims(&self) -> (usize, usize) {
606 (self.n_local, self.n_local)
607 }
608
609 fn matvec(&self, x: &[S], y: &mut [S]) {
610 let mut scratch = BridgeScratch::default();
611 self.matvec_s(x, y, &mut scratch);
612 }
613
614 fn try_matvec(&self, x: &[S], y: &mut [S]) -> Result<(), KError> {
615 if x.len() != self.n_local || y.len() != self.n_local {
616 return Err(KError::InvalidInput("dimension mismatch".into()));
617 }
618 self.matvec(x, y);
619 Ok(())
620 }
621
622 fn as_any(&self) -> &dyn Any {
623 self
624 }
625
626 fn structure_id(&self) -> StructureId {
627 self.ids.structure_id()
628 }
629
630 fn values_id(&self) -> ValuesId {
631 self.ids.values_id()
632 }
633
634 fn comm(&self) -> UniverseComm {
635 self.halo.index.comm.clone()
636 }
637
638 fn dist_layout(&self) -> Option<&DistLayout> {
639 Some(&self.layout)
640 }
641
642 fn format(&self) -> crate::matrix::format::OpFormat {
643 crate::matrix::format::OpFormat::Csr
644 }
645}
646
647#[cfg(test)]
648mod tests {
649 use super::*;
650
651 #[test]
652 fn planner_prefers_overlap_for_comm_heavy_metrics() {
653 let metrics = DistributedPlanMetrics {
654 n_local_rows: 4096,
655 local_nnz: 80_000,
656 local_diag_nnz: 30_000,
657 ghost_nnz: 50_000,
658 local_only_rows: 700,
659 border_rows: 3396,
660 halo_recv_volume: 12_000,
661 halo_send_volume: 10_000,
662 };
663 let diag = choose_distributed_plan(&metrics, Some(SpmvKernel::Scalar));
664 assert_eq!(diag.overlap_mode, HaloOverlapMode::Interior);
665 assert_eq!(
666 diag.kernel_strategy,
667 DistLocalKernelStrategy::RowSplitScalar
668 );
669 assert!(diag.expected_communication_fraction > diag.expected_computation_fraction);
670 }
671
672 #[test]
673 fn planner_prefers_local_diag_kernel_for_compute_heavy_metrics() {
674 let metrics = DistributedPlanMetrics {
675 n_local_rows: 4096,
676 local_nnz: 80_000,
677 local_diag_nnz: 76_000,
678 ghost_nnz: 4_000,
679 local_only_rows: 3600,
680 border_rows: 496,
681 halo_recv_volume: 500,
682 halo_send_volume: 600,
683 };
684 let diag = choose_distributed_plan(&metrics, Some(SpmvKernel::Scalar));
685 assert_eq!(diag.overlap_mode, HaloOverlapMode::Disabled);
686 assert_eq!(
687 diag.kernel_strategy,
688 DistLocalKernelStrategy::LocalDiagSpmvPlan
689 );
690 assert!(diag.expected_computation_fraction > diag.expected_communication_fraction);
691 }
692}