XPS: FULL: Bridging Parallel and Queueing-Theoretic Scheduling

XPS：FULL：桥接并行和排队理论调度

基本信息

批准号：
1629444
负责人：
Guy Blelloch
金额：
$ 82.5万
依托单位：
Carnegie-Mellon University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2016
资助国家：
美国
起止时间：
2016-07-01 至 2020-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1629444&HistoricalAwards=false
关键词：
XPS FULL Bridging Parallel Queueing

项目摘要

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.

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