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

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

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.