Collaborative Research: AF: Small: Efficient Massively Parallel Algorithms

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

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.