Parallel Empirical Evaluations: Resilience despite Concurrency

Johannes Klaus Fichte, Tobias Geibinger, Markus Hecher, Matthias SchlögelAAAI 2024 · DOI

TL;DR

Running large-scale empirical evaluations for combinatorial algorithms on computer clusters often leads to unreliable results due to hardware interference. This paper introduces a novel cache partitioning technique and memory channel resource management to achieve stable and reproducible parallel evaluations, significantly reducing runtime variations.

What Problem Does This Paper Address?

Empirical evaluation is fundamental to advancing research in fields like SAT solving, but scaling these experiments to modern computer clusters presents a significant challenge. While clusters offer immense computational power, running multiple benchmark jobs concurrently can lead to unpredictable interference between processes. This interference, particularly from shared hardware resources like CPU caches and memory channels, causes runtime variations that make results unreliable and difficult to reproduce. Existing solutions often involve limiting parallelism (inefficient) or are too complex to integrate into standard high-performance computing (HPC) environments. This paper tackles the problem of achieving stable and reproducible empirical evaluations in a parallel cluster setting, bridging the gap between the need for scalability and the requirement for scientific rigor.

Methods

The authors propose a multi-pronged approach to stabilize parallel empirical evaluations:

  • Cache Partitioning: This is the core novel technique. They leverage the Linux resctrl kernel feature to partition the L3 cache. By dividing the cache into smaller, dedicated portions and assigning them to specific processes (or groups of processes), they prevent one job from evicting another's cached data, thus reducing interference. This is achieved by constructing bitmasks that define cache access based on hardware capabilities.
  • Memory Channel Resource Management: Recognizing that memory channels also impact performance, they implement a system using SLURM's Generic Resources (GRES) to manage access to memory channels. This involves creating "mock resources" that SLURM can allocate, ensuring that jobs are assigned cores that are consecutively mapped to specific memory channels, thereby avoiding over-committing and reducing variability.
  • Task Affinity and Storage: They utilize SLURM's task/affinity plugin to bind processes to specific CPU cores, ensuring consistent memory access patterns. Additionally, they copy input files to the /dev/shm (shared memory file system) to avoid slow I/O and potential interference from file system caching.
  • Automated Job Generation: The copperbench tool is introduced to automate the creation of experiment jobs, reducing user overhead and ensuring consistent application of the developed techniques.

Datasets

The paper uses the set-asp-gauss instance set, which contains 200 publicly available SAT instances. These instances are described as having varying runtimes and coming from diverse domains, increasing practical hardness.

Key Insights and Ideas

  • Hardware Interference is a Major Reproducibility Killer: The paper strongly emphasizes that modern hardware architectures, particularly the complex memory hierarchy and shared resources, are significant sources of irreproducibility in empirical evaluations, often overlooked in favor of focusing solely on CPU performance.
  • Cache Partitioning is Key to Stability: The novel cache partitioning technique effectively mitigates interference between concurrent jobs, leading to significantly more stable and predictable runtimes, even when multiple cores are actively used.
  • Memory Channels Matter: Just like caches, memory channels can introduce significant performance variations. Managing their access alongside CPU cores is crucial for robust evaluations.
  • HPC Environments Can Be Leveraged: Contrary to the notion that HPC clusters are inherently problematic for reproducible research, this work demonstrates how they can be effectively utilized with the right techniques.
  • Trade-off Between Performance and Stability: While cache partitioning might slightly increase individual runtimes compared to unpartitioned, unhindered access, it achieves a much higher degree of stability and sustainability for hardware usage.

Key Results

  • Reduced Runtime Instability: The proposed approach reduces runtime instability on the majority of instances to within one second.
  • Stable Parallel Execution: With L3 cache partitioning, the standard deviation of solving times across multiple runs is significantly reduced, even when running multiple solvers concurrently. For example, running 8 solvers in parallel with cache partitioning shows comparable stability to running a single solver exclusively on a node.
  • Performance Degradation with Concurrency: Without cache partitioning, the overall performance of solvers degrades with the number of simultaneously committed cores. The variance in runtime for the exact same instances can increase by a factor of 5 to 7.
  • Slight Performance Overhead: Enabling cache partitioning leads to a marginal increase in individual solver runtimes (e.g., 4.7% to 7.4% increase in total wall clock time for the tested solvers when limited to a quarter of the cache), but this is offset by the gains in stability and sustainable hardware usage.

Limitations and Future Work

  • Limitations:
    • The effectiveness of cache partitioning is hardware-dependent, and the number of available "cache ways" can limit the granularity of partitioning.
  • The proposed memory channel management relies on SLURM's GRES, which might not be universally available or configurable in all HPC environments.
  • The paper notes that some hardware might have shared buffers or queues not covered by partitioning.
  • Future Work:
    • Investigate whether task isolation, frequency scaling, and other system memory management techniques can be employed to create abstract and reliable execution environments that are portable across different hardware.
  • Explore combined resource management for cachelines and memory channels for even more robust configurations.
  • Evaluate the impact of these techniques on a wider range of combinatorial problems and hardware architectures.

Summary updated

BibTeX
@inproceedings{fichte2024parallel,
  author = {Johannes Klaus Fichte and Tobias Geibinger and Markus Hecher and Matthias Schlögel},
  title = {{Parallel Empirical Evaluations: Resilience despite Concurrency}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i8.28638},
}
Figure