AF: Medium: Collaborative Research: Multi-dimensional Scheduling and Resource Allocation in Data Centers

AF：中：协同研究：数据中心多维调度与资源分配

• 批准号: 1409130
• 负责人: Sungjin Im
• 金额: $ 39.02万
• 依托单位: University of California - Merced
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1409130&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Multi

Data centers and cluster computing platforms have become the dominant computational paradigms of the past decade, becoming the de facto method of executing Big Data workloads. Typically, the entire cluster is treated as a set of resources shared by multiple clients who submit jobs requiring different types of resources. To add to this heterogeneity (or dimensionality) in resource requirements, machines in a cluster can be heterogeneous in terms of resources they provide. In such settings, resources need to be allocated and priced appropriately so as to balance performance with demand.In this project, the PIs seek to study job scheduling in data centers to optimize temporal Quality of Service metrics such as response time along with fairness, when jobs can have resource requirements that are multi-dimensional. The main question studied can be phrased as: How does the temporal nature of job scheduling interplay with the dimensionality of resource requirements, and how do these two in turn interact with the classical economic desiderata of incentives and fairness?This project is differentiated from previous work in aiming to develop appropriate models and algorithms through the lens of theoretical computer science, particularly by a fusion of the disparate fields of approximation and online algorithms, algorithmic game theory, and stochastic optimization. The resulting insights will be used to also develop new techniques to address classical scheduling and game theoretic problems that have defied successful solutions. The project is interdisciplinary, and the theoretical models and techniques developed will be motivated by the application domain of new hardware architectures stemming from emerging technologies, and the heterogeneity arising from provisioning them within a data center. Further, empirical validations will be performed, both via simulation on traces from data center executions, as well as deployment and experiments on clusters. This will ultimately influence the design and deployment of internet systems that use and generate massive data.The interdisciplinary nature of the project points to not only the need for training a pipeline of students from high school students to graduates and imparting to them the power of algorithmic thinking and its broader relevance, but also the necessity for bringing scientists, mathematicians, and system builders to the same platform for active exchange of ideas. Towards this end, the PIs seek to equip the next generation of students, including women and minorities, with the relevant algorithmic skills by an education plan that includes effective teaching and mentorship, as well as to broadly disseminate the proposed work by organizing workshops and by writing books and surveys.

数据中心和集群计算平台已经成为过去十年中占主导地位的计算范式，成为执行大数据工作负载的事实上的方法。通常，整个集群被视为由多个客户机共享的一组资源，这些客户机提交需要不同类型资源的作业。为了增加资源需求的异构性（或维度），集群中的机器就其提供的资源而言可以是异构的。在这种情况下，需要适当地分配和定价资源，以平衡绩效与需求。在这个项目中，pi试图研究数据中心中的作业调度，以优化时间服务质量指标，如响应时间和公平性，当作业可能具有多维资源需求时。研究的主要问题可以概括为：工作调度的时间性质如何与资源需求的维度相互作用，这两者又如何与激励和公平的经典经济学愿望相互作用？该项目与之前的工作不同，旨在通过理论计算机科学的视角开发适当的模型和算法，特别是通过融合近似和在线算法、算法博弈论和随机优化等不同领域。由此产生的见解也将用于开发新的技术来解决经典的调度和博弈论问题，这些问题没有成功的解决方案。该项目是跨学科的，所开发的理论模型和技术将受到源于新兴技术的新硬件架构的应用领域的激励，以及在数据中心内提供它们所产生的异质性。此外，还将通过对数据中心执行轨迹的模拟以及对集群的部署和实验进行经验验证。这将最终影响使用和产生大量数据的互联网系统的设计和部署。该项目的跨学科性质不仅表明需要培养从高中生到毕业生的学生管道，并向他们传授算法思维的力量及其更广泛的相关性，而且还需要将科学家，数学家和系统构建者带到同一个平台上积极交流思想。为此目的，ppi寻求通过一项包括有效教学和指导在内的教育计划，使包括妇女和少数民族在内的下一代学生掌握相关的算法技能，并通过组织讲习班和编写书籍和调查广泛传播拟议的工作。

项目成果

Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution

• DOI: 10.1137/1.9781611975994.170
• 发表时间: 2020-01
• 作者: Sungjin Im;Maryam Shadloo

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

Online Two-Dimensional Load Balancing

在线二维负载均衡

• DOI: 10.4230/lipics.icalp.2020.34
• 发表时间: 2020
• 期刊: ICALP
• 作者: Cohen, Ilan;Im, Sungjin;Panigrahi, Debmalya
• 通讯作者: Panigrahi, Debmalya

Dynamic Weighted Fairness with Minimal Disruptions

动态加权公平，干扰最小

• DOI: 10.1145/3379485
• 发表时间: 2020
• 期刊: Proceedings of the ACM on Measurement and Analysis of Computing Systems
• 作者: Im, Sungjin;Moseley, Benjamin;Munagala, Kamesh;Pruhs, Kirk
• 通讯作者: Pruhs, Kirk

Hallucination Helps: Energy Efficient Virtual Circuit Routing

幻觉有帮助：节能虚拟电路路由

• DOI: 10.1137/18m1228591
• 发表时间: 2020
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Antoniadis, Antonios;Im, Sungjin;Krishnaswamy, Ravishankar;Moseley, Benjamin;Nagarajan, Viswanath;Pruhs, Kirk;Stein, Clifford
• 通讯作者: Stein, Clifford