## 1 Introduction  
Data-parallel frameworks such as MapReduce [1], Hadoop [2], Spark [3], Pregel [4], and TensorFlow [5] have emerged as important components in big data-processing ecosystems. For example, the Spark deployment at Facebook processes tens of petabytes of newly-generated data every day, and a single job can process hundreds of terabytes of data [6]. Because data-parallel frameworks process terabytes or petabytes of data on hundreds or thousands of servers, the costs of transferring data between servers significantly affect the frameworks' performance. Hence, data locality becomes a fundamental problem for all data-parallel frameworks. Data locality means moving computational tasks rather than moving data to save the network bandwidth. In data-parallel frameworks such as Hadoop or Spark, data files are divided into fixed-size data blocks and stored on distributed file systems. (On the Hadoop distributed file system, a data block's default size is 128 megabytes (MB).) For fault tolerance, each block has multiple replicas that spread over the servers. To process the file, a job is divided into data-parallel tasks (e.g., Hadoop's map tasks and Spark's narrow transformation tasks), each of which is assigned to an idle server and processes a data block on the server. As data blocks are distributed over servers, a task reads the input data blocks from either local memories/disks (i.e., data local) or remote servers through networks (i.e., data remote). To reduce data transfer costs, data-locality-aware task scheduling that assigns tasks close to the input data block is used widely by existing data-parallel frameworks. Although the idea is quite simple, it is non-trivial to design an effective and efficient data-locality-aware task scheduler, because it should consider the time for waiting for free servers, the time for transferring data blocks, and the data blocks' placements. At the same time, it is required to handle the scheduling instances that contain a large number of tasks and servers in a timely fashion. Thus, an ideal data-locality-aware task scheduler is expected to minimize job completion time, adaptively adjust data locality, and timely schedule tens of thousands or more tasks. Although researchers proposed many data-locality-aware scheduling algorithms in the past decade, it is difficult to design an ideal data-locality-aware task scheduler for multicore servers. A multicore server contains two or more identical processor cores that are connected to a single shared main memory, and has full access to all input and output devices. In a modern data center, the number of processor cores on a single server can be tens or more. For example, the Amazon Elastic Compute Cloud (EC2) r5.24 xlarge instances ([[https://aws.amazon.com/ec2/instance-types](https://aws.amazon.com/ec2/instance-types)]([https://aws.amazon.com/ec2/instance-types](https://aws.amazon.com/ec2/instance-types))) support up to 96 processor cores. Because of the multiple cores, multiple tasks (which compete for limited network bandwidth) can simultaneously run on the same server. Figure 1 illustrates this problem. The Hadoop default scheduler assigns two data-remote tasks to the second server. However, for an optimal assignment, it assigns only a data-remote task to the server. Its data transfer cost and makespan are much lower than the Hadoop default scheduler's, but this leads to an onerous challenge: How can we design an effective and efficient data-locality-aware task scheduler for large-scale multicore servers? * First, the data transfer cost on a multicore server is dynamic. It changes with the number of concurrent data-remote tasks on the server. For example, if \(k\) data-remote tasks on the same server transfer data simultaneously, the data transfer costs are almost \(k\) times larger than the data transfer cost of a single data-remote task. This significantly increases the difficulties in minimizing job completion time. Suppose a server is running \(k\) data-remote tasks.