XPS: FULL: Bridging Parallel and Queueing-Theoretic Scheduling

自20世纪50年代以来，在计算资源上调度计算任务在计算机科学中扮演着重要的角色。调度的一个分支(排队论)专注于分析多个连续作业竞争共享资源，目标是最小化所有作业的响应时间(延迟)。大多数操作系统和服务器调度器使用的想法都是本研究的一部分。调度的另一个分支(并行)专注于分析在专用并行机上运行的单个并行作业，目标是最大化作业的效率(吞吐量)。大多数动态并行程序的调度器使用作为本研究的一部分开发的想法。直到最近，这些分支机构本身就足够了，研究它们的社区几乎没有互动。然而，并行硬件的主流可用性，以及处理共享单个资源的多个并行作业的需要，最近改变了这一点。该项目的目标是通过开发新的理论和实用的调度算法来连接这两个分支，以处理多个动态并行的作业竞争共享资源。该项目汇集了来自每个领域的专业人员，并将应用和结合来自每个领域的技术。该项目有可能对广泛使用的共享并行系统的理论和实践产生重大而广泛的影响。该项目将包括一个教育外展部分，在该部分中，私人投资总监将在他们教授的课程中纳入该项目的想法。这个项目是第一个处理这两个领域结合的项目。PI将为到达的作业流开发调度算法，其中作业是复杂的多线程细粒度并行作业，任务之间具有动态并行性和依赖性。这项研究将解决三个具体挑战，如下所示。挑战1，统计特征/建模：调度多个作业需要了解每个作业何时完成以及它将来要做什么，例如它将创建的任务数量或任务的粒度。该项目的很大一部分致力于衡量并行工作并对其进行统计表征，以创建其行为的简单模型。挑战2，算法开发和分析：目前还没有针对正在考虑的问题的调度算法。虽然排队理论吹捧总是以最短的预期剩余时间运行作业是最优的，但当作业是并行的并且有很多资源时，这就没有什么意义了。新的定理和分析技术将被开发出来。挑战3，实施和基准：该项目的一个重要组成部分将是在原型系统上实施和基准我们的算法。PI将调查多个指标，包括延迟、吞吐量、公平性和稳健性。

Scheduling computational tasks on computational resources has played a fundamental role in computer science since the 1950s. One branch of scheduling (queueing theoretic) has focused on analyzing multiple sequential jobs competing for a shared resource with the goal of minimizing the response time (latency) over all jobs. Most operating system and server schedulers use ideas developed as part of this research. Another branch of scheduling (parallel) has focused on analyzing a single parallel job running on a dedicated parallel machine, with the goal of maximizing efficiency (throughput) of the job. Most schedulers for dynamically parallel programs use ideas developed as part of this research. Until recently these branches were adequate on their own, and the communities studying them have had very little interaction. However, the mainstream availability of parallel hardware, and the need to handle many parallel jobs sharing a single resource, has recently changed this. The goal of this project is to bridge the two branches by developing new theory and practical scheduling algorithms, that can handle multiple dynamically parallel jobs competing for shared resources. The project brings together PIs with expertise from each area, and will apply and combine techniques from each area. The project has the potential to have significant broad impact on the theory and practice of widely used shared parallel systems. The project will include an educational outreach component in which the PIs will include ideas from the project in courses they teach.This project is the first to tackle the union of these two domains. The PIs will develop scheduling algorithms for a stream of arriving jobs, where the jobs are complex multi-threaded fine-grained parallel jobs with dynamic parallelism and dependencies among tasks. The research will address three specific challenges, as follows. Challenge 1, Statistical Characterization/Modeling: Scheduling multiple jobs requires knowing something about when each job will complete and what it will do in the future, such as the number of tasks it will create or the granularity of tasks. A significant part of the project is devoted to measuring parallel jobs and statistically characterizing them to create simple models of their behavior. Challenge 2, Algorithmic Development and Analysis: There are currently no scheduling algorithms for the problem that is being considered. While queueing theory touts the optimality of always running the job with the "shortest expected remaining time," this has little meaning when jobs are parallel and there are many resources. New theorems and analytical techniques will be developed. Challenge 3, Implementation and Benchmarking: An important component of the project will be the implementation and benchmarking of our algorithms on prototype systems. The PIs will investigate multiple metrics including latency, throughput, fairness, and robustness.