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寻求在数据中心研究工作时间表，以优化诸如响应时间的时间质量质量质量，例如响应时间及其公平性，以及工作的资源需求可以具有多维的资源要求。 研究所研究的主要问题可以写成：工作安排与资源需求维度的相互作用的时间性质如何，以及这两者如何与激励和公平的经典经济持续性相互作用？该项目与以前的工作不同？与以前的工作相互区分，旨在通过在线计算机科学的范围来开发适当的模型和算法，尤其是通过理论计算机科学的镜头来开发适当的模型和算法。算法游戏理论和随机优化。由此产生的见解也将用于开发新技术，以解决违反成功解决方案的经典调度和游戏理论问题。 该项目是跨学科的，而开发的理论模型和技术将由新硬件架构的应用领域源于新兴技术的新硬件体系结构，以及在数据中心中配备它们而产生的异质性。此外，还将通过对数据中心执行的痕迹进行仿真，以及集群的部署和实验，进行经验验证。 这最终将影响使用和生成大量数据的互联网系统的设计和部署。项目的跨学科性质不仅指出，不仅需要培训从高中生到毕业生的学生的管道，并向他们传授算法思维的力量及其更广泛的相关性，而且还需要更广泛的相关性，还需要使科学家，数学相同的构建构建者和系统建设者相同的构建者，以实现与我们相同的构建者。为此，PI试图通过包括有效的教学和指导的教育计划来为下一代学生（包括妇女和少数民族）配备相关的算法技能，并通过组织研讨会和撰写书籍和调查来广泛地传播拟议的工作。

项目成果

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