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

现代计算机基础设施系统需要管理大量的异构资源，并运行复杂、分布式和动态的计算。 通常，计算的分布式特性要求高效的通信;动态资源和计算需要在线解决方案，而无需对未来有充分的了解。例如，可扩展人工智能（AI）需要将动态神经网络计算有效映射到计算设备网络中。该项目涉及设计高效和有效的算法，用于在分布式基础设施（如云系统和数据中心网络）中调度大规模计算。 该项目的预期成果是在云计算系统中更有效地处理大型人工智能任务和资源分配策略的解决方案，并提高业务运营和关键任务系统的性能。 该项目的综合教育部分包括培训本科生和博士生的基础设施算法，课程开发和推广，以吸引高中生，并激励他们探索数学和计算的职业生涯。该项目有两个主要目标。 第一个问题是在分布式网络和可重构机器中优先约束作业和计算图的调度。 这是因为随着计算工作量变得越来越大，越来越复杂，通常需要在大型设备网络中分配许多通信作业。这些设备可能具有不同的速度，不同的计算能力，以及由于资源和安全问题而对其可以执行的作业的限制。 第二个重点是在分布式系统中响应动态请求的计算和服务器的在线迁移。一个动机来自于产生大量网络流量的数据密集型应用;为了实现分散在许多集群中的进程之间的有效通信，分布式系统越来越多地可重新配置，并战略性地迁移进程以减少通信。所提出的问题包括通信感知调度的优先级约束的作业在网络中一般延迟，调度分裂表作业在可重构机器，最小拉伸嵌入的图形，异构变种的经典在线k-服务器问题，在线平衡图分割。技术方法包括新的线性规划为基础的技术，解决通信和拓扑约束，以及在线算法的新方法。该项目还探索了研究这些问题的新框架，包括通过预测处理时间和通信需求的学习增强算法、可重构架构以及具有异构设备的移动的ad hoc网络。该奖项反映了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.