Collaborative Research: CNS Core: Small: A Principled Framework for Workload Distribution Techniques in Large-Scale Networks

在过去十年中，分布式计算和大数据分析使人类生活取得了前所未有的进步，包括在医药和卫生、教育、商业以及激发新职业方面。而且，它是计算机行业的基础，而计算机行业是美国重要的经济引擎。然而，传统的分布式计算方法是作为针对单个应用程序的临时解决方案开发的。在经典范例中，系统设计者指定一个简单的网络模型，以及一些低级设计目标，例如高利用率和低作业完成时间，然后开发一个固定的算法来将计算分配给各个工作人员。尽管这种范式导致了在实践中有效的启发式，但网络和应用程序的复杂性和异质性不断增长，因此，设计在各种条件下都能很好地工作的工作负载分布算法的关键任务变得极其困难。这个建议通过开发一个通用框架来解决这个挑战，该框架可以随着应用程序和网络的增长而使用。最终，它将使分布式计算更易于解释，并更好地适应应用程序的需求。工作负载分配有着悠久而丰富的历史。然而，现有文献缺乏在大规模网络中计算与通信权衡的推理设计原则。本建议旨在为工作量分配技术开发一个原则性框架。它旨在提供分布式网络中函数计算背后的数学基础，其中函数是计算任务的抽象，例如训练神经网络，索引web，查询处理等。因此，操作员不必依赖启发式或简化模型来决定工作负载分布。相反，建议的框架提供了成本和性能之间的权衡空间，以最佳地利用可用资源。本提案旨在解决分布式网络中并行函数计算的基本挑战，以及如何通过以下方式对部署的方法进行严格的数学分析：(i)通过分析各种应用，包括数据中心作业调度、分散的随机梯度下降训练和推理作业的擦除编码，为工作量分配系统开发一系列核心原则；（ii）设计一种新的调度框架，用于在分布式网络中分配计算任务。在设计实用、健壮和高性能的工作负载分配算法时，所提出的框架利用利特尔定律来最小化通信和计算时间。pi将根据最先进的启发式算法评估拟议的调度器，并确定约束和特征，使每个启发式成为通用框架的特殊用例。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Over the last decade, distributed computing and big data analytics have enabled unprecedented advancements in human life, including in medicine and health, education, business, and in stimulating new careers. And, it is fundamental to the computing industry, a significant economic engine for the US. However, traditional approaches to distributed computing are developed as ad hoc solutions to individual applications. In the classical paradigm, the system designer specifies a simple model of the network, along with a few low-level design goals, such as high utilization and low job completion time, and then develops a fixed algorithm to distribute the computation across workers. Although this paradigm has resulted in heuristics that work in practice, networks and applications continuously grow in complexity and heterogeneity, hence, the critical task of designing workload distribution algorithms that work well across a variety of conditions has become exceedingly difficult. This proposal addresses that challenge by developing a general framework that can be used as applications and networks grow. Ultimately, it will make distributed computing more explainable and better tailored to the needs of applications.Workload distribution has a long and rich history. However, the existing literature lacks design principles for reasoning about compute versus communication tradeoffs in large-scale networks. This proposal seeks to develop a principled framework for workload distribution techniques. It aims to provide the mathematical foundations behind function computation in distributed networks, where a function is an abstraction of a computation task, such as training a neural network, indexing the web, query processing, etc. Hence, the operator does not have to rely on heuristics or simplified models to decide on workload distribution. Instead, the proposed framework offers the trade-off space between cost and performance for the best use of available resources. This proposal aims to address the fundamental challenge of parallel function computation in distributed networks and how to enable rigorous mathematical analysis of deployed approaches by (i) developing a series of core principles for workload distribution systems through analyzing a variety of applications, including datacenter job scheduling, decentralized Stochastic Gradient Descent training, and erasure coding for inference jobs, and (ii) devising a novel scheduling framework for distributing computation tasks in distributed networks. The proposed framework leverages Little’s Law to minimize both communication and computation times when designing practical, robust, and high-performance workload distribution algorithms. The PIs will evaluate the proposed scheduler against state-of-the-art heuristic algorithms and pin-point the constraints and features that makes each heuristic a special use case of the generic framework.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.