## 3 The DynDL Scheduling Model  
In this section, we focus on a scheduling problem that assigns data-parallel tasks on a multicore-server-based computing cluster. The cluster follows a shared-nothing architecture, consisting of many network-connected servers. Each server contains multiple homogenous processor cores that share the server's storage space and network bandwidth. The data-parallel tasks are independent and data-intensive. Each task processes an input file block, and then it places the file blocks on the server's local storage (disks or memories). Before performing data processing, tasks are assigned to an idle core, and then they read the data blocks from local storage or a remote server. The scheduling problem is to find a _task assignment strategy_ that minimizes all the tasks' completion time, taking into account the core's initial loads, tasks' running time, and data's transfer time. We formally define the scheduling problem as follows. The computing system is a 3-tuple \((S,T,DL^{srv})\), where \(S\) and \(T\) are the server and task sets, respectively, and \(DL^{srv}\) is a data placement function. Each server \(s\in S\) contains a set of cores \(core(s)\). We denote the core set as \(P\), such that \(P=\bigcup_{s\in S}core(s)\). Each core \(p\in P\) belongs to a unique server \(srv(p)\in S\). If task \(t\)'s data block stores on server \(s\)'s storage, we say that \(t\) prefers \(s\) (or the cores on \(s\)). The sets of servers and cores that task \(t\) prefers are denoted as \(DL^{srv}(t)\) and \(DL^{core}(t)\), respectively. In real-life systems, each data block has a fixed number of replicas and each server has a fixed number of cores, so in our problem \(|DL^{srv}(t)|\) and \(|core(s)|\) are constants. **Task assignment and makespan. ** The task assignment strategy is a mapping function \(\mathcal{A}:T\to P\) that assigns tasks to cores. We measure an assignment's quality by a makespan. To define the makespan, we first define the task costs and core loads. Given an assignment \(\mathcal{A}\), a task \(t\) is data-local if and only if \(\mathcal{A}(t)\in DL^{core}(t)\). Otherwise, task \(t\) is data-remote. Because data-parallel tasks are homogeneous, we assume the cost of executing a data-local task is identical. For simplicity, let the data-local cost be 1. Regarding data-remote tasks, because the cores on the same server share limited network bandwidth, the data-remote cost increases with the number of data-remote tasks. Let \(r_{\mathcal{A}}^{s}\) be the number of data-remote tasks on server \(s\), then the task costs are  
\[C_{\mathcal{A}}(t)=\left\{ \begin{array}{ll}1,&\mathcal{A}(t)\in DL^{core}(t),\\ g_{s}(r_{\mathcal{A}}^{s}),&\text{otherwise},\end{array} \right. \tag{1}\]  
where \(s=srv(\mathcal{A}(t))\) and \(g_{s}(\cdot)>1\) is the data-remote cost, which is a non-decreasing function of the number of remote tasks on server \(s\). The _load_ of a core \(p\) is the time required to finish all the tasks assigned to \(p\). Given an assignment \(\mathcal{A}\), the load of core \(p\), \(L_{\mathcal{A}}(p)\), is  
\[L_{\mathcal{A}}(p)=L^{init}(p)+\sum_{t:\mathcal{A}(t)=p}C_{\mathcal{A}}(t), \tag{2}\]  
where \(L^{init}(p)\) is the _initial load_ on core \(p\) and \(\sum_{t:\mathcal{A}(t)=p}C_{\mathcal{A}}(t)\) is the time required to finish the tasks on \(p\). We use an initial load to model the core's idle time. Once we determine the task costs and core loads, then we know the makespan of \(\mathcal{A}\), the time when all the tasks are finished:  
\[\textit{makespan}(\mathcal{A})=\max_{p\in\mathcal{P}_{\mathcal{A}}}L_{ \mathcal{A}}(p). \tag{3}\]  
Here, \(\hat{P}_{\mathcal{A}}\) is a set of active cores. A core is active if and only if at least one task is assigned to the core. Table 1 lists the frequently used notations. Based on these definitions, we define the scheduling problem. **Scheduling problem. ** Given a computing system, each server's task cost function, and all the cores' initial loads, the problem's goal is to find an assignment that minimizes the makespan.