Collaborative Research: AF: Small: Efficient Massively Parallel Algorithms

现代计算系统已经从单核单处理器设备发展到在网络系统中运行的更现代的多核处理器，并且可以在Amazon或b谷歌等公司推广的仓库规模的云计算中使用。未来计算能力的进步可能不会主要来自更快的设备，而是来自固有的并行和分布式环境的处理，以及通过理解如何利用许多算法问题中固有的并行性。与此同时，世界已经进入了“大数据”时代，大数据集需要解决以前无法想象的、具有巨大经济和社会影响的问题。这个新的并行、互联的大数据世界特别需要对它们的算法进行基础研究，这些算法既是并行的，又是分布式的。本项目中的算法通过构建和开发大规模并行计算的新通用框架来解决这一重要的研究挑战。作为该项目的主要推动力，研究人员将为核心大规模并行计算设计基本和有效的算法，特别是在实际的大规模并行计算（MPC）框架中。特别是，他们将考虑在MPC模型中减少回合数的方法，以及回合，内存，机器数量和通信时间之间的权衡。他们试图寻找新的MPC算法来解决基本图问题，如连通性、匹配、顶点覆盖、最大独立集，以及其他基本字符串匹配问题，如后缀树、编辑距离和最长公共子序列。另一个重点是大规模并行计算的动态算法，它基于输入的频繁修改，在并行/分布式设置中有效地修改输出，并直接应用于不断发展的社交网络、万维网、道路网络、调度系统等。研究人员将用更好的数据结构和抽象来增强当前的并行环境/架构，以允许通过开源代码在实践中使用的当前基本算法的简化和快速实现。这个项目的发现将被整合到现有的和新的关于并行算法、分布式算法和大数据基础的课程和书籍中。这些领域中有吸引力的开放问题的财富将提供具有挑战性的研究主题和直观的可访问问题，以激励学生进入计算机科学和数学的研究。特别是该项目将涉及博士生和博士后，本科生，甚至高中生（特别是少数民族和女性学生），其中许多人将继续在其他学术机构和研究中心进行研究，进一步扩大本研究的影响。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Modern computing systems have moved beyond single-coresingle-processor devices to more modern multicore processors operatingin networked systems and available in warehouse-scale cloudspopularized by companies such as Amazon or Google. Future advances incomputing power will likely come not mainly from faster devices, butby processing in inherently parallel and distributed environments, andby understanding how to exploit the parallelism inherent in manyalgorithmic problems. Simultaneously, the world has entered the era of``big data'' with large data sets on which previously unthinkablesized problems with great economic and social impact need to besolved. This new parallel, interconnected, big-data world speciallyrequires fundamental research on their algorithms, which are bothparallel and distributed.The algorithms in this project address thisimportant research challenge by building and developing new generalframeworks for massively parallel computation.As the main thrust of this project, the investigators will designfundamental and efficient algorithms for core massively parallelcomputations especially in the practical Massively ParallelComputation (MPC) framework. In particular, they will consider methodsfor reducing the number of rounds in the MPC model as well astradeoffs between rounds, memory, number of machines, andcommunication time. They seek to find new MPC algorithms for basicgraph problems such as connectivity, matching, vertex cover, maximalindependent set, as well as other basic string matching problems suchas suffix trees, edit distance, and longest commonsubsequence. Another focus is dynamic algorithms for massivelyparallel computation, which modify the output efficiently in aparallel/distributed setting based on frequent modifications of theinput and with direct applications in evolving social networks, theWorld Wide Web, road networks, scheduling systems among others. Theinvestigators will augmenting current parallelenvironments/architectures with better data structures andabstractions to allow simplified and fast implementations of thecurrent fundamental algorithms that can be used in practicevia open-source codes. The discoveries in this project will beintegrated into existing and new courses and books about parallelalgorithms, distributed algorithms, and foundations of big data. Thewealth of attractive open problems in these areas will provide bothchallenging research topics and intuitive accessible problems toinspire students to enter research in computer science andmathematics. In particular the project will involve Ph.D. students andpost-docs, undergraduate students, and even high-school students(especially students among minorities and women), many of whom willcontinue their research at other academic institutions and researchcenters, further broadening the impact of this research.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.