priority.py

#/usr/bin/env python

import numpy as np
import matplotlib

#matplotlib.use('Qt4Agg')

import matplotlib.pyplot as plt

age_max = 14 * 24 # PriorityMaxAge in hours
age_factor = 2000 # PriorityWeightAge
fair_share_factor = 4000 # PriorityWeightFairshare
starting_u = 0.026894 # My effective usage as of 8/15/2016
s = 0.001471 # My share
half_life = 21 * 24 # PriorityDecayHalfLife in hours

# Given a difference between submit times dt and a submit time
# of the latter job (t), what is the difference in priority between
# the two jobs
def age_priority(dt, t):
    result = (dt + t < age_max) * dt
    result += ((dt + t > age_max) * (t < age_max)) * (age_max - t)
    return result * age_factor / age_max

# Given an initial usage u0, assuming the user is not using
# any other resources, what is the users usage a time t later. This is
# an idealized continuously-updating usage; in reality, the usage is
# updated discretely on the interval of a "billing period"
def u(u0, t):
    return u0 * 0.5**(t/half_life)

# Given an initial usage u0, assuming the user is not using
# any other resources, what is the users fair-share priority
# a time t later. Same caveat as above.
def fair_priority(u0, t):
    return 2**(-u(u0, t)/s) * fair_share_factor

# Assume two jobs are queued competing for priority. Job A is submitted
# a time dt before job B. Job A is not accruing Fair Share priority
# (because the user has currently running jobs, for example), but job B
# is (because the user has no running jobs, for example). What is the
# difference in priority between the jobs some time t after job B has been
# submitted given that job B's submitter had a usage of u0 when the job
# was submitted.
def dp(u0, dt, t):
    return fair_priority(u0, t) - age_priority(dt, t)

# Given my usage from 8/15/2016 and my share, at what point does
# my job B overtake job A's priority
t = np.linspace(0, 350, 1000)
fig, ax1 = plt.subplots()
ax1.plot(t/24, dp(starting_u, 0.1, t), t/24, t*0)
ax1.set_xlabel('Time (days)')
ax1.set_ylabel('Difference in priority')
plt.savefig('delta_priority_vs_time.png')
plt.show()

# Assuming the Schmidt group stops submitting jobs immediately, what
# do my usage and fair-share priority look like some time t later
t = np.linspace(0, 300, 1000)
fig, ax1 = plt.subplots()
ax1.plot(t, u(s*50, t*24)/s, 'k-')
ax1.set_xlabel('Wait time (days)')
ax1.set_ylabel('Normalized effective utilization, u/s', color='k')
for tl in ax1.get_yticklabels():
    tl.set_color('k')

ax2 = ax1.twinx()
ax2.plot(t, fair_priority(s*50, t*24))
ax2.set_ylabel('Fair share priority', color='b')
for tl in ax2.get_yticklabels():
    tl.set_color('b')

plt.savefig('usage_fair_share_vs_time.png')
plt.show()


# Given a normalized usage u/s and a time dt between jobs A and B, how long
# do I have to wait before job B has a higher priority than job A. The upper
# curve is a "worst case scenario", in that it is the longest I would have to
# wait *assuming I have no other jobs running*. The ACTUAL worst case scenario
# is I don't acquire any fair-share priority because I am still running jobs;
# in that case it will *always* take PriorityMaxAge i.e. 14 days.
def chi(t, u, dt):
    return dp(u, dt, t)

def simplex(f, t0, dt, epsilon, *args):
    if f(0, *args) >= 0:
        return 0

    tplus = t0 + dt
    uplus = f(tplus, *args)

    # Make sure the upper bound is above 0
    while uplus < 0:
        tplus += dt
        uplus = f(tplus, *args)

    # Make sure the lower bound is below 0
    tminus = tplus - 2*dt
    uminus = f(tminus, *args)
    while uminus > 0:
        tminus -= dt
        uminus = f(tminus, *args)

    tmid = tminus + dt
    umid = f(tmid, *args)
    tplus = tmid + dt
    uplus = f(tplus, *args)

    while abs(umid) > epsilon:
        if umid < 0:
            tminus = tmid
            uminus = umid
        else:
            tplus = tmid
            uplus = umid
        if (tplus - tminus) < epsilon:
            tmid = (tplus + tminus) / 2.
            break
        low_factor = -uminus / (uplus - uminus)
        tmid = tminus * low_factor + tplus * (1 - low_factor)
        umid = f(tmid, *args)
    return tmid


my_u = np.linspace(0, 0.025, 1000)
twait = np.zeros((10, 1000))

for i, ui in enumerate(my_u):
    for j in range(10):
        twait[j, i] = simplex(chi, 335., 1., 1e-9, ui, float(2**j))
my_us = my_u / s
twait /= 24

fig, ax1 = plt.subplots()
ax1.plot(my_us, twait[0], my_us, twait[1], my_us, twait[2], my_us, twait[3], my_us, twait[4], my_us, twait[5], my_us, twait[6], my_us, twait[7], my_us, twait[8], my_us, twait[9])
ax1.set_xlabel('Normalized effective usage, u/s')
ax1.set_ylabel('Wait time (days)')
plt.ylim(0, 14)
plt.savefig('wait_time_vs_usage.png')
plt.show()