Research map / Learning theory and algorithms / Combinatorial and search optimization
Parallel Empirical Evaluations: Resilience despite Concurrency
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a cluster-scheduling setup (SLURM with L3 cache partitioning via resctrl, memory-channel GRES resources, and core binding) that keeps runtime measurements of parallel SAT solver runs stable and replicable.
Problem
Parallel execution of combinatorial solver benchmarks on shared cluster nodes causes interference among jobs (shared cache and memory channels), making runtime measurements unstable and experiments irreproducible, while sequential exclusive runs are inefficient.
Approach
Applies L3 cache partitioning via the Linux resctrl interface with a gcd-based bitmask formula, plus SLURM generic resources modeling memory channels and cache-aware core binding, so concurrent benchmark jobs get non-overlapping cache and memory resources and stable runtimes.
Key results
- With cache partitioning, runtime instability is reduced to about one second on the majority of instances even under parallel execution.
- Without cache partitioning, running 24 solvers in parallel on one node increases runtime by up to 18-20% (e.g., CaDiCaL -18.9%, Kissat -20.1%), and standard deviation rises up to 5-7x.
- Cache-partitioned runs with 8 parallel solvers match the performance of a single solver with the same cache restriction, with a total-runtime cost of about 4.7-7.4% versus exclusive full-node runs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add L3-cache partitioning | CaDiCaL, Kissat, and glucose · set-asp-gauss; 8 cores | relative wall clock time difference to baseline (%): CaDiCaL -5.3 -> -0.4; Kissat -5.4 -> -0.3; glucose -2.6 -> -0.4 | Mixed |
| Add L3-cache partitioning | CaDiCaL, Kissat, and glucose · set-asp-gauss; 1 core, exclusive node access | total wall clock time (h): CaDiCaL 8.38 -> 9.01; Kissat 6.55 -> 6.87; glucose 7.12 -> 7.69 | Hurt |
| Add L3-cache partitioning | CaDiCaL, Kissat, and glucose · set-asp-gauss; repeated runs across concurrent settings | runtime standard deviation: from 5s to 25 or 35s | Helped |
| Run 24 cores concurrently without cache partitioning | CaDiCaL, Kissat, and glucose · set-asp-gauss; 24 cores | relative wall clock time difference to baseline (%): CaDiCaL -18.9; Kissat -20.1; glucose -11.0 | Hurt |
Surprising findings
- Cache partitioning slightly degrades individual solver runtime (4.7-7.4%) relative to exclusive node access, yet is preferred for stability and sustainability.
- Parallel execution without isolation increases runtime variance substantially, which the authors note is worse for instances that solve quickly.
Limitations
- Evaluation is small: one 11-node Intel Xeon E5-2650v4 cluster, three SAT solvers and one 200-instance set.
- Cache partitioning is hardware-specific (bitmask limits, cache ways) and some configurations are unavailable (marked as missing runs).
- Cache-aware scheduling is not natively supported in SLURM and requires custom setup; BenchExec often cannot be used on HPC systems.
Experimental setup
Datasets: set-asp-gauss (200 SAT instances)
Benchmarks: set-asp-gauss
Metrics: relative wall clock time difference standard deviation of solving time across 5 repetitions number of solved instances total runtime
Baselines: sequential exclusive execution (1 core occupied) parallel execution without cache partitioning
Builds on: BenchExec SLURM perf runsolver
Closest papers by meaning
- Resilient Byzantine Agreement with Predictions (NeurIPS 2026 · similarity 0.83)
- Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations (NeurIPS 2024 · similarity 0.83)
- Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics (ICLR 2025 · similarity 0.82)
- ReCoVer: Resilient LLM Pre-Training System via Fault-Tolerant Collective and Versatile Workload (NeurIPS 2026 · similarity 0.82)
- Improving Parallel Program Performance with LLM Optimizers via Agent-System Interfaces (ICML 2025 · similarity 0.82)
- Predictability Enables Parallelization of Nonlinear State Space Models (NeurIPS 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.