Ticket-Based Multifactor Priority Plugin
Contents
Introduction
A ticket-based variant of the priority/multifactor plugin is available. The reader is assumed to be familiar with the priority/multifactor plugin and only the differences are documented here.
Fair-share Factor
Note: Computing the fair-share factor requires the installation and operation of the Slurm Accounting Database to provide the assigned shares and the consumed, computing resources described below.
In the ticket-based variant, the fair-share component of the job priority is calculated differently. The goal is to make sure that the priority strictly follows the account hierarchy, so that jobs under accounts with usage lower than their fair share will always have a higher priority than jobs belonging to accounts which are over their fair share.
The algorithm is based on ticket scheduling, where at the root of the account hierarchy one starts with a number of tickets, which are then distributed per the fairshare policy to the child accounts and users. Then, the job whose user has the highest number of tickets is assigned the fairshare priority of 1.0, and the other pending jobs are assigned priorities according to how many tickets their users have compared to the highest priority job.
PriorityFS = Ticketsuser / Ticketsmax
The normalized share and normalized usage are calculated in the same way as for the multifactor plugin. However, the fair-share factor for an account/user is calculated as
F = S/Ueff
where the effective usage Ueff is defined as
Ueff = max(U, 0.01 * s)
This prevents F from diverging as the usage U approaches zero. Another way of seeing it is that an account/user that has used less than 1% of its fair share will get the maximum factor (which has the value 100). When the usage of an account/user is exactly proportional to its fair share, the fair-share factor will have the value 1.0.
Compared to the fair-share factor formula in the multifactor plugin, this formula behaves better when one has users which are much above their fair share, which can easily happen e.g. if an account has many other users with very little usage.
Distributing tickets
Tickets are distributed to pending jobs as follows. At the root of the account tree, start with N tickets (the exact value doesn't matter, only the proportions). Those N tickets are distributed to active child nodes (accounts/users) proportional to the number of shares the node has multiplied by the fairshare factor (S * F). An active node is defined as one which has pending jobs, or where one of its child/grandchild/etc. nodes have pending jobs. Tickets are thus distributed to a node per the formula
T = Tparent * S * F / SUM(S*F)active_siblings
Example
Here the same example as in the multifactor plugin page is shown, calculated using the ticket-based algorithm.
- 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
The effective usage for all the accounts equals the normalized usage, except for account F:
- Account F effective usage: max(0, 0.01 * 0.35) = 0.0035
The effective usage for all the users:
- User 1 effective usage: max(0.2, 0.01 * 0.3) = 0.2
- User 2 effective usage: max(0.25, 0.01 * 0.05) = 0.25
- User 3 effective usage: max(0.0, 0.01 * 0.05) = 0.0005
- User 4 effective usage: max(0.25, 0.01 * 0.25) = 0.25
- User 5 effective usage: max(0.0, 0.01 * 0.35) = 0.0035
The fair-share factor for each account, calculated per the formula
F = S/Ueff
is thus
- Account A fair-share factor: 0.4 / 0.45 = 0.89
- Account B fair-share factor: 0.3 / 0.2 = 1.50
- Account C fair-share factor: 0.1 / 0.25 = 0.4
- Account D fair-share factor: 0.6 / 0.25 = 2.40
- Account E fair-share factor: 0.25 / 0.25 = 1
- Account F fair-share factor: 0.35 / 0.0035 = 100
Similarly, the fair-share factor for each user is
- User 1 fair-share factor: 0.3 / 0.2 = 1.5
- User 2 fair-share factor: 0.05 / 0.25 = 0.2
- User 3 fair-share factor: 0.05 / 0.0005 = 100
- User 4 fair-share factor: 0.25 / 0.25 = 1
- User 5 fair-share factor: 0.35 / 0.0035 = 100
Now that the fair-share factors for all nodes in the tree have been calculated, we can distribute the tickets to the active nodes. Assume that only user 2 and user 5 have pending jobs. Assume that we start with 1000 tickets at the root.
Since both child accounts of the root account (A and D) are active, distribute tickets to both of them. Thus,
- Account A tickets: 1000 * 0.4 * 0.89 / (0.4 * 0.89 + 0.6 * 2.40) = 198
- Account D tickets: 1000 * 0.6 * 2.40 / (0.4 * 0.89 + 0.6 * 2.40) = 802
For the children of account A, only account C is active, so all 198 tickets are given to account C. Similarly, for the children of account D, only account F is active, so all 802 tickets are given to accountF.
Finally, user 2 then gets 198 tickets, and user 5 802 tickets. As user 5 has the most tickets, the jobs belonging to user 5 in account F thus get the fair-share priority 1.0. The jobs of user 2 get a fair-share priority of
PriorityFS = 198 / 802 = 0.25
Configuration
The following slurm.conf (SLURM_CONFIG_FILE) parameters are used to configure the Multi-factor Job Priority 2 Plugin. See slurm.conf(5) man page for more details.
- PriorityFlags
- Set to "TICKET_BASED".
- PriorityType
- Set this value to "priority/multifactor". The default value for this variable is "priority/basic" which enables simple FIFO scheduling.
Note: As the ticket-based algorithm ensures that the highest priority pending job will have the fair-share factor 1.0, there is a need to rebalance the relative weights of the different factors compared to the priority/multifactor plugin.
Last modified 14 January 2013