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）需要将动态神经网络计算有效映射到计算设备网络中。该项目涉及设计高效且有效的算法，用于在云系统和数据中心网络等分布式基础设施中调度大规模计算。 该项目的预期成果是更有效地处理大型人工智能任务和云计算系统中的资源分配策略的解决方案，并提高业务运营和关键任务系统的性能。 该项目的综合教育部分包括在基础设施算法、课程开发和外展方面对本科生和博士生进行培训，以吸引高中生并激励他们探索数学和计算领域的职业生涯。该项目有两个主要目标。 第一个涉及分布式网络和可重构机器中优先级约束作业和计算图的调度。 这是因为随着计算工作负载变得越来越大、越来越复杂，通常需要在大型设备网络上分配许多通信作业。这些设备可能具有不同的速度、不同的计算能力，并且由于资源和安全问题，它们可以执行的作业受到限制。 第二个重点涉及分布式系统中计算和服务器的在线迁移，以响应动态请求。动机之一来自于产生大量网络流量的数据密集型应用程序；为了实现分散在多个集群中的进程之间的有效通信，分布式系统越来越可重新配置，并有策略地迁移进程以减少通信。提出的问题包括具有一般延迟的网络中优先级约束作业的通信感知调度、可重构机器中的拆分表作业调度、图的最小拉伸嵌入、经典在线 k-server 问题的异构变体以及在线平衡图分区。这些技术方法包括解决通信和拓扑约束的基于线性规划的新技术，以及在线算法的新方法。该项目还探索了研究这些问题的新框架，包括通过预测处理时间和通信需求的学习增强算法、可重构架构以及具有异构设备的移动自组织网络。该奖项反映了 NSF 的法定使命，并被认为值得支持通过使用基金会的智力优点和更广泛的影响审查标准进行评估。