Optimal Scheduling of Parallelizable Jobs in Cloud Computing Environments

该奖项将通过得出改进云计算环境中处理作业的响应时间的方法，为促进国家繁荣和经济福利做出贡献。如今，大公司的数据中心和超算中心都在大量占用处理机器学习的作业，每个作业并行占用多个服务器/核心。虽然对串行作业的调度有很长的历史，但对并行作业调度的了解较少，而且现有的启发式算法在云计算环境中的性能很差。该奖项将开发在一组可并行作业中高效地分配有限数量的服务器的算法。最优调度是困难的，因为单个并行作业从分配给它的每个额外的服务器获得递减的边际收益。绩效指标将开发新的分析方法来解决这一复杂的调度问题。这项研究的结果与行业高度相关，并将为最先进的云调度系统提供参考。算法、协议和实验结果将通过期刊出版物、在线代码和开放访问数据存储库传播。作为该奖项的一部分，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.