Collaborative Research: AF: Small: Efficient Massively Parallel Algorithms

University Of Maryland, College Park, College Park MD

Investigators

Abstract

Modern computing systems have moved beyond single-core single-processor devices to more modern multicore processors operating in networked systems and available in warehouse-scale clouds popularized by companies such as Amazon or Google. Future advances in computing power will likely come not mainly from faster devices, but by processing in inherently parallel and distributed environments, and by understanding how to exploit the parallelism inherent in many algorithmic problems. Simultaneously, the world has entered the era of ``big data'' with large data sets on which previously unthinkable sized problems with great economic and social impact need to be solved. This new parallel, interconnected, big-data world specially requires fundamental research on their algorithms, which are both parallel and distributed.The algorithms in this project address this important research challenge by building and developing new general frameworks for massively parallel computation. As the main thrust of this project, the investigators will design fundamental and efficient algorithms for core massively parallel computations especially in the practical Massively Parallel Computation (MPC) framework. In particular, they will consider methods for reducing the number of rounds in the MPC model as well as tradeoffs between rounds, memory, number of machines, and communication time. They seek to find new MPC algorithms for basic graph problems such as connectivity, matching, vertex cover, maximal independent set, as well as other basic string matching problems such as suffix trees, edit distance, and longest common subsequence. Another focus is dynamic algorithms for massively parallel computation, which modify the output efficiently in a parallel/distributed setting based on frequent modifications of the input and with direct applications in evolving social networks, the World Wide Web, road networks, scheduling systems among others. The investigators will augmenting current parallel environments/architectures with better data structures and abstractions to allow simplified and fast implementations of the current fundamental algorithms that can be used in practice via open-source codes. The discoveries in this project will be integrated into existing and new courses and books about parallel algorithms, distributed algorithms, and foundations of big data. The wealth of attractive open problems in these areas will provide both challenging research topics and intuitive accessible problems to inspire students to enter research in computer science and mathematics. In particular the project will involve Ph.D. students and post-docs, undergraduate students, and even high-school students (especially students among minorities and women), many of whom will continue their research at other academic institutions and research centers, 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.