CAREER: New Algorithmic Foundations for Online Scheduling

职业：在线调度的新算法基础

• 批准号: 1844939
• 负责人: Sungjin Im
• 金额: $ 50万
• 依托单位: University of California - Merced
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1844939&HistoricalAwards=false
• 关键词: CAREER; New; Algorithmic; Foundations; Online

As massive low-cost computing resources become increasingly available, harnessing their power is crucial in modern science and engineering. One particular issue involves scheduling: what is the most effective way to assign resources, say computing cycles, to tasks in order to ensure good performance? The scheduling problem is especially acute when little to nothing is known in advance about the tasks, including when they might arrive and how much compute time they may need; in such cases, dynamic allocation of resources is required. Over the past two decades, exciting advances in approaches for addressing these so-called on-line scheduling problems have emerged, but the field is still struggling to address the increasingly challenging scheduling environments found in modern computing clusters. This project aims to develop new methods to design and analyze online scheduling algorithms systematically with the aid of widely used optimization techniques, and as a result to potentially resolve some key open questions in online scheduling. The research findings will likely provide an alternative method of educating students on scheduling in a broad context, which will have a significant impact on the computer science curriculum. This project will also involve mentoring students and disseminating the research outcomes through workshops, writing tutorials, and developing new course materials. At a more technical level, this project intends to investigate the effectiveness of online scheduling techniques for a variety of problems. The project's first objective is to develop new gradient-descent methods to design and analyze online-scheduling. The second objective is to use bin-packing to study fundamental admission-control problems, and to develop new algorithmic tools when pre-emption is allowed. The third research problem to be studied involves the development of fine-grained scheduling algorithms for low-dimensional scheduling environments. Surprisingly, despite recent advances, many existing algorithms are no match even for the simplest greedy algorithms in the low-dimensional case, which is common in practice. The fourth research goal is to refine the behavior of the online algorithms as the workload approaches the system limit, which is related to fundamental questions regarding the underlying analysis models. The last goal is to explore new models for scheduling jobs with inter-dependencies by taking advantage of large-scale scheduling environments to circumvent the intractability results that are commonly found in the traditional models.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

随着大量低成本计算资源变得越来越可用，利用它们的能力在现代科学和工程中至关重要。一个特别的问题涉及调度：什么是最有效的方式来分配资源，比如计算周期，任务，以确保良好的性能？ 调度问题在对任务几乎一无所知的情况下尤其严重，包括任务何时到达以及需要多少计算时间;在这种情况下，需要动态分配资源。 在过去的二十年中，令人兴奋的进步，解决这些所谓的在线调度问题的方法已经出现，但该领域仍然在努力解决日益具有挑战性的调度环境中发现现代计算集群。 本项目的目的是开发新的方法来设计和分析在线调度算法系统的辅助下，广泛使用的优化技术，并作为一个潜在的解决在线调度中的一些关键的开放问题。 研究结果可能会提供一种替代方法，在广泛的背景下，这将对计算机科学课程产生重大影响的调度教育学生。该项目还将涉及指导学生和通过研讨会传播研究成果，编写教程和开发新的课程材料。在一个更技术的水平，这个项目打算调查的有效性，在线调度技术的各种问题。 该项目的第一个目标是开发新的梯度下降法来设计和分析在线调度。第二个目标是使用装箱研究基本的准入控制问题，并开发新的算法工具时，允许抢占。要研究的第三个研究问题涉及低维调度环境的细粒度调度算法的发展。令人惊讶的是，尽管最近的进展，许多现有的算法是不匹配的，即使是最简单的贪婪算法在低维的情况下，这是常见的在实践中。第四个研究目标是在工作量接近系统极限时改进在线算法的行为，这与底层分析模型的基本问题有关。最后一个目标是利用大规模的调度环境来规避传统模型中常见的棘手结果，从而探索调度具有相互依赖性的作业的新模型。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Faster Matchings via Learned Duals

• 发表时间: 2021-07
• 期刊: ArXiv
• 作者: M. Dinitz;Sungjin Im;Thomas Lavastida;Benjamin Moseley;Sergei Vassilvitskii

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.

Approximate Aggregate Queries Under Additive Inequalities

加性不等式下的近似聚合查询

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

Online Learning and Bandits with Queried Hints

• DOI: 10.48550/arxiv.2211.02703
• 发表时间: 2022-11
• 作者: Aditya Bhaskara;Sreenivas Gollapudi;Sungjin Im;Kostas Kollias;Kamesh Munagala

Instance Optimal Join Size Estimation

实例最佳连接大小估计

• DOI: 10.1016/j.procs.2021.11.019
• 发表时间: 2021
• 期刊: Procedia Computer Science
• 作者: Abo-Khamis, Mahmoud;Im, Sungjin;Moseley, Benjamin;Pruhs, Kirk;Samadian, Alireza
• 通讯作者: Samadian, Alireza