kmp_affinity.cpp

/*
 * kmp_affinity.cpp -- affinity management
 */
 
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
 
#include "kmp.h"
#include "kmp_affinity.h"
#include "kmp_i18n.h"
#include "kmp_io.h"
#include "kmp_str.h"
#include "kmp_wrapper_getpid.h"
#if KMP_USE_HIER_SCHED
#include "kmp_dispatch_hier.h"
#endif
#if KMP_USE_HWLOC
// Copied from hwloc
#define HWLOC_GROUP_KIND_INTEL_MODULE 102
#define HWLOC_GROUP_KIND_INTEL_TILE 103
#define HWLOC_GROUP_KIND_INTEL_DIE 104
#define HWLOC_GROUP_KIND_WINDOWS_PROCESSOR_GROUP 220
#endif
 
// The machine topology
kmp_topology_t *__kmp_topology = nullptr;
// KMP_HW_SUBSET environment variable
kmp_hw_subset_t *__kmp_hw_subset = nullptr;
 
// Store the real or imagined machine hierarchy here
static hierarchy_info machine_hierarchy;
 
void __kmp_cleanup_hierarchy() { machine_hierarchy.fini(); }
 
void __kmp_get_hierarchy(kmp_uint32 nproc, kmp_bstate_t *thr_bar) {
  kmp_uint32 depth;
  // The test below is true if affinity is available, but set to "none". Need to
  // init on first use of hierarchical barrier.
  if (TCR_1(machine_hierarchy.uninitialized))
    machine_hierarchy.init(nproc);
 
  // Adjust the hierarchy in case num threads exceeds original
  if (nproc > machine_hierarchy.base_num_threads)
    machine_hierarchy.resize(nproc);
 
  depth = machine_hierarchy.depth;
  KMP_DEBUG_ASSERT(depth > 0);
 
  thr_bar->depth = depth;
  __kmp_type_convert(machine_hierarchy.numPerLevel[0] - 1,
                     &(thr_bar->base_leaf_kids));
  thr_bar->skip_per_level = machine_hierarchy.skipPerLevel;
}
 
static int nCoresPerPkg, nPackages;
static int __kmp_nThreadsPerCore;
#ifndef KMP_DFLT_NTH_CORES
static int __kmp_ncores;
#endif
 
const char *__kmp_hw_get_catalog_string(kmp_hw_t type, bool plural) {
  switch (type) {
  case KMP_HW_SOCKET:
    return ((plural) ? KMP_I18N_STR(Sockets) : KMP_I18N_STR(Socket));
  case KMP_HW_DIE:
    return ((plural) ? KMP_I18N_STR(Dice) : KMP_I18N_STR(Die));
  case KMP_HW_MODULE:
    return ((plural) ? KMP_I18N_STR(Modules) : KMP_I18N_STR(Module));
  case KMP_HW_TILE:
    return ((plural) ? KMP_I18N_STR(Tiles) : KMP_I18N_STR(Tile));
  case KMP_HW_NUMA:
    return ((plural) ? KMP_I18N_STR(NumaDomains) : KMP_I18N_STR(NumaDomain));
  case KMP_HW_L3:
    return ((plural) ? KMP_I18N_STR(L3Caches) : KMP_I18N_STR(L3Cache));
  case KMP_HW_L2:
    return ((plural) ? KMP_I18N_STR(L2Caches) : KMP_I18N_STR(L2Cache));
  case KMP_HW_L1:
    return ((plural) ? KMP_I18N_STR(L1Caches) : KMP_I18N_STR(L1Cache));
  case KMP_HW_LLC:
    return ((plural) ? KMP_I18N_STR(LLCaches) : KMP_I18N_STR(LLCache));
  case KMP_HW_CORE:
    return ((plural) ? KMP_I18N_STR(Cores) : KMP_I18N_STR(Core));
  case KMP_HW_THREAD:
    return ((plural) ? KMP_I18N_STR(Threads) : KMP_I18N_STR(Thread));
  case KMP_HW_PROC_GROUP:
    return ((plural) ? KMP_I18N_STR(ProcGroups) : KMP_I18N_STR(ProcGroup));
  }
  return KMP_I18N_STR(Unknown);
}
 
const char *__kmp_hw_get_keyword(kmp_hw_t type, bool plural) {
  switch (type) {
  case KMP_HW_SOCKET:
    return ((plural) ? "sockets" : "socket");
  case KMP_HW_DIE:
    return ((plural) ? "dice" : "die");
  case KMP_HW_MODULE:
    return ((plural) ? "modules" : "module");
  case KMP_HW_TILE:
    return ((plural) ? "tiles" : "tile");
  case KMP_HW_NUMA:
    return ((plural) ? "numa_domains" : "numa_domain");
  case KMP_HW_L3:
    return ((plural) ? "l3_caches" : "l3_cache");
  case KMP_HW_L2:
    return ((plural) ? "l2_caches" : "l2_cache");
  case KMP_HW_L1:
    return ((plural) ? "l1_caches" : "l1_cache");
  case KMP_HW_LLC:
    return ((plural) ? "ll_caches" : "ll_cache");
  case KMP_HW_CORE:
    return ((plural) ? "cores" : "core");
  case KMP_HW_THREAD:
    return ((plural) ? "threads" : "thread");
  case KMP_HW_PROC_GROUP:
    return ((plural) ? "proc_groups" : "proc_group");
  }
  return ((plural) ? "unknowns" : "unknown");
}
 
// kmp_hw_thread_t methods
int kmp_hw_thread_t::compare_ids(const void *a, const void *b) {
  const kmp_hw_thread_t *ahwthread = (const kmp_hw_thread_t *)a;
  const kmp_hw_thread_t *bhwthread = (const kmp_hw_thread_t *)b;
  int depth = __kmp_topology->get_depth();
  for (int level = 0; level < depth; ++level) {
    if (ahwthread->ids[level] < bhwthread->ids[level])
      return -1;
    else if (ahwthread->ids[level] > bhwthread->ids[level])
      return 1;
  }
  if (ahwthread->os_id < bhwthread->os_id)
    return -1;
  else if (ahwthread->os_id > bhwthread->os_id)
    return 1;
  return 0;
}
 
#if KMP_AFFINITY_SUPPORTED
int kmp_hw_thread_t::compare_compact(const void *a, const void *b) {
  int i;
  const kmp_hw_thread_t *aa = (const kmp_hw_thread_t *)a;
  const kmp_hw_thread_t *bb = (const kmp_hw_thread_t *)b;
  int depth = __kmp_topology->get_depth();
  KMP_DEBUG_ASSERT(__kmp_affinity_compact >= 0);
  KMP_DEBUG_ASSERT(__kmp_affinity_compact <= depth);
  for (i = 0; i < __kmp_affinity_compact; i++) {
    int j = depth - i - 1;
    if (aa->sub_ids[j] < bb->sub_ids[j])
      return -1;
    if (aa->sub_ids[j] > bb->sub_ids[j])
      return 1;
  }
  for (; i < depth; i++) {
    int j = i - __kmp_affinity_compact;
    if (aa->sub_ids[j] < bb->sub_ids[j])
      return -1;
    if (aa->sub_ids[j] > bb->sub_ids[j])
      return 1;
  }
  return 0;
}
#endif
 
void kmp_hw_thread_t::print() const {
  int depth = __kmp_topology->get_depth();
  printf("%4d ", os_id);
  for (int i = 0; i < depth; ++i) {
    printf("%4d ", ids[i]);
  }
  printf("\n");
}
 
// kmp_topology_t methods
 
// Remove layers that don't add information to the topology.
// This is done by having the layer take on the id = UNKNOWN_ID (-1)
void kmp_topology_t::_remove_radix1_layers() {
  int preference[KMP_HW_LAST];
  int top_index1, top_index2;
  // Set up preference associative array
  preference[KMP_HW_PROC_GROUP] = 110;
  preference[KMP_HW_SOCKET] = 100;
  preference[KMP_HW_CORE] = 95;
  preference[KMP_HW_THREAD] = 90;
  preference[KMP_HW_NUMA] = 85;
  preference[KMP_HW_DIE] = 80;
  preference[KMP_HW_TILE] = 75;
  preference[KMP_HW_MODULE] = 73;
  preference[KMP_HW_L3] = 70;
  preference[KMP_HW_L2] = 65;
  preference[KMP_HW_L1] = 60;
  preference[KMP_HW_LLC] = 5;
  top_index1 = 0;
  top_index2 = 1;
  while (top_index1 < depth - 1 && top_index2 < depth) {
    kmp_hw_t type1 = types[top_index1];
    kmp_hw_t type2 = types[top_index2];
    KMP_ASSERT_VALID_HW_TYPE(type1);
    KMP_ASSERT_VALID_HW_TYPE(type2);
    // Do not allow the three main topology levels (sockets, cores, threads) to
    // be compacted down
    if ((type1 == KMP_HW_THREAD || type1 == KMP_HW_CORE ||
         type1 == KMP_HW_SOCKET) &&
        (type2 == KMP_HW_THREAD || type2 == KMP_HW_CORE ||
         type2 == KMP_HW_SOCKET)) {
      top_index1 = top_index2++;
      continue;
    }
    bool radix1 = true;
    bool all_same = true;
    int id1 = hw_threads[0].ids[top_index1];
    int id2 = hw_threads[0].ids[top_index2];
    int pref1 = preference[type1];
    int pref2 = preference[type2];
    for (int hwidx = 1; hwidx < num_hw_threads; ++hwidx) {
      if (hw_threads[hwidx].ids[top_index1] == id1 &&
          hw_threads[hwidx].ids[top_index2] != id2) {
        radix1 = false;
        break;
      }
      if (hw_threads[hwidx].ids[top_index2] != id2)
        all_same = false;
      id1 = hw_threads[hwidx].ids[top_index1];
      id2 = hw_threads[hwidx].ids[top_index2];
    }
    if (radix1) {
      // Select the layer to remove based on preference
      kmp_hw_t remove_type, keep_type;
      int remove_layer, remove_layer_ids;
      if (pref1 > pref2) {
        remove_type = type2;
        remove_layer = remove_layer_ids = top_index2;
        keep_type = type1;
      } else {
        remove_type = type1;
        remove_layer = remove_layer_ids = top_index1;
        keep_type = type2;
      }
      // If all the indexes for the second (deeper) layer are the same.
      // e.g., all are zero, then make sure to keep the first layer's ids
      if (all_same)
        remove_layer_ids = top_index2;
      // Remove radix one type by setting the equivalence, removing the id from
      // the hw threads and removing the layer from types and depth
      set_equivalent_type(remove_type, keep_type);
      for (int idx = 0; idx < num_hw_threads; ++idx) {
        kmp_hw_thread_t &hw_thread = hw_threads[idx];
        for (int d = remove_layer_ids; d < depth - 1; ++d)
          hw_thread.ids[d] = hw_thread.ids[d + 1];
      }
      for (int idx = remove_layer; idx < depth - 1; ++idx)
        types[idx] = types[idx + 1];
      depth--;
    } else {
      top_index1 = top_index2++;
    }
  }
  KMP_ASSERT(depth > 0);
}
 
void kmp_topology_t::_set_last_level_cache() {
  if (get_equivalent_type(KMP_HW_L3) != KMP_HW_UNKNOWN)
    set_equivalent_type(KMP_HW_LLC, KMP_HW_L3);
  else if (get_equivalent_type(KMP_HW_L2) != KMP_HW_UNKNOWN)
    set_equivalent_type(KMP_HW_LLC, KMP_HW_L2);
#if KMP_MIC_SUPPORTED
  else if (__kmp_mic_type == mic3) {
    if (get_equivalent_type(KMP_HW_L2) != KMP_HW_UNKNOWN)
      set_equivalent_type(KMP_HW_LLC, KMP_HW_L2);
    else if (get_equivalent_type(KMP_HW_TILE) != KMP_HW_UNKNOWN)
      set_equivalent_type(KMP_HW_LLC, KMP_HW_TILE);
    // L2/Tile wasn't detected so just say L1
    else
      set_equivalent_type(KMP_HW_LLC, KMP_HW_L1);
  }
#endif
  else if (get_equivalent_type(KMP_HW_L1) != KMP_HW_UNKNOWN)
    set_equivalent_type(KMP_HW_LLC, KMP_HW_L1);
  // Fallback is to set last level cache to socket or core
  if (get_equivalent_type(KMP_HW_LLC) == KMP_HW_UNKNOWN) {
    if (get_equivalent_type(KMP_HW_SOCKET) != KMP_HW_UNKNOWN)
      set_equivalent_type(KMP_HW_LLC, KMP_HW_SOCKET);
    else if (get_equivalent_type(KMP_HW_CORE) != KMP_HW_UNKNOWN)
      set_equivalent_type(KMP_HW_LLC, KMP_HW_CORE);
  }
  KMP_ASSERT(get_equivalent_type(KMP_HW_LLC) != KMP_HW_UNKNOWN);
}
 
// Gather the count of each topology layer and the ratio
void kmp_topology_t::_gather_enumeration_information() {
  int previous_id[KMP_HW_LAST];
  int max[KMP_HW_LAST];
 
  for (int i = 0; i < depth; ++i) {
    previous_id[i] = kmp_hw_thread_t::UNKNOWN_ID;
    max[i] = 0;
    count[i] = 0;
    ratio[i] = 0;
  }
  for (int i = 0; i < num_hw_threads; ++i) {
    kmp_hw_thread_t &hw_thread = hw_threads[i];
    for (int layer = 0; layer < depth; ++layer) {
      int id = hw_thread.ids[layer];
      if (id != previous_id[layer]) {
        // Add an additional increment to each count
        for (int l = layer; l < depth; ++l)
          count[l]++;
        // Keep track of topology layer ratio statistics
        max[layer]++;
        for (int l = layer + 1; l < depth; ++l) {
          if (max[l] > ratio[l])
            ratio[l] = max[l];
          max[l] = 1;
        }
        break;
      }
    }
    for (int layer = 0; layer < depth; ++layer) {
      previous_id[layer] = hw_thread.ids[layer];
    }
  }
  for (int layer = 0; layer < depth; ++layer) {
    if (max[layer] > ratio[layer])
      ratio[layer] = max[layer];
  }
}
 
// Find out if the topology is uniform
void kmp_topology_t::_discover_uniformity() {
  int num = 1;
  for (int level = 0; level < depth; ++level)
    num *= ratio[level];
  flags.uniform = (num == count[depth - 1]);
}
 
// Set all the sub_ids for each hardware thread
void kmp_topology_t::_set_sub_ids() {
  int previous_id[KMP_HW_LAST];
  int sub_id[KMP_HW_LAST];
 
  for (int i = 0; i < depth; ++i) {
    previous_id[i] = -1;
    sub_id[i] = -1;
  }
  for (int i = 0; i < num_hw_threads; ++i) {
    kmp_hw_thread_t &hw_thread = hw_threads[i];
    // Setup the sub_id
    for (int j = 0; j < depth; ++j) {
      if (hw_thread.ids[j] != previous_id[j]) {
        sub_id[j]++;
        for (int k = j + 1; k < depth; ++k) {
          sub_id[k] = 0;
        }
        break;
      }
    }
    // Set previous_id
    for (int j = 0; j < depth; ++j) {
      previous_id[j] = hw_thread.ids[j];
    }
    // Set the sub_ids field
    for (int j = 0; j < depth; ++j) {
      hw_thread.sub_ids[j] = sub_id[j];
    }
  }
}
 
void kmp_topology_t::_set_globals() {
  // Set nCoresPerPkg, nPackages, __kmp_nThreadsPerCore, __kmp_ncores
  int core_level, thread_level, package_level;
  package_level = get_level(KMP_HW_SOCKET);
#if KMP_GROUP_AFFINITY
  if (package_level == -1)
    package_level = get_level(KMP_HW_PROC_GROUP);
#endif
  core_level = get_level(KMP_HW_CORE);
  thread_level = get_level(KMP_HW_THREAD);
 
  KMP_ASSERT(core_level != -1);
  KMP_ASSERT(thread_level != -1);
 
  __kmp_nThreadsPerCore = calculate_ratio(thread_level, core_level);
  if (package_level != -1) {
    nCoresPerPkg = calculate_ratio(core_level, package_level);
    nPackages = get_count(package_level);
  } else {
    // assume one socket
    nCoresPerPkg = get_count(core_level);
    nPackages = 1;
  }
#ifndef KMP_DFLT_NTH_CORES
  __kmp_ncores = get_count(core_level);
#endif
}
 
kmp_topology_t *kmp_topology_t::allocate(int nproc, int ndepth,
                                         const kmp_hw_t *types) {
  kmp_topology_t *retval;
  // Allocate all data in one large allocation
  size_t size = sizeof(kmp_topology_t) + sizeof(kmp_hw_thread_t) * nproc +
                sizeof(int) * ndepth * 3;
  char *bytes = (char *)__kmp_allocate(size);
  retval = (kmp_topology_t *)bytes;
  if (nproc > 0) {
    retval->hw_threads = (kmp_hw_thread_t *)(bytes + sizeof(kmp_topology_t));
  } else {
    retval->hw_threads = nullptr;
  }
  retval->num_hw_threads = nproc;
  retval->depth = ndepth;
  int *arr =
      (int *)(bytes + sizeof(kmp_topology_t) + sizeof(kmp_hw_thread_t) * nproc);
  retval->types = (kmp_hw_t *)arr;
  retval->ratio = arr + ndepth;
  retval->count = arr + 2 * ndepth;
  KMP_FOREACH_HW_TYPE(type) { retval->equivalent[type] = KMP_HW_UNKNOWN; }
  for (int i = 0; i < ndepth; ++i) {
    retval->types[i] = types[i];
    retval->equivalent[types[i]] = types[i];
  }
  return retval;
}
 
void kmp_topology_t::deallocate(kmp_topology_t *topology) {
  if (topology)
    __kmp_free(topology);
}
 
bool kmp_topology_t::check_ids() const {
  // Assume ids have been sorted
  if (num_hw_threads == 0)
    return true;
  for (int i = 1; i < num_hw_threads; ++i) {
    kmp_hw_thread_t &current_thread = hw_threads[i];
    kmp_hw_thread_t &previous_thread = hw_threads[i - 1];
    bool unique = false;
    for (int j = 0; j < depth; ++j) {
      if (previous_thread.ids[j] != current_thread.ids[j]) {
        unique = true;
        break;
      }
    }
    if (unique)
      continue;
    return false;
  }
  return true;
}
 
void kmp_topology_t::dump() const {
  printf("***********************\n");
  printf("*** __kmp_topology: ***\n");
  printf("***********************\n");
  printf("* depth: %d\n", depth);
 
  printf("* types: ");
  for (int i = 0; i < depth; ++i)
    printf("%15s ", __kmp_hw_get_keyword(types[i]));
  printf("\n");
 
  printf("* ratio: ");
  for (int i = 0; i < depth; ++i) {
    printf("%15d ", ratio[i]);
  }
  printf("\n");
 
  printf("* count: ");
  for (int i = 0; i < depth; ++i) {
    printf("%15d ", count[i]);
  }
  printf("\n");
 
  printf("* equivalent map:\n");
  KMP_FOREACH_HW_TYPE(i) {
    const char *key = __kmp_hw_get_keyword(i);
    const char *value = __kmp_hw_get_keyword(equivalent[i]);
    printf("%-15s -> %-15s\n", key, value);
  }
 
  printf("* uniform: %s\n", (is_uniform() ? "Yes" : "No"));
 
  printf("* num_hw_threads: %d\n", num_hw_threads);
  printf("* hw_threads:\n");
  for (int i = 0; i < num_hw_threads; ++i) {
    hw_threads[i].print();
  }
  printf("***********************\n");
}
 
void kmp_topology_t::print(const char *env_var) const {
  kmp_str_buf_t buf;
  int print_types_depth;
  __kmp_str_buf_init(&buf);
  kmp_hw_t print_types[KMP_HW_LAST + 2];
 
  // Num Available Threads
  KMP_INFORM(AvailableOSProc, env_var, num_hw_threads);
 
  // Uniform or not
  if (is_uniform()) {
    KMP_INFORM(Uniform, env_var);
  } else {
    KMP_INFORM(NonUniform, env_var);
  }
 
  // Equivalent types
  KMP_FOREACH_HW_TYPE(type) {
    kmp_hw_t eq_type = equivalent[type];
    if (eq_type != KMP_HW_UNKNOWN && eq_type != type) {
      KMP_INFORM(AffEqualTopologyTypes, env_var,
                 __kmp_hw_get_catalog_string(type),
                 __kmp_hw_get_catalog_string(eq_type));
    }
  }
 
  // Quick topology
  KMP_ASSERT(depth > 0 && depth <= (int)KMP_HW_LAST);
  // Create a print types array that always guarantees printing
  // the core and thread level
  print_types_depth = 0;
  for (int level = 0; level < depth; ++level)
    print_types[print_types_depth++] = types[level];
  if (equivalent[KMP_HW_CORE] != KMP_HW_CORE) {
    // Force in the core level for quick topology
    if (print_types[print_types_depth - 1] == KMP_HW_THREAD) {
      // Force core before thread e.g., 1 socket X 2 threads/socket
      // becomes 1 socket X 1 core/socket X 2 threads/socket
      print_types[print_types_depth - 1] = KMP_HW_CORE;
      print_types[print_types_depth++] = KMP_HW_THREAD;
    } else {
      print_types[print_types_depth++] = KMP_HW_CORE;
    }
  }
  // Always put threads at very end of quick topology
  if (equivalent[KMP_HW_THREAD] != KMP_HW_THREAD)
    print_types[print_types_depth++] = KMP_HW_THREAD;
 
  __kmp_str_buf_clear(&buf);
  kmp_hw_t numerator_type;
  kmp_hw_t denominator_type = KMP_HW_UNKNOWN;
  int core_level = get_level(KMP_HW_CORE);
  int ncores = get_count(core_level);
 
  for (int plevel = 0, level = 0; plevel < print_types_depth; ++plevel) {
    int c;
    bool plural;
    numerator_type = print_types[plevel];
    KMP_ASSERT_VALID_HW_TYPE(numerator_type);
    if (equivalent[numerator_type] != numerator_type)
      c = 1;
    else
      c = get_ratio(level++);
    plural = (c > 1);
    if (plevel == 0) {
      __kmp_str_buf_print(&buf, "%d %s", c,
                          __kmp_hw_get_catalog_string(numerator_type, plural));
    } else {
      __kmp_str_buf_print(&buf, " x %d %s/%s", c,
                          __kmp_hw_get_catalog_string(numerator_type, plural),
                          __kmp_hw_get_catalog_string(denominator_type));
    }
    denominator_type = numerator_type;
  }
  KMP_INFORM(TopologyGeneric, env_var, buf.str, ncores);
 
  if (num_hw_threads <= 0) {
    __kmp_str_buf_free(&buf);
    return;
  }
 
  // Full OS proc to hardware thread map
  KMP_INFORM(OSProcToPhysicalThreadMap, env_var);
  for (int i = 0; i < num_hw_threads; i++) {
    __kmp_str_buf_clear(&buf);
    for (int level = 0; level < depth; ++level) {
      kmp_hw_t type = types[level];
      __kmp_str_buf_print(&buf, "%s ", __kmp_hw_get_catalog_string(type));
      __kmp_str_buf_print(&buf, "%d ", hw_threads[i].ids[level]);
<