1#![allow(clippy::too_many_arguments, clippy::type_complexity)]
18
19use std::cmp::Ordering;
20use std::collections::BTreeMap;
21use std::collections::BinaryHeap;
22use std::sync::atomic::{AtomicU64, Ordering as AtomicOrdering};
23use std::sync::OnceLock;
24use std::time::Instant;
25
26use crate::bins::{self, flat_cell};
27use crate::cell::Cell;
28use crate::pairs::{self, pairs_within};
29use crate::Error;
30
31pub fn timer_resolution_ns() -> u64 {
37 static TICK: OnceLock<u64> = OnceLock::new();
38 *TICK.get_or_init(|| {
39 let mut samples = [1u64; 32];
40 for slot in &mut samples {
41 let start = Instant::now();
42 let mut next = Instant::now();
43 let mut spins = 0u32;
44 while next <= start && spins < 1_000_000 {
45 next = Instant::now();
46 spins += 1;
47 }
48 *slot = next.saturating_duration_since(start).as_nanos() as u64;
49 if *slot == 0 {
50 *slot = 1;
51 }
52 }
53 samples.sort_unstable();
54 samples[samples.len() / 2]
55 })
56}
57
58pub fn derived_balance(weight: &[u64], parts: u32) -> (u64, u64) {
68 let total: u64 = weight.iter().copied().sum();
69 if total == 0 || parts == 0 {
70 return (1, 1);
71 }
72 let w_max = weight.iter().copied().max().unwrap_or(0);
73 let extra = u64::from(parts).saturating_mul(w_max);
74 (total.saturating_add(extra), total)
75}
76
77pub fn derived_balance_f64(weight: &[u64], parts: u32) -> f64 {
79 let (num, den) = derived_balance(weight, parts);
80 if den == 0 {
81 1.0
82 } else {
83 num as f64 / den as f64
84 }
85}
86
87#[derive(Clone, Copy, Debug, Eq, PartialEq)]
89#[repr(u8)]
90pub enum Method {
91 Morton = 0,
93 Hilbert = 1,
95 Rcb = 2,
97 HilbertFm = 3,
99 RcbFm = 4,
101 Scotch = 5,
103 Multi = 6,
105 PtScotch = 7,
107}
108
109impl Method {
110 pub fn uses_curve(self) -> bool {
112 matches!(self, Method::Morton | Method::Hilbert | Method::HilbertFm)
113 }
114
115 pub fn refines(self) -> bool {
117 matches!(self, Method::HilbertFm | Method::RcbFm)
118 }
119
120 fn needs_edges(self) -> bool {
126 matches!(
127 self,
128 Method::HilbertFm | Method::RcbFm | Method::Scotch | Method::PtScotch | Method::Multi
129 )
130 }
131
132 fn from_code(code: u8) -> Result<Self, Error> {
133 match code {
134 0 => Ok(Method::Morton),
135 1 => Ok(Method::Hilbert),
136 2 => Ok(Method::Rcb),
137 3 => Ok(Method::HilbertFm),
138 4 => Ok(Method::RcbFm),
139 5 => Ok(Method::Scotch),
140 6 => Ok(Method::Multi),
141 7 => Ok(Method::PtScotch),
142 _ => Err(Error::BadPartition),
143 }
144 }
145}
146
147pub const DEFAULT_METHOD: Method = Method::RcbFm;
154
155#[derive(Clone, Copy, Debug, PartialEq)]
157pub struct PartRequest {
158 pub parts: u32,
160 pub method: Method,
162 pub balance: Option<f64>,
164 pub device: bool,
166}
167
168impl PartRequest {
169 pub fn new(parts: u32) -> Self {
171 Self {
172 parts,
173 method: DEFAULT_METHOD,
174 balance: None,
175 device: false,
176 }
177 }
178}
179
180#[derive(Clone, Debug, PartialEq)]
182pub struct CellGrid {
183 pub nx: i32,
185 pub ny: i32,
187 pub nz: i32,
189 pub bin_width: [f64; 3],
191 pub weight: Vec<u64>,
193}
194
195impl CellGrid {
196 pub fn ncell(&self) -> usize {
198 self.weight.len()
199 }
200}
201
202pub fn replicate_graph(graph: &CellGraph, copies: usize) -> Result<CellGraph, Error> {
208 if copies == 0 {
209 return Err(Error::BadGraph);
210 }
211 if copies == 1 {
212 return Ok(graph.clone());
213 }
214 let nx = graph.grid.nx;
215 let ny = graph.grid.ny;
216 let nz = graph.grid.nz;
217 if nx <= 0 || ny <= 0 || nz <= 0 {
218 return Err(Error::BadGraph);
219 }
220 let n = graph.grid.ncell();
221 let expect = (nx as usize)
222 .checked_mul(ny as usize)
223 .and_then(|v| v.checked_mul(nz as usize))
224 .ok_or(Error::BadGraph)?;
225 if expect != n || graph.offsets.len() != n + 1 {
226 return Err(Error::BadGraph);
227 }
228 let copies_i = i32::try_from(copies).map_err(|_| Error::BadGraph)?;
229 let big_nx = nx.checked_mul(copies_i).ok_or(Error::BadGraph)?;
230 let big_n = n.checked_mul(copies).ok_or(Error::BadGraph)?;
231 let nx_u = nx as usize;
232 let ny_u = ny as usize;
233 let big_nx_u = big_nx as usize;
234 let mut weight = vec![0u64; big_n];
235 for copy in 0..copies {
236 for iz in 0..nz as usize {
237 for iy in 0..ny_u {
238 for ix in 0..nx_u {
239 let src = ((iz * ny_u) + iy) * nx_u + ix;
240 let dst = ((iz * ny_u) + iy) * big_nx_u + copy * nx_u + ix;
241 weight[dst] = graph.grid.weight[src];
242 }
243 }
244 }
245 }
246 let mut neighbor = Vec::with_capacity(graph.neighbor.len().saturating_mul(copies));
247 let mut edge_weight = Vec::with_capacity(graph.edge_weight.len().saturating_mul(copies));
248 let mut offsets = vec![0u32; big_n + 1];
249 for dst in 0..big_n {
250 let plane = big_nx_u * ny_u;
251 let iz = dst / plane;
252 let rem = dst % plane;
253 let iy = rem / big_nx_u;
254 let ix_big = rem % big_nx_u;
255 let copy = ix_big / nx_u;
256 let ix = ix_big % nx_u;
257 let src = ((iz * ny_u) + iy) * nx_u + ix;
258 let lo = graph.offsets[src] as usize;
259 let hi = graph.offsets[src + 1] as usize;
260 for edge in lo..hi {
261 let nbr = graph.neighbor[edge] as usize;
262 if nbr >= n {
263 return Err(Error::BadGraph);
264 }
265 let nplane = nx_u * ny_u;
266 let niz = nbr / nplane;
267 let nrem = nbr % nplane;
268 let niy = nrem / nx_u;
269 let nix = nrem % nx_u;
270 let mapped = ((niz * ny_u) + niy) * big_nx_u + copy * nx_u + nix;
271 neighbor.push(mapped as u32);
272 edge_weight.push(graph.edge_weight[edge]);
273 }
274 offsets[dst + 1] = u32::try_from(neighbor.len()).map_err(|_| Error::BadGraph)?;
275 }
276 Ok(CellGraph {
277 grid: CellGrid {
278 nx: big_nx,
279 ny,
280 nz,
281 bin_width: graph.grid.bin_width,
282 weight,
283 },
284 offsets,
285 neighbor,
286 edge_weight,
287 })
288}
289
290#[derive(Clone, Debug, PartialEq)]
295pub struct CellGraph {
296 pub grid: CellGrid,
298 pub offsets: Vec<u32>,
300 pub neighbor: Vec<u32>,
302 pub edge_weight: Vec<u64>,
304}
305
306#[derive(Clone, Copy, Debug, PartialEq)]
308pub struct PartScore {
309 pub cut: u64,
311 pub imbalance: f64,
314 pub halo_fraction: f64,
317}
318
319pub fn halo_width(cutoff: f64, depth: u32, bin_width: [f64; 3]) -> Result<[u32; 3], Error> {
325 if !cutoff.is_finite() || cutoff < 0.0 {
326 return Err(Error::BadCutoff);
327 }
328 let length = cutoff * f64::from(depth);
329 if !length.is_finite() {
330 return Err(Error::BadCutoff);
331 }
332 let mut out = [0u32; 3];
333 for i in 0..3 {
334 out[i] = bins_needed(length, bin_width[i])?;
335 }
336 Ok(out)
337}
338
339pub fn halo(
345 grid: &CellGrid,
346 assign: &[u32],
347 domain: u32,
348 width: [u32; 3],
349) -> Result<Vec<u32>, Error> {
350 let n = check_assign(grid, assign)?;
351 let mut mark = vec![0u8; n];
352 let nx = grid.nx;
353 let ny = grid.ny;
354 let nz = grid.nz;
355 for (c, &owner) in assign.iter().enumerate().take(n) {
356 if owner != domain {
357 continue;
358 }
359 let (ix, iy, iz) = unravel(c, nx, ny);
360 paint(&mut mark, nx, ny, nz, ix, iy, iz, width);
361 }
362 let mut ghosts = Vec::new();
363 for c in 0..n {
364 if mark[c] != 0 && assign[c] != domain {
365 ghosts.push(c as u32);
366 }
367 }
368 Ok(ghosts)
369}
370
371pub fn mark_reached(
377 xyz: &[[f64; 3]],
378 lengths: [f64; 3],
379 nxyz: [i32; 3],
380 assign: &[u32],
381 point_cell: &[u32],
382 hwidth: [u32; 3],
383 domain: u32,
384 reach: f64,
385) -> Result<Vec<u8>, Error> {
386 if xyz.len() != point_cell.len() || !(reach.is_finite() && reach >= 0.0) {
387 return Err(Error::BadGraph);
388 }
389 if nxyz[0] <= 0 || nxyz[1] <= 0 || nxyz[2] <= 0 {
390 return Err(Error::BadGraph);
391 }
392 let nx = nxyz[0] as usize;
393 let ny = nxyz[1] as usize;
394 let nz = nxyz[2] as usize;
395 let ncell = nx
396 .checked_mul(ny)
397 .and_then(|v| v.checked_mul(nz))
398 .ok_or(Error::BadGraph)?;
399 if assign.len() != ncell {
400 return Err(Error::BadGraph);
401 }
402 let mut start = vec![0usize; ncell + 1];
403 for &cell in point_cell {
404 let c = cell as usize;
405 if c < ncell {
406 start[c + 1] += 1;
407 }
408 }
409 for c in 0..ncell {
410 start[c + 1] += start[c];
411 }
412 let mut cursor = start.clone();
413 let mut atoms = vec![0usize; xyz.len()];
414 for (i, &cell) in point_cell.iter().enumerate() {
415 let c = cell as usize;
416 if c < ncell {
417 atoms[cursor[c]] = i;
418 cursor[c] += 1;
419 }
420 }
421 let reach2 = reach * reach;
422 let rad = [hwidth[0] as i32, hwidth[1] as i32, hwidth[2] as i32];
423 let mut hit = vec![0u8; xyz.len()];
424 for (i, &cell) in point_cell.iter().enumerate() {
425 let c = cell as usize;
426 if c >= ncell {
427 continue;
428 }
429 if assign[c] == domain {
430 hit[i] = 2;
431 continue;
432 }
433 let ix = (c % nx) as i32;
434 let iy = ((c / nx) % ny) as i32;
435 let iz = (c / (nx * ny)) as i32;
436 let mut found = false;
437 'search: for dz in -rad[2]..=rad[2] {
438 for dy in -rad[1]..=rad[1] {
439 for dx in -rad[0]..=rad[0] {
440 let jx = (ix + dx).rem_euclid(nxyz[0]) as usize;
441 let jy = (iy + dy).rem_euclid(nxyz[1]) as usize;
442 let jz = (iz + dz).rem_euclid(nxyz[2]) as usize;
443 let other = (jz * ny + jy) * nx + jx;
444 if assign[other] != domain {
445 continue;
446 }
447 for &j in &atoms[start[other]..start[other + 1]] {
448 let mut sum = 0.0;
449 for d in 0..3 {
450 let mut delta = xyz[i][d] - xyz[j][d];
451 delta -= lengths[d] * (delta / lengths[d] + 0.5).floor();
452 sum += delta * delta;
453 }
454 if sum <= reach2 {
455 found = true;
456 break 'search;
457 }
458 }
459 }
460 }
461 }
462 if found {
463 hit[i] = 1;
464 }
465 }
466 Ok(hit)
467}
468
469pub fn cell_grid(
471 xyz: &[[f64; 3]],
472 sim: &Cell,
473 cutoff: f64,
474 mask: Option<&[bool]>,
475 cell_hint: Option<f64>,
476) -> Result<CellGrid, Error> {
477 prepared(xyz, sim, cutoff, mask, cell_hint, false).map(|p| p.graph.grid)
478}
479
480pub fn cell_graph(
482 xyz: &[[f64; 3]],
483 sim: &Cell,
484 cutoff: f64,
485 mask: Option<&[bool]>,
486 cell_hint: Option<f64>,
487) -> Result<CellGraph, Error> {
488 prepared(xyz, sim, cutoff, mask, cell_hint, true).map(|p| p.graph)
489}
490
491pub fn partition(
493 xyz: &[[f64; 3]],
494 sim: &Cell,
495 cutoff: f64,
496 mask: Option<&[bool]>,
497 cell_hint: Option<f64>,
498 request: PartRequest,
499) -> Result<Vec<u32>, Error> {
500 let prep = prepared(
505 xyz,
506 sim,
507 cutoff,
508 mask,
509 cell_hint,
510 request.method.needs_edges(),
511 )?;
512 partition_prepared(&prep, request)
513}
514
515pub fn partition_graph(graph: &CellGraph, request: PartRequest) -> Result<Vec<u32>, Error> {
519 if request.device {
520 return Err(Error::NoDevice);
521 }
522 let t_check = Instant::now();
523 check_graph(graph)?;
524 CHECK_NS.fetch_add(t_check.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
525 let t_ratio = Instant::now();
526 let ratio = balance_ratio(request.balance, &graph.grid.weight, request.parts)?;
527 PACK_NS.fetch_add(t_ratio.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
528 if request.parts == 0 {
529 return Err(Error::BadPartition);
530 }
531 dispatch(graph, request.method, request.parts, ratio, None)
532}
533
534pub fn curve_split_device(
540 xyz: &[[f64; 3]],
541 sim: &Cell,
542 cutoff: f64,
543 mask: Option<&[bool]>,
544 cell_hint: Option<f64>,
545 parts: u32,
546 method: Method,
547) -> Result<Vec<u32>, Error> {
548 if !method.uses_curve() {
549 return Err(Error::NoDevice);
550 }
551 if parts == 0 {
552 return Err(Error::BadPartition);
553 }
554 let prep = prepared(xyz, sim, cutoff, mask, cell_hint, false)?;
555 device_curve(&prep, parts, method)
556}
557
558pub fn score(
560 graph: &CellGraph,
561 assign: &[u32],
562 parts: u32,
563 width: [u32; 3],
564) -> Result<PartScore, Error> {
565 check_graph(graph)?;
566 check_assign(&graph.grid, assign)?;
567 if parts == 0 {
568 return Err(Error::BadPartition);
569 }
570 for &d in assign {
571 if d >= parts {
572 return Err(Error::BadPartition);
573 }
574 }
575 Ok(PartScore {
576 cut: edge_cut(graph, assign),
577 imbalance: max_imbalance(&graph.grid.weight, assign, parts),
578 halo_fraction: halo_fraction(&graph.grid, assign, parts, width)?,
579 })
580}
581
582pub fn edge_cut(graph: &CellGraph, assign: &[u32]) -> u64 {
584 let mut cut = 0u64;
585 let n = graph.grid.ncell();
586 for c in 0..n {
587 let a = assign[c];
588 let lo = graph.offsets[c] as usize;
589 let hi = graph.offsets[c + 1] as usize;
590 for e in lo..hi {
591 let nbr = graph.neighbor[e] as usize;
592 if nbr > c && assign[nbr] != a {
593 cut += graph.edge_weight[e];
594 }
595 }
596 }
597 cut
598}
599
600struct Prepared {
601 graph: CellGraph,
602 active_bins: Vec<u32>,
604 point_cell: Vec<u32>,
606}
607
608#[cfg(feature = "parallel")]
612fn bin_threads() -> usize {
613 if crate::on_caller() {
614 return 1;
615 }
616 std::thread::available_parallelism()
617 .map(|n| n.get())
618 .unwrap_or(1)
619}
620
621#[cfg(not(feature = "parallel"))]
622fn bin_threads() -> usize {
623 1
624}
625
626fn bin_points(
630 xyz: &[[f64; 3]],
631 sim: &Cell,
632 mask: Option<&[bool]>,
633 dims: [i32; 3],
634 ncell: usize,
635) -> (Vec<u64>, Vec<u32>, Vec<u32>) {
636 let n = xyz.len();
637 let threads = if n >= 8192 { bin_threads() } else { 1 };
638 let chunk = (n + threads - 1) / threads;
639 let mut bin_of = vec![0u32; n];
640 let mut weight = vec![0u64; ncell];
641 let bin_range = |t: usize, lo: usize, hi: usize| {
642 let mut local = vec![0u64; ncell];
643 let mut active = Vec::new();
644 for i in lo..hi {
645 if mask.is_some_and(|m| !m[i]) {
646 continue;
647 }
648 let (_, b) = bins::fold_point(sim, xyz[i], dims);
649 let c = flat_cell(b, dims) as u32;
650 local[c as usize] += 1;
651 active.push((i, c));
652 }
653 (t, active, local)
654 };
655 let mut hits: Vec<(usize, Vec<(usize, u32)>, Vec<u64>)> = if threads == 1 {
656 vec![bin_range(0, 0, n)]
657 } else {
658 std::thread::scope(|scope| {
659 let bin_range = &bin_range;
660 let mut joins = Vec::new();
661 for t in 0..threads {
662 let lo = t * chunk;
663 let hi = ((t + 1) * chunk).min(n);
664 if lo >= hi {
665 continue;
666 }
667 joins.push(scope.spawn(move || bin_range(t, lo, hi)));
668 }
669 joins
670 .into_iter()
671 .map(|join| join.join().expect("bin"))
672 .collect()
673 })
674 };
675 hits.sort_by_key(|(t, _, _)| *t);
676 let mut active_bins = Vec::new();
677 for (_, active, local) in hits {
678 for (c, w) in local.into_iter().enumerate() {
679 weight[c] += w;
680 }
681 for (i, c) in active {
682 bin_of[i] = c;
683 active_bins.push(c);
684 }
685 }
686 (weight, active_bins, bin_of)
687}
688
689fn prepared(
690 xyz: &[[f64; 3]],
691 sim: &Cell,
692 cutoff: f64,
693 mask: Option<&[bool]>,
694 cell_hint: Option<f64>,
695 with_edges: bool,
696) -> Result<Prepared, Error> {
697 if !cutoff.is_finite() || cutoff <= 0.0 {
698 return Err(Error::BadCutoff);
699 }
700 if xyz.is_empty() {
701 return Err(Error::Empty);
702 }
703 if let Some(m) = mask {
704 if m.len() != xyz.len() {
705 return Err(Error::MaskLen);
706 }
707 }
708 let mut n_act = 0usize;
709 for (i, p) in xyz.iter().enumerate() {
710 if !p[0].is_finite() || !p[1].is_finite() || !p[2].is_finite() {
711 return Err(Error::NonFinite);
712 }
713 if mask.is_some_and(|m| !m[i]) {
714 continue;
715 }
716 n_act += 1;
717 }
718 let edge = bins::target_edge(sim, cell_hint, pairs::default_edge(sim, n_act, cutoff));
719 let dims = bins::grid_dims(sim, edge)?;
720 let ncell = (dims[0] as usize) * (dims[1] as usize) * (dims[2] as usize);
721 let box_w = sim.widths();
722 let bin_width = [
723 box_w[0] / f64::from(dims[0]),
724 box_w[1] / f64::from(dims[1]),
725 box_w[2] / f64::from(dims[2]),
726 ];
727 let (weight, active_bins, bin_of) = bin_points(xyz, sim, mask, dims, ncell);
728 let (offsets, neighbor, edge_weight) = if with_edges {
729 arcs_from_pairs(xyz, sim, cutoff, mask, cell_hint, &bin_of, ncell)?
730 } else {
731 (vec![0u32; ncell + 1], Vec::new(), Vec::new())
732 };
733 Ok(Prepared {
734 graph: CellGraph {
735 grid: CellGrid {
736 nx: dims[0],
737 ny: dims[1],
738 nz: dims[2],
739 bin_width,
740 weight,
741 },
742 offsets,
743 neighbor,
744 edge_weight,
745 },
746 active_bins,
747 point_cell: bin_of,
748 })
749}
750
751pub struct MeshCut {
756 pub assign: Vec<u32>,
758 pub grid: CellGrid,
760 pub point_cell: Vec<u32>,
762}
763
764pub fn mesh_cut(
766 xyz: &[[f64; 3]],
767 sim: &Cell,
768 cutoff: f64,
769 mask: Option<&[bool]>,
770 cell_hint: Option<f64>,
771 request: PartRequest,
772) -> Result<MeshCut, Error> {
773 let prep = prepared(
774 xyz,
775 sim,
776 cutoff,
777 mask,
778 cell_hint,
779 request.method.needs_edges(),
780 )?;
781 let assign = partition_prepared(&prep, request)?;
782 Ok(MeshCut {
783 assign,
784 grid: prep.graph.grid,
785 point_cell: prep.point_cell,
786 })
787}
788
789pub struct RankMask {
791 pub mask: Vec<bool>,
793 pub owned: usize,
795 pub ghosts: usize,
797}
798
799pub fn fused_masks(
805 grid: &CellGrid,
806 assign: &[u32],
807 point_cell: &[u32],
808 parts: u32,
809 width: [u32; 3],
810) -> Result<Vec<RankMask>, Error> {
811 let n = check_assign(grid, assign)?;
812 if parts == 0 {
813 return Err(Error::BadPartition);
814 }
815 for &domain in assign {
816 if domain >= parts {
817 return Err(Error::BadPartition);
818 }
819 }
820 for &cell in point_cell {
821 if cell as usize >= n {
822 return Err(Error::BadPartition);
823 }
824 }
825 let owned = owned_cells(assign, parts);
826 let built = std::thread::scope(|scope| {
827 let mut joins = Vec::new();
828 for rank in 0..parts {
829 let cells = &owned[rank as usize];
830 joins
831 .push(scope.spawn(move || rank_mask(grid, assign, point_cell, cells, rank, width)));
832 }
833 joins
834 .into_iter()
835 .map(|join| join.join().expect("rank mask"))
836 .collect()
837 });
838 Ok(built)
839}
840
841pub fn owned_cells(assign: &[u32], parts: u32) -> Vec<Vec<u32>> {
843 let n = assign.len();
844 let threads = std::thread::available_parallelism()
845 .map(|n| n.get())
846 .unwrap_or(1);
847 let threads = if n >= 8192 { threads.max(1) } else { 1 };
848 let chunk = (n + threads - 1) / threads;
849 let mut hits: Vec<(usize, Vec<Vec<u32>>)> = Vec::new();
850 std::thread::scope(|scope| {
851 let mut joins = Vec::new();
852 for t in 0..threads {
853 let lo = t * chunk;
854 let hi = ((t + 1) * chunk).min(n);
855 if lo >= hi {
856 continue;
857 }
858 joins.push(scope.spawn(move || {
859 let mut rows = vec![Vec::new(); parts as usize];
860 for cell in lo..hi {
861 rows[assign[cell] as usize].push(cell as u32);
862 }
863 (t, rows)
864 }));
865 }
866 for join in joins {
867 hits.push(join.join().expect("owned"));
868 }
869 });
870 hits.sort_by_key(|(t, _)| *t);
871 let mut owned = vec![Vec::new(); parts as usize];
872 for (_, rows) in hits {
873 for (rank, cells) in rows.into_iter().enumerate() {
874 owned[rank].extend(cells);
875 }
876 }
877 owned
878}
879
880pub fn rank_mask(
884 grid: &CellGrid,
885 assign: &[u32],
886 point_cell: &[u32],
887 cells: &[u32],
888 rank: u32,
889 width: [u32; 3],
890) -> RankMask {
891 let n = grid.ncell();
892 let mut mark = vec![0u8; n];
893 for &cell in cells {
894 let (ix, iy, iz) = unravel(cell as usize, grid.nx, grid.ny);
895 paint(&mut mark, grid.nx, grid.ny, grid.nz, ix, iy, iz, width);
896 }
897 let mut ghosts = 0usize;
898 for (cell, &flag) in mark.iter().enumerate() {
899 if flag != 0 && assign[cell] != rank {
900 ghosts += 1;
901 }
902 }
903 let mut mask = vec![false; point_cell.len()];
904 let mut owned_pts = 0usize;
905 for (i, &cell) in point_cell.iter().enumerate() {
906 let cell = cell as usize;
907 if assign[cell] == rank {
908 owned_pts += 1;
909 }
910 mask[i] = mark[cell] != 0;
911 }
912 RankMask {
913 mask,
914 owned: owned_pts,
915 ghosts,
916 }
917}
918
919fn arcs_from_pairs(
920 xyz: &[[f64; 3]],
921 sim: &Cell,
922 cutoff: f64,
923 mask: Option<&[bool]>,
924 cell_hint: Option<f64>,
925 bin_of: &[u32],
926 ncell: usize,
927) -> Result<(Vec<u32>, Vec<u32>, Vec<u64>), Error> {
928 let pairs = pairs_within(xyz, sim, cutoff, mask, cell_hint, true)?;
929 let mut ends: Vec<(u32, u32)> = Vec::new();
930 for pair in pairs {
931 let a = bin_of[pair.i];
932 let b = bin_of[pair.j];
933 if a == b {
934 continue;
935 }
936 if a < b {
937 ends.push((a, b));
938 } else {
939 ends.push((b, a));
940 }
941 }
942 ends.sort_unstable();
943 let mut undirected: Vec<(u32, u32, u64)> = Vec::new();
944 let mut cursor = 0;
945 while cursor < ends.len() {
946 let (a, b) = ends[cursor];
947 let mut count = 1u64;
948 cursor += 1;
949 while cursor < ends.len() && ends[cursor] == (a, b) {
950 count += 1;
951 cursor += 1;
952 }
953 undirected.push((a, b, count));
954 }
955 let mut arcs: Vec<(u32, u32, u64)> = Vec::with_capacity(undirected.len() * 2);
956 for (a, b, w) in undirected {
957 arcs.push((a, b, w));
958 arcs.push((b, a, w));
959 }
960 arcs.sort_unstable();
961 if arcs.len() > u32::MAX as usize {
962 return Err(Error::Overflow);
963 }
964 let mut offsets = vec![0u32; ncell + 1];
965 let mut neighbor = Vec::with_capacity(arcs.len());
966 let mut edge_weight = Vec::with_capacity(arcs.len());
967 for (src, dst, w) in arcs {
968 offsets[src as usize + 1] += 1;
969 neighbor.push(dst);
970 edge_weight.push(w);
971 }
972 for c in 0..ncell {
973 offsets[c + 1] += offsets[c];
974 }
975 Ok((offsets, neighbor, edge_weight))
976}
977
978fn partition_prepared(prep: &Prepared, request: PartRequest) -> Result<Vec<u32>, Error> {
979 if request.parts == 0 {
980 return Err(Error::BadPartition);
981 }
982 let ratio = balance_ratio(request.balance, &prep.graph.grid.weight, request.parts)?;
983 let device_assign = if request.device {
984 if !request.method.uses_curve() {
985 return Err(Error::NoDevice);
986 }
987 Some(device_curve(prep, request.parts, request.method)?)
988 } else {
989 None
990 };
991 dispatch(
992 &prep.graph,
993 request.method,
994 request.parts,
995 ratio,
996 device_assign,
997 )
998}
999
1000fn cluster_cap(total: u64, parts: u32, w_max: u64, ratio: (u64, u64)) -> u64 {
1008 part_cap(total, parts, ratio).max(w_max).max(1)
1009}
1010
1011fn multi_assign(graph: &CellGraph, parts: u32, ratio: (u64, u64)) -> Vec<u32> {
1012 let n = graph.grid.ncell();
1013 let t_pack = Instant::now();
1014 let mut coords = Vec::with_capacity(n);
1015 for c in 0..n {
1016 let (ix, iy, iz) = unravel(c, graph.grid.nx, graph.grid.ny);
1017 coords.push((f64::from(ix), f64::from(iy), f64::from(iz)));
1018 }
1019 PACK_NS.fetch_add(t_pack.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1020 let mut best = rcb_assign(graph, parts, true, ratio);
1025 let t_cut = Instant::now();
1026 let mut best_cut = edge_cut(graph, &best);
1027 COARSE_NS.fetch_add(t_cut.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1028 loop {
1029 let next = v_cycle(graph, &coords, &best, parts, ratio);
1030 let t_cut = Instant::now();
1031 let next_cut = edge_cut(graph, &next);
1032 let keep = next_cut < best_cut && holds_balance(&graph.grid.weight, &next, parts, ratio);
1033 COARSE_NS.fetch_add(t_cut.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1034 if keep {
1035 best = next;
1036 best_cut = next_cut;
1037 } else {
1038 break;
1039 }
1040 }
1041 best
1042}
1043
1044fn holds_balance(weight: &[u64], assign: &[u32], parts: u32, ratio: (u64, u64)) -> bool {
1045 if parts == 0 {
1046 return false;
1047 }
1048 let mut part_w = vec![0u64; parts as usize];
1049 let mut total = 0u64;
1050 for (c, &d) in assign.iter().enumerate() {
1051 if d >= parts {
1052 return false;
1053 }
1054 part_w[d as usize] += weight[c];
1055 total += weight[c];
1056 }
1057 part_w
1058 .iter()
1059 .all(|&w| under_balance(w, total, parts, ratio))
1060}
1061
1062fn v_cycle(
1065 graph: &CellGraph,
1066 coords: &[(f64, f64, f64)],
1067 assign: &[u32],
1068 parts: u32,
1069 ratio: (u64, u64),
1070) -> Vec<u32> {
1071 let n = graph.grid.ncell();
1072 let t_prep = Instant::now();
1073 let total: u64 = graph.grid.weight.iter().copied().sum();
1074 let w_max = graph.grid.weight.iter().copied().max().unwrap_or(0);
1075 let cap = cluster_cap(total, parts, w_max, ratio);
1076 COARSE_NS.fetch_add(t_prep.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1077 if n <= parts as usize || graph.grid.weight.iter().any(|&w| w > cap) {
1080 let mut out = assign.to_vec();
1081 refine(&mut out, graph, parts, ratio);
1082 return out;
1083 }
1084 let t0 = Instant::now();
1085 let mate = heavy_match(graph, cap, Some(assign));
1086 let shrunk = mate.iter().enumerate().any(|(v, &m)| m != v as u32);
1087 if !shrunk {
1088 COARSE_NS.fetch_add(t0.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1089 let mut out = assign.to_vec();
1090 refine(&mut out, graph, parts, ratio);
1091 return out;
1092 }
1093 let (coarse, coarse_coords, owner) = contract(graph, coords, &mate);
1094 COARSE_NS.fetch_add(t0.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1095 let mut up = vec![0u32; coarse.grid.ncell()];
1096 for (fine, &cell) in owner.iter().enumerate() {
1097 up[cell as usize] = assign[fine];
1098 }
1099 let up = v_cycle(&coarse, &coarse_coords, &up, parts, ratio);
1100 let t_down = Instant::now();
1101 let mut out = vec![0u32; n];
1102 for (fine, &cell) in owner.iter().enumerate() {
1103 out[fine] = up[cell as usize];
1104 }
1105 COARSE_NS.fetch_add(t_down.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1106 refine(&mut out, graph, parts, ratio);
1107 out
1108}
1109
1110fn heavy_match(graph: &CellGraph, cap: u64, same: Option<&[u32]>) -> Vec<u32> {
1111 let n = graph.grid.ncell();
1112 let mut mate = vec![u32::MAX; n];
1113 for v in 0..n {
1114 if mate[v] != u32::MAX {
1115 continue;
1116 }
1117 let wv = graph.grid.weight[v];
1118 let mut best: Option<(u64, u64, u32)> = None;
1120 let lo = graph.offsets[v] as usize;
1121 let hi = graph.offsets[v + 1] as usize;
1122 for e in lo..hi {
1123 let u = graph.neighbor[e];
1124 if u as usize == v || mate[u as usize] != u32::MAX {
1125 continue;
1126 }
1127 let wu = graph.grid.weight[u as usize];
1128 if wv.saturating_add(wu) > cap {
1129 continue;
1130 }
1131 if let Some(parts_of) = same {
1132 if parts_of[u as usize] != parts_of[v] {
1133 continue;
1134 }
1135 }
1136 let w = graph.edge_weight[e];
1137 let denom = wv.max(1).saturating_add(wu.max(1));
1138 let take = match best {
1139 None => true,
1140 Some((bw, bden, bu)) => {
1141 let left = u128::from(w) * u128::from(bden);
1142 let right = u128::from(bw) * u128::from(denom);
1143 left > right || (left == right && u < bu)
1144 }
1145 };
1146 if take {
1147 best = Some((w, denom, u));
1148 }
1149 }
1150 if let Some((_, _, u)) = best {
1151 mate[v] = u;
1152 mate[u as usize] = v as u32;
1153 } else {
1154 mate[v] = v as u32;
1155 }
1156 }
1157 mate
1158}
1159
1160fn contract(
1161 graph: &CellGraph,
1162 coords: &[(f64, f64, f64)],
1163 mate: &[u32],
1164) -> (CellGraph, Vec<(f64, f64, f64)>, Vec<u32>) {
1165 let n = graph.grid.ncell();
1166 let mut coarse_of = vec![u32::MAX; n];
1167 let mut members: Vec<Vec<u32>> = Vec::new();
1168 for v in 0..n {
1169 let lead = (v as u32).min(mate[v]) as usize;
1170 if coarse_of[lead] == u32::MAX {
1171 coarse_of[lead] = members.len() as u32;
1172 members.push(Vec::new());
1173 }
1174 let id = coarse_of[lead];
1175 coarse_of[v] = id;
1176 members[id as usize].push(v as u32);
1177 }
1178 let nc = members.len();
1179 let mut weight = vec![0u64; nc];
1180 let mut ccoords = vec![(0.0, 0.0, 0.0); nc];
1181 for (c, group) in members.iter().enumerate() {
1182 let mut mass = 0u64;
1183 let mut acc = (0.0, 0.0, 0.0);
1184 for &v in group {
1185 let w = graph.grid.weight[v as usize];
1186 mass += w;
1187 let p = coords[v as usize];
1188 acc.0 += p.0 * w as f64;
1189 acc.1 += p.1 * w as f64;
1190 acc.2 += p.2 * w as f64;
1191 weight[c] += w;
1192 }
1193 if mass == 0 {
1194 let p = coords[group[0] as usize];
1195 ccoords[c] = p;
1196 } else {
1197 let mass = mass as f64;
1198 ccoords[c] = (acc.0 / mass, acc.1 / mass, acc.2 / mass);
1199 }
1200 }
1201 let mut ends: Vec<(u32, u32, u64)> = Vec::new();
1202 for v in 0..n {
1203 let cv = coarse_of[v];
1204 let lo = graph.offsets[v] as usize;
1205 let hi = graph.offsets[v + 1] as usize;
1206 for e in lo..hi {
1207 let u = graph.neighbor[e] as usize;
1208 if u <= v {
1209 continue;
1210 }
1211 let cu = coarse_of[u];
1212 if cu == cv {
1213 continue;
1214 }
1215 let (a, b) = if cv < cu { (cv, cu) } else { (cu, cv) };
1216 ends.push((a, b, graph.edge_weight[e]));
1217 }
1218 }
1219 ends.sort_unstable_by(|p, q| p.0.cmp(&q.0).then(p.1.cmp(&q.1)));
1220 let mut arcs: Vec<(u32, u32, u64)> = Vec::new();
1221 let mut i = 0;
1222 while i < ends.len() {
1223 let (a, b, mut w) = ends[i];
1224 i += 1;
1225 while i < ends.len() && ends[i].0 == a && ends[i].1 == b {
1226 w += ends[i].2;
1227 i += 1;
1228 }
1229 arcs.push((a, b, w));
1232 arcs.push((b, a, w));
1233 }
1234 arcs.sort_unstable_by(|p, q| p.0.cmp(&q.0).then(p.1.cmp(&q.1)));
1235 let mut offsets = vec![0u32; nc + 1];
1236 let mut neighbor = Vec::with_capacity(arcs.len());
1237 let mut edge_weight = Vec::with_capacity(arcs.len());
1238 for (src, dst, w) in arcs {
1239 offsets[src as usize + 1] += 1;
1240 neighbor.push(dst);
1241 edge_weight.push(w);
1242 }
1243 for c in 0..nc {
1244 offsets[c + 1] += offsets[c];
1245 }
1246 let coarse = CellGraph {
1247 grid: CellGrid {
1248 nx: nc as i32,
1249 ny: 1,
1250 nz: 1,
1251 bin_width: [1.0, 1.0, 1.0],
1252 weight,
1253 },
1254 offsets,
1255 neighbor,
1256 edge_weight,
1257 };
1258 (coarse, ccoords, coarse_of)
1259}
1260
1261fn ptscotch_assign(graph: &CellGraph, parts: u32, ratio: (u64, u64)) -> Result<Vec<u32>, Error> {
1262 #[cfg(not(feature = "ptscotch"))]
1263 {
1264 let _ = (graph, parts, ratio);
1265 Err(Error::ScotchDisabled)
1266 }
1267 #[cfg(feature = "ptscotch")]
1268 {
1269 ptscotch_linked(graph, parts, ratio)
1270 }
1271}
1272
1273#[cfg(feature = "ptscotch")]
1274fn ptscotch_linked(graph: &CellGraph, parts: u32, ratio: (u64, u64)) -> Result<Vec<u32>, Error> {
1275 let n = graph.grid.ncell();
1276 if n > i32::MAX as usize || parts > i32::MAX as u32 {
1277 return Err(Error::Overflow);
1278 }
1279 let mut offsets = Vec::with_capacity(n + 1);
1280 let mut edges = Vec::with_capacity(graph.neighbor.len());
1281 let mut vwgt = Vec::with_capacity(n);
1282 let mut ewgt = Vec::with_capacity(graph.edge_weight.len());
1283 for &v in &graph.offsets {
1284 if v > i32::MAX as u32 {
1285 return Err(Error::Overflow);
1286 }
1287 offsets.push(v as i32);
1288 }
1289 for &v in &graph.neighbor {
1290 if v > i32::MAX as u32 {
1291 return Err(Error::Overflow);
1292 }
1293 edges.push(v as i32);
1294 }
1295 for &v in &graph.grid.weight {
1296 if v > i32::MAX as u64 {
1297 return Err(Error::Overflow);
1298 }
1299 vwgt.push(v as i32);
1300 }
1301 for &v in &graph.edge_weight {
1302 if v > i32::MAX as u64 {
1303 return Err(Error::Overflow);
1304 }
1305 ewgt.push(v as i32);
1306 }
1307 let mut part = vec![0i32; n];
1308 let (num, den) = ratio;
1309 let imbalance = if den == 0 {
1310 0.0
1311 } else {
1312 (num as f64 / den as f64) - 1.0
1313 };
1314 let mut seconds = 0.0f64;
1315 let rc = unsafe {
1316 lc_ptscotch_part(
1317 n as i32,
1318 offsets.as_ptr(),
1319 edges.as_ptr(),
1320 vwgt.as_ptr(),
1321 ewgt.as_ptr(),
1322 parts as i32,
1323 imbalance,
1324 part.as_mut_ptr(),
1325 &mut seconds,
1326 )
1327 };
1328 if rc != 0 {
1329 return Err(Error::ScotchFailed);
1330 }
1331 let _ = seconds;
1332 let mut out = Vec::with_capacity(n);
1333 for v in part {
1334 if v < 0 || v as u32 >= parts {
1335 return Err(Error::ScotchFailed);
1336 }
1337 out.push(v as u32);
1338 }
1339 Ok(out)
1340}
1341
1342#[cfg(feature = "ptscotch")]
1343unsafe extern "C" {
1344 fn lc_ptscotch_part(
1345 n: i32,
1346 offsets: *const i32,
1347 edges: *const i32,
1348 vwgt: *const i32,
1349 ewgt: *const i32,
1350 parts: i32,
1351 imbalance: f64,
1352 part: *mut i32,
1353 seconds_max: *mut f64,
1354 ) -> i32;
1355}
1356
1357fn dispatch(
1358 graph: &CellGraph,
1359 method: Method,
1360 parts: u32,
1361 ratio: (u64, u64),
1362 device_assign: Option<Vec<u32>>,
1363) -> Result<Vec<u32>, Error> {
1364 let mut assign = match method {
1365 Method::Scotch => scotch_assign(graph, parts, ratio)?,
1366 Method::PtScotch => ptscotch_assign(graph, parts, ratio)?,
1367 Method::Multi => multi_assign(graph, parts, ratio),
1368 Method::Rcb | Method::RcbFm => rcb_assign(graph, parts, method == Method::RcbFm, ratio),
1369 Method::Morton | Method::Hilbert | Method::HilbertFm => match device_assign {
1370 Some(done) => done,
1371 None => curve_assign(graph, parts, method)?,
1372 },
1373 };
1374 if method.refines() {
1375 refine(&mut assign, graph, parts, ratio);
1376 }
1377 if matches!(method, Method::RcbFm | Method::HilbertFm | Method::Multi) {
1378 let t_repair = Instant::now();
1379 repair_balance(&mut assign, graph, parts, ratio);
1380 if matches!(method, Method::RcbFm | Method::Multi)
1381 && !holds_balance(&graph.grid.weight, &assign, parts, ratio)
1382 {
1383 REPAIR_NS.fetch_add(
1384 t_repair.elapsed().as_nanos() as u64,
1385 AtomicOrdering::Relaxed,
1386 );
1387 assign = rcb_assign(graph, parts, false, ratio);
1388 } else {
1389 REPAIR_NS.fetch_add(
1390 t_repair.elapsed().as_nanos() as u64,
1391 AtomicOrdering::Relaxed,
1392 );
1393 }
1394 }
1395 Ok(assign)
1396}
1397
1398fn part_cap(total: u64, parts: u32, ratio: (u64, u64)) -> u64 {
1399 let (num, den) = ratio;
1400 if parts == 0 || den == 0 {
1401 return total;
1402 }
1403 ((u128::from(total) * u128::from(num)) / (u128::from(parts) * u128::from(den))) as u64
1404}
1405
1406fn repair_balance(assign: &mut [u32], graph: &CellGraph, parts: u32, ratio: (u64, u64)) {
1408 if parts <= 1 {
1409 return;
1410 }
1411 let n = assign.len();
1412 let weight = &graph.grid.weight;
1413 let total: u64 = weight.iter().copied().sum();
1414 let cap = part_cap(total, parts, ratio);
1415 let mut part_w = vec![0u64; parts as usize];
1416 for (c, &d) in assign.iter().enumerate() {
1417 if (d as usize) < part_w.len() {
1418 part_w[d as usize] += weight[c];
1419 }
1420 }
1421 for _ in 0..n {
1422 let Some(src) = part_w.iter().position(|&w| w > cap) else {
1423 return;
1424 };
1425 let mut best: Option<(i64, usize, u32)> = None;
1426 for cell in 0..n {
1427 if assign[cell] as usize != src {
1428 continue;
1429 }
1430 let w = weight[cell];
1431 if w == 0 || part_w[src] < w || !part_boundary(cell, assign, graph) {
1432 continue;
1433 }
1434 let lo = graph.offsets[cell] as usize;
1435 let hi = graph.offsets[cell + 1] as usize;
1436 let mut dests: Vec<u32> = Vec::new();
1437 let mut to_src = 0i64;
1438 let mut to_dest_w = vec![0i64; parts as usize];
1439 for e in lo..hi {
1440 let nbr = graph.neighbor[e] as usize;
1441 let dest = assign[nbr];
1442 let ww = graph.edge_weight[e] as i64;
1443 if dest as usize == src {
1444 to_src += ww;
1445 } else if (dest as usize) < to_dest_w.len() {
1446 to_dest_w[dest as usize] += ww;
1447 if !dests.contains(&dest) {
1448 dests.push(dest);
1449 }
1450 }
1451 }
1452 for dest in dests {
1453 if part_w[dest as usize].saturating_add(w) > cap {
1454 continue;
1455 }
1456 let gain = to_dest_w[dest as usize] - to_src;
1457 let take = match best {
1458 None => true,
1459 Some((bg, bcell, bdest)) => {
1460 gain > bg
1461 || (gain == bg && (cell < bcell || (cell == bcell && dest < bdest)))
1462 }
1463 };
1464 if take {
1465 best = Some((gain, cell, dest));
1466 }
1467 }
1468 }
1469 let Some((_, cell, dest)) = best else {
1470 return;
1471 };
1472 let w = weight[cell];
1473 part_w[src] -= w;
1474 part_w[dest as usize] += w;
1475 assign[cell] = dest;
1476 }
1477}
1478
1479fn curve_assign(graph: &CellGraph, parts: u32, method: Method) -> Result<Vec<u32>, Error> {
1480 let n = graph.grid.ncell();
1481 let mut order: Vec<u32> = (0..n as u32).collect();
1482 match method {
1483 Method::Morton => {
1484 order.sort_by(|&a, &b| morton_ord(a, b, &graph.grid).then(a.cmp(&b)));
1485 }
1486 Method::Hilbert | Method::HilbertFm => {
1487 let bits = hilbert_bits(graph.grid.nx, graph.grid.ny, graph.grid.nz);
1488 let mut keys = vec![0u64; n];
1489 for (c, key) in keys.iter_mut().enumerate() {
1490 let (x, y, z) = unravel(c, graph.grid.nx, graph.grid.ny);
1491 *key = hilbert_key(x as u32, y as u32, z as u32, bits);
1492 }
1493 order.sort_by(|&a, &b| keys[a as usize].cmp(&keys[b as usize]).then(a.cmp(&b)));
1494 }
1495 _ => return Err(Error::BadPartition),
1496 }
1497 Ok(prefix_assign(&order, &graph.grid.weight, parts))
1498}
1499
1500fn device_curve(prep: &Prepared, parts: u32, method: Method) -> Result<Vec<u32>, Error> {
1501 let n = prep.graph.grid.ncell();
1502 let coords = cell_coords(&prep.graph.grid);
1503 let mut assign = vec![0u32; n];
1504 let mut got_w = vec![0u64; n];
1505 let rc = unsafe {
1506 call_device_curve(
1507 prep.active_bins.as_ptr(),
1508 prep.active_bins.len(),
1509 coords.as_ptr(),
1510 n,
1511 parts,
1512 assign.as_mut_ptr(),
1513 got_w.as_mut_ptr(),
1514 method as u8,
1515 )
1516 };
1517 match rc {
1518 0 => {}
1519 2 => return Err(Error::NoDevice),
1520 _ => return Err(Error::NoDevice),
1521 }
1522 if got_w != prep.graph.grid.weight {
1523 return Err(Error::DeviceMismatch);
1524 }
1525 for &d in &assign {
1526 if d >= parts {
1527 return Err(Error::DeviceMismatch);
1528 }
1529 }
1530 Ok(assign)
1531}
1532
1533fn cell_coords(grid: &CellGrid) -> Vec<u32> {
1534 let mut coords = Vec::with_capacity(grid.ncell() * 3);
1535 for iz in 0..grid.nz {
1536 for iy in 0..grid.ny {
1537 for ix in 0..grid.nx {
1538 coords.push(ix as u32);
1539 coords.push(iy as u32);
1540 coords.push(iz as u32);
1541 }
1542 }
1543 }
1544 coords
1545}
1546
1547pub fn prefix_assign(order: &[u32], weight: &[u64], parts: u32) -> Vec<u32> {
1549 let n = weight.len();
1550 let mut assign = vec![0u32; n];
1551 if parts == 0 || n == 0 {
1552 return assign;
1553 }
1554 let total: u64 = weight.iter().copied().sum();
1555 let mut before = 0u64;
1556 for &cell in order {
1557 let w = if total == 0 { 1 } else { weight[cell as usize] };
1558 let tot = if total == 0 { n as u64 } else { total };
1559 assign[cell as usize] = owner_of(before, w, tot, parts);
1560 before += w;
1561 }
1562 assign
1563}
1564
1565fn owner_of(before: u64, weight: u64, total: u64, parts: u32) -> u32 {
1566 if total == 0 || parts == 0 {
1567 return 0;
1568 }
1569 let num = (2u128 * u128::from(before) + u128::from(weight)) * u128::from(parts);
1570 let den = 2u128 * u128::from(total);
1571 let mut owner = (num / den) as u32;
1572 if owner >= parts {
1573 owner = parts - 1;
1574 }
1575 owner
1576}
1577
1578static SELECT_NS: AtomicU64 = AtomicU64::new(0);
1579static FM_NS: AtomicU64 = AtomicU64::new(0);
1580static COARSE_NS: AtomicU64 = AtomicU64::new(0);
1581static PACK_NS: AtomicU64 = AtomicU64::new(0);
1582static REPAIR_NS: AtomicU64 = AtomicU64::new(0);
1583static CHECK_NS: AtomicU64 = AtomicU64::new(0);
1584static SCHEDULE_NS: AtomicU64 = AtomicU64::new(0);
1585
1586pub fn profile_reset() {
1588 SELECT_NS.store(0, AtomicOrdering::Relaxed);
1589 FM_NS.store(0, AtomicOrdering::Relaxed);
1590 COARSE_NS.store(0, AtomicOrdering::Relaxed);
1591 PACK_NS.store(0, AtomicOrdering::Relaxed);
1592 REPAIR_NS.store(0, AtomicOrdering::Relaxed);
1593 CHECK_NS.store(0, AtomicOrdering::Relaxed);
1594 SCHEDULE_NS.store(0, AtomicOrdering::Relaxed);
1595}
1596
1597pub fn profile_ns() -> (u64, u64, u64, u64, u64, u64, u64) {
1606 (
1607 SELECT_NS.load(AtomicOrdering::Relaxed),
1608 FM_NS.load(AtomicOrdering::Relaxed),
1609 COARSE_NS.load(AtomicOrdering::Relaxed),
1610 PACK_NS.load(AtomicOrdering::Relaxed),
1611 REPAIR_NS.load(AtomicOrdering::Relaxed),
1612 CHECK_NS.load(AtomicOrdering::Relaxed),
1613 SCHEDULE_NS.load(AtomicOrdering::Relaxed),
1614 )
1615}
1616
1617fn axis_coord(geom: &RcbGeom, axis: usize, id: u32) -> f64 {
1618 match axis {
1619 0 => geom.x[id as usize],
1620 1 => geom.y[id as usize],
1621 _ => geom.z[id as usize],
1622 }
1623}
1624
1625fn coord_before(geom: &RcbGeom, axis: usize, a: u32, b: u32) -> bool {
1626 let ca = axis_coord(geom, axis, a);
1627 let cb = axis_coord(geom, axis, b);
1628 ca < cb || (ca == cb && a < b)
1629}
1630
1631fn partition_at(ids: &mut [u32], geom: &RcbGeom, axis: usize, lo: usize, hi: usize) -> usize {
1632 let mid = lo + (hi - lo) / 2;
1633 let a = ids[lo];
1634 let b = ids[mid];
1635 let c = ids[hi - 1];
1636 let pivot = if coord_before(geom, axis, a, b) {
1637 if coord_before(geom, axis, b, c) {
1638 b
1639 } else if coord_before(geom, axis, a, c) {
1640 c
1641 } else {
1642 a
1643 }
1644 } else if coord_before(geom, axis, a, c) {
1645 a
1646 } else if coord_before(geom, axis, b, c) {
1647 c
1648 } else {
1649 b
1650 };
1651 let mut pivot_at = lo;
1652 if ids[mid] == pivot {
1653 pivot_at = mid;
1654 } else if ids[hi - 1] == pivot {
1655 pivot_at = hi - 1;
1656 }
1657 ids.swap(pivot_at, hi - 1);
1658 let pivot = ids[hi - 1];
1659 let mut store = lo;
1660 for i in lo..hi - 1 {
1661 if coord_before(geom, axis, ids[i], pivot) {
1662 ids.swap(store, i);
1663 store += 1;
1664 }
1665 }
1666 ids.swap(store, hi - 1);
1667 store
1668}
1669
1670fn clamp_cut(cut: usize, n: usize) -> usize {
1671 if n <= 1 {
1672 return 0;
1673 }
1674 cut.clamp(1, n - 1)
1675}
1676
1677fn subset_cut(ids: &[u32], cut: usize, graph: &CellGraph, side: &mut [u8]) -> u64 {
1678 side.fill(0);
1679 for &id in &ids[..cut] {
1680 side[id as usize] = 1;
1681 }
1682 for &id in &ids[cut..] {
1683 side[id as usize] = 2;
1684 }
1685 let side_ref: &[u8] = side;
1686 let left = &ids[..cut];
1687 #[cfg(feature = "parallel")]
1688 {
1689 if crate::pool_width() > 1 && left.len() > 1 {
1690 use rayon::prelude::*;
1691 let chunk = work_chunk(left.len());
1692 return left
1693 .par_chunks(chunk)
1694 .map(|group| crossing_weight(group, graph, side_ref))
1695 .sum();
1696 }
1697 }
1698 crossing_weight(left, graph, side_ref)
1699}
1700
1701fn crossing_weight(group: &[u32], graph: &CellGraph, side: &[u8]) -> u64 {
1702 let mut crossed = 0u64;
1703 for &id in group {
1704 let lo = graph.offsets[id as usize] as usize;
1705 let hi = graph.offsets[id as usize + 1] as usize;
1706 for e in lo..hi {
1707 let nbr = graph.neighbor[e] as usize;
1708 if side[nbr] == 2 {
1709 crossed += graph.edge_weight[e];
1710 }
1711 }
1712 }
1713 crossed
1714}
1715
1716#[cfg(feature = "parallel")]
1717fn work_chunk(n: usize) -> usize {
1718 let threads = {
1719 #[cfg(feature = "parallel")]
1720 {
1721 crate::pool_width().max(1)
1722 }
1723 #[cfg(not(feature = "parallel"))]
1724 {
1725 1
1726 }
1727 };
1728 (n / threads).max(1)
1729}
1730
1731fn lightest_axis(
1734 ids: &mut [u32],
1735 geom: &RcbGeom,
1736 graph: &CellGraph,
1737 total: u64,
1738 parts: u32,
1739 parts_l: u32,
1740 prefer: usize,
1741) -> usize {
1742 let saved = ids.to_vec();
1743 let mut side = vec![0u8; graph.grid.ncell()];
1744 let mut best_score = u64::MAX;
1745 let mut best_order = saved.clone();
1746 let mut best_at = 0usize;
1747 for axis_try in 0..3 {
1748 ids.copy_from_slice(&saved);
1749 let at = clamp_cut(
1750 if total == 0 {
1751 ids.len() * parts_l as usize / parts.max(1) as usize
1752 } else {
1753 weighted_cut(ids, geom, axis_try, total, parts, parts_l)
1754 },
1755 ids.len(),
1756 );
1757 let score = subset_cut(ids, at, graph, &mut side);
1758 let better = score < best_score || (score == best_score && axis_try == prefer);
1759 if better {
1760 best_score = score;
1761 best_order.copy_from_slice(ids);
1762 best_at = at;
1763 }
1764 }
1765 ids.copy_from_slice(&best_order);
1766 best_at
1767}
1768
1769fn weighted_cut(
1776 ids: &mut [u32],
1777 geom: &RcbGeom,
1778 axis: usize,
1779 total: u64,
1780 parts: u32,
1781 parts_l: u32,
1782) -> usize {
1783 if total > 0 && ids_increase(ids) {
1784 if let Some(cut) = weighted_cut_bins(ids, geom, axis, total, parts, parts_l) {
1785 return cut;
1786 }
1787 }
1788 weighted_cut_quick(ids, geom, axis, total, parts, parts_l)
1789}
1790
1791fn ids_increase(ids: &[u32]) -> bool {
1792 ids.windows(2).all(|pair| pair[0] < pair[1])
1793}
1794
1795fn coord_i64(geom: &RcbGeom, axis: usize, id: u32) -> Option<i64> {
1796 let value = axis_coord(geom, axis, id);
1797 if !value.is_finite() {
1798 return None;
1799 }
1800 let whole = value as i64;
1801 if whole as f64 != value {
1802 return None;
1803 }
1804 Some(whole)
1805}
1806
1807fn weighted_cut_bins(
1808 ids: &mut [u32],
1809 geom: &RcbGeom,
1810 axis: usize,
1811 total: u64,
1812 parts: u32,
1813 parts_l: u32,
1814) -> Option<usize> {
1815 let n = ids.len();
1816 if n < 2 {
1817 return Some(clamp_cut(0, n));
1818 }
1819 let mut min_c = i64::MAX;
1820 let mut max_c = i64::MIN;
1821 for &id in ids.iter() {
1822 let c = coord_i64(geom, axis, id)?;
1823 min_c = min_c.min(c);
1824 max_c = max_c.max(c);
1825 }
1826 let bins = (max_c - min_c + 1) as usize;
1827 if bins == 0 || bins > n {
1828 return None;
1829 }
1830 let (hist_w, hist_n) = bin_hist(ids, geom, axis, min_c, bins)?;
1831 let mut before_w = 0u64;
1832 let mut before_n = 0usize;
1833 let mut cut_bin = None;
1834 for b in 0..bins {
1835 let w = hist_w[b];
1836 let count = hist_n[b];
1837 if count == 0 {
1838 continue;
1839 }
1840 if owner_of(before_w.saturating_add(w), 0, total, parts) < parts_l {
1841 before_w = before_w.saturating_add(w);
1842 before_n += count;
1843 continue;
1844 }
1845 cut_bin = Some((b, before_w, before_n));
1846 break;
1847 }
1848 let (cut_b, before_w, before_n) = cut_bin.unwrap_or((bins, before_w, before_n));
1849 let cut_c = min_c + cut_b as i64;
1850 let take = if cut_b >= bins || owner_of(before_w, 0, total, parts) >= parts_l {
1851 0
1852 } else {
1853 bin_take(ids, geom, axis, cut_c, before_w, total, parts, parts_l)
1854 };
1855 let light_n = before_n + take;
1856 let cut = clamp_cut(light_n, n);
1857 arrange_cut(ids, geom, axis, cut_c, take, cut);
1858 Some(cut)
1859}
1860
1861fn bin_hist(
1862 ids: &[u32],
1863 geom: &RcbGeom,
1864 axis: usize,
1865 min_c: i64,
1866 bins: usize,
1867) -> Option<(Vec<u64>, Vec<usize>)> {
1868 let one = |group: &[u32]| -> Option<(Vec<u64>, Vec<usize>)> {
1869 let mut weight = vec![0u64; bins];
1870 let mut count = vec![0usize; bins];
1871 for &id in group {
1872 let c = coord_i64(geom, axis, id)?;
1873 let b = (c - min_c) as usize;
1874 if b >= bins {
1875 return None;
1876 }
1877 weight[b] = weight[b].saturating_add(geom.w[id as usize]);
1878 count[b] += 1;
1879 }
1880 Some((weight, count))
1881 };
1882 #[cfg(feature = "parallel")]
1883 {
1884 if crate::pool_width() > 1 && ids.len() > 1 {
1885 use rayon::prelude::*;
1886 let chunk = work_chunk(ids.len());
1887 let parts: Vec<Option<(Vec<u64>, Vec<usize>)>> =
1888 ids.par_chunks(chunk).map(one).collect();
1889 let mut weight = vec![0u64; bins];
1890 let mut count = vec![0usize; bins];
1891 for part in parts {
1892 let (w, c) = part?;
1893 for b in 0..bins {
1894 weight[b] = weight[b].saturating_add(w[b]);
1895 count[b] += c[b];
1896 }
1897 }
1898 return Some((weight, count));
1899 }
1900 }
1901 one(ids)
1902}
1903
1904fn bin_take(
1905 ids: &[u32],
1906 geom: &RcbGeom,
1907 axis: usize,
1908 cut_c: i64,
1909 mut before_w: u64,
1910 total: u64,
1911 parts: u32,
1912 parts_l: u32,
1913) -> usize {
1914 let mut take = 0usize;
1915 for &id in ids {
1916 let Some(c) = coord_i64(geom, axis, id) else {
1917 continue;
1918 };
1919 if c != cut_c {
1920 continue;
1921 }
1922 let w = geom.w[id as usize];
1923 if owner_of(before_w, w, total, parts) >= parts_l {
1924 break;
1925 }
1926 before_w = before_w.saturating_add(w);
1927 take += 1;
1928 }
1929 take
1930}
1931
1932fn arrange_cut(ids: &mut [u32], geom: &RcbGeom, axis: usize, cut_c: i64, take: usize, cut: usize) {
1933 #[cfg(feature = "parallel")]
1934 if crate::pool_width() > 1 && ids.len() >= 4096 {
1935 arrange_cut_parallel(ids, geom, axis, cut_c, take);
1936 return;
1937 }
1938 let _ = cut;
1939 arrange_cut_serial(ids, geom, axis, cut_c, take);
1940}
1941
1942fn arrange_cut_serial(ids: &mut [u32], geom: &RcbGeom, axis: usize, cut_c: i64, take: usize) {
1945 let mut seen = 0usize;
1946 let mut light = Vec::with_capacity(ids.len());
1947 let mut heavy = Vec::with_capacity(ids.len());
1948 for &id in ids.iter() {
1949 let Some(c) = coord_i64(geom, axis, id) else {
1950 heavy.push(id);
1951 continue;
1952 };
1953 if c < cut_c || (c == cut_c && seen < take) {
1954 if c == cut_c {
1955 seen += 1;
1956 }
1957 light.push(id);
1958 } else {
1959 heavy.push(id);
1960 }
1961 }
1962 let n = light.len();
1963 ids[..n].copy_from_slice(&light);
1964 ids[n..].copy_from_slice(&heavy);
1965}
1966
1967#[cfg(feature = "parallel")]
1970fn arrange_cut_parallel(ids: &mut [u32], geom: &RcbGeom, axis: usize, cut_c: i64, take: usize) {
1971 use rayon::prelude::*;
1972 let chunk = work_chunk(ids.len());
1973 let groups: Vec<(Vec<u32>, Vec<u32>, Vec<u32>)> = ids
1974 .par_chunks(chunk)
1975 .map(|group| {
1976 let mut below = Vec::new();
1977 let mut equal = Vec::new();
1978 let mut above = Vec::new();
1979 for &id in group {
1980 match coord_i64(geom, axis, id) {
1981 Some(c) if c < cut_c => below.push(id),
1982 Some(c) if c == cut_c => equal.push(id),
1983 _ => above.push(id),
1984 }
1985 }
1986 (below, equal, above)
1987 })
1988 .collect();
1989 let mut below = Vec::new();
1990 let mut equal = Vec::new();
1991 let mut above = Vec::new();
1992 for (lo, mid, hi) in groups {
1993 below.extend(lo);
1994 equal.extend(mid);
1995 above.extend(hi);
1996 }
1997 let take = take.min(equal.len());
1998 let light_n = below.len() + take;
1999 ids[..below.len()].copy_from_slice(&below);
2000 ids[below.len()..light_n].copy_from_slice(&equal[..take]);
2001 let rest = equal.len() - take;
2002 ids[light_n..light_n + rest].copy_from_slice(&equal[take..]);
2003 ids[light_n + rest..].copy_from_slice(&above);
2004}
2005
2006fn slice_span(ids: &[u32], geom: &RcbGeom) -> ([f64; 3], [f64; 3], u64) {
2008 let one = |group: &[u32]| {
2009 let mut min = [f64::MAX; 3];
2010 let mut max = [f64::MIN; 3];
2011 let mut total = 0u64;
2012 for &id in group {
2013 let c = [
2014 geom.x[id as usize],
2015 geom.y[id as usize],
2016 geom.z[id as usize],
2017 ];
2018 for axis in 0..3 {
2019 min[axis] = min[axis].min(c[axis]);
2020 max[axis] = max[axis].max(c[axis]);
2021 }
2022 total = total.saturating_add(geom.w[id as usize]);
2023 }
2024 (min, max, total)
2025 };
2026 #[cfg(feature = "parallel")]
2027 if crate::pool_width() > 1 && ids.len() >= 4096 {
2028 use rayon::prelude::*;
2029 let chunk = work_chunk(ids.len());
2030 let parts: Vec<_> = ids.par_chunks(chunk).map(one).collect();
2031 let mut min = [f64::MAX; 3];
2032 let mut max = [f64::MIN; 3];
2033 let mut total = 0u64;
2034 for (lo, hi, weight) in parts {
2035 for axis in 0..3 {
2036 min[axis] = min[axis].min(lo[axis]);
2037 max[axis] = max[axis].max(hi[axis]);
2038 }
2039 total = total.saturating_add(weight);
2040 }
2041 return (min, max, total);
2042 }
2043 one(ids)
2044}
2045
2046fn weighted_cut_quick(
2047 ids: &mut [u32],
2048 geom: &RcbGeom,
2049 axis: usize,
2050 total: u64,
2051 parts: u32,
2052 parts_l: u32,
2053) -> usize {
2054 fn walk(
2055 ids: &mut [u32],
2056 geom: &RcbGeom,
2057 axis: usize,
2058 lo: usize,
2059 hi: usize,
2060 before: u64,
2061 total: u64,
2062 parts: u32,
2063 parts_l: u32,
2064 ) -> usize {
2065 if hi <= lo {
2066 return lo;
2067 }
2068 if hi - lo == 1 {
2069 let w = geom.w[ids[lo] as usize];
2070 return if owner_of(before, w, total, parts) >= parts_l {
2071 lo
2072 } else {
2073 lo + 1
2074 };
2075 }
2076 let pivot = partition_at(ids, geom, axis, lo, hi);
2077 let mut left_w = before;
2078 for id in &ids[lo..pivot] {
2079 left_w += geom.w[*id as usize];
2080 }
2081 let pivot_w = geom.w[ids[pivot] as usize];
2082 if owner_of(left_w, pivot_w, total, parts) >= parts_l {
2083 walk(ids, geom, axis, lo, pivot, before, total, parts, parts_l)
2084 } else {
2085 walk(
2086 ids,
2087 geom,
2088 axis,
2089 pivot + 1,
2090 hi,
2091 left_w + pivot_w,
2092 total,
2093 parts,
2094 parts_l,
2095 )
2096 }
2097 }
2098 let cut = walk(ids, geom, axis, 0, ids.len(), 0, total, parts, parts_l);
2099 cut.clamp(1, ids.len().saturating_sub(1))
2100}
2101
2102fn rcb_assign(graph: &CellGraph, parts: u32, refine_cuts: bool, ratio: (u64, u64)) -> Vec<u32> {
2103 let n = graph.grid.ncell();
2104 let t_pack = Instant::now();
2105 let mut x = vec![0.0f64; n];
2106 let mut y = vec![0.0f64; n];
2107 let mut z = vec![0.0f64; n];
2108 for c in 0..n {
2109 let (ix, iy, iz) = unravel(c, graph.grid.nx, graph.grid.ny);
2110 x[c] = f64::from(ix);
2111 y[c] = f64::from(iy);
2112 z[c] = f64::from(iz);
2113 }
2114 let geom = RcbGeom {
2115 x,
2116 y,
2117 z,
2118 w: graph.grid.weight.clone(),
2119 };
2120 let mut ids: Vec<u32> = (0..n as u32).collect();
2121 let mut out = vec![0u32; n];
2122 PACK_NS.fetch_add(t_pack.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
2123 let phase = rcb_slice(
2124 &mut ids,
2125 parts,
2126 0,
2127 &geom,
2128 SendPtr(out.as_mut_ptr()),
2129 graph,
2130 refine_cuts,
2131 ratio,
2132 );
2133 record_phase(phase);
2134 out
2135}
2136
2137#[derive(Clone, Copy)]
2138struct SendPtr(*mut u32);
2139unsafe impl Send for SendPtr {}
2140unsafe impl Sync for SendPtr {}
2141
2142#[derive(Clone, Copy, Default)]
2148struct Phase {
2149 select: u64,
2150 fm: u64,
2151 pack: u64,
2152 schedule: u64,
2153}
2154
2155#[cfg(feature = "parallel")]
2156fn phase_wall(phase: Phase) -> u64 {
2157 phase
2158 .select
2159 .saturating_add(phase.fm)
2160 .saturating_add(phase.pack)
2161 .saturating_add(phase.schedule)
2162}
2163
2164fn record_phase(phase: Phase) {
2165 SELECT_NS.fetch_add(phase.select, AtomicOrdering::Relaxed);
2166 FM_NS.fetch_add(phase.fm, AtomicOrdering::Relaxed);
2167 PACK_NS.fetch_add(phase.pack, AtomicOrdering::Relaxed);
2168 SCHEDULE_NS.fetch_add(phase.schedule, AtomicOrdering::Relaxed);
2169}
2170
2171#[cfg(feature = "parallel")]
2172fn join_measured(a: Phase, b: Phase, wall: u64) -> Phase {
2173 let sum_w = phase_wall(a).saturating_add(phase_wall(b));
2174 let max_w = phase_wall(a).max(phase_wall(b));
2175 let overlapped = wall.saturating_add(timer_resolution_ns()) < sum_w;
2179 let mut child = if overlapped {
2180 if phase_wall(a) >= phase_wall(b) {
2181 a
2182 } else {
2183 b
2184 }
2185 } else {
2186 Phase {
2187 select: a.select.saturating_add(b.select),
2188 fm: a.fm.saturating_add(b.fm),
2189 pack: a.pack.saturating_add(b.pack),
2190 schedule: a.schedule.saturating_add(b.schedule),
2191 }
2192 };
2193 let base = if overlapped { max_w } else { sum_w };
2194 if wall > base {
2195 child.schedule = child.schedule.saturating_add(wall - base);
2196 }
2197 child
2198}
2199
2200fn phase_join(a: Phase, b: Phase) -> Phase {
2201 #[cfg(feature = "parallel")]
2202 {
2203 if crate::pool_width() > 1 {
2204 return if phase_wall(a) >= phase_wall(b) { a } else { b };
2205 }
2206 }
2207 Phase {
2208 select: a.select.saturating_add(b.select),
2209 fm: a.fm.saturating_add(b.fm),
2210 pack: a.pack.saturating_add(b.pack),
2211 schedule: a.schedule.saturating_add(b.schedule),
2212 }
2213}
2214
2215fn phase_after(select_here: u64, fm_here: u64, pack_here: u64, child: Phase) -> Phase {
2216 Phase {
2217 select: select_here.saturating_add(child.select),
2218 fm: fm_here.saturating_add(child.fm),
2219 pack: pack_here.saturating_add(child.pack),
2220 schedule: child.schedule,
2221 }
2222}
2223
2224struct RcbGeom {
2225 x: Vec<f64>,
2226 y: Vec<f64>,
2227 z: Vec<f64>,
2228 w: Vec<u64>,
2229}
2230
2231fn rcb_slice(
2232 ids: &mut [u32],
2233 parts: u32,
2234 part0: u32,
2235 geom: &RcbGeom,
2236 out: SendPtr,
2237 graph: &CellGraph,
2238 refine_cuts: bool,
2239 ratio: (u64, u64),
2240) -> Phase {
2241 if ids.is_empty() {
2242 return Phase::default();
2243 }
2244 if parts <= 1 || ids.len() == 1 {
2245 let t_pack = Instant::now();
2246 for &id in ids.iter() {
2247 unsafe { out.0.add(id as usize).write(part0) };
2249 }
2250 return Phase {
2251 select: 0,
2252 fm: 0,
2253 pack: t_pack.elapsed().as_nanos() as u64,
2254 schedule: 0,
2255 };
2256 }
2257 let parts_l = parts / 2;
2258 let parts_r = parts - parts_l;
2259 let t_pack = Instant::now();
2260 let (min, max, total) = slice_span(ids, geom);
2261 let span = [max[0] - min[0], max[1] - min[1], max[2] - min[2]];
2262 let axis = if span[0] >= span[1] && span[0] >= span[2] {
2263 0
2264 } else if span[1] >= span[2] {
2265 1
2266 } else {
2267 2
2268 };
2269 let pack_span = t_pack.elapsed().as_nanos() as u64;
2270 let t_sel = Instant::now();
2271 let mut cut = if refine_cuts {
2272 lightest_axis(ids, geom, graph, total, parts, parts_l, axis)
2274 } else if total == 0 {
2275 ids.len() * parts_l as usize / parts as usize
2276 } else {
2277 weighted_cut(ids, geom, axis, total, parts, parts_l)
2278 };
2279 let select_here = t_sel.elapsed().as_nanos() as u64;
2280 if cut == 0 {
2281 cut = 1;
2282 }
2283 if cut >= ids.len() {
2284 cut = ids.len() - 1;
2285 }
2286 if !refine_cuts {
2289 let (left_ids, right_ids) = ids.split_at_mut(cut);
2290 let child = descend(
2291 left_ids,
2292 parts_l,
2293 part0,
2294 right_ids,
2295 parts_r,
2296 part0 + parts_l,
2297 geom,
2298 out,
2299 graph,
2300 refine_cuts,
2301 ratio,
2302 );
2303 return phase_after(select_here, 0, pack_span, child);
2304 }
2305 let t_side = Instant::now();
2306 let mut side = vec![1u8; ids.len()];
2307 for s in side.iter_mut().take(cut) {
2308 *s = 0;
2309 }
2310 let pack_side = t_side.elapsed().as_nanos() as u64;
2311 let t_fm = Instant::now();
2312 bipartition_fm(ids, &mut side, geom, graph, parts_l, parts_r, ratio);
2313 let fm_here = t_fm.elapsed().as_nanos() as u64;
2314 let t_split = Instant::now();
2315 let mut left = Vec::new();
2316 let mut right = Vec::new();
2317 for (i, &id) in ids.iter().enumerate() {
2318 if side[i] == 0 {
2319 left.push(id);
2320 } else {
2321 right.push(id);
2322 }
2323 }
2324 let pack_here = pack_span
2325 .saturating_add(pack_side)
2326 .saturating_add(t_split.elapsed().as_nanos() as u64);
2327 let child = if left.is_empty() || right.is_empty() {
2328 let (left_ids, right_ids) = ids.split_at_mut(cut);
2329 descend(
2330 left_ids,
2331 parts_l,
2332 part0,
2333 right_ids,
2334 parts_r,
2335 part0 + parts_l,
2336 geom,
2337 out,
2338 graph,
2339 refine_cuts,
2340 ratio,
2341 )
2342 } else {
2343 descend(
2344 &mut left,
2345 parts_l,
2346 part0,
2347 &mut right,
2348 parts_r,
2349 part0 + parts_l,
2350 geom,
2351 out,
2352 graph,
2353 refine_cuts,
2354 ratio,
2355 )
2356 };
2357 let t_drop = Instant::now();
2358 drop(left);
2359 drop(right);
2360 drop(side);
2361 let pack_drop = t_drop.elapsed().as_nanos() as u64;
2362 phase_after(
2363 select_here,
2364 fm_here,
2365 pack_here.saturating_add(pack_drop),
2366 child,
2367 )
2368}
2369
2370fn descend(
2371 left: &mut [u32],
2372 parts_l: u32,
2373 part_l: u32,
2374 right: &mut [u32],
2375 parts_r: u32,
2376 part_r: u32,
2377 geom: &RcbGeom,
2378 out: SendPtr,
2379 graph: &CellGraph,
2380 refine_cuts: bool,
2381 ratio: (u64, u64),
2382) -> Phase {
2383 #[cfg(feature = "parallel")]
2384 if crate::pool_width() > 1 {
2385 let left_out = out;
2386 let right_out = out;
2387 let t_join = Instant::now();
2388 let (a, b) = rayon::join(
2389 move || {
2390 rcb_slice(
2391 left,
2392 parts_l,
2393 part_l,
2394 geom,
2395 left_out,
2396 graph,
2397 refine_cuts,
2398 ratio,
2399 )
2400 },
2401 move || {
2402 rcb_slice(
2403 right,
2404 parts_r,
2405 part_r,
2406 geom,
2407 right_out,
2408 graph,
2409 refine_cuts,
2410 ratio,
2411 )
2412 },
2413 );
2414 let wall = t_join.elapsed().as_nanos() as u64;
2415 return join_measured(a, b, wall);
2416 }
2417 {
2418 let a = rcb_slice(left, parts_l, part_l, geom, out, graph, refine_cuts, ratio);
2419 let b = rcb_slice(right, parts_r, part_r, geom, out, graph, refine_cuts, ratio);
2420 phase_join(a, b)
2421 }
2422}
2423
2424fn bipartition_fm(
2426 ids: &[u32],
2427 side: &mut [u8],
2428 geom: &RcbGeom,
2429 graph: &CellGraph,
2430 parts_l: u32,
2431 parts_r: u32,
2432 ratio: (u64, u64),
2433) {
2434 let parts = parts_l + parts_r;
2435 if parts_l == 0 || parts_r == 0 {
2436 return;
2437 }
2438 let mut index = vec![usize::MAX; graph.grid.ncell()];
2439 let mut weight_l = 0u64;
2440 let mut weight_r = 0u64;
2441 for (i, &id) in ids.iter().enumerate() {
2442 index[id as usize] = i;
2443 if side[i] == 0 {
2444 weight_l += geom.w[id as usize];
2445 } else {
2446 weight_r += geom.w[id as usize];
2447 }
2448 }
2449 let total = weight_l + weight_r;
2450 loop {
2451 if !boundary_pass(
2452 ids,
2453 side,
2454 &index,
2455 geom,
2456 graph,
2457 parts_l,
2458 parts_r,
2459 parts,
2460 ratio,
2461 total,
2462 &mut weight_l,
2463 &mut weight_r,
2464 ) {
2465 break;
2466 }
2467 }
2468}
2469
2470fn side_limit(total: u64, side_parts: u32, parts: u32, ratio: (u64, u64)) -> u64 {
2471 if total == 0 || parts == 0 {
2472 return 0;
2473 }
2474 let (num, den) = ratio;
2475 let num = u128::from(total) * u128::from(side_parts) * u128::from(num);
2476 let den = u128::from(parts) * u128::from(den);
2477 (num / den) as u64
2478}
2479
2480fn cross_gain(slot: usize, ids: &[u32], side: &[u8], index: &[usize], graph: &CellGraph) -> i64 {
2481 let id = ids[slot] as usize;
2482 let src = side[slot];
2483 let mut to_src = 0i64;
2484 let mut to_dest = 0i64;
2485 let lo = graph.offsets[id] as usize;
2486 let hi = graph.offsets[id + 1] as usize;
2487 for e in lo..hi {
2488 let nbr = graph.neighbor[e] as usize;
2489 let other = index[nbr];
2490 if other == usize::MAX {
2491 continue;
2492 }
2493 let ww = graph.edge_weight[e] as i64;
2494 if side[other] == src {
2495 to_src += ww;
2496 } else {
2497 to_dest += ww;
2498 }
2499 }
2500 to_dest - to_src
2501}
2502
2503fn side_fits(
2504 slot: usize,
2505 ids: &[u32],
2506 side: &[u8],
2507 geom: &RcbGeom,
2508 weight_l: u64,
2509 weight_r: u64,
2510 limit_l: u64,
2511 limit_r: u64,
2512) -> bool {
2513 let w = geom.w[ids[slot] as usize];
2514 let (new_l, new_r) = if side[slot] == 0 {
2515 (weight_l - w, weight_r + w)
2516 } else {
2517 (weight_l + w, weight_r - w)
2518 };
2519 new_l <= limit_l && new_r <= limit_r
2520}
2521
2522#[allow(dead_code)]
2523fn bucket_drop(slot: usize, bins: &mut BTreeMap<i64, Vec<u32>>, loc: &mut [Option<(i64, usize)>]) {
2524 let Some((gain, at)) = loc[slot] else { return };
2525 let bin = bins.get_mut(&gain).unwrap();
2526 let last = bin.len() - 1;
2527 bin.swap(at, last);
2528 let moved = bin[at] as usize;
2529 if moved != slot {
2530 if let Some(entry) = loc[moved].as_mut() {
2531 entry.1 = at;
2532 }
2533 }
2534 bin.pop();
2535 if bin.is_empty() {
2536 bins.remove(&gain);
2537 }
2538 loc[slot] = None;
2539}
2540
2541#[allow(dead_code)]
2542fn bucket_add(
2543 slot: usize,
2544 bins: &mut BTreeMap<i64, Vec<u32>>,
2545 loc: &mut [Option<(i64, usize)>],
2546 ids: &[u32],
2547 side: &[u8],
2548 index: &[usize],
2549 graph: &CellGraph,
2550 geom: &RcbGeom,
2551 locked: &[bool],
2552 weight_l: u64,
2553 weight_r: u64,
2554 limit_l: u64,
2555 limit_r: u64,
2556) {
2557 if locked[slot] {
2558 return;
2559 }
2560 bucket_drop(slot, bins, loc);
2561 if !is_boundary(slot, ids, side, index, graph) {
2562 return;
2563 }
2564 if !side_fits(slot, ids, side, geom, weight_l, weight_r, limit_l, limit_r) {
2565 return;
2566 }
2567 let gain = cross_gain(slot, ids, side, index, graph);
2568 let bin = bins.entry(gain).or_default();
2569 loc[slot] = Some((gain, bin.len()));
2570 bin.push(slot as u32);
2571}
2572
2573#[allow(dead_code)]
2574fn boundary_pass(
2575 ids: &[u32],
2576 side: &mut [u8],
2577 index: &[usize],
2578 geom: &RcbGeom,
2579 graph: &CellGraph,
2580 parts_l: u32,
2581 parts_r: u32,
2582 parts: u32,
2583 ratio: (u64, u64),
2584 total: u64,
2585 weight_l: &mut u64,
2586 weight_r: &mut u64,
2587) -> bool {
2588 let t0 = Instant::now();
2589 let n = ids.len();
2590 let limit_l = side_limit(total, parts_l, parts, ratio);
2591 let limit_r = side_limit(total, parts_r, parts, ratio);
2592 let mut locked = vec![false; n];
2593 let mut loc: Vec<Option<(i64, usize)>> = vec![None; n];
2594 let mut bins: BTreeMap<i64, Vec<u32>> = BTreeMap::new();
2595 let gains = bisect_gains(
2598 ids, side, index, graph, geom, *weight_l, *weight_r, limit_l, limit_r,
2599 );
2600 for slot in 0..n {
2601 let Some(gain) = gains[slot] else {
2602 continue;
2603 };
2604 let bin = bins.entry(gain).or_default();
2605 loc[slot] = Some((gain, bin.len()));
2606 bin.push(slot as u32);
2607 }
2608 let mut moves: Vec<(usize, u8)> = Vec::new();
2609 let mut cum: i128 = 0;
2610 let mut best: i128 = 0;
2611 let mut best_len = 0usize;
2612 let heaviest = ids.iter().map(|&id| geom.w[id as usize]).max().unwrap_or(1);
2615 let mut neg_left = heaviest.max(1) as usize;
2616 while let Some((&gain, _)) = bins.iter().next_back() {
2617 if gain <= 0 {
2618 neg_left = neg_left.saturating_sub(1);
2619 if neg_left == 0 {
2620 break;
2621 }
2622 }
2623 let bin = bins.get_mut(&gain).unwrap();
2624 let slot = bin.pop().unwrap() as usize;
2625 if bin.is_empty() {
2626 bins.remove(&gain);
2627 }
2628 loc[slot] = None;
2629 if locked[slot] {
2630 continue;
2631 }
2632 if !side_fits(
2633 slot, ids, side, geom, *weight_l, *weight_r, limit_l, limit_r,
2634 ) {
2635 continue;
2636 }
2637 let fresh = cross_gain(slot, ids, side, index, graph);
2638 if fresh != gain {
2639 bucket_add(
2640 slot, &mut bins, &mut loc, ids, side, index, graph, geom, &locked, *weight_l,
2641 *weight_r, limit_l, limit_r,
2642 );
2643 continue;
2644 }
2645 let id = ids[slot] as usize;
2646 let w = geom.w[id];
2647 let src = side[slot];
2648 if src == 0 {
2649 *weight_l -= w;
2650 *weight_r += w;
2651 side[slot] = 1;
2652 } else {
2653 *weight_r -= w;
2654 *weight_l += w;
2655 side[slot] = 0;
2656 }
2657 locked[slot] = true;
2658 moves.push((slot, src));
2659 cum += i128::from(fresh);
2660 if cum > best {
2661 best = cum;
2662 best_len = moves.len();
2663 }
2664 let lo = graph.offsets[id] as usize;
2665 let hi = graph.offsets[id + 1] as usize;
2666 for e in lo..hi {
2667 let other = index[graph.neighbor[e] as usize];
2668 if other != usize::MAX && !locked[other] {
2669 bucket_add(
2670 other, &mut bins, &mut loc, ids, side, index, graph, geom, &locked, *weight_l,
2671 *weight_r, limit_l, limit_r,
2672 );
2673 }
2674 }
2675 }
2676 if best <= 0 {
2677 best_len = 0;
2678 }
2679 for &(slot, src) in moves
2680 .iter()
2681 .rev()
2682 .take(moves.len().saturating_sub(best_len))
2683 {
2684 let id = ids[slot] as usize;
2685 let w = geom.w[id];
2686 if side[slot] == 0 {
2687 *weight_l -= w;
2688 *weight_r += w;
2689 } else {
2690 *weight_r -= w;
2691 *weight_l += w;
2692 }
2693 side[slot] = src;
2694 }
2695 let _ = t0;
2696 best > 0
2697}
2698
2699fn is_boundary(slot: usize, ids: &[u32], side: &[u8], index: &[usize], graph: &CellGraph) -> bool {
2700 let id = ids[slot] as usize;
2701 let src = side[slot];
2702 let lo = graph.offsets[id] as usize;
2703 let hi = graph.offsets[id + 1] as usize;
2704 for e in lo..hi {
2705 let other = index[graph.neighbor[e] as usize];
2706 if other != usize::MAX && side[other] != src {
2707 return true;
2708 }
2709 }
2710 false
2711}
2712
2713fn bisect_gains(
2714 ids: &[u32],
2715 side: &[u8],
2716 index: &[usize],
2717 graph: &CellGraph,
2718 geom: &RcbGeom,
2719 weight_l: u64,
2720 weight_r: u64,
2721 limit_l: u64,
2722 limit_r: u64,
2723) -> Vec<Option<i64>> {
2724 let n = ids.len();
2725 let one = |slot: usize| -> Option<i64> {
2726 if !is_boundary(slot, ids, side, index, graph) {
2727 return None;
2728 }
2729 if !side_fits(slot, ids, side, geom, weight_l, weight_r, limit_l, limit_r) {
2730 return None;
2731 }
2732 Some(cross_gain(slot, ids, side, index, graph))
2733 };
2734 #[cfg(feature = "parallel")]
2735 {
2736 if crate::pool_width() > 1 {
2739 use rayon::prelude::*;
2740 return (0..n).into_par_iter().map(one).collect();
2741 }
2742 }
2743 (0..n).map(one).collect()
2744}
2745
2746fn refine(assign: &mut [u32], graph: &CellGraph, parts: u32, ratio: (u64, u64)) {
2747 if parts <= 1 {
2748 return;
2749 }
2750 let t0 = Instant::now();
2751 let weight = &graph.grid.weight;
2752 let mut part_w = vec![0u64; parts as usize];
2753 for (c, &d) in assign.iter().enumerate() {
2754 part_w[d as usize] += weight[c];
2755 }
2756 let total: u64 = part_w.iter().copied().sum();
2757 loop {
2758 if !fm_pass(assign, graph, parts, ratio, &mut part_w, total, weight) {
2759 break;
2760 }
2761 }
2762 FM_NS.fetch_add(t0.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
2763}
2764
2765fn kway_proposal(
2766 assign: &[u32],
2767 graph: &CellGraph,
2768 parts: u32,
2769 ratio: (u64, u64),
2770 part_w: &[u64],
2771 total: u64,
2772 weight: &[u64],
2773) -> Vec<Option<(i64, u32)>> {
2774 let n = assign.len();
2775 let one = |cell: usize| -> Option<(i64, u32)> {
2776 if !part_boundary(cell, assign, graph) {
2777 return None;
2778 }
2779 let mut scratch = vec![0u64; parts as usize];
2780 best_move(
2781 cell as u32,
2782 assign,
2783 graph,
2784 parts,
2785 ratio,
2786 part_w,
2787 total,
2788 weight,
2789 &mut scratch,
2790 )
2791 };
2792 #[cfg(feature = "parallel")]
2793 {
2794 if crate::pool_width() > 1 {
2797 use rayon::prelude::*;
2798 return (0..n).into_par_iter().map(one).collect();
2799 }
2800 }
2801 (0..n).map(one).collect()
2802}
2803
2804#[allow(dead_code)]
2805#[derive(Clone, Copy, Eq, PartialEq)]
2806struct Cand {
2807 gain: i64,
2808 cell: u32,
2809 dest: u32,
2810 stamp: u32,
2811}
2812
2813impl Ord for Cand {
2814 fn cmp(&self, other: &Self) -> Ordering {
2815 self.gain
2816 .cmp(&other.gain)
2817 .then(other.cell.cmp(&self.cell))
2818 .then(other.dest.cmp(&self.dest))
2819 }
2820}
2821
2822impl PartialOrd for Cand {
2823 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2824 Some(self.cmp(other))
2825 }
2826}
2827
2828#[allow(dead_code)]
2829fn fm_pass(
2830 assign: &mut [u32],
2831 graph: &CellGraph,
2832 parts: u32,
2833 ratio: (u64, u64),
2834 part_w: &mut [u64],
2835 total: u64,
2836 weight: &[u64],
2837) -> bool {
2838 let t0 = Instant::now();
2839 let n = assign.len();
2840 let mut locked = vec![false; n];
2841 let mut stamp = vec![0u32; n];
2842 let mut heap: BinaryHeap<Cand> = BinaryHeap::new();
2843 let mut scratch = vec![0u64; parts as usize];
2844 let proposal = kway_proposal(assign, graph, parts, ratio, part_w, total, weight);
2847 for cell in 0..n {
2848 let Some((gain, dest)) = proposal[cell] else {
2849 continue;
2850 };
2851 stamp[cell] = stamp[cell].wrapping_add(1);
2852 heap.push(Cand {
2853 gain,
2854 cell: cell as u32,
2855 dest,
2856 stamp: stamp[cell],
2857 });
2858 }
2859 let mut moves: Vec<(u32, u32, u32)> = Vec::new();
2860 let mut cum: i128 = 0;
2861 let mut best: i128 = 0;
2862 let mut best_len = 0usize;
2863 let heaviest = weight.iter().copied().max().unwrap_or(1);
2864 let mut neg_left = heaviest.max(1) as usize;
2865 while let Some(cand) = heap.pop() {
2866 if cand.gain <= 0 {
2867 neg_left = neg_left.saturating_sub(1);
2868 if neg_left == 0 {
2869 break;
2870 }
2871 }
2872 let cell = cand.cell as usize;
2873 if locked[cell] || stamp[cell] != cand.stamp {
2874 continue;
2875 }
2876 let fresh = best_move(
2877 cand.cell,
2878 assign,
2879 graph,
2880 parts,
2881 ratio,
2882 part_w,
2883 total,
2884 weight,
2885 &mut scratch,
2886 );
2887 let Some((gain, dest)) = fresh else {
2888 continue;
2889 };
2890 if gain != cand.gain || dest != cand.dest {
2891 stamp[cell] = stamp[cell].wrapping_add(1);
2892 heap.push(Cand {
2893 gain,
2894 cell: cand.cell,
2895 dest,
2896 stamp: stamp[cell],
2897 });
2898 continue;
2899 }
2900 let src = assign[cell];
2901 let w = weight[cell];
2902 part_w[src as usize] -= w;
2903 part_w[dest as usize] += w;
2904 assign[cell] = dest;
2905 locked[cell] = true;
2906 moves.push((cand.cell, src, dest));
2907 cum += i128::from(gain);
2908 if cum > best {
2909 best = cum;
2910 best_len = moves.len();
2911 }
2912 let lo = graph.offsets[cell] as usize;
2913 let hi = graph.offsets[cell + 1] as usize;
2914 for e in lo..hi {
2915 let nbr = graph.neighbor[e] as usize;
2916 if !locked[nbr] {
2917 push_best(
2918 nbr as u32,
2919 assign,
2920 graph,
2921 parts,
2922 ratio,
2923 part_w,
2924 total,
2925 weight,
2926 &locked,
2927 &mut stamp,
2928 &mut scratch,
2929 &mut heap,
2930 );
2931 }
2932 }
2933 }
2934 if best <= 0 {
2935 best_len = 0;
2936 }
2937 for (cell, src, dest) in moves.iter().rev().take(moves.len() - best_len) {
2938 let w = weight[*cell as usize];
2939 part_w[*dest as usize] -= w;
2940 part_w[*src as usize] += w;
2941 assign[*cell as usize] = *src;
2942 }
2943 let _ = t0;
2944 best > 0
2945}
2946
2947fn part_boundary(cell: usize, assign: &[u32], graph: &CellGraph) -> bool {
2948 let src = assign[cell];
2949 let lo = graph.offsets[cell] as usize;
2950 let hi = graph.offsets[cell + 1] as usize;
2951 for e in lo..hi {
2952 if assign[graph.neighbor[e] as usize] != src {
2953 return true;
2954 }
2955 }
2956 false
2957}
2958
2959#[allow(dead_code)]
2960fn push_best(
2961 cell: u32,
2962 assign: &[u32],
2963 graph: &CellGraph,
2964 parts: u32,
2965 ratio: (u64, u64),
2966 part_w: &[u64],
2967 total: u64,
2968 weight: &[u64],
2969 locked: &[bool],
2970 stamp: &mut [u32],
2971 scratch: &mut [u64],
2972 heap: &mut BinaryHeap<Cand>,
2973) {
2974 if locked[cell as usize] || !part_boundary(cell as usize, assign, graph) {
2975 return;
2976 }
2977 let Some((gain, dest)) = best_move(
2978 cell, assign, graph, parts, ratio, part_w, total, weight, scratch,
2979 ) else {
2980 return;
2981 };
2982 stamp[cell as usize] = stamp[cell as usize].wrapping_add(1);
2983 heap.push(Cand {
2984 gain,
2985 cell,
2986 dest,
2987 stamp: stamp[cell as usize],
2988 });
2989}
2990
2991fn best_move(
2992 cell: u32,
2993 assign: &[u32],
2994 graph: &CellGraph,
2995 parts: u32,
2996 ratio: (u64, u64),
2997 part_w: &[u64],
2998 total: u64,
2999 weight: &[u64],
3000 scratch: &mut [u64],
3001) -> Option<(i64, u32)> {
3002 scratch.fill(0);
3003 let src = assign[cell as usize];
3004 let lo = graph.offsets[cell as usize] as usize;
3005 let hi = graph.offsets[cell as usize + 1] as usize;
3006 for e in lo..hi {
3007 let nbr = graph.neighbor[e] as usize;
3008 let part = assign[nbr] as usize;
3009 scratch[part] = scratch[part].saturating_add(graph.edge_weight[e]);
3010 }
3011 let w = weight[cell as usize];
3012 let mut best: Option<(i64, u32)> = None;
3013 for dest in 0..parts {
3014 if dest == src {
3015 continue;
3016 }
3017 let new_src = part_w[src as usize] - w;
3018 let new_dest = part_w[dest as usize] + w;
3019 if !under_balance(new_src, total, parts, ratio)
3020 || !under_balance(new_dest, total, parts, ratio)
3021 {
3022 continue;
3023 }
3024 let gain = scratch[dest as usize] as i64 - scratch[src as usize] as i64;
3025 let take = match best {
3026 None => true,
3027 Some((g, d)) => gain > g || (gain == g && dest < d),
3028 };
3029 if take {
3030 best = Some((gain, dest));
3031 }
3032 }
3033 best
3034}
3035
3036fn scotch_assign(graph: &CellGraph, parts: u32, ratio: (u64, u64)) -> Result<Vec<u32>, Error> {
3037 #[cfg(not(feature = "scotch"))]
3038 {
3039 let _ = (graph, parts, ratio);
3040 Err(Error::ScotchDisabled)
3041 }
3042 #[cfg(feature = "scotch")]
3043 {
3044 scotch_assign_linked(graph, parts, ratio)
3045 }
3046}
3047
3048#[cfg(feature = "scotch")]
3049fn scotch_assign_linked(
3050 graph: &CellGraph,
3051 parts: u32,
3052 ratio: (u64, u64),
3053) -> Result<Vec<u32>, Error> {
3054 let n = graph.grid.ncell();
3055 if n > i32::MAX as usize || parts > i32::MAX as u32 {
3056 return Err(Error::Overflow);
3057 }
3058 let mut offsets = Vec::with_capacity(n + 1);
3059 let mut edges = Vec::with_capacity(graph.neighbor.len());
3060 let mut vwgt = Vec::with_capacity(n);
3061 let mut ewgt = Vec::with_capacity(graph.edge_weight.len());
3062 for &v in &graph.offsets {
3063 if v > i32::MAX as u32 {
3064 return Err(Error::Overflow);
3065 }
3066 offsets.push(v as i32);
3067 }
3068 for &v in &graph.neighbor {
3069 if v > i32::MAX as u32 {
3070 return Err(Error::Overflow);
3071 }
3072 edges.push(v as i32);
3073 }
3074 for &v in &graph.grid.weight {
3075 if v > i32::MAX as u64 {
3076 return Err(Error::Overflow);
3077 }
3078 vwgt.push(v as i32);
3079 }
3080 for &v in &graph.edge_weight {
3081 if v > i32::MAX as u64 {
3082 return Err(Error::Overflow);
3083 }
3084 ewgt.push(v as i32);
3085 }
3086 let mut part = vec![0i32; n];
3087 let (num, den) = ratio;
3088 let imbalance = (num - den) as f64 / den as f64;
3089 let rc = unsafe {
3090 lc_scotch_part(
3091 n as i32,
3092 offsets.as_ptr(),
3093 edges.as_ptr(),
3094 vwgt.as_ptr(),
3095 ewgt.as_ptr(),
3096 parts as i32,
3097 imbalance,
3098 part.as_mut_ptr(),
3099 )
3100 };
3101 if rc != 0 {
3102 return Err(Error::ScotchFailed);
3103 }
3104 let mut out = Vec::with_capacity(n);
3105 for v in part {
3106 if v < 0 || v as u32 >= parts {
3107 return Err(Error::ScotchFailed);
3108 }
3109 out.push(v as u32);
3110 }
3111 Ok(out)
3112}
3113
3114#[cfg(feature = "scotch")]
3115unsafe extern "C" {
3116 fn lc_scotch_part(
3117 n: i32,
3118 offsets: *const i32,
3119 edges: *const i32,
3120 vwgt: *const i32,
3121 ewgt: *const i32,
3122 parts: i32,
3123 imbalance: f64,
3124 part: *mut i32,
3125 ) -> i32;
3126}
3127
3128fn max_imbalance(weight: &[u64], assign: &[u32], parts: u32) -> f64 {
3129 let mut part_w = vec![0u64; parts as usize];
3130 let mut total = 0u64;
3131 for (c, &d) in assign.iter().enumerate() {
3132 part_w[d as usize] += weight[c];
3133 total += weight[c];
3134 }
3135 if total == 0 {
3136 return 1.0;
3137 }
3138 let mean = total as f64 / parts as f64;
3139 let heavy = part_w.iter().copied().max().unwrap_or(0) as f64;
3140 heavy / mean
3141}
3142
3143fn halo_fraction(
3144 grid: &CellGrid,
3145 assign: &[u32],
3146 parts: u32,
3147 width: [u32; 3],
3148) -> Result<f64, Error> {
3149 let mut best = 0.0f64;
3150 for domain in 0..parts {
3151 let owned = assign.iter().filter(|&&d| d == domain).count();
3152 if owned == 0 {
3153 continue;
3154 }
3155 let ghosts = halo(grid, assign, domain, width)?.len();
3156 let ratio = ghosts as f64 / owned as f64;
3157 if ratio > best {
3158 best = ratio;
3159 }
3160 }
3161 Ok(best)
3162}
3163
3164fn balance_ratio(balance: Option<f64>, weight: &[u64], parts: u32) -> Result<(u64, u64), Error> {
3165 match balance {
3166 None => Ok(derived_balance(weight, parts)),
3167 Some(value) => {
3168 if !value.is_finite() || value < 1.0 {
3169 return Err(Error::BadPartition);
3170 }
3171 let den = 1_000_000u64;
3173 let scaled = value * den as f64;
3174 if !scaled.is_finite() || scaled > u64::MAX as f64 {
3175 return Err(Error::BadPartition);
3176 }
3177 let num = scaled.round() as u64;
3178 if num < den {
3179 return Err(Error::BadPartition);
3180 }
3181 Ok((num, den))
3182 }
3183 }
3184}
3185
3186fn under_balance(weight: u64, total: u64, parts: u32, ratio: (u64, u64)) -> bool {
3187 if total == 0 {
3188 return true;
3189 }
3190 let (num, den) = ratio;
3191 u128::from(weight) * u128::from(parts) * u128::from(den) <= u128::from(total) * u128::from(num)
3192}
3193
3194fn bins_needed(length: f64, width: f64) -> Result<u32, Error> {
3195 if length.partial_cmp(&0.0) != Some(Ordering::Greater)
3197 || width.partial_cmp(&0.0) != Some(Ordering::Greater)
3198 {
3199 return Ok(0);
3200 }
3201 let q = length / width;
3202 if !q.is_finite() {
3203 return Err(Error::Overflow);
3204 }
3205 let ceil = q.ceil();
3206 if !ceil.is_finite() || ceil > u32::MAX as f64 {
3207 return Err(Error::Overflow);
3208 }
3209 let mut n = ceil as u32;
3210 while (n as f64) * width < length {
3211 n = n.saturating_add(1);
3212 if n == u32::MAX {
3213 break;
3214 }
3215 }
3216 Ok(n)
3217}
3218
3219fn check_graph(graph: &CellGraph) -> Result<usize, Error> {
3220 let n = graph.grid.ncell();
3221 if graph.grid.nx <= 0 || graph.grid.ny <= 0 || graph.grid.nz <= 0 {
3222 return Err(Error::BadGraph);
3223 }
3224 let expect = (graph.grid.nx as usize)
3225 .checked_mul(graph.grid.ny as usize)
3226 .and_then(|v| v.checked_mul(graph.grid.nz as usize))
3227 .ok_or(Error::BadGraph)?;
3228 if expect != n || graph.offsets.len() != n + 1 || graph.offsets[0] != 0 {
3229 return Err(Error::BadGraph);
3230 }
3231 if !offsets_increase(&graph.offsets) {
3232 return Err(Error::BadGraph);
3233 }
3234 let narc = graph.offsets[n] as usize;
3235 if graph.neighbor.len() != narc || graph.edge_weight.len() != narc {
3236 return Err(Error::BadGraph);
3237 }
3238 if !neighbors_in_range(&graph.neighbor, n) {
3239 return Err(Error::BadGraph);
3240 }
3241 Ok(n)
3242}
3243
3244fn offsets_increase(offsets: &[u32]) -> bool {
3245 let check = |start: usize, part: &[u32]| -> bool {
3246 let mut prev = if start == 0 { 0 } else { offsets[start - 1] };
3247 for &off in part {
3248 if off < prev {
3249 return false;
3250 }
3251 prev = off;
3252 }
3253 true
3254 };
3255 #[cfg(feature = "parallel")]
3256 {
3257 if crate::pool_width() > 1 && offsets.len() > 1 {
3258 use rayon::prelude::*;
3259 let chunk = work_chunk(offsets.len());
3260 return offsets
3261 .par_chunks(chunk)
3262 .enumerate()
3263 .all(|(index, part)| check(index * chunk, part));
3264 }
3265 }
3266 check(0, offsets)
3267}
3268
3269fn neighbors_in_range(neighbor: &[u32], n: usize) -> bool {
3270 let inside = |part: &[u32]| part.iter().all(|&nbr| (nbr as usize) < n);
3271 #[cfg(feature = "parallel")]
3272 {
3273 if crate::pool_width() > 1 && neighbor.len() > 1 {
3274 use rayon::prelude::*;
3275 let chunk = work_chunk(neighbor.len());
3276 return neighbor.par_chunks(chunk).all(inside);
3277 }
3278 }
3279 inside(neighbor)
3280}
3281
3282fn check_assign(grid: &CellGrid, assign: &[u32]) -> Result<usize, Error> {
3283 let n = grid.ncell();
3284 if assign.len() != n {
3285 return Err(Error::BadPartition);
3286 }
3287 let expect = (grid.nx as usize)
3288 .saturating_mul(grid.ny as usize)
3289 .saturating_mul(grid.nz as usize);
3290 if expect != n {
3291 return Err(Error::BadGraph);
3292 }
3293 Ok(n)
3294}
3295
3296fn unravel(c: usize, nx: i32, ny: i32) -> (i32, i32, i32) {
3297 let nx = nx as usize;
3298 let ny = ny as usize;
3299 let ix = (c % nx) as i32;
3300 let iy = ((c / nx) % ny) as i32;
3301 let iz = (c / (nx * ny)) as i32;
3302 (ix, iy, iz)
3303}
3304
3305fn paint(mark: &mut [u8], nx: i32, ny: i32, nz: i32, ix: i32, iy: i32, iz: i32, width: [u32; 3]) {
3306 let rx = width[0] as i32;
3307 let ry = width[1] as i32;
3308 let rz = width[2] as i32;
3309 for dz in -rz..=rz {
3310 for dy in -ry..=ry {
3311 for dx in -rx..=rx {
3312 let x = rem_euclid(ix + dx, nx);
3313 let y = rem_euclid(iy + dy, ny);
3314 let z = rem_euclid(iz + dz, nz);
3315 let c = ((z as usize * ny as usize) + y as usize) * nx as usize + x as usize;
3316 mark[c] = 1;
3317 }
3318 }
3319 }
3320}
3321
3322fn rem_euclid(v: i32, n: i32) -> i32 {
3323 let mut r = v % n;
3324 if r < 0 {
3325 r += n;
3326 }
3327 r
3328}
3329
3330fn morton_ord(a: u32, b: u32, grid: &CellGrid) -> Ordering {
3331 let (ax, ay, az) = unravel(a as usize, grid.nx, grid.ny);
3332 let (bx, by, bz) = unravel(b as usize, grid.nx, grid.ny);
3333 morton_cmp(
3334 [ax as u32, ay as u32, az as u32],
3335 [bx as u32, by as u32, bz as u32],
3336 )
3337}
3338
3339pub fn morton_cmp(a: [u32; 3], b: [u32; 3]) -> Ordering {
3344 for bit in (0..32).rev() {
3345 let mask = 1u32 << bit;
3346 let az = a[2] & mask;
3347 let bz = b[2] & mask;
3348 if az != bz {
3349 return az.cmp(&bz);
3350 }
3351 let ay = a[1] & mask;
3352 let by = b[1] & mask;
3353 if ay != by {
3354 return ay.cmp(&by);
3355 }
3356 let ax = a[0] & mask;
3357 let bx = b[0] & mask;
3358 if ax != bx {
3359 return ax.cmp(&bx);
3360 }
3361 }
3362 Ordering::Equal
3363}
3364
3365pub fn morton_key(x: u32, y: u32, z: u32) -> Option<u64> {
3367 if x >= (1 << 21) || y >= (1 << 21) || z >= (1 << 21) {
3368 return None;
3369 }
3370 Some(spread21(x) | (spread21(y) << 1) | (spread21(z) << 2))
3371}
3372
3373fn spread21(v: u32) -> u64 {
3374 let mut x = u64::from(v & 0x1f_ffff);
3375 x = (x | (x << 32)) & 0x001f_0000_0000_ffff;
3376 x = (x | (x << 16)) & 0x001f_0000_ff00_00ff;
3377 x = (x | (x << 8)) & 0x100f_00f0_0f00_f00f;
3378 x = (x | (x << 4)) & 0x10c3_0c30_c30c_30c3;
3379 x = (x | (x << 2)) & 0x1249_2492_4924_9249;
3380 x
3381}
3382
3383fn hilbert_bits(nx: i32, ny: i32, nz: i32) -> u32 {
3384 let n = (nx as u32).max(ny as u32).max(nz as u32);
3385 if n <= 1 {
3386 0
3387 } else {
3388 32 - (n - 1).leading_zeros()
3389 }
3390}
3391
3392pub fn hilbert_key(x: u32, y: u32, z: u32, bits: u32) -> u64 {
3394 if bits == 0 {
3395 return 0;
3396 }
3397 let mut p = [x, y, z];
3398 let mut q = 1u32 << (bits - 1);
3399 while q > 1 {
3400 let mask = q - 1;
3401 for i in 0..3 {
3402 if p[i] & q != 0 {
3403 p[0] ^= mask;
3404 } else {
3405 let t = (p[0] ^ p[i]) & mask;
3406 p[0] ^= t;
3407 p[i] ^= t;
3408 }
3409 }
3410 q >>= 1;
3411 }
3412 p[1] ^= p[0];
3413 p[2] ^= p[1];
3414 let mut t = 0u32;
3415 q = 1u32 << (bits - 1);
3416 while q > 1 {
3417 if p[2] & q != 0 {
3418 t ^= q - 1;
3419 }
3420 q >>= 1;
3421 }
3422 for v in &mut p {
3423 *v ^= t;
3424 }
3425 let mut key = 0u64;
3426 for b in (0..bits).rev() {
3427 for v in &p {
3428 key = (key << 1) | u64::from((v >> b) & 1);
3429 }
3430 }
3431 key
3432}
3433
3434pub fn histogram(bins_of: &[u32], ncell: usize) -> Vec<u64> {
3436 let mut weight = vec![0u64; ncell];
3437 for &b in bins_of {
3438 weight[b as usize] += 1;
3439 }
3440 weight
3441}
3442
3443pub fn exclusive_prefix(values: &[u64]) -> Vec<u64> {
3445 let mut out = vec![0u64; values.len() + 1];
3446 for (i, &v) in values.iter().enumerate() {
3447 out[i + 1] = out[i] + v;
3448 }
3449 out
3450}
3451
3452pub type DeviceCurveFn = unsafe extern "C" fn(
3457 atom_bin: *const u32,
3458 natom: usize,
3459 coords: *const u32,
3460 ncell: usize,
3461 parts: u32,
3462 assign: *mut u32,
3463 out_weight: *mut u64,
3464 method: u8,
3465) -> i32;
3466
3467static DEVICE_CURVE: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);
3468
3469pub fn register_device_curve(f: Option<DeviceCurveFn>) {
3471 DEVICE_CURVE.store(f.map_or(0, |f| f as usize), AtomicOrdering::Release);
3472}
3473
3474#[allow(clippy::too_many_arguments)]
3475unsafe fn call_device_curve(
3476 atom_bin: *const u32,
3477 natom: usize,
3478 coords: *const u32,
3479 ncell: usize,
3480 parts: u32,
3481 assign: *mut u32,
3482 out_weight: *mut u64,
3483 method: u8,
3484) -> i32 {
3485 let raw = DEVICE_CURVE.load(AtomicOrdering::Acquire);
3486 if raw == 0 {
3487 return 2;
3488 }
3489 let f: DeviceCurveFn = unsafe { std::mem::transmute::<usize, DeviceCurveFn>(raw) };
3492 unsafe {
3493 f(
3494 atom_bin, natom, coords, ncell, parts, assign, out_weight, method,
3495 )
3496 }
3497}
3498
3499pub fn method_from_c(code: u8) -> Result<Method, Error> {
3501 Method::from_code(code)
3502}
3503
3504#[cfg(test)]
3505mod tests {
3506 use super::*;
3507
3508 #[test]
3509 fn morton_matches_the_bit_order() {
3510 assert_eq!(morton_key(0, 0, 0), Some(0));
3511 assert_eq!(morton_key(1, 0, 0), Some(1));
3512 assert_eq!(morton_key(0, 1, 0), Some(2));
3513 assert_eq!(morton_key(0, 0, 1), Some(4));
3514 let mut coords = Vec::new();
3515 for z in 0..8u32 {
3516 for y in 0..8 {
3517 for x in 0..8 {
3518 coords.push([x, y, z]);
3519 }
3520 }
3521 }
3522 let mut by_key = coords.clone();
3523 by_key.sort_by(|a, b| {
3524 morton_key(a[0], a[1], a[2])
3525 .unwrap()
3526 .cmp(&morton_key(b[0], b[1], b[2]).unwrap())
3527 });
3528 let mut by_cmp = coords.clone();
3529 by_cmp.sort_by(|a, b| morton_cmp(*a, *b));
3530 assert_eq!(by_key, by_cmp);
3531 }
3532
3533 #[test]
3534 fn histogram_median_matches_quickselect() {
3535 let mut weight = vec![1u64; 60];
3536 weight[3] = 5;
3537 weight[11] = 8;
3538 weight[40] = 2;
3539 let geom = RcbGeom {
3540 x: (0..60).map(|i| (i % 9) as f64).collect(),
3541 y: (0..60).map(|i| (i % 4) as f64).collect(),
3542 z: (0..60).map(|i| (i % 3) as f64).collect(),
3543 w: weight,
3544 };
3545 let total = geom.w.iter().sum();
3546 for axis in 0..3 {
3547 let mut hist = (0..60u32).collect::<Vec<_>>();
3548 let mut quick = hist.clone();
3549 let got = weighted_cut_bins(&mut hist, &geom, axis, total, 8, 4).unwrap();
3550 let expect = weighted_cut_quick(&mut quick, &geom, axis, total, 8, 4);
3551 assert_eq!(got, expect, "axis {axis}");
3552 let mut a = hist[..got].to_vec();
3553 let mut b = quick[..expect].to_vec();
3554 a.sort();
3555 b.sort();
3556 assert_eq!(a, b, "set axis {axis}");
3557 }
3558 }
3559
3560 #[test]
3561 fn histogram_and_prefix_are_exact() {
3562 let bins_of = [0u32, 1, 1, 2, 0];
3563 let weight = histogram(&bins_of, 4);
3564 assert_eq!(weight, vec![2, 2, 1, 0]);
3565 let prefix = exclusive_prefix(&weight);
3566 assert_eq!(prefix, vec![0, 2, 4, 5, 5]);
3567 assert_eq!(prefix.windows(2).map(|w| w[1] - w[0]).sum::<u64>(), 5);
3568 }
3569
3570 #[test]
3571 fn hilbert_keys_permute_a_cube() {
3572 for bits in 1u32..=4 {
3573 let side = 1u32 << bits;
3574 let mut seen = vec![false; (side * side * side) as usize];
3575 for z in 0..side {
3576 for y in 0..side {
3577 for x in 0..side {
3578 let key = hilbert_key(x, y, z, bits) as usize;
3579 assert!(key < seen.len());
3580 assert!(!seen[key]);
3581 seen[key] = true;
3582 }
3583 }
3584 }
3585 assert!(seen.iter().all(|&v| v));
3586 }
3587 assert_eq!(hilbert_key(0, 0, 0, 1), 0);
3588 assert_eq!(hilbert_key(1, 0, 0, 1), 7);
3589 assert_eq!(hilbert_key(0, 1, 0, 2), 1);
3590 assert_eq!(hilbert_key(1, 1, 1, 2), 5);
3591 }
3592
3593 #[test]
3594 fn replicated_copies_keep_cells_and_arcs() {
3595 let cell = Cell::ortho(8.0, 8.0, 8.0).unwrap();
3596 let xyz: Vec<[f64; 3]> = (0..4).map(|i| [1.0 + i as f64, 1.0, 1.0]).collect();
3597 let graph = cell_graph(&xyz, &cell, 2.0, None, None).unwrap();
3598 let copies = 4;
3599 let tiled = replicate_graph(&graph, copies).unwrap();
3600 assert_eq!(tiled.grid.ncell(), graph.grid.ncell() * copies);
3601 assert_eq!(tiled.neighbor.len(), graph.neighbor.len() * copies);
3602 assert_eq!(tiled.grid.ncell() / copies, graph.grid.ncell());
3603 assert_eq!(tiled.neighbor.len() / copies, graph.neighbor.len());
3604 }
3605
3606 #[test]
3607 fn prefix_puts_each_cell_in_one_part() {
3608 let weight = [1u64, 1, 1, 1];
3609 let order = [0u32, 1, 2, 3];
3610 let assign = prefix_assign(&order, &weight, 2);
3611 assert_eq!(assign.iter().filter(|&&d| d == 0).count(), 2);
3612 assert_eq!(assign.iter().filter(|&&d| d == 1).count(), 2);
3613 assert!(assign.iter().all(|&d| d < 2));
3614 }
3615}