Dependencies

Within our model, assuming jobs are malleable, have exponentially distributed sizes, and all follow the same speed-up function, \(s \colon C_c \to \mathbb {R}\), \(\mathbb {E}[T]^{EQUI} \leq \mathbb {E}[T]^P\) for any scheduling policy \(P\) i.e. The mean response time of EQUI is always better than any other policy \(P\).

In the previous situation \(\mathbb {E}[N]^P \leq \mathbb {E}[N]^Q\).

coreSpace is defined to be the actual allowed allotment of cores i.e. if given a vector \(c \in \mathbb {R}^n\) describing how many cores we have then our corespace becomes: \(x \in \mathbb {R}^n\) with the requirement that: \(0 \leq x_i \leq s_i\) forall \(1 \leq i \leq n\). After this we shall abbreviate this space as \(C_c\).

An infinite-dimensional vector lambda described by a function \(\mathbb {N} \to \mathbb {R}\) is said to be an invariant distribution for a queue \(Q\) if the following holds:

1. \(\forall n \in \mathbb {N}, n \neq 0, \lambda (n-1) * Q(n-1,n) + \lambda (n+1) * Q(n+1,n) = \lambda (n)\)

2. \(\lambda (1) * Q(1,0) = \lambda (0)\)

3. \(||\lambda ||_1 = 1\).

The mean response time, denoted as \(\mathbb {E}[T]\) of a queue is defined to be the mean number in the system / mean throughput i.e. (mean throughput is equal to \(\Lambda \) since this doesn’t vary per state):

A function \(f\) is said to be concave on \(c \in \mathbb {R^n}\) the core vector if \(\forall x, y \in C_c\) and all \(a, b \in \mathbb {R}\) with the property that \(a + b = 1\) implies that:

A policy is a function \(p \colon \mathbb {N} \times \mathbb {N} \to \mathbb {R}^n\) describing per state \(n\) how to allocate cores in \(C_c\) over \(j\), \(0 \leq j \leq n\), jobs. Thus if we write this out, \(p\) is subject to the following conditions:

1. \(p(n,j) = 0 \forall j {\gt} n\).

2. \(\left(\sum _{k=0}^i p(i, k)\right) \in C_c\)

3. \(\forall 0 \leq i \leq n, p(n,i) \geq 0\)

A function \(Q \colon \mathbb {N} \times \mathbb {N} \to \mathbb {R}\) is said to be a rate matrix if the following holds:

1. \(Q(0,1) = -Q(0,0)\)

2. \(\forall n \in \mathbb {N} \neq 0, Q(n, n+1) + Q(n, n-1) = -Q(n,n)\)

3. \(\forall n, k \in \mathbb {N}, |k-n| \geq 2, Q(n,k) = 0\)

A schedule policy is a function describing for a specific queue \(Q\) and a specific speedup function \(s\) the departurerates per state \(n\).

A function \(s \colon C_c \to \mathbb {R}\) is said to be a speedup function if \(s\) is concave and sublinear on \(C_c\).

A function \(f\) is said to be sublinear on \(C_c\), with \(c\) the core vector if \(\forall x \in C_c\) \(||f(x)|| \leq ||x||\).

For any two scheduling policies whose departure rates differ at exactly one index \(n\), \(\forall i \in \mathbb {N}\) with \(i \geq n\) the invariant distribution differs only a constant \(c \in \mathbb {R}\) or \(c = \infty \).

For any two scheduling policies whose departure rates differ at exactly one index \(n\), \(\forall i \in \mathbb {N}\) with \(i \leq n - 1\) the invariant distribution at index \(i\) differs only a constant \(c \in \mathbb {R}\) or \(c = \infty \).

For any two scheduling policies \(P\) and \(Q\) whose departure rates differ at one index \(n\), and \(P's\) departure rate at this index is higher than \(Q\)’s. Then \(Q\)’s invariant distribution is a constant \(c \leq 1\) smaller than \(P\) at the indices \(i \leq n - 1\) and \(Q\)’s invariant distribution is a constant \(C \geq 1\) bigger than \(P\)’s at the indices \(i \geq n\).

The invariant distribution of a scheduling policy whose rate is never \(0\) is of the form:

at index \(n\)

For any concave, sublinear speedup function, \(s\) with \(\alpha \in \mathbb {R}^n\), the function \(i\cdot s(\frac{\alpha }{i})\) is increasing in \(i\) for all \(i{\lt}||\alpha ||_1\), and is non-decreasing in \(i\) for all \(i\geq ||\alpha ||_1\).

If there exists finite \(A \subsetneq \mathbb {N}\) such that for all \(n \in A\) the departure rate at state \(n\) is zero and there exists no \(n \notin A\) with departurerate \(0\). Then the invariant distribution has value \(0\) at \(i {\lt} \max (A)\).

The invariant distribution of a scheduling policy whose rate is never \(0\) is of the form:

at index \(n\).

Suppose we have an index \(n\) s.t. we know that \(\lambda _i = 0\) for all \(i {\lt} n\), and furthermore that the departurerate at index \(n\) is \(0\). And we also know that \(\exists m {\gt} n \in \mathbb {N}\) s.t \(\forall k \in \mathbb {N}\) with \(m \geq k {\gt} n\) the departurerates are greater than \(0\) then \(\lambda _k\) is of the form:

If there exists unique \(n \in \mathbb {N}\) such that the departure rate is \(0\) at state \(n\) then \(\forall i {\lt} n\) the invariant distribution has value \(0\) for state \(i\).

If we have two scheduling policies \(P\) and \(Q\). And \(P's\) departurerates are always higher than or equal to \(Q\)’s and let \(Q\) only have finite zero-valued departure rates. Then: