AF: Small: Communication-Aware Algorithms for Dynamic Allocation of Heterogeneous Resources

AF：小型：用于异构资源动态分配的通信感知算法

• 批准号: 2335187
• 负责人: Rajmohan Rajaraman
• 金额: $ 59.94万
• 依托单位: Northeastern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-02-15 至 2027-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2335187&HistoricalAwards=false
• 关键词: AF; Small; Communication; Aware; Algorithms

Modern computer infrastructure systems need to manage vast heterogeneous resources and run computations that are complex, distributed, and dynamic. Often, the distributed nature of the computations demands efficient communication; dynamic resources and computations demand online solutions without full knowledge of the future. For instance, scalable artificial intelligence (AI) requires the effective mapping of dynamic neural network computations into networks of computing devices. This project concerns the design of efficient and effective algorithms for scheduling large-scale computations in distributed infrastructure such as cloud systems and datacenter networks. The expected outcomes of the project are solutions for more effective processing of large AI tasks and resource allocation policies in cloud computing systems, with improved performance for business operations and mission-critical systems. The integrated educational component of the project includes training undergraduate and doctoral students in infrastructure algorithms, curriculum development, and outreach to engage high school students and inspire them to explore careers in math and computing.This project has two major thrusts. The first concerns the scheduling of precedence-constrained jobs and computation graphs in distributed networks and reconfigurable machines. This is motivated by the fact that as computational workloads get larger and more complex, it is often necessary to distribute many communicating jobs across a large network of devices. These devices may have different speeds, different computing capabilities, and restrictions on which jobs they can execute due to resource and security concerns. The second thrust concerns the online migration of computations and servers in a distributed system in response to dynamic requests. One motivation comes from data intensive applications that generate significant network traffic; to enable efficient communication among processes dispersed across many clusters, distributed systems are increasingly reconfigurable and strategically migrate processes to reduce communication. The presented problems include communication-aware scheduling of precedence-constrained jobs in networks with general delays, scheduling of split table jobs in reconfigurable machines, minimum-stretch embedding of graphs, heterogeneous variants of the classic online k-server problem, and online balanced graph partitioning. The technical approaches include new linear-programming based techniques that address communication and topological constraints, and new methods in online algorithms. This project also explores new frameworks for studying these problems, including learning-augmented algorithms through predictions of processing times and communication needs, reconfigurable architectures, and mobile ad hoc networks with heterogeneous devices.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.

现代计算机基础架构系统需要管理大量的异质资源，并运行复杂，分布和动态的计算。 通常，计算的分布性质需要有效的沟通；动态资源和计算需要在线解决方案，而无需充分了解未来。例如，可扩展的人工智能（AI）需要将动态神经网络计算的有效映射到计算设备网络中。该项目涉及在分布式基础架构（例如云系统和数据中心网络）中计划大规模计算的高效算法的设计。 该项目的预期结果是解决云计算系统中大型AI任务和资源分配政策的解决方案，并改善了业务运营和关键任务系统的绩效。 该项目的综合教育组成部分包括培训基础设施算法，课程开发的本科生和博士生，并宣传与高中生互动，并激发他们探索数学和计算中的职业。该项目有两个主要的推力。 第一个涉及分布式网络和可重新配置机器中的优先限制的作业和计算图的调度。 这是因为随着计算工作负载变得更大，越来越复杂，通常有必要在大型设备网络上分发许多交流作业。这些设备可能具有不同的速度，不同的计算功能以及由于资源和安全问题而可以执行的作业的限制。 第二个推力涉及分布式系统中计算和服务器的在线迁移，以响应动态请求。一种动机来自产生大量网络流量的数据密集型应用程序。为了使分散在许多集群中的流程之间有效沟通，分布式系统越来越可重新配置，并且在战略上迁移过程以减少交流。提出的问题包括具有一般延迟的网络中的优先限制的作业的通信感知调度，可重新配置的机器中的拆分表作业安排，图形的最小拉伸嵌入，经典在线K-Server问题的异质变体以及在线平衡图形分区。技术方法包括新的基于线性编程的技术，这些技术解决了通信和拓扑约束，以及在线算法中的新方法。该项目还探讨了研究这些问题的新框架，包括通过预测处理时间和沟通需求，可重新配置的架构以及具有异质设备的移动临时网络，包括学习算法的算法。这奖反映了NSF的立法任务，并被认为是通过基础智力的评估来评估的，并值得通过评估来评估基金会的智力和广泛的范围。