排列 OpenMP 实验性调度层级的配置
LLVM OpenMP 的实验性层级调度配置，用选择排序排列少量硬件层级，并同步调整各层的策略与 chunk 大小。
工程问题#
层级调度配置分别指定 L1、L2、L3、NUMA 等层级的调度方式和块大小，配置书写顺序不一定符合运行时要求的层级顺序。重排时必须让层级、策略及两种整数宽度的 chunk 参数保持一一对应。
实际实现#
OMP_SCHEDULE 的 EXPERIMENTAL 解析路径把层级配置写入按相同下标对应的四个数组，随后调用 kmp_hier_sched_env_t::sort。每轮在未排序后缀中找到最小层级，再将四个数组相同位置的元素一起交换。循环分派初始化使用排好序的层级、策略和 chunk 建立运行时层级调度。
处理流程#
- 在受支持的构建中解析 EXPERIMENTAL 层级调度配置
- 从未排序后缀选择最小硬件层级
- 将该层级及对应策略、32 位和 64 位 chunk 一起交换到当前位置
- 在符合条件的 schedule(runtime) 循环中，用排序后的配置初始化层级调度
源码片段#
固定版本 · 原文摘录4383#if KMP_USE_HIER_SCHED4384 if (!__kmp_strcasecmp_with_sentinel("EXPERIMENTAL", ptr, ' ')) {4385 SKIP_TOKEN(ptr);4386 SKIP_WS(ptr);4387 while ((ptr = __kmp_parse_single_omp_schedule(name, ptr, true))) {4388 while (*ptr == ' ' || *ptr == '\t' || *ptr == ':')4389 ptr++;4390 if (*ptr == '\0')4391 break;4392 }4393 } else4394#endif4395 __kmp_parse_single_omp_schedule(name, ptr);4396 } else4397 KMP_WARNING(EmptyString, name);4398 }4399#if KMP_USE_HIER_SCHED4400 __kmp_hier_scheds.sort();4401#endif只有 EXPERIMENTAL 分支解析多层级配置，解析结束调用 __kmp_hier_scheds.sort；编译宏明确限制可用范围。
81 // Sort the hierarchy using selection sort, size will always be small82 // (less than LAYER_LAST) so it is not necessary to use an nlog(n) algorithm83 void sort() {84 if (size <= 1)85 return;86 for (int i = 0; i < size; ++i) {87 int switch_index = i;88 for (int j = i + 1; j < size; ++j) {89 if (layers[j] < layers[switch_index])90 switch_index = j;91 }每轮完整扫描未排序后缀，保存最小层级的位置，这是直接的选择排序；注释说明目标是少量层级。
92 if (switch_index != i) {93 kmp_hier_layer_e temp1 = layers[i];94 enum sched_type temp2 = scheds[i];95 kmp_int32 temp3 = small_chunks[i];96 kmp_int64 temp4 = large_chunks[i];97 layers[i] = layers[switch_index];98 scheds[i] = scheds[switch_index];99 small_chunks[i] = small_chunks[switch_index];100 large_chunks[i] = large_chunks[switch_index];101 layers[switch_index] = temp1;102 scheds[switch_index] = temp2;103 small_chunks[switch_index] = temp3;104 large_chunks[switch_index] = temp4;105 }106 }107 }同一次交换同时维护 layers、scheds、small_chunks、large_chunks，防止层级与参数失配。
909template <>910inline void911__kmp_dispatch_init_hier_runtime<kmp_int32>(ident_t *loc, kmp_int32 lb,912 kmp_int32 ub, kmp_int32 st) {913 __kmp_dispatch_init_hierarchy<kmp_int32>(914 loc, __kmp_hier_scheds.size, __kmp_hier_scheds.layers,915 __kmp_hier_scheds.scheds, __kmp_hier_scheds.small_chunks, lb, ub, st);916}把排序后的层级和策略数组传入实际分层调度初始化，并为 32 位循环索引选择 small_chunks。
1039 if (schedule == kmp_sch_runtime && __kmp_hier_scheds.size > 0) {1040 // Don't use hierarchical for ordered parallel loops and don't1041 // use the runtime hierarchy if one was specified in the program1042 if (!ordered && !pr->flags.use_hier)1043 __kmp_dispatch_init_hier_runtime<T>(loc, lb, ub, st);1044 }1045#endif // KMP_USE_HIER_SCHED只有 runtime 调度且存在层级配置时才考虑这条路径；ordered 循环和已指定程序层级的情况不会走该初始化。
片段贯穿实验性配置解析、选择最小项、参数联动交换和运行时消费者。排序发生在配置阶段，不是在循环执行期间对每个任务进行选择排序。
收益与取舍#
工程分析带来的收益
- 对设计为少量硬件层级的配置，选择排序易于实现；上游注释明确说明不需要为该小数组引入 n log n 算法
- 每轮至多交换一组对应参数，能够清楚保持四个数组之间的关联
付出的代价
- 若把层级数 n 当作变量，比较次数仍为 O(n²)；不能将此选择推广为大任务队列的排序方案
- 每次交换必须同步更新四个数组；漏掉一个数组会把层级与其调度参数配错
可比较的选择
把层级及参数组成结构体后排序字段关联由单个对象表达，更易增加字段，但需要改变现有配置存储及传参布局。
插入排序同样适合少量条目，但需要同步移动多组参数；本案例没有实测证据证明其中一种更快。
版本与适用范围#
对应 LLVM llvmorg-19.1.0 OpenMP runtime。仅适用于 KMP_USE_HIER_SCHED 开启且受支持的构建、OMP_SCHEDULE 的 EXPERIMENTAL 层级配置；runtime 初始化还排除 ordered 循环以及已由程序指定层级的情况。这不是标准 OpenMP 默认调度的通用实现。
参考来源#
源码、官方文档与原始论文openmp/runtime/src/kmp_settings.cpp · __kmp_stg_parse_omp_schedule
openmp/runtime/src/kmp_dispatch_hier.h · kmp_hier_sched_env_t::sort · select
openmp/runtime/src/kmp_dispatch_hier.h · kmp_hier_sched_env_t::sort · swap
openmp/runtime/src/kmp_dispatch.cpp · __kmp_dispatch_init_hier_runtime<kmp_int32>
openmp/runtime/src/kmp_dispatch.cpp · __kmp_dispatch_init · runtime hierarchy