公平树公平共享算法

目录

介绍

公平树优先考虑用户,如果账户 A 和 B 是兄弟账户,而 A 的公平共享因子高于 B,则 A 的所有子账户将拥有高于 B 所有子账户的公平共享因子。

一些好处包括:

  • 来自更高优先级账户的所有用户获得的公平共享因子高于来自较低优先级账户的所有用户。
  • 用户被排序和排名,以防止由于精度损失而导致的错误。允许平局。
  • 账户协调员无法意外地损害其用户相对于其他账户用户的优先级。
  • 由于计算中的精度损失,用户极不可能与其他用户拥有完全相同的公平共享因子。
  • 新作业会立即分配优先级。

终端用户概述

本节旨在为非管理员用户提供他们的公平共享因子是如何确定的信息。运行 sshare -l(小写 "L")以查看以下列: FairShare, Level FS。请注意,如果关联没有使用,Level FS 值为无穷大。

如果一个账户的 Level FS 值高于任何其他兄弟用户或兄弟账户,则该账户的所有子账户将拥有高于其他账户子账户的 FairShare 值。这在关联树的每个级别都是正确的。

FairShare 值是通过使用公平树算法对所有用户进行排名,以确定他们的优先级(降序)。FairShare 值是用户的排名除以用户关联的总数。排名最高的用户获得 1.0 的公平共享值。

如果你(用户 A)拥有低于另一个用户(用户 B)的 FairShare 值并想知道原因,请找到第一个共同祖先账户。在共同祖先下面的级别,比较你的祖先的 Level FS 值与用户 B 的祖先的 Level FS 值。你的祖先的 Level FS 值低于用户 B 的祖先。有关 Level FS 值的计算方式的信息,请阅读Level FS 方程部分。

例如,假设关联树包含用户 A 和用户 B,如下所示:

root => Acct1 => Acct12 => UserA
root => Acct1 => Acct16 => UserB

Acct1 是用户 A 和用户 B 的第一个共同祖先。检查 Acct12 和 Acct16 的 Level FS 值。如果用户 B 的 FairShare 值高于用户 A,则 Acct16 的 Level FS 值高于 Acct12。

下面的部分包含有关算法的更多信息,包括最终公平共享因子和 Level FS 值的计算方式。

算法

使用一个方程来计算每个关联的级别公平共享值,仅考虑其自身及其兄弟的份额和使用情况。一个根树 (PDF 下载),也称为根有序树,逻辑上创建,然后按级别公平共享进行排序,最高值在左侧。然后以深度优先遍历的方式访问树。用户在找到时按先序排名。该排名用于创建用户的最终公平共享因子。

该算法对树进行单次遍历,因为所有步骤可以组合在一起。基本思想是将 rank 设置为用户关联的计数,然后从根开始:

  • 计算子树的子节点的级别公平共享
  • 对子树的子节点进行排序
  • 按降序访问子节点
    • 如果是用户,则分配类似于 (rank-- / user_assoc_count) 的最终公平共享因子
    • 如果是账户,则向下遍历到账户

级别公平共享计算

级别公平共享方程如下所述。服务不足的关联将具有大于 1.0 的值。服务过多的关联将具有介于 0.0 和 1.0 之间的值。

LF = S / U
LF
是关联的级别公平共享
S
也称为份额规范,S 是关联的分配份额,归一化为分配给其自身及其兄弟的份额: S = Srawself / Srawself+siblings
U
也称为有效使用,U 是关联的使用情况,归一化为账户的使用情况: U = Urawself / Urawself+siblings

U 和 S 的范围为 0.0 .. 1.0。LF 的范围为 0.0 .. infinity.

平局

平局的处理方式如下:

  • 具有相同级别公平共享的兄弟用户获得相同的排名
  • 与兄弟账户具有相同级别公平共享的用户将获得与其排名最高的用户相同的排名
  • 具有相同级别公平共享的兄弟账户在向下遍历之前合并其子列表

sshare

sshare 被修改为在指定 -l(长)参数时显示级别公平共享值为 Level FS。该字段显示每个关联的值,从而允许用户查看每个级别的公平共享计算结果。

注意:规范使用在公平树中未使用,但仍然显示。

配置

以下 slurm.conf 参数用于配置公平树算法。有关更多详细信息,请参阅 slurm.conf(5) 手册页。

PriorityType
将此值设置为 "priority/multifactor"。
PriorityCalcPeriod
PriorityCalcPeriod 是作业半衰期衰减和公平树计算执行的频率(以分钟为单位)。

重要说明

  • 由于公平树算法对所有用户进行排名,无论是否活跃,管理员必须仔细考虑如何在 priority/multifactor 插件中应用其他优先级权重。PriorityWeightFairshare 可以设置为比通常小得多的值,可能低至用户关联数量的 1 或 2 倍。
  • 公平树需要Slurm 会计数据库提供使用信息和分配份额值。
  • scontrol reconfigure 不会导致公平树算法立即运行,即使是从不同的算法切换。您可能需要等到下一个迭代,如PriorityCalcPeriod所定义的那样。

最后修改于 2023 年 6 月 26 日