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. Note that Level FS values are infinity if the association has no usage.
このセクションは、フェアシェア係数の決定方法を知りたいだけの非管理者ユーザーを対象としています。sshare -l（小文字の「L」）を実行して、FairShare、Level FSの列を表示します。関連付けに使用法がない場合、レベル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. This is true at every level of the association tree.
アカウントのLevel FS値が他の兄弟ユーザーまたは兄弟アカウントよりも高い場合、そのアカウントのすべての子は、他のアカウントの子よりもFairShare値が高くなります。これは、関連ツリーのすべてのレベルで当てはまります。

The FairShare value is obtained by using the Fair Tree algorithm to rank all users in the order that they should be prioritized (descending). The FairShare value is the user's rank divided by the total number of user associations. The highest ranked user receives a 1.0 fairshare value.
FairShare値は、Fair Treeアルゴリズムを使用してすべてのユーザーを優先順位（降順）でランク付けすることにより取得されます。FairShareの値は、ユーザーのランクをユーザーアソシエーションの総数で割った値です。最高ランクのユーザーは、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. At the level below the common ancestor, compare the Level FS value of your ancestor to the Level FS value of UserB's ancestor. Your ancestor has a lower Level FS value than UserB's ancestor. For information on how Level FS value is calculated, read the section about the Level FS equation.
あなた（UserA）が別のユーザー（UserB）よりもFairShare値が低く、その理由を知りたい場合は、最初の共通祖先アカウントを見つけます。共通の祖先の下のレベルで、祖先のレベルFS値をUserBの祖先のレベルFS値と比較します。祖先のレベルFS値がUserBの祖先よりも低くなっています。レベル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. Check the Level FS values of Acct12 and Acct16. If UserB has a higher FairShare value than UserA, Acct16 has a higher Level FS value than Acct12.
Acct1は、UserAとUserBの最初の共通祖先です。Acct12およびAcct16のLevel FS値を確認します。UserBがUserAよりも高いFairShare値を持っている場合、Acct16はAcct12よりも高いレベルFS値を持っています。

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. 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.
方程式は、各関連付けのレベルフェアシェア値を計算するために使用され、それ自体とその兄弟のシェアと使用状況のみを考慮します。ルート付き平面ツリー（PDFダウンロード）（ルート付き順序付きツリーとも呼ばれる）は論理的に作成され、左側に最も高い値を持つレベルフェアシェアによってソートされます。次に、深さ優先のトラバーサルでツリーにアクセスします。ユーザーは、見つかると事前にランク付けされます。ランキングは、ユーザーの最終的なフェアシェア要素を作成するために使用されます。

The algorithm performs a single traversal of the tree since all the steps can be combined. 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. Over-served associations will have a value between 0.0 and 1.0.
レベルフェアシェアの式を以下に示します。サービスが不十分な関連付けは、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. LF is in the range 0.0 .. infinity.
UとSの範囲は0.0〜1.0です。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. The field shows the value for each association, thus allowing users to see the results of the fairshare calculation at each level.
sshareが変更され、-l（ロング）パラメーターが指定されている場合、レベルフェアシェア値がレベルFSとして表示されるようになりました。このフィールドには各関連付けの値が表示されるため、ユーザーは各レベルでのフェアシェア計算の結果を確認できます。

Note: Norm Usage is not used by Fair Tree but is still displayed.
注：Norm UsageはFair Treeでは使用されませんが、引き続き表示されます。

Configuration

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

PriorityType
Set this value to "priority/multifactor". The default value for this variable is "priority/basic" which enables simple FIFO scheduling.
この値を「priority / multifactor」に設定します。この変数のデフォルト値は「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. 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.
    フェアツリーでは、使用情報と割り当てられたシェア値を提供するためにSlurm Accounting Databaseが必要です。
  • scontrol reconfigure does not cause the Fair Tree algorithm to run immediately, even if switching from a different algorithm. You may have to wait until the next iteration as defined by PriorityCalcPeriod.
    scontrol reconfigureは、別のアルゴリズムから切り替えた場合でも、Fair Treeアルゴリズムをすぐには実行しません。PriorityCalcPeriodで定義されている次の反復まで待機する必要がある場合があります。

Last modified 16 Jan 2019