## 5 DynDLOff: An Offline Algorithm
### Phase II: Assign Data-Remote Tasks  
Phase II assigns data-remote tasks to reduce the balanced assignment's makespan. As we mentioned, a data-remote task's cost is dynamic, changing with the number of data-remote tasks on each server, so it is challenging to compute the cores' loads. To address this challenge, Phase II utilizes the balanced assignment's Property 1 to identify the data-remote tasks. Figure 4 and Algorithm 3 show the basic idea of Phase II. Given several deadlines, the algorithm generates a series of assignments. For each deadline \(D\), it tests whether there exists a new assignment \(\mathcal{A}\) with \(\mathit{makespan}(\mathcal{A})\leq D\). To perform the test, it divides the task set into two subsets, \(T_{loc}\) and \(T_{rem}\), according to the task finish time based on \(\mathcal{B}\), such that \(T_{loc}=\{t|t\in T\wedge F_{\mathcal{B}}(t)\leq D\}\) and \(T_{rem}=\{t|t\in T\wedge F_{\mathcal{B}}(t)>\mathcal{D}\}\), where \(F_{\mathcal{B}}(t)\) is task \(t\)'s finish time (given the initial assignment \(\mathcal{B}\) and a task \(t\); suppose \(t\) is the \(k\)th task on \(\mathcal{B}(t)\), then \(F_{\mathcal{B}}(t)=L^{init}(\mathcal{B}(t))+k\)). To lower the makespan, each task \(t\) in \(T_{loc}\) is assigned to \(\mathcal{B}(t)\) and the tasks in \(T_{rem}\) are moved to cores whose loads are smaller than \(D\). According to the balanced assignment's Property 1, we can conclude that the tasks in \(T_{rem}\) must be data-remote. Then, the algorithm checks \(\sum_{s\in S}r^{s}_{max}\geq|T_{rem}|\) to determine whether a task passes the test, where \(r^{s}_{max}\) is the maximum number of server \(s\)'s data-remote tasks that are completable before \(D\). The algorithm continuously checks different deadlines until a task fails the test. Then, it derives the final number of data-remote tasks and outputs a final assignment. Next, we illustrate how to compute deadlines and generate final assignments. **Input:** Balanced Assignment \(\mathcal{B}\), Servers \(S\), Cores \(P\), Tasks \(T\), Matrix \(\mathbf{R}\)  
**Output:** Final Assignment  
\(\mathbf{T}\gets\mathit{SortTasks}(\mathcal{B},T,P)\)  
for\(i\gets 0\) to \(|\mathbf{T}|\)do  
\(\mathbf{D}[i]\gets\)\(\mathcal{B}\)\(\mathbf{T}[i]\)  
// Array _tests_ stores the result of each test. // _tests_ contains the \(r_{max}^{s}\) for each server \(s\) for deadline \(\mathbf{D}[i]\). \(index\leftarrow\mathit{ComputeFinalDeadline}(0,|T|,\mathbf{D},tests,\mathbf{R})\)  
\(\mathcal{A}_{1}\leftarrow\mathit{ComputeFinalAssignment}(\mathcal{B}, \mathbf{T},\mathbf{D}[index],index,tests[index])\)  
\(\mathcal{A}_{2}\leftarrow\mathit{ComputeFinalAssignment}(\mathcal{B}, \mathbf{T},\mathbf{D}[index+1],index+1,tests[index+1])\)  
**return**\(\mathit{BestAssignment}(\mathcal{A}_{1},\mathcal{A}_{2})\)  
**Algorithm 3** DynDLOff: Assign Data-Remote Tasks (Phase II). **Computing proper deadline \(\mathbf{D}\). ** Given a balanced assignment \(\mathcal{B}\) and initial load \(L^{init}(p)\) for each core \(p\), this step computes a proper deadline \(D\). Based on \(\mathcal{B}\) and \(L^{init}\), we first sort the all the tasks by their finish time \(F_{\mathcal{B}}(t)\) in descending order such that \(F_{\mathcal{B}}(t_{1})\geq F_{\mathcal{B}}(t_{2})\geq\cdots\geq F_{\mathcal{B }}(t_{|T|})\), and then compute an array \(\mathbf{D}\) containing \(|T|\) deadlines such that \(\mathbf{D}[i]=F_{\mathcal{B}}(t_{i+1})\). Because we base the deadlines on the task finish time, deadline \(\mathbf{D}[i]\) implies there are \(i\) data-remote tasks. Our goal is to find an index \(k\) such that \(\forall i\leq k\), deadline \(\mathbf{D}[i]\) passes the test and \(\forall i>k\), deadline \(\mathbf{D}[i]\) fails the test. We find \(k\) by performing a binary search on \(\mathbf{D}\), and then set \(D\) to \(\mathbf{D}[k]\). To perform a test for \(\mathbf{D}[i]\), we compute \(r_{max}^{s}\) for each server, then check whether \(\sum_{s\in S}r^{s}\geq i\).