Collaborative Research: AF: Small: Efficient Massively Parallel Algorithms

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