RFC: Collective Algorithm Selection Redesign

[hzhou]

Here is the plan, RFC, using Bcast as an example.

Function interfaces -

1. MPIR_Coll_composition_auto
   • It runs json csel from coll_composition.json, which selects one of the "composition" algorithms (defined below).
2. MPIR_Bcast_impl
   • the binding layer calls this: MPI_Bcast->MPIR_Bcast_impl
   • It constructs coll_sig and call MPIR_Coll_composition
3. MPIR_Bcast_auto - all composition algorithms call _auto functions.
   • It runs json csel from coll_select.json, which selects one of the "pure" algorithm (defined below).
   • MPIR_Bcast_auto itself is a "composition" algorithm to be selected by MPIR_Bcast_impl
4. MPIR_Bcast_fallback - a manual "auto" function that selects a small list of "pure" algorithm (often just 1 basic algorithm).
   • It is either a macro alias to a specific algorithm or a simple if/else hard coded selection.
   • Most internal usage collectives - during initialization, communicator and window creation - call this fallback function.
   • Less focused on performance, but emphasizes simplicity and robustness.

JSON tuning files

1. src/mpi/coll/composition.json - MPIR_CVAR_COLL_COMPOSITION_JSON_FILE
2. src/mpi/coll/selection.json - MPIR_CVAR_COLL_SELECTION_JSON_FILE
   The former only selects "composition" algorithms, and the later only selects "pure" algorithms.
   • PS, maybe "simple" is better name than "pure"?

Types of algorithms -

1. Pure (or Simple) algorithm - that does not call another collective
   • One (main) source file for each algorithm
   • Comment block at the top listing -
     • name
     • collective type
     • restriction list (we'll standardize a list of restrictions)
     • extra params
     • cvar params
     • more
       • for example, heuristic performance guide?
2. Compositional algorithm - that calls other collectives
   • Algorithmic composition - calls other collective with the same communicator
     • Pipeline algorithm can be designed as an algorithmic composition
   • Hierarchical composition - calls other collective on sub-communicators
     • Potentially recursive for multi-level hierarchy
   • State composition - Calls the same collective with modified state (coll_sig)
     • GPU buffer-swap
     • Blocking collectives using NB (nonblocking) collectives
   • Null composition - MPIR_Bcast_auto

Types of restrictions (non-exhaustive):

• intra/inter
• gpu/host
• ipc
• parent-comm
• power-of-two
• inplace/no-inplace
• commutative/builtin-op
• node-consecutive
• more
  If there is restrictions listed, call MPIR_COLL_Check_restrictions at the beginning of the algorithm. It will either error out or fallback when restrictions are violated - controlled by MPIR_CVAR_COLL_FALLBACK (boolean). If fallback, it falls back to MPIR_Bcast_auto.
  NOTE: MPIR_Bcast_auto will never select a function that fails a restriction. This will be ensured by a json validation check at autogen/init time

Direct Overwriting CVAR

• MPIR_CVAR_BCAST_INTRA_ALGORITHM will instruct
  • MPIR_Bcast_auto to call the cvar selected algo function
  • MPIR_Coll_composition_auto to call MPIR_Bcast_auto unless MPIR_CVAR_BCAST_INTRA_COMPOSITION is also selected, then it will call the cvar selected composition algo.
  • MPIR_Bcast_auto will set a bit in coll_attr and skip the cvar check if the bit is set. This will prevent cvar recursion.
    • alternative MPIR_Bcast_auto check restrictions before call the CVAR selected algorithm
• Alternatively, add one more abstraction above MPIR_Bcast_auto, say MPIR_Bcast_auto_and_cvar (name for illustration).
  • MPIR_Bcast_composition_auto and all composition algorithm will call MPIR_Bcast_auto_and_cvar.
  • MPIR_Bcast_auto_and_cvar will call MPIR_Bcast_auto or the cvar-specified algorithm
  • All simple algorithms only fallback to MPIR_Bcast_auto, thus avoiding cvar recursions.

JSON Decision Tree

There are 2 types of decision nodes -

1. Boolean or Discrete conditions
   • intercomm or intracomm
   • comm_size is power-of-2
   • builtin-op
   • data is contiguous
   • gpu buffer
   • etc.
2. Continuous threshold
   • comm_size
   • msg_size

• Discrete conditions effectively makes a Venn diagram with each intersect region containing a list of algorithms
• Continuous threshold provides tunable selection of the final algorithm.

An intuitive design for JSON tree is to have discrete nodes first and then threshold nodes within each intersect regions.

I assume the discrete condition that provides simple regions should be tested first.

Device-specific Collective Algorithm

1. Device-specific built-in JSON at configure time
   • configure can select the json tree corresponding to the configured device
   • The JSON file can use template to avoid duplicating MPIR-only default JSON.
2. Device-specific selection condition
   • MPIR_Csel_coll_sig_s can have an attr for bit-mask conditions and a generic attr_mask=name can check that named bit mask
   • MPIR_init_coll_sig can have device hooks to initialize device-specific conditions
   • MPII_Csel_container_type_e can have device-specific entries
   • MPII_Create_container can call MPID_Create_container for algorithm entries that start with MPID_ prefix
   • MPII_Call_container can call MPID_Call_container for device-layer algorithms.