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

合作研究：CNS 核心：小型：大规模网络中工作负载分配技术的原则框架

基本信息

批准号：
2008639
负责人：
Koushik Kar
金额：
$ 16.65万
依托单位：
Rensselaer Polytechnic Institute
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008639&HistoricalAwards=false
关键词：
Collaborative Research CNS Core Small

项目摘要

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.

在过去的十年中，分布式计算和大数据分析已使人类生活中的前所未有的进步，包括医学和健康，教育，商业以及刺激新职业。而且，这对于美国的重要经济引擎而言，这对于计算行业至关重要。但是，传统的分布式计算方法是针对各个应用程序的临时解决方案。在经典范式中，系统设计人员指定了一个简单的网络模型，以及一些低级设计目标，例如高利用率和低工作完成时间，然后开发了固定的算法以在工人之间分配计算。尽管这种范式导致了在实践中起作用的启发式方法，但网络和应用程序的复杂性和异质性继续增长，因此，设计工作负载分布算法的关键任务在各种条件下都可以正常工作。该建议通过开发可以用作应用程序和网络增长的一般框架来解决挑战。最终，它将使分布式计算更加可解释，并且可以更好地满足应用程序的需求。工作负载分布具有悠久而丰富的历史。但是，现有文献缺乏有关大规模网络中有关计算与通信折衷的推理的设计原则。该建议旨在为工作量分配技术开发主要的框架。它的目的是在分布式网络中提供功能计算背后的数学基础，其中函数是计算任务的抽象，例如培训神经网络，索引网络，查询处理等。因此，操作员不必依靠启发式方法或简化的模型来决定工作负载分布。取而代之的是，提议的框架提供了成本和性能之间的权衡空间，以最佳利用可用的资源。 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 analysis 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分布式网络中的任务。提出的框架利用Little的定律来最大程度地减少沟通和计算时间，当时设计实用，健壮和高性能的工作负载分配算法。 PI将根据最先进的启发式算法评估拟议的调度程序，并将其引起点的约束和功能，这使每个启发式都是通用框架的特殊用例。该奖项反映了NSF的法定任务，并通过评估该基金会的知识功能和广泛的影响来评估NSF的法定任务。