A Survey of Methods for Collective Communication Optimization and Tuning — Detailed Summary

Udayanga Wickramasinghe, Andrew Lumsdaine | Indiana University & Pacific Northwest National Laboratory | arXiv:1611.06334 (2016)

Per-section summary organized by paper headings. Each section includes paragraph-level bullet points. The paper is a literature survey; the detailed walkthrough therefore tracks the taxonomy and the configuration design space it maps out, since those are the action-space DynamICCL's Agent-2 must learn over.

Abstract

• HPC collective communication faces a "combinatorial explosion" of tuning options as multi-core CPUs, high-bandwidth memory, and modern interconnects multiply the dimensions of the configuration space.
• For collectives like Broadcast and Allreduce, finding the optimal set of tuning parameters by brute force is no longer feasible.
• The paper surveys analytical models, statistical/empirical search techniques, graphical encodings, and machine-learning approaches that automate this tuning process.
• The stated goal is to provide a roadmap toward exascale-ready collective performance.

1. Introduction

Motivation:

• Collective operations (Broadcast, Allreduce, Allgather, Alltoall, Scatter, Gather, Reduce, Reduce-scatter) dominate communication time for communication-bound HPC applications.
• Modern systems blend NUMA hierarchies, accelerators, RDMA fabrics, and topology-aware routing — every layer adds tunable knobs that interact.

The algorithm-selection problem:

• For any single collective there exist many implementation algorithms (Ring/Tree/Dissemination/Recursive-Doubling/Bruck/...), each with internal parameters (segment size, pipeline depth, topology mapping).
• The problem is: given application context (process count, message size, topology, network conditions, on-node hierarchy), pick the (algorithm, parameter) tuple that minimizes completion time.

Two scopes the paper distinguishes:

• Microscopic tuning: optimizing a single collective in isolation (algorithm
  • parameters).
• Macroscopic tuning: optimizing across the application — overlap with computation, scheduling of multiple collectives, transport-layer knobs.

2. Collective Algorithms and Implementation

Algorithm taxonomy (rooted vs. non-rooted):

• Rooted collectives have a designated root process (Broadcast, Reduce, Scatter, Gather). Common algorithms: Flat Tree, Binomial Tree, Binary Tree, Pipeline (Ring), Chain.
• Non-rooted collectives are symmetric across all ranks (Allreduce, Allgather, Alltoall, Barrier, Reduce-scatter). Common algorithms: Recursive Doubling, Recursive Halving + Doubling, Ring, Bruck, Dissemination.

Algorithm-by-collective examples:

• Broadcast: Binomial Tree (low latency, small messages); Pipeline/Ring (high bandwidth, large messages); Scatter+Allgather composite (Van de Geijn).
• Allreduce: Recursive Doubling (small messages, log p steps); Reduce-Scatter+Allgather (large messages, bandwidth-optimal); Ring (highest bandwidth, latency O(p)).
• Alltoall: Pairwise Exchange, Bruck (log p stages, ideal for small messages), Direct (large messages).

Segmentation as a fundamental knob:

• Large messages are split into segments; segments pipeline through the collective topology, overlapping latency stages.
• Segment size critically determines pipelining efficiency: too small inflates per-segment overhead; too large kills pipeline parallelism.
• Segmentation introduces compounded tuning knobs: (segment size, number of outstanding segments, pipeline depth) interact with (algorithm, topology-mapping).

3. Collective Tuning

This is the core of the survey, organized into four method classes.

3.1 Analytical Models

• Hockney model: T = alpha + beta * m. Two parameters (latency, inverse bandwidth) — too coarse for modern systems.
• LogP: latency L, overhead o, gap g, processor count P. Captures per-message overhead and injection-rate limits.
• LogGP: extends LogP with G (gap per byte) for long messages.
• PLogP: parameterized LogP, where g(m) is a function of message size.
• These models permit closed-form derivation of "optimal segment size" by taking derivatives of the per-collective time formula with respect to segment size.

Strengths/weaknesses:

• Strength: cheap to evaluate; gives intuition; provides crossover predictions between algorithms.
• Weakness: ignores network congestion, NUMA effects, OS jitter, kernel noise, hierarchical topology — which dominate at scale.

3.2 Statistical / Empirical Techniques

• AEOS (Automated Empirical Optimization of Software) — offline exhaustive benchmarking, store best parameters in a lookup table. Pioneered by ATLAS (BLAS) and FFTW (FFTs); applied to MPI by LAM/MPI.
• STAR-MPI — dynamic, online variant. Alternates between a measure state (try several algorithms while servicing real traffic) and a select state (commit to the empirically best algorithm), re-entering measure when context shifts.
• OpenMPI rule-based mechanism: at install time, hand-coded heuristics select algorithms based on (comm size, message size); operators can override via MCA parameters.

Strengths/weaknesses:

• Strength: captures real machine behavior, no model assumptions.
• Weakness: training data explosion at exascale; static lookup tables cannot track time-varying conditions; STAR-MPI's measure-phase cost can dominate.

3.3 Graphical / Logic Encoding

• Pjesivac-Grbovic's Quad-Tree approach: the (process count P, message size M) plane is recursively partitioned into rectangles; each leaf rectangle stores the best-performing algorithm in that region.
• Achieves within 10% of optimal with only 3 quad-tree levels.
• Compact, fast at lookup, interpretable.

Strengths/weaknesses:

• Strength: extremely lightweight runtime decision; human-inspectable.
• Weakness: limited to 2-D inputs; misses non-rectangular performance regions; ignores network state and on-node topology.

3.4 Machine Learning

• Supervised classification trees: C4.5, CART, ID3 used to map (P, M, plus optional features) to algorithm choice. Less brittle than fixed quad-trees, but axis-aligned splits remain a limitation.
• Regression trees (REPTree): predict continuous performance directly; reach ~90% of max gain on Jacobi and Integer Sort kernels.
• Artificial Neural Networks: fit a regression surface over the full parameter space; reach up to 95% of max gain but require expensive training data and are opaque.
• Rule-based runtime feedback: after each collective, observed performance updates a rule store that biases future selections — an early form of online learning, conceptually adjacent to bandit / RL approaches.

Strengths/weaknesses:

• Strength: highest accuracy reported in survey; flexible feature inputs.
• Weakness: black-box, training-data-hungry, susceptible to distribution shift, no formal guarantees.

4. Application Centric Tuning

4.1 Programmable Overlap (Communication / Computation)

• Non-blocking MPI primitives (MPI_Iallreduce, MPI_Ibcast) expose explicit overlap windows.
• CC-MPI and Hoefler's framework use compiler analysis to automatically transform blocking collectives into non-blocking versions and reorder computation to fill the overlap window.
• Reported gains: 21% on 3D FFT, ~16% on other scientific kernels.
• Static analysis is blocked by pointer aliasing and dynamic memory in C/C++, limiting applicability.

4.2 RDMA / One-sided Optimizations

• MVAPICH uses InfiniBand RDMA verbs to implement collectives with zero-copy, kernel-bypass transfers.
• New knobs introduced: buffer registration size, Queue Pair (QP) counts, polling vs. event-driven completion, eager vs. rendezvous protocol crossover.
• Performance ceiling raised, but configuration complexity grows: protocol choice now depends on message size, NIC capability, and concurrency level.

5. Discussion — Unified Multidimensional Tuning Architecture (UMTAC)

Argument:

• Single-class methods are individually inadequate: analytical is too coarse, empirical does not scale, quad-tree is too low-dimensional, ML is opaque and data-hungry.
• The way forward is a hybrid pipeline.

Proposed UMTAC pipeline (conceptual block diagram):

+-----------------+   +----------------+   +--------------------+
| Application     |-->| Benchmark      |-->| Data Preprocessing |
| Profiling       |   | Execution      |   | / Feature Eng.     |
+-----------------+   +----------------+   +--------------------+
                                                    |
                                                    v
                                       +----------------------------+
                                       | Ensemble Model Generation  |
                                       | (analytical + ML + rules)  |
                                       +----------------------------+
                                                    |
                                                    v
                                       +----------------------------+
                                       | Model Validation & Deploy  |
                                       +----------------------------+

• Application profiling identifies dominant collectives, message-size distributions, and overlap opportunities.
• Benchmark execution generates labeled data over the parameter space (guided, not exhaustive).
• Ensemble model generation combines analytical priors with ML predictors and rule-based fallbacks.
• Model validation closes the loop with a measure-and-correct stage.

6. Final Remarks

• Collective tuning is unavoidable on the path to exascale.
• No silver bullet; hybrid, ensemble, application-aware tuning is the productive research frontier.
• Open directions: hybrid models, sparse search, feature selection, cross-layer (algorithm + transport) coordination.

Configuration Knobs Identified by the Survey

This is the action-space the survey enumerates — exactly what DynamICCL's Agent-2 must select among.

Surveyed Systems Reference Table

Relevance to DynamICCL

DynamICCL is an RL-based NCCL configuration optimizer. Agent-2 (the Config Agent) selects, per collective, an action tuple (algorithm, protocol, nChannels, numThreads) — and this survey is the canonical reference for what that action space is and how prior work has tried to choose it.

Takeaways for the dissertation literature review:

1. The configuration design space DynamICCL operates over is not novel in its dimensions; it is novel in being learned online from real cluster measurements rather than statically tuned.
2. The survey provides a clear comparative baseline taxonomy — DynamICCL should position itself as online-ML / RL with rule-based feedback, the most expressive corner of the survey's 2x2 (online-vs-offline) x (model-vs-measurement) grid.
3. The reported numbers (90-95% of max gain for ML predictors) define the performance bar Agent-2 must clear, while STAR-MPI's online-measurement overhead is the cost model Agent-2 must come in under.
4. The survey's UMTAC vision validates DynamICCL's plausible architectural choice of combining an analytical bandwidth/latency prior with an RL policy trained on measurements — this is the survey's stated path forward, never fully realized.