Brain-imaging studies now process tens of thousands of scans, and the expensive part is often the choice of map. A parcellation is a division of the brain into regions whose signals are averaged together. Coarse maps are cheap but blur away small disease-related signals. Fine maps preserve those signals but multiply memory and compute, because a connectivity matrix over $N$ regions grows as $N^2$. Cluster schedulers see each such analysis as an opaque, fixed-size job.
This proposal makes the analysis an anytime job, meaning one that has a usable answer early and improves if given more time. We split each subject's analysis along the parcellation tree into stages: a coarse stage that is cheap and easy to predict, followed by refinement tasks that are small and individually optional. A shortest-job-first backfilling scheduler (one that fills idle gaps in the cluster with the shortest predicted jobs) can then pack refinements into gaps. Because every completed tree level is already a valid scientific result, a refinement that runs longer than predicted can be stopped with little lost work. The bet is that this lowers the worst-case damage from runtime misprediction while keeping most of the scientific benefit of fine maps.
Core Claim
Learning-augmented backfilling is fragile in one specific way: a job whose runtime is under-predicted blocks others. ATLAS benchmarks shortest-predicted-job-first policies on 730,000 Alibaba jobs. It shows that max-stretch, a fairness metric measuring the worst slowdown any job suffers, is far more sensitive to prediction error than total completion time. Improving backfilling by using machine learning to predict running times responds with a loss that penalizes under-prediction more heavily (E-Loss) and with incremental extension of overrunning jobs. Both treat the job's work as fixed and try to predict it better.
We claim that for spatially hierarchical workloads, the better fix is to change the job's shape so that under-prediction becomes cheap. Prior work on learning-augmented scheduling (Dell'Amico, Bampis et al.) shows that preemption corrects prediction errors. It costs little, however, only when interrupted work keeps its value. The parcellation tree supplies exactly that property. Hierarchical Brain Parcellation with Uncertainty labels the brain over a 6-level, 151-leaf anatomical tree and falls back to a parent region when finer boundaries are ambiguous. We reuse that tree, and its uncertainty estimates, as a schedule.
The decisive prediction is twofold. First, max-stretch and bounded slowdown (waiting plus running time divided by running time, with a floor on very short jobs) should improve over ML-based backfilling even when both use the same runtime predictor. Second, downstream scientific accuracy should stay within a small margin of always running the finest map.
Research Program
The coarse-to-fine job
For functional MRI connectivity analyses, a subject's job is a chain of levels. Level 0 is a coarse atlas such as Harvard-Oxford. The next level is AAL with 116 regions, then the 360-area HCP multimodal map, then optionally voxel-level analysis. For structural parcellation, the levels are the GIF tree used by the hierarchical-uncertainty paper.
Each refinement task re-splits one parent region (or one subtree) into its children. It computes only the new rows of the connectivity matrix, or only the new label branch, and writes a checkpoint when it finishes. Task size follows from known quantities: child count, voxel count, and time-series length. Prediction should therefore be far tighter than for opaque jobs. This is the analogue of the per-chromosome memory predictor in Efficient Chromosome Parallelization. That work showed that biologically fixed units (chromosome 1 versus chromosome 22) create skew that predictive packing can absorb. Unlike that work, our units are not fixed: the scheduler chooses how deep to go.
The scheduling rule
The policy is EASY backfilling, which lets a later job jump the queue only if it does not delay the reservation held by the job at the head of the queue. We keep that reservation guarantee, so both the head-of-queue job and the coarse stages of new jobs keep their protected start times. Refinement tasks are optional filler. Each is ranked by expected fidelity gain per unit of upper-quantile predicted runtime:
$$\text{priority}(t) = \frac{\Delta V_t}{\hat r_t^{(q)}}$$
Here $\Delta V_t$ is the estimated value of refining region $t$, and $\hat r_t^{(q)}$ is the $q$-th quantile of its predicted runtime from conformal quantile regression as used in ATLAS.
We estimate $\Delta V_t$ from the parcellation model's uncertainty at that branch. Where the hierarchical model is uncertain about child boundaries, refinement adds little, because the model would fall back to the parent anyway. This is where spatial uncertainty and runtime uncertainty, which the literature treats separately, meet in a single number.
A refinement that exceeds its predicted quantile is preempted. Its parent-level result stands, and the task is requeued at lower priority. Every subject's coarse result is guaranteed, which bounds the scientific loss from starvation.
Two-tier control as a scaling constraint
Running this over 100,000 UK Biobank subjects means millions of small refinement tasks. That is the regime where a single central scheduler's decision loop can become the bottleneck.
Following the split between fast and slow decisions in SPINE (a fast executor running parameterized sub-policies, retuned periodically by a slow learned policy) and the state-abstraction idea in SoftMoW, we use two tiers. The root scheduler sees only coarse stages and a per-node "refinement budget" summary. Node-level controllers backfill refinement tasks locally, at high frequency, against that budget.
We treat this tier as something to justify rather than assume. If a centralized scheduler keeps decision latency acceptable at the measured task rates, we report that and drop the hierarchy.
Baselines
The naive reference is standard EASY backfilling that uses user-requested runtimes and first-come-first-served backfill order, with each analysis submitted as one job at the finest atlas. We pair it with the opposite naive choice: every analysis submitted at the coarsest atlas. Together these two bound the speed–fidelity trade-off.
The strongest existing method is ML-based EASY with shortest-job-backfilled-first ordering and the E-Loss predictor from Improving backfilling by using machine learning to predict running times. It is the strongest competitor because it targets the same metric in the same setting, and it reports an 86% reduction in average bounded slowdown on the Curie log and 28% on average across six production logs. We will run it with exactly the same features, training data and tuning budget as our runtime predictor, on the same simulated traces, submitting monolithic fine-atlas jobs.
For the learning-augmented ordering side, we also run shortest-predicted-job-first and Meta-SPRPT as benchmarked in ATLAS. ATLAS reports a total completion time ratio of 1.106 for SPJF against 1.975 for Round Robin, and an 11x max-stretch improvement for Meta-SPRPT. To beat these, we need lower max-stretch and lower bounded slowdown than ML-SJBF and SPJF on the same traces. Downstream accuracy must also stay within one percentage point of the always-fine baseline.
Three ablations isolate the ingredients. The first gives ML-SJBF the parcel count as an explicit predictor feature but keeps jobs monolithic, separating "better prediction" from "different job shape." The second keeps coarse-to-fine decomposition but replaces the uncertainty-based value estimate with uniform value, isolating the role of spatial uncertainty. The third runs the same policy with a single central controller, isolating the hierarchy.
Why not just…?
Why not just run coarse atlases everywhere? It is fast and predictable, but it discards the signal that motivates fine maps. The HCP study in Методы и средства анализа сигналов found AAL gave 1.5–2% higher task classification accuracy than Harvard-Oxford. Voxel-level analysis was needed to detect autism-related disruptions in Cheng et al.. The always-coarse baseline quantifies exactly what is lost.
Why not just add parcellation granularity as a feature to the runtime predictor? This is the real threat. Fine-atlas runtimes are largely determined by region count, so a good predictor plus E-Loss might capture most of the gain. The first ablation tests it directly. Our hypothesis is that it will match us on mean bounded slowdown but not on max-stretch, because the tail is driven by contention and by data-dependent variation that no feature removes. If the feature-augmented baseline matches us on max-stretch too, the decomposition is not worth its complexity, and we would say so.
Why not just checkpoint and preempt monolithic jobs? Generic checkpointing saves state, not answers. A half-finished 360-region connectivity matrix is not a usable result, so a preempted job still contributes nothing until resumed. Our design makes each checkpoint a complete analysis at some resolution. We test this by giving the monolithic baseline the same preemption rule and measuring scientific value delivered at fixed deadlines.
Why not just use one central scheduler? It may well suffice. The third ablation measures decision latency and throughput as task counts grow toward UK Biobank scale, and the hierarchy stays only if it shows a measurable advantage.
Proposed Experiments
We will profile real per-level runtimes and memory use of connectivity pipelines on HCP subjects at Harvard-Oxford, AAL, HCP_MMP1.0 and voxel resolution. We will also profile structural parcellation at each GIF tree level on ADNI2 scans. From these profiles we build a generative workload: imaging analyses arrive in bursts, as study cohorts do, and are mixed into background load replayed from the Parallel Workload Archive logs (Curie, Metacentrum, SDSC-BLUE) and from the ATLAS trace. All policies are simulated on identical event streams.
The system metrics are average bounded slowdown, max-stretch, completion time ratio, and scheduler decision latency. The scientific metrics are HCP 7-category task classification accuracy, and per-level Dice on ADNI2 relative to always-fine. On HCP, the cited paper reports 95.7% accuracy with a CNN on AAL. For the hierarchical model, no reported numerical Dice score was found on Lacuna. Both metrics are plotted against the fraction of subjects reaching each refinement level.
The decisive check is the max-stretch comparison under injected under-prediction. We scale predicted runtimes down by controlled factors for both our method and feature-augmented ML-SJBF. If the coarse-to-fine design is right, our max-stretch should stay roughly flat while the baseline's inflates as ATLAS observed.
A second check tests whether the uncertainty-based value estimate preserves more accuracy per core-hour than uniform refinement. A third check is a shift test: we train the runtime predictor on HCP-length acquisitions and deploy it on UK Biobank-length ones, roughly 6 versus 60 minutes, mirroring the domain gap described in Generalising the HCP multimodal cortical parcellation to UK Biobank. This shows whether guaranteed coarse results keep the system usable when predictions drift.
References
- ATLAS: Alibaba Dataset and Benchmark for Learning-Augmented Scheduling
- Improving backfilling by using machine learning to predict running times
- The Supermarket Model with Known and Predicted Service Times
- Non-Clairvoyant Makespan Minimization Scheduling with Predictions
- Hierarchical Brain Parcellation with Uncertainty
- Efficient Chromosome Parallelization for Precision Medicine Genomic Workflows
- Efficient DRL-Based Congestion Control With Ultra-Low Overhead
- SoftMoW: Recursive and Reconfigurable Cellular WAN Architecture
- Методы и средства анализа сигналов головного мозга человека на данных функциональной магнитно-резонансной томографии (Methods and Tools for the Human Brain Signals Analysis over the Functional Magnetic Resonance Imaging Data)
- Autism: reduced connectivity between cortical areas involved in face expression, theory of mind, and the sense of self
- Generalising the HCP multimodal cortical parcellation to UK Biobank