Optimal Scheduling of Parallelizable Jobs in Cloud Computing Environments

该奖项将通过衍生方法来改善云计算环境中处理作业的响应时间，从而促进国家繁荣和经济福利。 如今，大公司的数据中心和超级计算中心都在大量处理机器学习作业，其中每个作业都并行占用多个服务器/核心。 虽然串行作业调度有很长的历史，但对并行作业调度知之甚少，现有的并行作业调度在云计算环境中表现不佳。 该奖项将开发算法，有效地分配有限数量的服务器在一组并行化的作业。 最优调度是困难的，因为单个并行作业从分配给它的每个附加服务器接收递减的边际效益。 PI将开发新的分析方法来解决这个复杂的调度问题。 这项研究的结果与行业高度相关，并将为最先进的云调度系统提供信息。 算法、协议和实验结果将通过期刊出版物、在线代码和开放获取数据库进行传播。 作为该奖项的一部分，PI将为中学女生提供外展服务，以提高她们在数学和计算方面的接触和技能，并对本科生和博士生进行并行计算、调度和调度方面的培训。该奖项将支持在并行作业中优化分配有限数量的服务器的研究，以最小化平均流时间、平均减速和相关指标。受现实世界的基准测试和测量的启发，并行作业通过凹加速函数建模，该函数指定作业的加速效益作为分配给它的服务器数量的函数。研究计划解决了各种各样的情况，包括作业具有不同加速函数的情况，作业具有不同优先级的情况，作业大小先验未知的情况，以及随着时间的推移，工作岗位会在哪里出现。 导出最佳调度策略将需要开发新的分析技术，以大大减少可能的分配的搜索空间，并揭示最佳解决方案的结构。 为了实现这一目标，该奖项将开发一系列降维技术，包括无标度属性，大小不变属性，在线完成顺序属性，用于权衡作业大小和不同并行化级别的技术，以及Gittins Index调度策略的并行对应物。 结果将首先通过随机模拟进行验证，然后通过使用来自行业和超级计算中心的跟踪的跟踪驱动模拟进行验证。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。

This award will contribute to the advancement of national prosperity and economic welfare by deriving methods to improve response times for processing jobs in cloud computing environments. Today, data centers of major companies and supercomputing centers are heavily occupied in processing machine learning jobs, where each job occupies multiple servers/cores in parallel. While there is a long history on scheduling for serial jobs, less is known about parallel job scheduling, and existing heuristics perform poorly in the cloud computing environment. This award will develop algorithms for efficiently allocating a finite number of servers across a set of parallelizable jobs. Optimal scheduling is difficult because an individual parallel job receives decreasing marginal benefit from each additional server that it is allocated. The PIs will develop new analytical methods to address this complex scheduling problem. The results of this research are highly relevant to industry and will inform state-of-the-art cloud scheduling systems. Algorithms, protocols, and experimental results will be disseminated via journal publications, online code and open access data repositories. As part of this award, the PIs will provide outreach to middle school girls to increase exposure and skills in mathematics and computing, as well as training of both undergraduates and PhD students in the areas of parallel computing, scheduling, and queueing.This award will support research on optimally allocating a finite number of servers across parallel jobs, so as to minimize mean flow time, mean slowdown, and related metrics. Motivated by real-world benchmarks and measurements, parallel jobs are modeled via a concave speedup function which specifies the speedup benefit to the job as a function of the number of servers which are allocated to it. The research plan addresses a wide variety of situations, including the case where jobs have different speedup functions, where jobs have different priorities, where job sizes are not known a priori, and where jobs arrive over time. Deriving optimal scheduling strategies will require the development of new analytic techniques to vastly reduce the search space of possible allocations and reveal the structure of the optimal solution. Towards that goal, the award will develop a series of dimensionality reduction techniques, including a scale-free property, a size-invariant property, an online completion order property, a technique for trading off job sizes and different parallelization levels, and a parallel counterpart to the Gittins Index scheduling policy. Results will be validated first via stochastic simulation and then via trace-driven simulation using traces from industry and supercomputing centers.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.