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.

随着大量低成本计算资源的越来越多，利用其力量在现代科学和工程中至关重要。一个特定的问题涉及调度：将资源（例如计算周期）分配给任务以确保良好性能的最有效方法是什么？ 当对任务的预先了解，包括何时到达以及可能需要多少计算时间时，调度问题尤其严重。在这种情况下，需要动态资源分配。 在过去的二十年中，已经出现了令人兴奋的解决这些所谓的在线调度问题的方法，但是该领域仍在努力解决现代计算集群中日益具有挑战性的调度环境。 该项目旨在开发新的方法，借助广泛使用的优化技术来系统地设计和分析在线调度算法，并因此可以解决在线计划中的一些关键开放问题。 研究发现可能会提供另一种方法，以在广泛的背景下对学生进行教育，这将对计算机科学课程产生重大影响。该项目还将涉及指导学生并通过研讨会，撰写教程和开发新课程材料来传播研究成果。在技​​术层面上，该项目打算研究在线调度技术针对各种问题的有效性。 该项目的第一个目标是开发新的渐变方法来设计和分析在线安排。第二个目标是使用bin包装来研究基本的录取控制问题，并在允许先发制的时候开发新的算法工具。要研究的第三个研究问题涉及开发低维度调度环境的细粒度调度算法。令人惊讶的是，尽管最近进步，但在低维情况下，即使对于最简单的贪婪算法来说，许多现有算法也不匹配，这在实践中很常见。第四个研究目标是在工作量接近系统限制时完善在线算法的行为，这与有关基础分析模型的基本问题有关。最后的目标是通过利用大规模的调度环境来探索与依赖性相互依存的新模型，以避免传统模型中常见的棘手性结果。该奖项反映了NSF的法定任务，并认为通过使用该基金会的知识分子和更广泛的影响来评估Criteria Criteria Criteria，并被认为是通过评估来通过评估来获得支持的。

项目成果

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.

Faster Matchings via Learned Duals

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

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 Knapsack with Frequency Predictions

带有频率预测的在线背包

• 发表时间: 2021
• 期刊: Advances in neural information processing systems
• 作者: Im, Sungjin;Kumar, Ravi;Montazer Qaem, Mahshid;Purohit, Manish
• 通讯作者: Purohit, Manish

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