权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

CIF: Small: Leveraging Coding Techniques for Distributed Computing

CIF：小型：利用编码技术进行分布式计算

基本信息

批准号：
1910840
负责人：
Aditya Ramamoorthy
金额：
$ 49.23万
依托单位：
Iowa State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910840&HistoricalAwards=false
关键词：
CIF Small Leveraging Coding Techniques

项目摘要

Clusters of computer processors that process huge amounts of data at specialized locations called data centers are ubiquitous in both industry and academia. The usage of distributed clusters is a necessity rather than a luxury since many modern datasets are too large to be stored in the memory or disk of a single computer. However, using such clusters to obtain answers quickly and efficiently presents many new challenges. These include dealing with issues such as slow or failed processors (ie., worker nodes) and taking into account the time for these worker nodes to communicate among themselves for collaboratively executing a job. Such issues are critical, as it is well-recognized that for such large scale systems, worker node failures are the norm rather than the exception. The project will investigate classes of methods for the robust and efficient operation of large-scale distributed computing clusters. Furthermore, the project will train graduate and undergraduate students in data analytics and in using industry standard techniques for working with these clusters.The overarching goal of this project is to leverage coding-theoretic ideas to make distributed computation robust to stragglers (slow or failed worker nodes) and reduce the communication overhead of distributed computing paradigms such as MapReduce and Spark. While there has been some recent work on the topic of straggler mitigation for distributed matrix computations, the majority of prior work proceeds by treating stragglers exclusively as node failures. This project will investigate rigorous techniques for leveraging slow (but not failed) stragglers. In particular, the sequential nature of computation within a worker node will be taken into account when designing codes for our systems. The second part of the project will deal with issues around the numerical stability of recovery within distributed matrix computation. Several well-known erasure codes that have been proposed for this problem perform rather poorly on this metric. The project will design classes of codes that are useful in straggler mitigation and analyze them through the lens of numerical stability. The last part of the project will address the reduction of shuffle phase traffic in MapReduce-like systems that are used for executing jobs over distributed clusters. Prior work in this area proposes techniques that are information-theoretically optimal (under an appropriate model). A major assumption of prior work is that jobs can be split into arbitrarily small parts. However, in practical systems, this assumption severely limits the actual gain in the overall job execution time. This project will study a large class of techniques that reduce shuffle phase traffic and the overall job execution time by leveraging the properties of suitably defined linear block codes.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.

在称为数据中心的专门位置处理大量数据的计算机处理器集群在工业界和学术界都无处不在。分布式集群的使用是必要的，而不是奢侈品，因为许多现代数据集太大，无法存储在单个计算机的内存或磁盘中。然而，使用这样的集群来快速有效地获得答案提出了许多新的挑战。其中包括处理处理速度慢或出现故障的处理器（即，工作者节点），并考虑这些工作者节点在它们之间通信以协作地执行作业的时间。这样的问题是至关重要的，因为众所周知，对于这样的大规模系统，工作节点故障是正常的而不是例外。该项目将研究大型分布式计算集群的鲁棒和有效操作的方法。此外，该项目还将培训研究生和本科生数据分析和使用行业标准技术来处理这些集群。该项目的总体目标是利用编码理论思想使分布式计算对落后者（缓慢或失败的工作节点）具有鲁棒性，并减少分布式计算范例（如MapReduce和Spark）的通信开销。虽然最近已经有一些关于分散矩阵计算的离散缓解的主题的工作，但大多数先前的工作都是将离散者完全视为节点故障。这个项目将研究利用缓慢（但不是失败）的落伍者的严格技术。特别是，在为我们的系统设计代码时，将考虑工作节点内计算的顺序性质。该项目的第二部分将处理分布式矩阵计算中恢复的数值稳定性问题。几个著名的擦除码，已经提出了这个问题，执行这个指标相当差。该项目将设计的代码类，是有用的，在落伍者缓解和分析他们通过数值稳定性的透镜。该项目的最后一部分将解决在MapReduce类系统中减少shuffle阶段流量的问题，这些系统用于在分布式集群上执行作业。在此领域的先前工作提出了信息理论上最优的技术（在适当的模型下）。先前工作的一个主要假设是，作业可以分成任意小的部分。然而，在实际系统中，这种假设严重限制了总体作业执行时间的实际收益。该项目将研究一大类技术，通过利用适当定义的线性块码的特性来减少洗牌阶段的流量和总体作业执行时间。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（16）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Asynchronous Coded Caching With Uncoded Prefetching

DOI：
10.1109/tnet.2020.3003907
发表时间：
2019-07
期刊：
IEEE/ACM Transactions on Networking
影响因子：
0
作者：
H. Ghasemi;A. Ramamoorthy
通讯作者：
H. Ghasemi;A. Ramamoorthy

Coded matrix computation with gradient coding

使用梯度编码的编码矩阵计算

DOI：
10.1109/isit54713.2023.10206996
发表时间：
2023
期刊：
IEEE
影响因子：
0
作者：
Son, Kyungrak;Ramamoorthy, Aditya
通讯作者：
Ramamoorthy, Aditya

An Integrated Method to Deal with Partial Stragglers and Sparse Matrices in Distributed Computations

分布式计算中处理部分散乱矩阵和稀疏矩阵的综合方法

DOI：
10.1109/isit50566.2022.9834346
发表时间：
2022
期刊：
IEEE International Symposium on Information Theory
影响因子：
0
作者：
Das, Anindya Bijoy;Ramamoorthy, Aditya
通讯作者：
Ramamoorthy, Aditya

Distributed Matrix Computations with Low-weight Encodings

使用低权重编码的分布式矩阵计算

DOI：
10.1109/isit54713.2023.10206445
发表时间：
2023
期刊：
IEEE
影响因子：
0
作者：
Das, Anindya Bijoy;Ramamoorthy, Aditya;Love, David J.;Brinton, Christopher G.
通讯作者：
Brinton, Christopher G.

A Unified Treatment of Partial Stragglers and Sparse Matrices in Coded Matrix Computation

编码矩阵计算中部分散乱矩阵和稀疏矩阵的统一处理