Workshop: IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms
Authors: Aaron Li, Yifan Li, Drew DeHaas, and Giulia Guidi (Cornell University)
Abstract: Adding nodes in a graph while reusing existing structure is a recurring computational problem.
In population genetics, this problem arises in genotype representation graph (GRG), a DAG that losslessly encodes genetic variation across thousands of samples by sharing subgraph structure.
In GRG, mutation’s carrier is encoded as leaf nodes reachable from the node it is assigned to.
Current approaches update mutations individually.
This paper introduces a batched mutation-remapping algorithm that replaces independent traversals with a shared reverse-topological pass, identifying reuse candidates for a batch at once.
The pass propagates compact bit-parallel per-mutation state and uses an adaptive sparse/dense carrier set representation spanning rare-to-common variant densities.
Batching adds memory-scalablility to split-based parallelism, which replicates graph and traversal state per worker.
Our remapping approach is evaluated on standalone scenarios and end-to-end allele polarization workload.
It is up to 10.5$\times$ faster than independent remapping while preserving exact carrier-set semantics.
Back to IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms Archive Listing
Back to Full Workshop Archive Listing