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

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

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.