Fair Tree Fairshare Algorithm

Contents

Introduction

Fair Tree prioritizes users such that if accounts A and B are siblings and A has a higher fairshare factor than B, all children of A will have higher fairshare factors than all children of B.
フェアツリーは、アカウントAとBが兄弟であり、Aのフェアシェア係数がBよりも高い場合、Aのすべての子がBのすべての子よりも高いフェアシェア係数を持つようにユーザーに優先順位を付けます。

Some of the benefits include:
いくつかの利点は次のとおりです。

  • All users from a higher priority account receive a higher fair share factor than all users from a lower priority account.
    優先度の高いアカウントのすべてのユーザーは、優先度の低いアカウントのすべてのユーザーよりも高いフェアシェアファクターを受け取ります。
  • Users are sorted and ranked to prevent errors due to precision loss.
    精度の低下によるエラーを防ぐために、ユーザーは並べ替えられ、ランク付けされます。
     Ties are allowed.
    ネクタイは許可されています。
  • Account coordinators cannot accidentally harm the priority of their users relative to users in other accounts.
    アカウントコーディネーターは、他のアカウントのユーザーに対するユーザーの優先順位を誤って損なうことはありません。
  • Users are extremely unlikely to have exactly the same fairshare factor as another user due to loss of precision in calculations.
    計算の精度が低下するため、ユーザーが他のユーザーとまったく同じフェアシェア係数を持つ可能性は非常に低くなります。
  • New jobs are immediately assigned a priority.
    新しいジョブにはすぐに優先順位が割り当てられます。

Overview for End Users

This section is intended for non-admin users who just want to know how their fairshare factor is determined.
このセクションは、フェアシェア係数がどのように決定されるかを知りたいだけの管理者以外のユーザーを対象としています。
 Run sshare -l (lowercase "L") to view the following columns: FairShare, Level FS.
sshare -l（小文字の「L」）を実行して、FairShare、LevelFSの列を表示します。
 Note that Level FS values are infinity if the association has no usage.
アソシエーションに使用法がない場合、レベルFS値は無限大であることに注意してください。

If an account has a higher Level FS value than any other sibling user or sibling account, all children of that account will have a higher FairShare value than the children of the other account.
アカウントのレベルFS値が他の兄弟ユーザーまたは兄弟アカウントよりも高い場合、そのアカウントのすべての子は、他のアカウントの子よりも高いFairShare値を持ちます。
 This is true at every level of the association tree.
これは、アソシエーションツリーのすべてのレベルに当てはまります。

The FairShare value is obtained by using the Fair Tree algorithm to rank all users in the order that they should be prioritized (descending).
FairShare値は、Fair Treeアルゴリズムを使用して、すべてのユーザーを優先順位（降順）の順にランク付けすることによって取得されます。
 The FairShare value is the user's rank divided by the total number of user associations.
FairShare値は、ユーザーのランクをユーザーアソシエーションの総数で割ったものです。
 The highest ranked user receives a 1.0 fairshare value.
最高ランクのユーザーは、1.0のフェアシェア値を受け取ります。

If you (UserA) have a lower FairShare value than another user (UserB) and want to know why, find the first common ancestor account.
あなた（UserA）のFairShare値が別のユーザー（UserB）よりも低く、その理由を知りたい場合は、最初の共通の祖先アカウントを見つけてください。
 At the level below the common ancestor, compare the Level FS value of your ancestor to the Level FS value of UserB's ancestor.
共通の祖先より下のレベルで、祖先のレベルFS値をUserBの祖先のレベルFS値と比較します。
 Your ancestor has a lower Level FS value than UserB's ancestor.
あなたの祖先は、UserBの祖先よりも低いレベルFS値を持っています。
 For information on how Level FS value is calculated, read the section about the Level FS equation.
レベルFS値の計算方法については、レベルFSの式に関するセクションを参照してください。

For example, assume the association tree contains UserA and UserB as follows:
たとえば、関連付けツリーに次のようにUserAとUserBが含まれているとします。

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

Acct1 is the first common ancestor of UserA and UserB.
Acct1は、UserAとUserBの最初の共通の祖先です。
 Check the Level FS values of Acct12 and Acct16.
Acct12およびAcct16のレベルFS値を確認します。
 If UserB has a higher FairShare value than UserA, Acct16 has a higher Level FS value than Acct12.
UserBのFairShare値がUserAよりも高い場合、Acct16のレベルFS値はAcct12よりも高くなります。

The sections below contain more information about the algorithm, including how the final fairshare factor and the Level FS values are calculated.
以下のセクションには、最終的なフェアシェア係数やレベルFS値の計算方法など、アルゴリズムに関する詳細情報が含まれています。

Algorithm

An equation is used to calculate a Level Fairshare value for each association, only considering the shares and usage of itself and its siblings.
方程式は、各アソシエーションのレベルフェアシェア値を計算するために使用され、それ自体とその兄弟のシェアと使用法のみを考慮します。
 A rooted plane tree (PDF download), also known as a rooted ordered tree, is logically created then sorted by Level Fairshare with the highest values on the left.
ルート化されたプラタナスツリー（PDFダウンロード）は、ルート化された順序付きツリーとも呼ばれ、論理的に作成されてから、左側が最も高いレベルのフェアシェアで並べ替えられます。
 The tree is then visited in a depth-first traversal.
次に、深さ優先探索でツリーが訪問されます。
 Users are ranked in pre-order as they are found.
ユーザーは、見つかった時点で先行予約でランク付けされます。
 The ranking is used to create the final fairshare factor for the user.
ランキングは、ユーザーの最終的なフェアシェア係数を作成するために使用されます。

The algorithm performs a single traversal of the tree since all the steps can be combined.
すべてのステップを組み合わせることができるため、アルゴリズムはツリーの1回の走査を実行します。
 The basic idea is to set rank equal to the count of user associations then start at root:
基本的な考え方は、ランクをユーザーの関連付けの数と等しく設定してから、ルートから開始することです。

  • Calculate Level Fairshare for the subtree's children
    サブツリーの子のレベルフェアシェアを計算します
  • Sort children of the subtree
    サブツリーの子を並べ替える
  • Visit the children in descending order
    降順で子供たちを訪ねる
    • If user, assign a final fairshare factor similar to (rank-- / user_assoc_count)
      ユーザーの場合、（rank-- / user_assoc_count）のような最終的なフェアシェア係数を割り当てます
    • If account, descend to account
      アカウントの場合は、アカウントに降ります

Level Fairshare Calculation

The Level Fairshare equation is described below.
レベルフェアシェアの式を以下に説明します。
 Under-served associations will have a value greater than 1.0.
サービスが不十分なアソシエーションの値は1.0より大きくなります。
 Over-served associations will have a value between 0.0 and 1.0.
過剰にサービスされたアソシエーションの値は0.0から1.0の間です。
 

LF = S / U
LF
is the association's Level Fairshare
協会のレベルフェアシェアです
S
also known as Shares Norm, S is the association's assigned shares normalized to the shares assigned to itself and its siblings:
シェアノルムとも呼ばれるSは、アソシエーションに割り当てられたシェアであり、それ自体とその兄弟に割り当てられたシェアに正規化されています。
 S = Srawself / Srawself+siblings
U
also known as Effective Usage, U is the association's usage normalized to the account's usage:
有効使用量とも呼ばれるUは、アカウントの使用量に正規化されたアソシエーションの使用量です。
 U = Urawself / Urawself+siblings

U and S are in the range 0.0 .. 1.0.
UとSは0.0..1.0の範囲にあります。
 LF is in the range 0.0 .. infinity.
LFは0.0 ..無限大の範囲にあります。

Ties

Ties are handled as follows:
ネクタイは次のように処理されます。

  • Sibling users with the same Level Fairshare receive the same rank
    同じレベルのフェアシェアを持つ兄弟ユーザーは同じランクを受け取ります
  • A user with the same Level Fairshare as a sibling account will receive the same rank as its highest ranked user
    兄弟アカウントと同じレベルのフェアシェアを持つユーザーは、最高ランクのユーザーと同じランクを受け取ります
  • Sibling accounts with the same Level Fairshare have their children lists merged before descending
    同じレベルのフェアシェアを持つ兄弟アカウントでは、子リストがマージされてから降順になります

sshare

sshare was modified to show the Level Fairshare value as Level FS when the -l (long) parameter is specified.
-l（long）パラメーターが指定されている場合、レベルFairshare値をレベルFSとして表示するようにsshareが変更されました。
 The field shows the value for each association, thus allowing users to see the results of the fairshare calculation at each level.
このフィールドには各関連付けの値が表示されるため、ユーザーは各レベルでのフェアシェア計算の結果を確認できます。

Note: Norm Usage is not used by Fair Tree but is still displayed.
注：標準使用法はフェアツリーでは使用されませんが、引き続き表示されます。

Configuration

The following slurm.conf (SLURM_CONFIG_FILE) parameters are used to configure the Fair Tree algorithm.
次のslurm.conf（SLURM_CONFIG_FILE）パラメーターは、フェアツリーアルゴリズムを構成するために使用されます。
 See slurm.conf(5) man page for more details.
詳細については、slurm.conf（5）のマニュアルページを参照してください。

PriorityType
Set this value to "priority/multifactor".
この値を「priority / multifactor」に設定します。
 The default value for this variable is "priority/basic" which enables simple FIFO scheduling.
この変数のデフォルト値は「priority / basic」で、単純なFIFOスケジューリングが可能です。
PriorityCalcPeriod
PriorityCalcPeriod is the frequency in minutes that job half-life decay and Fair Tree calculations are performed.
PriorityCalcPeriodは、ジョブの半減期の減衰とフェアツリーの計算が実行される分単位の頻度です。

Important Notes

  • As the Fair Tree algorithm ranks all users, active or not, the administrator must carefully consider how to apply other priority weights in the priority/multifactor plugin.
    Fair Treeアルゴリズムは、アクティブかどうかに関係なくすべてのユーザーをランク付けするため、管理者は、priority / multifactorプラグインで他の優先度の重みを適用する方法を慎重に検討する必要があります。
     The PriorityWeightFairshare can be usefully set to a much smaller value than usual, possibly as low as 1 or 2 times the number of user associations.
    PriorityWeightFairshareは、通常よりもはるかに小さい値に設定すると便利です。おそらく、ユーザーの関連付けの数の1倍または2倍に設定できます。
  • Fair Tree requires the Slurm Accounting Database to provide usage information and the assigned shares values.
    Fair Treeでは、Slurmアカウンティングデータベースが使用情報と割り当てられた共有値を提供する必要があります。
  • scontrol reconfigure does not cause the Fair Tree algorithm to run immediately, even if switching from a different algorithm.
    scontrol reconfigureは、別のアルゴリズムから切り替えた場合でも、FairTreeアルゴリズムをすぐに実行しません。
     You may have to wait until the next iteration as defined by PriorityCalcPeriod.
    PriorityCalcPeriodで定義されているように、次の反復まで待たなければならない場合があります。

Last modified 16 Jan 2019