[OpenMP] Add experimental nesting mode

[tlwilmar]

Summary

Nesting mode is a new experimental feature in the OpenMP runtime. It allows a user to set up nesting for an application in a way that corresponds to the hardware topology levels on the machine an application is being run on. For example, if a machine has 2 sockets, each with 12 cores, then use of nesting mode could set up an outer level of nesting that uses 2 threads per parallel region, and an inner level of nesting that uses 12 threads per parallel region.

Nesting mode is controlled with the KMP_NESTING_MODE environment variable as follows:

1. KMP_NESTING_MODE = 0: nesting mode is off (default); max-active-levels-var is set to 1 (the default -- nesting is off, nested parallel regions are serialized).
2. KMP_NESTING_MODE = 1: nesting mode is on, and a number of threads will be assigned for each level discovered in the machine topology; max-active-levels-var is set to the number of levels discovered.

If the user sets OMP_NUM_THREADS or OMP_MAX_ACTIVE_LEVELS, they will override KMP_NESTING_MODE settings for the associated environment variables. The detected topology may be limited by an affinity mask setting on the initial thread, or if the user sets KMP_HW_SUBSET. See also: KMP_HOT_TEAMS_MAX_LEVEL for controlling use of hot teams for nested parallel regions. Note that this feature only sets numbers of threads used at nesting levels. The user should make use of OMP_PLACES and OMP_PROC_BIND or KMP_AFFINITY for affinitizing those threads, if desired.

[JonChesterfield]

There's a bunch of potentially worthwhile topology descriptions we might want. Some systems do big/little cores. Some x64 chips have numa, e.g. the threadripper cores that don't have direct access to dram. There's also the mapping from offload target to cores, where some cores may have a better/direct connection to some GPUs.

N sockets with ~equal chips and lower bandwidth between them seems a good start point. E.g. a recent epyc probably wants to present as 8 top level nodes, each with 8 cores.

[ye-luo]

Why "12 threads per parallel region" instead of 24? I thought hyper-threads are used by default. Maybe you assume no-SMT in your example? it will be helpful if you make it clear.

[tlwilmar]

In D102188#2752410, @ye-luo wrote:

Why "12 threads per parallel region" instead of 24? I thought hyper-threads are used by default. Maybe you assume no-SMT in your example? it will be helpful if you make it clear.

Yes, it works that way if SMT is available. So, if there are 2 threads available per core, it would allow for a third nesting level, with size 2.

[tlwilmar]

In D102188#2752325, @JonChesterfield wrote:

There's a bunch of potentially worthwhile topology descriptions we might want. Some systems do big/little cores. Some x64 chips have numa, e.g. the threadripper cores that don't have direct access to dram. There's also the mapping from offload target to cores, where some cores may have a better/direct connection to some GPUs.

N sockets with ~equal chips and lower bandwidth between them seems a good start point. E.g. a recent epyc probably wants to present as 8 top level nodes, each with 8 cores.

For now, this is a shortcut to enable a "reasonable" nesting set-up for fairly simple topologies for users who want to use nesting, but in a portable fashion, without really knowing what hardware the code might be running on. Existing features like KMP_HW_SUBSET, use of list for OMP_NUM_THREADS, KMP_AFFINITY, OMP_PLACES, OMP_PROC_BIND, and the APIs for setting the associated ICVs, can all be used to get a suitable nest on specific, more complex, hardware. But I'd welcome improvements to this that use topo info to design a better nest for such hardware.

[tlwilmar]

In D102188#2755329, @tlwilmar wrote:

In D102188#2752410, @ye-luo wrote:

Why "12 threads per parallel region" instead of 24? I thought hyper-threads are used by default. Maybe you assume no-SMT in your example? it will be helpful if you make it clear.

Yes, it works that way if SMT is available. So, if there are 2 threads available per core, it would allow for a third nesting level, with size 2.

I should also add, since it uses whatever topology hwloc discovers, if it sees NUMA nodes, tiles, etc., it adds levels for those too -- any level in the topology that is distinct and has more than one item gets a nesting level.

[tlwilmar]

A few updates that were missed in the original patch were added. Condition fix in the init function, and a topology method check to make use of hwloc if available.

[Nawrin]

openmp/runtime/src/kmp_runtime.cpp

8740

Could you please add a note about what KMP_NESTING_MODE > 1 means in the top where you described KMP_NESTING_MODE 0 and 1?

[tlwilmar]

Nawrin -- I added a comment about it. I'm hesitant to document that part of this experimental feature in its current form -- it's needed for experimentation at the moment, but is likely to change in syntax or otherwise. It's for having an app use a limited outer level of parallelism, and then library calls into selected libraries can turn on nesting and avoid oversubscription. So, I've left out that option in the commit message, but added the comment to the code, emphasizing that it is an experimental option on an experimental feature.

[Nawrin]

LGTM

openmp/runtime/src/kmp.h

 int __kmp_execute_tasks_oncore(kmp_info_t *thread, kmp_int32 gtid,
                                kmp_flag_oncore *flag, int final_spin,
                                int *thread_finished,
 #if USE_ITT_BUILD
                                void *itt_sync_obj,
 #endif /* USE_ITT_BUILD */
                                kmp_int32 is_constrained);
 
+extern int __kmp_nesting_mode;
+extern int __kmp_nesting_mode_nlevels;
+extern int *__kmp_nesting_nth_level;
+extern void __kmp_init_nesting_mode();
+extern void __kmp_set_nesting_mode_threads();
+
 /// This class safely opens and closes a C-style FILE* object using RAII
 /// semantics. There are also methods which allow using stdout or stderr as
 /// the underlying FILE* object. With the implicit conversion operator to
 /// FILE*, an object with this type can be used in any function which takes
 /// a FILE* object e.g., fprintf().
 /// No close method is needed at use sites.
 class kmp_safe_raii_file_t {
   FILE *f;

openmp/runtime/src/kmp_ftn_entry.h

 #endif
 }
 
 int FTN_STDCALL KMP_EXPAND_NAME(FTN_GET_MAX_ACTIVE_LEVELS)(void) {
 #ifdef KMP_STUB
   return 0;
 #else
   /* TO DO: We want per-task implementation of this internal control */
+  if (!TCR_4(__kmp_init_middle)) {
+    __kmp_middle_initialize();
+  }
   return __kmp_get_max_active_levels(__kmp_entry_gtid());
 #endif
 }
 
 int FTN_STDCALL KMP_EXPAND_NAME(FTN_GET_ACTIVE_LEVEL)(void) {
 #ifdef KMP_STUB
   return 0; // returns 0 if it is called from the sequential part of the program
 #else

openmp/runtime/src/kmp_global.cpp

 int _You_must_link_with_Microsoft_OpenMP_library = 1;
 #endif
 
 kmp_target_offload_kind_t __kmp_target_offload = tgt_default;
 
 // OMP Pause Resources
 kmp_pause_status_t __kmp_pause_status = kmp_not_paused;
 
+// Nesting mode
+int __kmp_nesting_mode = 0;
+int __kmp_nesting_mode_nlevels = 1;
+int *__kmp_nesting_nth_level;
+
 // end of file //

openmp/runtime/src/kmp_runtime.cpp

 #endif
 
   // From "KMP_FOREIGN_THREADS_THREADPRIVATE" initialization
   __kmp_foreign_tp = TRUE;
 
   __kmp_global.g.g_dynamic = FALSE;
   __kmp_global.g.g_dynamic_mode = dynamic_default;
 
+  __kmp_init_nesting_mode();
+
   __kmp_env_initialize(NULL);
 
 #if KMP_HAVE_MWAIT || KMP_HAVE_UMWAIT
   __kmp_user_level_mwait_init();
 #endif
 // Print all messages in message catalog for testing purposes.
 #ifdef KMP_DEBUG
   char const *val = __kmp_env_get("KMP_DUMP_CATALOG");
#endif /* KMP_DFLT_NTH_CORES */
 
   if (__kmp_dflt_team_nth < KMP_MIN_NTH) {
     __kmp_dflt_team_nth = KMP_MIN_NTH;
   }
   if (__kmp_dflt_team_nth > __kmp_sys_max_nth) {
     __kmp_dflt_team_nth = __kmp_sys_max_nth;
   }
 
+  if (__kmp_nesting_mode > 0)
+    __kmp_set_nesting_mode_threads();
+
   // There's no harm in continuing if the following check fails,
   // but it indicates an error in the previous logic.
   KMP_DEBUG_ASSERT(__kmp_dflt_team_nth <= __kmp_dflt_team_nth_ub);
 
   if (__kmp_dflt_team_nth != prev_dflt_team_nth) {
     // Run through the __kmp_threads array and set the num threads icv for each
     // root thread that is currently registered with the RTL (which has not
     // already explicitly set its nthreads-var with a call to
void __kmp_hidden_helper_threads_initz_routine() {
 
   __kmpc_fork_call(nullptr, 0, __kmp_hidden_helper_wrapper_fn);
 
   // Set the initialization flag to FALSE
   TCW_SYNC_4(__kmp_init_hidden_helper, FALSE);
 
   __kmp_hidden_helper_threads_deinitz_release();
 }
+
+/* Nesting Mode:
+   Set via KMP_NESTING_MODE, which takes an integer.
+   Note: we skip duplicate topology levels, and skip levels with only
+      one entity.
+   KMP_NESTING_MODE=0 is the default, and doesn't use nesting mode.
+   KMP_NESTING_MODE=1 sets as many nesting levels as there are distinct levels
+      in the topology, and initializes the number of threads at each of those
+      levels to the number of entities at each level, respectively, below the
+      entity at the parent level.
+   KMP_NESTING_MODE=N, where N>1, attempts to create up to N nesting levels,
+      but starts with nesting OFF -- max-active-levels-var is 1 -- and requires
+      the user to turn nesting on explicitly. This is an even more experimental
+      option to this experimental feature, and may change or go away in the
+      future.
+*/
+
+// Allocate space to store nesting levels
+void __kmp_init_nesting_mode() {
+  int levels = KMP_HW_LAST;
+  __kmp_nesting_mode_nlevels = levels;
+  __kmp_nesting_nth_level = (int *)KMP_INTERNAL_MALLOC(levels * sizeof(int));
+  for (int i = 0; i < levels; ++i)
+    __kmp_nesting_nth_level[i] = 0;
+  if (__kmp_nested_nth.size < levels) {
+    __kmp_nested_nth.nth =
+        (int *)KMP_INTERNAL_REALLOC(__kmp_nested_nth.nth, levels * sizeof(int));
+    __kmp_nested_nth.size = levels;
+  }
+}
+
+// Set # threads for top levels of nesting; must be called after topology set
+void __kmp_set_nesting_mode_threads() {
+  kmp_info_t *thread = __kmp_threads[__kmp_entry_gtid()];
+
+  if (__kmp_nesting_mode == 1)
+    __kmp_nesting_mode_nlevels = KMP_MAX_ACTIVE_LEVELS_LIMIT;
+  else if (__kmp_nesting_mode > 1)
+    __kmp_nesting_mode_nlevels = __kmp_nesting_mode;
+
+  if (__kmp_topology) { // use topology info
+    int loc, hw_level;
+    for (loc = 0, hw_level = 0; hw_level < __kmp_topology->get_depth() &&
+                                loc < __kmp_nesting_mode_nlevels;
+         loc++, hw_level++) {
+      __kmp_nesting_nth_level[loc] = __kmp_topology->get_ratio(hw_level);
+      if (__kmp_nesting_nth_level[loc] == 1)
+        loc--;
+    }
+    // Make sure all cores are used
+    if (__kmp_nesting_mode > 1 && loc > 1) {
+      int core_level = __kmp_topology->get_level(KMP_HW_CORE);
+      int num_cores = __kmp_topology->get_count(core_level);
+      int upper_levels = 1;
+      for (int level = 0; level < loc - 1; ++level)
+        upper_levels *= __kmp_nesting_nth_level[level];
+      if (upper_levels * __kmp_nesting_nth_level[loc - 1] < num_cores)
+        __kmp_nesting_nth_level[loc - 1] =
+            num_cores / __kmp_nesting_nth_level[loc - 2];
+    }
+    __kmp_nesting_mode_nlevels = loc;
+    __kmp_nested_nth.used = __kmp_nesting_mode_nlevels;
+  } else { // no topology info available; provide a reasonable guesstimation
+    if (__kmp_avail_proc >= 4) {
+      __kmp_nesting_nth_level[0] = __kmp_avail_proc / 2;
+      __kmp_nesting_nth_level[1] = 2;
+      __kmp_nesting_mode_nlevels = 2;
+    } else {
+      __kmp_nesting_nth_level[0] = __kmp_avail_proc;
+      __kmp_nesting_mode_nlevels = 1;
+    }
+    __kmp_nested_nth.used = __kmp_nesting_mode_nlevels;
+  }
+  for (int i = 0; i < __kmp_nesting_mode_nlevels; ++i) {
+    __kmp_nested_nth.nth[i] = __kmp_nesting_nth_level[i];
+  }
+  set__nproc(thread, __kmp_nesting_nth_level[0]);
+  if (__kmp_nesting_mode > 1 && __kmp_nesting_mode_nlevels > __kmp_nesting_mode)
+    __kmp_nesting_mode_nlevels = __kmp_nesting_mode;
+  if (get__max_active_levels(thread) > 1) {
+    // if max levels was set, set nesting mode levels to same
+    __kmp_nesting_mode_nlevels = get__max_active_levels(thread);
+  }
+  if (__kmp_nesting_mode == 1) // turn on nesting for this case only
+    set__max_active_levels(thread, __kmp_nesting_mode_nlevels);
+}

openmp/runtime/src/kmp_settings.cpp

 
 static void __kmp_stg_print_warnings(kmp_str_buf_t *buffer, char const *name,
                                      void *data) {
   // AC: TODO: change to print_int? (needs documentation change)
   __kmp_stg_print_bool(buffer, name, __kmp_generate_warnings);
 } // __kmp_stg_print_warnings
 
 // -----------------------------------------------------------------------------
+// KMP_NESTING_MODE
+
+static void __kmp_stg_parse_nesting_mode(char const *name, char const *value,
+                                         void *data) {
+  __kmp_stg_parse_int(name, value, 0, INT_MAX, &__kmp_nesting_mode);
+#if KMP_AFFINITY_SUPPORTED && KMP_USE_HWLOC
+  if (__kmp_nesting_mode > 0)
+    __kmp_affinity_top_method = affinity_top_method_hwloc;
+#endif
+} // __kmp_stg_parse_nesting_mode
+
+static void __kmp_stg_print_nesting_mode(kmp_str_buf_t *buffer,
+                                         char const *name, void *data) {
+  if (__kmp_env_format) {
+    KMP_STR_BUF_PRINT_NAME;
+  } else {
+    __kmp_str_buf_print(buffer, "   %s", name);
+  }
+  __kmp_str_buf_print(buffer, "=%d\n", __kmp_nesting_mode);
+} // __kmp_stg_print_nesting_mode
+
+// -----------------------------------------------------------------------------
 // OMP_NESTED, OMP_NUM_THREADS
 
 static void __kmp_stg_parse_nested(char const *name, char const *value,
                                    void *data) {
   int nested;
   KMP_INFORM(EnvVarDeprecated, name, "OMP_MAX_ACTIVE_LEVELS");
   __kmp_stg_parse_bool(name, value, &nested);
   if (nested) {
#endif
      NULL, 0, 0},
     {"KMP_STACKPAD", __kmp_stg_parse_stackpad, __kmp_stg_print_stackpad, NULL,
      0, 0},
     {"KMP_VERSION", __kmp_stg_parse_version, __kmp_stg_print_version, NULL, 0,
      0},
     {"KMP_WARNINGS", __kmp_stg_parse_warnings, __kmp_stg_print_warnings, NULL,
      0, 0},
 
+    {"KMP_NESTING_MODE", __kmp_stg_parse_nesting_mode,
+     __kmp_stg_print_nesting_mode, NULL, 0, 0},
     {"OMP_NESTED", __kmp_stg_parse_nested, __kmp_stg_print_nested, NULL, 0, 0},
     {"OMP_NUM_THREADS", __kmp_stg_parse_num_threads,
      __kmp_stg_print_num_threads, NULL, 0, 0},
     {"OMP_STACKSIZE", __kmp_stg_parse_stacksize, __kmp_stg_print_stacksize,
      NULL, 0, 0},
 
     {"KMP_TASKING", __kmp_stg_parse_tasking, __kmp_stg_print_tasking, NULL, 0,
      0},