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

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

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.