Clarify scope: for large-scale Kruskal on massively-parallel hardware (GPUs) the problem is to process many edges in weight order while maintaining a dynamic disjoint-set (union‑find, UF) structure across thousands of threads. Pure serial UF (with path compression + union-by-rank) is not directly GPU-friendly; practical solutions use hybrid parallel strategies, lock-free primitives, and phases that reduce contention.Typical parallelization strategies- Batch / relaxed Kruskal: process edges in weight-ordered batches (or buckets). Within a batch, attempt unions in parallel; conflicts resolved later. This reduces strict global ordering needs and allows wide parallelism.- Borůvka-like phases: repeatedly contract components using cheapest outgoing edges (massively parallel and communication-friendly) until few components remain; then finish with serial/less-parallel UF.- Two-level UF: per-threadblock local UF for its subset of vertices/edges (fast shared memory ops), then merge block-level components globally in rounds.Role of atomic operations- Atomics (atomicCAS, atomicMin) provide lock-free ways to update parent pointers or component representatives. Common pattern: try to "hook" one root to another using atomicCAS on parent[root].- Atomics are necessary for correctness under concurrent unions but are expensive and cause contention hotspots when many threads target the same root. Use them sparingly and at coarse granularity (after local reduction) when possible.Path compression trade-offs- Full path compression reduces find time but requires many writes to global memory and can create heavy contention on parent pointers in parallel. On GPUs, prefer lighter-weight strategies: - Path halving or splitting: moves nodes halfway to the root, fewer writes per find, good warp-coalescing properties. - Lazy compression: perform compression periodically (between phases) rather than on every find.- Practical approach: do inexpensive finds during heavy parallel phases (minimal compression) and a final global compression pass after most unions are done.Handling concurrency conflicts when merging sets- Hook-and-contract pattern: "hook" roots with atomicCAS; later "contract" by repeating finds/relaxation so chains shorten. If atomicCAS fails, read new parent and retry (loop).- Leader election / deterministic ordering: decide ordering by rank or by vertex ID (hook smaller ID to larger), avoiding cycles and livelock.- Batch conflict resolution: accumulate attempted unions in a worklist, then resolve conflicts via reduction (e.g., build a small graph of hooks and compress it deterministically).- Epochs and retries: perform unions in rounds; in each round perform non-blocking attempts and then synchronize to consolidate. This bounds retry storms.- Use of per-block locks or owner flags in shared memory for high-contention roots to serialize updates cheaply, falling back to global atomics otherwise.GPU-specific optimizations- Use shared memory for block-local UF to massively reduce global atomics and divergence.- Warp-synchronous find with ballot/warp-level intrinsics to reduce branch divergence.- Coalesce memory accesses: store parent array as 32-bit ints, align accesses, and avoid random writes during compression-heavy passes.- Reduce contention by pre-filtering edges: ignore intra-block edges after local contraction, only pass inter-block edges to global UF.Example hook (simplified pattern, pseudo-CUDA):cpp
// try to hook u_root to v_root
int ru = find(u), rv = find(v);
while (ru != rv) {
if (ru < rv) { // deterministic direction
int old = atomicCAS(&parent[rv], rv, ru);
if (old == rv) break; // success
rv = find(parent[rv]); // someone else changed it, retry
} else {
// symmetric
}
ru = find(ru);
}
