经典公平共享算法

概述

自 19.05 版本起，公平树算法成为默认算法，经典公平共享算法仅在 PriorityFlags=NO_FAIR_TREE 被显式配置时可用。

标准化份额

公平共享层次结构表示已分配给不同项目的计算资源部分。这些分配被分配给一个账户。可以对一个账户进行多级分配，分配的账户进一步划分为子账户：

图 1. 机器分配

上图显示了分配给四个账户 A、B、C 和 D 的机器资源。此外，账户 A 的份额被分配给子账户 A1 到 A4。用户通过 sacctmgr 被授予权限以针对特定账户提交作业。如果有 10 个用户在账户 A3 中获得相等的份额，他们每人将被分配 1% 的机器资源。

用户的标准化份额简单地表示为：

S =	(S_user / S_siblings) *
	(S_account / S_{sibling-accounts}) *
	(S_parent / S_{parent-siblings}) * ...

其中：

S: 是用户的标准化份额，介于零和一之间
S_user: 是分配给用户的账户的份额数量
S_siblings: 是允许向账户收费的所有用户的总份额（包括 S_user）
S_account: 是分配给账户的父账户的份额数量
S_{sibling-accounts}: 是分配给父账户所有子账户的总份额
S_parent: 是分配给父账户的祖父账户的份额数量
S_{parent-siblings}: 是分配给祖父账户所有子账户的总份额

标准化使用

每个作业分配的处理器*秒数实时跟踪。如果只考虑固定时间段内的使用，则计算用户的标准化使用将是一个简单的商：

	U_N = U_user / U_total

其中：

U_N: 是标准化使用，介于零和一之间
U_user: 是在给定账户中所有用户作业在固定时间段内消耗的处理器*秒数
U_total: 是在同一时间段内整个集群中使用的处理器*秒数总数

然而，实际使用量跨越多个时间段。Slurm 的公平共享优先级计算对最近的资源使用赋予更高的重要性，而对遥远过去的使用赋予较低的重要性。

Slurm 的使用指标基于半衰期公式，偏向于最近的使用统计数据。过去的使用统计数据根据单一衰减因子 D 的影响而减少重要性：

	U_H = U_{current_period} +
	     ( D * U_{last_period}) + (D * D * U_period-2) + ...

其中：

U_H: 是受半衰期衰减影响的历史使用
U_{current_period}: 是在当前测量期间内的使用
U_{last_period}: 是在上一个测量期间内的使用
U_period-2: 是在倒数第二个测量期间内的使用
D: 是介于零和一之间的衰减因子，基于 slurm.conf 文件中的 PriorityDecayHalfLife 设置提供半衰期衰减。在没有积累额外使用的情况下，用户的 U_H 使用将在 PriorityDecayHalfLife 秒后衰减到其原始值的一半。

实际上，PriorityDecayHalfLife 可能是适合每个站点的几秒或几天。衰减每 PriorityCalcPeriod 分钟重新计算，默认值为 5 分钟。衰减因子 D 被赋予一个值，以实现 PriorityDecayHalfLife 参数指定的半衰期衰减率。

总的处理器*秒数使用量也可以使用相同的衰减因子进行汇总：

	R_H = R_{current_period} +
	    ( D * R_{last_period}) + (D * D * R_period-2) + ...

其中：

R_H: 是受与使用公式相同的半衰期衰减影响的总历史使用
R_{current_period}: 是在当前测量期间内的总使用
R_{last_period}: 是在上一个测量期间内的总使用
R_period-2: 是在倒数第二个测量期间内的总使用
D: 是介于零和一之间的衰减因子

跨越多个时间段的用户标准化使用变为：

	U = U_H / R_H

简化的公平共享公式

计算跨越多个时间段并受半衰期衰减影响的公平共享因子的简化公式为：

	F = 2**(-U/S/d)

其中：

F: 是公平共享因子
S: 是标准化份额
U: 是考虑半衰期衰减的标准化使用
d: 是公平共享阻尼因子（配置参数，默认值为 1）

因此，公平共享因子的范围为零到一，其中一表示作业的最高优先级。公平共享因子为 0.5 表示用户的作业恰好使用了他们被分配的机器部分。公平共享因子高于 0.5 表示用户的作业消耗的资源少于他们的分配份额，而公平共享因子低于 0.5 表示用户的作业消耗的资源超过了他们的分配份额。

账户层次结构下的公平共享因子

上述方法提供了一种系统，通过该系统可以根据分配给用户的机器部分和该用户在特定账户下运行的所有作业的历史使用情况来计算作业的优先级。

然而，还需要另一个“公平”层次，考虑来自同一账户的其他用户的使用。这允许作业的公平共享因子受到来自同一账户的其他用户作业所提供的计算资源的影响。

如果某个账户有两个成员，并且其中一个用户在该账户下运行了许多作业，则未运行任何作业的用户提交的作业优先级将受到负面影响。这确保了对账户的综合使用与分配给该账户的机器部分相匹配。

在下面的示例中，当用户 3 使用账户 C 提交他们的第一个作业时，他们希望他们的作业优先级反映分配给账户 B 的所有资源。他们并不关心用户 1 已经使用了账户 B 分配的相当大一部分周期，而用户 2 尚未从账户 B 运行作业。如果用户 2 使用账户 B 提交作业，而用户 3 使用账户 C 提交作业，用户 3 期望他们的作业在用户 2 的作业之前被调度。

图 2. 使用示例

Slurm 公平共享公式

Slurm 公平共享公式旨在根据每个账户的分配和使用情况为用户提供公平调度。

实际使用的公式是对上述公式的改进：

	F = 2**(-U_E/S)

不同之处在于使用项是有效使用，定义为：

	U_E = U_Achild +
		  ((U_Eparent - U_Achild) * S_child/S_{all_siblings})

其中：

U_E: 是子用户或子账户的有效使用
U_Achild: 是子用户或子账户的实际使用
U_Eparent: 是父账户的有效使用
S_child: 是分配给子用户或子账户的份额
S_{all_siblings}: 是分配给父账户所有子账户的份额

此公式仅适用于根账户下的第二层账户。对于紧挨根账户的账户，它们的有效使用等于它们的实际使用。

由于有效使用的公式包含父账户的有效使用项，因此树中每个账户的计算必须从第二层账户开始，并向下进行：到子账户，然后是孙子账户，等等。用户的有效使用将是最后计算的。

将有效使用代入上述公平共享公式，得出反映公平共享层次结构中每个账户的汇总使用的公平共享因子。

FairShare=parent

可以通过使用 sacctmgr 的 FairShare=parent 选项在公平共享层次的某些级别禁用公平共享。对于配置为 FairShare=parent 的用户和账户，在计算公平共享优先级时将使用层次中的父账户的标准化份额和有效使用值。

如果账户中的所有用户都配置为 FairShare=parent，则结果是所有从该账户提取的作业将获得相同的公平共享优先级，基于账户的总使用情况。不会根据用户的个体使用情况增加额外的公平性。

示例

以下示例演示了有效使用计算和结果公平共享因子。（见下方图 3。）

机器的计算资源分配给账户 A 和 D，分别为 40 和 60 份额。账户 A 进一步划分为两个子账户，B 有 30 份额，C 有 10 份额。账户 D 进一步划分为两个子账户，E 有 25 份额，F 有 35 份额。

注意：在账户层次的任何给定层次上的份额不需要总计到 100 份额。此示例显示它们总计到 100，以便于您在脑海中跟随算术。

用户 1 被授予对 B 账户提交作业的权限。用户 2 和 3 在 C 账户中各获得一份额。用户 4 是 E 账户的唯一成员，用户 5 是 F 账户的唯一成员。

注意：在此示例中，账户 A 和 D 没有任何用户成员，尽管可以分配用户。

分配给每个账户的份额使得确定机器完整资源的标准化份额变得容易。账户 A 的标准化份额为 0.4，B 为 0.3，等等。作为账户的唯一成员的用户，其标准化份额与账户相同。（例如，用户 1 的标准化份额为 0.3）。共享账户的用户的标准化份额基于他们的份额。例如，如果用户 2 被分配了 4 份额而不是 1，用户 2 将拥有 0.08 的标准化份额。由于用户 2 和 3 各持有 1 份额，他们各自的标准化份额为 0.05。

用户 1、2 和 4 已运行消耗机器计算资源的作业。用户 1 的实际使用为 0.2，用户 2 为 0.25，用户 4 为 0.25。

每个账户的实际使用通过实线箭头表示。每个账户的实际使用在向上走树时相加。账户 C 的使用是用户 2 和 3 使用的总和；账户 A 的实际使用是其子账户 B 和 C 的总和。

图 3. 公平共享示例

用户 1 标准化份额：0.3
用户 2 标准化份额：0.05
用户 3 标准化份额：0.05
用户 4 标准化份额：0.25
用户 5 标准化份额：0.35

如上所述，有效使用是根据以下公式计算的：

	U_E = U_Achild +
		  ((U_Eparent - U_Achild) * S_child/S_{all_siblings})

因此，根分配下第一层账户的有效使用始终等于实际使用：

账户 A 的有效使用因此等于 0.45。账户 D 的有效使用等于 0.25。

账户 B 有效使用：0.2 + ((0.45 - 0.2) * 30 / 40) = 0.3875
账户 C 有效使用：0.25 + ((0.45 - 0.25) * 10 / 40) = 0.3
账户 E 有效使用：0.25 + ((0.25 - 0.25) * 25 / 60) = 0.25
账户 F 有效使用：0.0 + ((0.25 - 0.0) * 35 / 60) = 0.1458

每个用户的有效使用使用相同的公式计算：

用户 1 有效使用：0.2 + ((0.3875 - 0.2) * 1 / 1) = 0.3875
用户 2 有效使用：0.25 + ((0.3 - 0.25) * 1 / 2) = 0.275
用户 3 有效使用：0.0 + ((0.3 - 0.0) * 1 / 2) = 0.15
用户 4 有效使用：0.25 + ((0.25 - 0.25) * 1 / 1) = 0.25
用户 5 有效使用：0.0 + ((.1458 - 0.0) * 1 / 1) = 0.1458

使用 Slurm 公平共享公式，

	F = 2**(-U_E/S)

每个用户的公平共享因子为：

用户 1 公平共享因子：2**(-.3875 / .3) = 0.408479
用户 2 公平共享因子：2**(-.275 / .05) = 0.022097
用户 3 公平共享因子：2**(-.15 / .05) = 0.125000
用户 4 公平共享因子：2**(-.25 / .25) = 0.500000
用户 5 公平共享因子：2**(-.1458 / .35) = 0.749154

从这个例子中可以看出，用户 1、2 和 3 得到了过度服务，而用户 5 得到了不足服务。尽管用户 3 尚未提交作业，但他的公平共享因子受到用户 1 和 2 运行的作业的负面影响。

仅根据公平共享因子，如果所有 5 个用户都提交作业并向各自的账户收费，用户 5 的作业将获得最高的调度优先级。

最后修改于 2019 年 6 月 11 日