Classic Fairshare Algorithm

Overview

As of the 19.05 release, the Fair Tree algorithm is now the default, and the classic fair share algorithm is only available if PriorityFlags=NO_FAIR_TREE has been explicitly configured.
19.05リリースの時点で、フェアツリーアルゴリズムがデフォルトになり、従来のフェアシェアアルゴリズムは、PriorityFlags = NO_FAIR_TREEが明示的に構成されている場合にのみ使用できます。

Normalized Shares

The fair-share hierarchy represents the portion of the computing resources that have been allocated to different projects.
フェアシェア階層は、さまざまなプロジェクトに割り当てられたコンピューティングリソースの部分を表します。
 These allocations are assigned to an account.
これらの割り当てはアカウントに割り当てられます。
 There can be multiple levels of allocations made as allocations of a given account are further divided to sub-accounts:
特定のアカウントの割り当てがさらにサブアカウントに分割されるため、複数のレベルの割り当てが行われる可能性があります。


Figure 1. Machine Allocation

The chart above shows the resources of the machine allocated to four accounts: A, B, C and D.
上のグラフは、A、B、C、Dの4つのアカウントに割り当てられたマシンのリソースを示しています。
 Furthermore, account A's shares are allocated to sub-accounts A1 through A4.
さらに、アカウントAのシェアはサブアカウントA1からA4に割り当てられます。
 Users are granted permission (through sacctmgr) to submit jobs against specific accounts.
ユーザーには、特定のアカウントに対してジョブを送信するためのアクセス許可が（sacctmgrを介して）付与されます。
 If there are 10 users given equal shares in Account A3, they will each be allocated 1% of the machine.
アカウントA3に等しいシェアが与えられた10人のユーザーがいる場合、各ユーザーにはマシンの1％が割り当てられます。

A user's normalized shares are simply:
ユーザーの正規化された共有は単純に次のとおりです。

S =	(Suser / Ssiblings) *
	(Saccount / Ssibling-accounts) *
	(Sparent / Sparent-siblings) * ...
Where:
S
is the user's normalized share, between zero and one
Sは、0と1の間のユーザーの正規化されたシェアです。
Suser
are the number of shares of the account allocated to the user
Suserは、ユーザーに割り当てられたアカウントの共有数です。
Ssiblings
are the total number of shares allocated to all users permitted to charge the account (including Suser)
兄弟は、アカウントへの請求を許可されたすべてのユーザー（ユーザーを含む）に割り当てられた共有の総数です。
Saccount
are the number of shares of the parent account allocated to the account
Saccountは、アカウントに割り当てられた親アカウントの株式数です。
Ssibling-accounts
are the total number of shares allocated to all sub-accounts of the parent account
兄弟アカウントは、親アカウントのすべてのサブアカウントに割り当てられた株式の総数です。
Sparent
are the number of shares of the grandparent account allocated to the parent
親は、親に割り当てられた祖父母アカウントの株式数です。
Sparent-siblings
are the total number of shares allocated to all sub-accounts of the grandparent account
親兄弟は、祖父母アカウントのすべてのサブアカウントに割り当てられた株式の総数です。

Normalized Usage

The processor*seconds allocated to every job are tracked in real-time.
すべてのジョブに割り当てられたプロセッサー*秒は、リアルタイムで追跡されます。
 If one only considered usage over a fixed time period, then calculating a user's normalized usage would be a simple quotient:
一定期間の使用量のみを考慮した場合、ユーザーの正規化された使用量を計算することは単純な商になります。

	UN = Uuser / Utotal
Where:
UN
is normalized usage, between zero and one
UNは、0から1の間の正規化された使用法です。
Uuser
is the processor*seconds consumed by all of a user's jobs in a given account for over a fixed time period
Uuserは、特定のアカウントで一定期間にすべてのユーザーのジョブによって消費されたプロセッサー*秒です。
Utotal
is the total number of processor*seconds utilized across the cluster during that same time period
Utotalは、同じ期間中にクラスター全体で使用されたプロセッサー*秒の総数です。

However, significant real-world usage quantities span multiple time periods.
ただし、実際の使用量は複数の期間にまたがっています。
 Rather than treating usage over a number of weeks or months with equal importance, Slurm's fair-share priority calculation places more importance on the most recent resource usage and less importance on usage from the distant past.
Slurmのフェアシェア優先度の計算では、数週間または数か月にわたる使用量を同等の重要性で扱うのではなく、最新のリソース使用量を重視し、遠い過去の使用量を重視しません。

The Slurm usage metric is based off a half-life formula that favors the most recent usage statistics.
Slurmの使用状況メトリックは、最新の使用状況統計を優先する半減期の式に基づいています。
 Usage statistics from the past decrease in importance based on a single decay factor, D:
過去の使用統計は、単一の減衰係数Dに基づいて重要性が低下します。

	UH = Ucurrent_period +
	     ( D * Ulast_period) + (D * D * Uperiod-2) + ...
Where:
UH
is the historical usage subject to the half-life decay
UHは、半減期の減衰の影響を受ける過去の使用法です
Ucurrent_period
is the usage charged over the current measurement period
Ucurrent_periodは、現在の測定期間中に課金される使用量です
Ulast_period
is the usage charged over the last measurement period
Ulast_periodは、最後の測定期間に請求された使用量です
Uperiod-2
is the usage charged over the second last measurement period
Uperiod-2は、最後から2番目の測定期間に請求された使用量です。
D
is a decay factor between zero and one that delivers the half-life decay based off the PriorityDecayHalfLife setting in the slurm.conf file.
Dは、slurm.confファイルのPriorityDecayHalfLife設定に基づいて半減期の減衰を提供する0と1の間の減衰係数です。
 Without accruing additional usage, a user's UH usage will decay to half its original value after a time period of PriorityDecayHalfLife seconds.
追加の使用量が発生しない場合、ユーザーのUH使用量は、PriorityDecayHalfLife秒の期間が経過すると、元の値の半分に減衰します。

In practice, the PriorityDecayHalfLife could be a matter of seconds or days as appropriate for each site.
実際には、PriorityDecayHalfLifeは、各サイトに応じて数秒または数日で済みます。
 The decay is recalculated every PriorityCalcPeriod minutes, or 5 minutes by default.
減衰は、PriorityCalcPeriod分ごと、またはデフォルトでは5分ごとに再計算されます。
 The decay factor, D, is assigned the value that will achieve the half-life decay rate specified by the PriorityDecayHalfLife parameter.
減衰係数Dには、PriorityDecayHalfLifeパラメーターで指定された半減期減衰率を達成する値が割り当てられます。

The total number of processor*seconds utilized can be similarly aggregated with the same decay factor:
使用されたプロセッサ*秒の総数は、同じ減衰係数で同様に集計できます。

	RH = Rcurrent_period +
	    ( D * Rlast_period) + (D * D * Rperiod-2) + ...
Where:
RH
is the total historical usage subject to the same half-life decay as the usage formula.
RHは、使用式と同じ半減期の減衰の対象となる過去の使用量の合計です。
Rcurrent_period
is the total usage charged over the current measurement period
Rcurrent_periodは、現在の測定期間中に請求された合計使用量です。
Rlast_period
is the total usage charged over the last measurement period
Rlast_periodは、最後の測定期間に請求された合計使用量です
Rperiod-2
is the total usage charged over the second last measurement period
Rperiod-2は、最後から2番目の測定期間に請求された合計使用量です。
D
is the decay factor between zero and one
Dは0と1の間の減衰係数です

A user's normalized usage that spans multiple time periods then becomes:
複数の期間にわたるユーザーの正規化された使用法は、次のようになります。

	U = UH / RH

Simplified Fair-Share Formula

The simplified formula for calculating the fair-share factor for usage that spans multiple time periods and subject to a half-life decay is:
複数の期間にまたがり、半減期の減衰を受ける使用量のフェアシェア係数を計算するための簡略化された式は次のとおりです。

	F = 2**(-U/S/d)
Where:
F
is the fair-share factor
Fはフェアシェアファクターです
S
is the normalized shares
Sは正規化されたシェアです
U
is the normalized usage factoring in half-life decay
Uは、半減期の減衰を考慮した正規化された使用量です
d
is the FairShareDampeningFactor (a configuration parameter, default value of 1)
dはFairShareDampeningFactor（構成パラメーター、デフォルト値1）です。

The fair-share factor will therefore range from zero to one, where one represents the highest priority for a job.
したがって、フェアシェア係数は0から1の範囲になり、1はジョブの最高の優先順位を表します。
 A fair-share factor of 0.5 indicates that the user's jobs have used exactly the portion of the machine that they have been allocated.
フェアシェア係数0.5は、ユーザーのジョブが割り当てられたマシンの部分を正確に使用したことを示します。
 A fair-share factor of above 0.5 indicates that the user's jobs have consumed less than their allocated share while a fair-share factor below 0.5 indicates that the user's jobs have consumed more than their allocated share of the computing resources.
0.5を超えるフェアシェア係数は、ユーザーのジョブが割り当てられたシェアよりも少ない量を消費したことを示し、0.5未満のフェアシェア係数は、ユーザーのジョブがコンピューティングリソースの割り当てられたシェアよりも多く消費したことを示します。

The Fair-share Factor Under An Account Hierarchy

The method described above presents a system whereby the priority of a user's job is calculated based on the portion of the machine allocated to the user and the historical usage of all the jobs run by that user under a specific account.
上記の方法は、ユーザに割り当てられたマシンの部分と、特定のアカウントの下でそのユーザによって実行されたすべてのジョブの履歴使用量に基づいて、ユーザのジョブの優先度が計算されるシステムを提示する。

Another layer of "fairness" is necessary however, one that factors in the usage of other users drawing from the same account.
ただし、同じアカウントから描画する他のユーザーの使用を考慮した「公平性」の別のレイヤーが必要です。
 This allows a job's fair-share factor to be influenced by the computing resources delivered to jobs of other users drawing from the same account.
これにより、ジョブのフェアシェア係数は、同じアカウントから描画する他のユーザーのジョブに提供されるコンピューティングリソースの影響を受ける可能性があります。

If there are two members of a given account, and if one of those users has run many jobs under that account, the job priority of a job submitted by the user who has not run any jobs will be negatively affected.
特定のアカウントに2人のメンバーがいて、それらのユーザーの1人がそのアカウントで多くのジョブを実行した場合、ジョブを実行していないユーザーによって送信されたジョブのジョブ優先度は悪影響を受けます。
 This ensures that the combined usage charged to an account matches the portion of the machine that is allocated to that account.
これにより、アカウントに請求される合計使用量が、そのアカウントに割り当てられているマシンの部分と一致することが保証されます。

In the example below, when user 3 submits their first job using account C, they will want their job's priority to reflect all the resources delivered to account B.
以下の例では、ユーザー3がアカウントCを使用して最初のジョブを送信するときに、アカウントBに配信されたすべてのリソースをジョブの優先度に反映させる必要があります。
 They do not care that user 1 has been using up a significant portion of the cycles allocated to account B and user 2 has yet to run a job out of account B.
ユーザー1がアカウントBに割り当てられたサイクルのかなりの部分を使い果たしており、ユーザー2がまだアカウントBからジョブを実行していないことを気にしません。
 If user 2 submits a job using account B and user 3 submits a job using account C, user 3 expects their job to be scheduled before the job from user 2.
ユーザー2がアカウントBを使用してジョブを送信し、ユーザー3がアカウントCを使用してジョブを送信する場合、ユーザー3は、ユーザー2からのジョブの前に自分のジョブがスケジュールされることを期待します。


Figure 2. Usage Example

The Slurm Fair-Share Formula

The Slurm fair-share formula has been designed to provide fair scheduling to users based on the allocation and usage of every account.
Slurmフェアシェア方式は、すべてのアカウントの割り当てと使用に基づいて、ユーザーに公平なスケジュールを提供するように設計されています。

The actual formula used is a refinement of the formula presented above:
使用される実際の式は、上記の式を改良したものです。

	F = 2**(-UE/S)

The difference is that the usage term is effective usage, which is defined as:
違いは、使用用語が有効な使用法であるということです。これは次のように定義されます。

	UE = UAchild +
		  ((UEparent - UAchild) * Schild/Sall_siblings)
Where:
UE
is the effective usage of the child user or child account
UEは、子ユーザーまたは子アカウントの効果的な使用法です
UAchild
is the actual usage of the child user or child account
UAchildは、子ユーザーまたは子アカウントの実際の使用法です
UEparent
is the effective usage of the parent account
UEparentは、親アカウントの効果的な使用法です
Schild
is the shares allocated to the child user or child account
Schildは、子ユーザーまたは子アカウントに割り当てられた共有です。
Sall_siblings
is the shares allocated to all the children of the parent account
Sall_siblingsは、親アカウントのすべての子に割り当てられた共有です。

This formula only applies with the second tier of accounts below root.
この式は、ルートの下のアカウントの2番目の層にのみ適用されます。
 For the tier of accounts just under root, their effective usage equals their actual usage.
ルートのすぐ下のアカウントの層では、それらの有効な使用量は実際の使用量と同じです。

Because the formula for effective usage includes a term of the effective usage of the parent, the calculation for each account in the tree must start at the second tier of accounts and proceed downward: to the children accounts, then grandchildren, etc.
有効使用量の式には親の有効使用量の項が含まれているため、ツリー内の各アカウントの計算は、アカウントの2番目の層から開始し、子アカウント、孫などの順に下に進む必要があります。
 The effective usage of the users will be the last to be calculated.
ユーザーの有効使用量が最後に計算されます。

Plugging in the effective usage into the fair-share formula above yields a fair-share factor that reflects the aggregated usage charged to each of the accounts in the fair-share hierarchy.
上記のフェアシェア式に実効使用量をプラグインすると、フェアシェア階層内の各アカウントに請求される合計使用量を反映するフェアシェア係数が得られます。

FairShare=parent

It is possible to disable the fairshare at certain levels of the fair share hierarchy by using the FairShare=parent option of sacctmgr.
sacctmgrのFairShare = parentオプションを使用して、フェアシェア階層の特定のレベルでフェアシェアを無効にすることができます。
 For users and accounts with FairShare=parent the normalized shares and effective usage values from the parent in the hierarchy will be used when calculating fairshare priories.
FairShare = parentのユーザーとアカウントの場合、階層内の親からの正規化された共有と有効使用量の値が、fairshareの優先順位を計算するときに使用されます。

If all users in an account are configured with FairShare=parent the result is that all the jobs drawing from that account will get the same fairshare priority, based on the accounts total usage.
アカウント内のすべてのユーザーがFairShare = parentで構成されている場合、そのアカウントから引き出されるすべてのジョブは、アカウントの合計使用量に基づいて、同じフェアシェア優先度を取得します。
 No additional fairness is added based on a user's individual usage.
ユーザーの個々の使用法に基づいて追加の公平性が追加されることはありません。

Example

The following example demonstrates the effective usage calculations and resultant fair-share factors.
次の例は、効果的な使用量の計算とその結果のフェアシェア係数を示しています。
 (See Figure 3 below.)
（下の図3を参照してください。）

The machine's computing resources are allocated to accounts A and D with 40 and 60 shares respectively.
マシンのコンピューティングリソースは、それぞれ40シェアと60シェアのアカウントAとDに割り当てられます。
 Account A is further divided into two children accounts, B with 30 shares and C with 10 shares.
アカウントAはさらに2つの子アカウントに分割されます。Bは30株、Cは10株です。
 Account D is further divided into two children accounts, E with 25 shares and F with 35 shares.
アカウントDはさらに2つの子アカウントに分割されます。Eは25株、Fは35株です。

Note: the shares at any given tier in the Account hierarchy do not need to total up to 100 shares.
注：アカウント階層の特定の層の共有は、合計で最大100共有である必要はありません。
 This example shows them totaling up to 100 to make the arithmetic easier to follow in your head.
この例では、合計で最大100を示し、頭の中で算術演算を簡単に実行できるようにしています。

User 1 is granted permission to submit jobs against the B account.
ユーザー1には、Bアカウントに対してジョブを送信する権限が付与されます。
 Users 2 and 3 are granted one share each in the C account.
ユーザー2と3には、Cアカウントでそれぞれ1つの共有が付与されます。
 User 4 is the sole member of the E account and User 5 is the sole member of the F account.
ユーザー4はEアカウントの唯一のメンバーであり、ユーザー5はFアカウントの唯一のメンバーです。

Note: accounts A and D do not have any user members in this example, though users could have been assigned.
注：この例では、アカウントAとDにはユーザーメンバーがいませんが、ユーザーが割り当てられている可能性があります。

The shares assigned to each account make it easy to determine normalized shares of the machine's complete resources.
各アカウントに割り当てられた共有により、マシンの完全なリソースの正規化された共有を簡単に決定できます。
 Account A has .4 normalized shares, B has .3 normalized shares, etc.
アカウントAには.4の正規化された株式があり、Bには.3の正規化された株式があります。
 Users who are sole members of an account have the same number of normalized shares as the account.
アカウントの唯一のメンバーであるユーザーは、アカウントと同じ数の正規化されたシェアを持っています。
 (E.g., User 1 has .3 normalized shares).
（たとえば、ユーザー1には0.3の正規化された共有があります）。
 Users who share accounts have a portion of the normalized shares based on their shares.
アカウントを共有するユーザーは、自分の共有に基づいて正規化された共有の一部を持っています。
 For example, if user 2 had been allocated 4 shares instead of 1, user 2 would have had .08 normalized shares.
たとえば、ユーザー2に1ではなく4のシェアが割り当てられていた場合、ユーザー2には.08の正規化されたシェアがあります。
 With users 2 and 3 each holding 1 share, they each have a normalized share of 0.05.
ユーザー2と3がそれぞれ1つのシェアを保持している場合、それぞれの正規化されたシェアは0.05です。

Users 1, 2, and 4 have run jobs that have consumed the machine's computing resources.
ユーザー1、2、および4は、マシンのコンピューティングリソースを消費したジョブを実行しました。
 User 1's actual usage is 0.2 of the machine; user 2 is 0.25, and user 4 is 0.25.
ユーザー1の実際の使用量はマシンの0.2です。ユーザー2は0.25、ユーザー4は0.25です。

The actual usage charged to each account is represented by the solid arrows.
各アカウントに請求される実際の使用量は、実線の矢印で表されます。
 The actual usage charged to each account is summed as one goes up the tree.
各アカウントに請求される実際の使用量は、ツリーを上るときに合計されます。
 Account C's usage is the sum of the usage of Users 2 and 3; account A's actual usage is the sum of its children, accounts B and C.
アカウントCの使用量は、ユーザー2と3の使用量の合計です。アカウントAの実際の使用量は、その子、アカウントBおよびCの合計です。


Figure 3. Fair-share Example
  • User 1 normalized share: 0.3
  • User 2 normalized share: 0.05
  • User 3 normalized share: 0.05
  • User 4 normalized share: 0.25
  • User 5 normalized share: 0.35

As stated above, the effective usage is computed from the formula:
上記のように、有効使用量は次の式から計算されます。

	UE = UAchild +
		  ((UEparent - UAchild) * Schild/Sall_siblings)

The effective usage for all accounts at the first tier under the root allocation is always equal to the actual usage:
ルート割り当ての下の最初の層にあるすべてのアカウントの有効な使用量は、常に実際の使用量と同じです。

Account A's effective usage is therefore equal to .45.
したがって、アカウントAの有効使用量は.45になります。
 Account D's effective usage is equal to .25.
アカウントDの有効使用量は0.25です。
  • Account B effective usage: 0.2 + ((0.45 - 0.2) * 30 / 40) = 0.3875
  • Account C effective usage: 0.25 + ((0.45 - 0.25) * 10 / 40) = 0.3
  • Account E effective usage: 0.25 + ((0.25 - 0.25) * 25 / 60) = 0.25
  • Account F effective usage: 0.0 + ((0.25 - 0.0) * 35 / 60) = 0.1458

The effective usage of each user is calculated using the same formula:
各ユーザーの有効使用量は、同じ式を使用して計算されます。

  • User 1 effective usage: 0.2 + ((0.3875 - 0.2) * 1 / 1) = 0.3875
  • User 2 effective usage: 0.25 + ((0.3 - 0.25) * 1 / 2) = 0.275
  • User 3 effective usage: 0.0 + ((0.3 - 0.0) * 1 / 2) = 0.15
  • User 4 effective usage: 0.25 + ((0.25 - 0.25) * 1 / 1) = 0.25
  • User 5 effective usage: 0.0 + ((.1458 - 0.0) * 1 / 1) = 0.1458

Using the Slurm fair-share formula,
Slurmフェアシェア式を使用して、

	F = 2**(-UE/S)

the fair-share factor for each user is:
各ユーザーのフェアシェア係数は次のとおりです。

  • User 1 fair-share factor: 2**(-.3875 / .3) = 0.408479
  • User 2 fair-share factor: 2**(-.275 / .05) = 0.022097
  • User 3 fair-share factor: 2**(-.15 / .05) = 0.125000
  • User 4 fair-share factor: 2**(-.25 / .25) = 0.500000
  • User 5 fair-share factor: 2**(-.1458 / .35) = 0.749154

From this example, once can see that users 1,2, and 3 are over-serviced while user 5 is under-serviced.
この例から、ユーザー1、2、および3はサービスが過剰であり、ユーザー5はサービスが不足していることがわかります。
 Even though user 3 has yet to submit a job, his/her fair-share factor is negatively influenced by the jobs users 1 and 2 have run.
ユーザー3はまだジョブを送信していませんが、彼/彼女のフェアシェア係数は、ユーザー1と2が実行したジョブによって悪影響を受けます。

Based on the fair-share factor alone, if all 5 users were to submit a job charging their respective accounts, user 5's job would be granted the highest scheduling priority.
フェアシェア係数のみに基づいて、5人のユーザー全員がそれぞれのアカウントに課金するジョブを送信した場合、ユーザー5のジョブには最高のスケジューリング優先度が付与されます。

Last modified 11 June 2019