权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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将为到达的作业流开发调度算法，其中的作业是复杂的多线程细粒度并行作业，具有动态并行性和任务之间的依赖性。该研究将解决以下三个具体挑战。挑战1，统计表征/建模：调度多个作业需要了解每个作业何时完成以及它将来会做什么，例如它将创建的任务数量或任务粒度。该项目的一个重要部分致力于测量并行工作，并对它们进行统计表征，以创建其行为的简单模型。挑战2，算法开发和分析：目前还没有针对正在考虑的问题的调度算法。虽然排队理论鼓吹总是以“最短的预期剩余时间”运行作业的最优性，但当作业是并行的并且有许多资源时，这一点几乎没有意义。新的定理和分析技术将得到发展。挑战3，实现和基准测试：项目的一个重要组成部分将是我们的算法在原型系统上的实现和基准测试。pi将调查多个指标，包括延迟、吞吐量、公平性和鲁棒性。