## 1 Introduction
If we assign additional data-remote tasks to the server, all the tasks' (including the existing \(k\) data-remote tasks) data transfer costs must be recomputed. To minimize job completion time, the scheduler needs more adjustment and recomputation, which significantly increases time complexity. * Second, the scheduling instance is large. A production data-parallel system might even contain tens of thousands of multicore servers. Because each server contains tens of processor cores, the total number of task slots can be hundreds of thousands. Meanwhile, the number of data-parallel tasks is also large. For example, assuming a data block's size is 128 MB, the scheduler needs to assign about 8000 tasks to process a 1-terabyte file. Because the data transfer cost is dynamic and the scheduling instance is large, it is difficult to design an effective scheduler that has a low scheduling latency. Keeping this in mind, here we study a data-locality-aware task-scheduling problem, taking the dynamic data transfer costs into account. Although many have proposed data-locality-aware task-scheduling algorithms [7; 8; 9; 10; 11; 12], usually researchers define data transfer costs as static values, rather than making them robustly adaptable or representative of changes in costs. Some recent research does consider dynamic data transfer costs. For instance, the Hadoop task-assignment problem [13; 14] uses a non-decreasing function to evaluate data transfer costs such that the data transfer cost increases with the total number of data-remote tasks. [PERSON] [15] models data-remote tasks' runtime as random variables. However, these works either set an identical cost for all data-remote tasks or assume all data-remote tasks' runtime follows the same stochastic model, which does not fit our situation (where data transfer costs on different servers are quite different). Previous approaches also discussed both offline and online scheduling modes. First, offline scheduling uses elaborate algorithms to find high-quality assignments [8; 9; 13; 14], but most of them have high scheduling latencies. One approach, Firmament [9], is a low-latency offline scheduling algorithm, but its sophistic model is hard to extend to dynamic data transfer costs. Second, online scheduling [2; 7] is based on a sever-by-server policy. Once a server is idle, the scheduler scans the task queue to select the best task for the server. Compared to the offline scheduling algorithms, the online scheduling algorithms usually possess low scheduling latencies, but they generate suboptimal assignments. Moreover, to the best of our knowledge, dynamic data transfer costs are not considered by existing online scheduling algorithms. To address these problems, we propose a novel task-scheduling model, called DynDL (Dynamic Data Locality), for assigning data-locality-aware tasks on multicore servers. Inspired by the Hadoop Task Assignment (HTA) model, we use a non-decreasing function \(g_{i}(n_{i})\) to evaluate the dynamic data transfer cost on server \(i\), where \(n_{i}\) is the number of data-remote tasks on server \(i\). Compared to existing models, our model is more flexible, letting users define a personalized cost function \(g_{i}(\cdot)\) for each server \(i\) according to the server's workload and network bandwidth. To quickly schedule tasks, we propose two efficient task-scheduling algorithms, called DynDLOff and DynDLOn, for the offline and online modes, respectively. DynDLOff first generates an initial task assignment that only contains  
Figure 1: Data-locality-aware task scheduling (task \(t_{i}\) processes block \(i\)). (**a**) Hadoop default scheduler’s assignment; (**b**) Optimal assignment. data-local tasks, then refines the task assignment by gradually adding data-remote tasks. Based on the initial task assignment, DynDLOff can efficiently evaluate the dynamic data transfer cost for each server, so it has latencies of subseconds or seconds. DynDLOn is based on a delay-scheduling heuristic.