AITF: Applied Algorithmic Foundation for Scheduling Multiprogrammed Parallelizable Workloads

AITF：调度多程序可并行工作负载的应用算法基础

• 批准号: 1733873
• 负责人: I-Ting Lee
• 金额: $ 65万
• 依托单位: Washington University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1733873&HistoricalAwards=false
• 关键词: AITF; Applied; Algorithmic; Foundation; Scheduling

Most modern computing systems contain multiprocessor hardware which is shared by many applications. In these systems, good scheduling algorithms that decide how to allocate resources among applications are crucial to ensure good quality of service and efficient use of system resources. This project will design foundational algorithms and prototype implementations of scheduling algorithms that provide guarantees of performance and resource utilization for these shared machines. This work will shape the efficiency of critical computing infrastructure by improving performance of parallel systems from personal computers to data centers to supercomputers. All results, including published articles and software artifacts, will be released to the public via world-wide web. The PIs will integrate research with education by incorporating this research into the PIs' graduate courses and training PhD, MS, and BS students in applied and theoretical parallel computing research.The project will involve designing practically efficient schedulers guided by theoretical foundations. The PIs will design a theory of multi-programmed scheduling for parallel programs by considering a variety of scheduling objectives important to system designers. In particular, the research will focus on optimizing latency objectives that are used in servers, clouds, and interactive systems. The PIs will also explore efficient mechanisms that can be used to implement these algorithms in practice and perform empirical validations of their designs. By combining theoretical analysis with feedback from empirical evaluations, the proposed work will gain insights that will advance the state of the art of both theory and practice of parallel job scheduling.

大多数现代计算系统包含由许多应用程序共享的多处理器硬件。 在这些系统中，良好的调度算法决定如何分配资源之间的应用程序是至关重要的，以确保良好的服务质量和系统资源的有效利用。 这个项目将设计基础算法和原型实现的调度算法，提供保证的性能和资源利用率，这些共享的机器。 这项工作将通过提高从个人计算机到数据中心再到超级计算机的并行系统的性能来塑造关键计算基础设施的效率。 所有结果，包括已发表的文章和软件工件，将通过万维网向公众发布。 该项目将把研究与教育结合起来，把这项研究纳入研究所的研究生课程，培训博士、硕士和学士学位的学生进行应用和理论并行计算研究。该项目将涉及在理论基础的指导下设计实用高效的并行计算器。 PI将通过考虑对系统设计者重要的各种调度目标来设计并行程序的多程序调度理论。 特别是，该研究将专注于优化服务器、云和交互式系统中使用的延迟目标。 PI还将探索可用于在实践中实现这些算法的有效机制，并对其设计进行经验验证。 通过将理论分析与经验评估的反馈相结合，所提出的工作将获得见解，这将推进并行作业调度的理论和实践的最新发展。

项目成果

Contention Resolution with Message Deadlines

• DOI: 10.1145/3350755.3400239
• 发表时间: 2020-07
• 期刊: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: Kunal Agrawal;M. A. Bender;Jeremy T. Fineman;Seth Gilbert;Maxwell Young

Efficient Access History for Race Detection

用于种族检测的高效访问历史记录

• DOI: 10.1145/3409964.3461825
• 发表时间: 2022
• 期刊: 022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX
• 作者: Xu, Yifan;Zhou, Anchengcheng;Yin, Grace Q.;Agrawal, Kunal;Lee, I-Ting Angelina;Schardl, Tao B.
• 通讯作者: Schardl, Tao B.

Submodular Optimization with Contention Resolution Extensions

具有争用解决扩展的子模块优化

• DOI: 10.4230/lipics.approx-random.2019.3
• 发表时间: 2019
• 期刊: APPROX
• 作者: Benjamin Moseley, Maxim Sviridenko

Responsive parallelism with futures and state

与 future 和 state 的响应式并行

• DOI: 10.1145/3385412.3386013
• 发表时间: 2020
• 期刊: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation
• 作者: Muller, Stefan K.;Singer, Kyle;Goldstein, Noah;Acar, Umut A.;Agrawal, Kunal;Lee, I-Ting Angelina
• 通讯作者: Lee, I-Ting Angelina

A Relational Gradient Descent Algorithm For Support Vector Machine Training

支持向量机训练的关系梯度下降算法

• DOI: 10.1137/1.9781611976489.8
• 发表时间: 2021
• 期刊: Symposium on Algorithmic Principles of Computer Systems (APOCS
• 作者: Abo-Khamis, M.;Im, S.;Moseley, B.;Pruhs, K.;Samadian, A.
• 通讯作者: Samadian, A.