Collaborative Research: CIF: Small: Maximizing Coding Gain in Coded Computing

人工智能和机器学习算法依赖于并行的分布式计算系统来高效地执行复杂的、数据繁重的任务。设计大规模分布式计算系统的一个重大挑战是解决跨多个服务器的服务时间的不可预测变化。计算冗余度，例如任务复制，是一种很有前途的强大工具，可以减少服务时间的总体可变性。本课题主要研究分布式计算中影响数据密集型算法在大规模系统中执行效率的冗余问题的智能管理。该项目将量化冗余效益，这对开发并最终部署高效的冗余计划以执行人工智能和机器学习工作负载至关重要。该项目的教育目标包括激发学生对应用概率和数学建模的兴趣，并开发云计算基础设施的动手实验室。该项目将为本科生和高中生的研究体验做出贡献，并将招募和指导女性和代表性不足群体的成员。该项目考虑使用复制和擦除编码来减少作业执行时间的分布式计算系统。该项目旨在最大限度地提高在实际场景中使用计算冗余(编码增益)的收益。它补充了最近关于分布式系统中冗余的工作，主要侧重于使用擦除码设计冗余方案。该项目将使用统计分析、排队和编码理论来做出以下贡献：(I)描述在分布式计算中使用冗余的关键影响，包括对冗余的益处和成本的分析；(Ii)捕捉具有掉队的分布式计算系统的性能的新的数学模型；(Iii)用于计算编码计算系统中的编码增益的新的分析工具；(Iv)冗余管理算法的开发；(V)多样性与并行性的权衡；以及(Vi)解决编码计算中的其他关键问题，这些问题不存在于更好地理解的复制解决方案中。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Artificial intelligence and machine learning algorithms rely on parallel, distributed computing systems to efficiently carry out intricate, data-heavy tasks. A significant challenge in designing large-scale distributed computing systems is addressing the unpredictable variations in service times across multiple servers. Computing redundancy, such as task replication, is a promising powerful tool to curtail the overall variability in service time. This project focuses on the intelligent management of redundancy in distributed computing that will affect the execution efficiency of data-intensive algorithms in large-scale systems. The project will quantify redundancy benefits, pivotal to developing and ultimately deploying efficient redundancy schemes for executing artificial intelligence and machine learning workloads. The educational goal of the project includes stimulating students' interest in applied probability and mathematical modeling and developing hands-on labs on cloud computing infrastructure. The project will contribute to the Research Experiences for Undergraduate and High School students and will recruit and mentor women and members of underrepresented groups.This project considers distributed computing systems that use replication and erasure coding to reduce job execution times. The project aims to maximize the gain of using computing redundancy (coding gain) in practical scenarios. It complements recent work on redundancy in distributed systems, focusing primarily on designing redundancy schemes using erasure codes. The project will use statistical analysis and queueing and coding theories to make the following contributions: (i) characterization of the crucial effects of using redundancy in distributed computing, including analysis of the benefits and costs of redundancy; (ii) new mathematical models that capture the performance of distributed computing systems with stragglers; (iii) new analysis tools for computing coding gain in coded computing systems; (iv) development of redundancy management algorithms; (v) characterization of the diversity vs. parallelism trade-off; and (vi) addressing other critical issues in coded computing that do not exist in the better-understood replication solutions.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.