Abstract: The transition from single core general-purpose commodity CPUs to parallel multicore ones required figuring out the best design for both new parallel hardware and cost-effective parallel algorithms and programming. Given a benchmark suite of application code and respective workloads, hardware designers are at their best when tasked with optimizing their designs. Given a computation cost model, algorithm designers specialize in designing algorithms for optimizing such costs. However, since the transition to multiple core CPUs around 2005, hardware designers followed a build-first figure out-how-to-program later approach. Algorithms could not do much to remedy suboptimal hardware. It is now clear that this attempt did not yield the desired results. As one of several faults: too few program today’s multicore CPU for parallelism. In the same vein, hardware design leaders concluded in 2019 that it is “unlikely that simple multicore scaling will provide cost-effective path to growing performance”.

I long believed that: (i) for general parallel computing to become ubiquitous, algorithm and hardware design communities need to pull together their respective strengths, and (ii) parallel algorithms and programming need to provide an extensive benchmark suite of codes that meet two main requirements:

• The benchmark should reflect scalable algorithm design framework that will attract massive participation of programmers, once the framework is supported by commodity manycore CPUs.
• The framework should be supportable by cost-effective hardware, including constant factors.

The second requirement clearly exceeds the comfort zone of most algorithm designers. Still, the most important objective for research in general and parallel algorithms in particular is to maximize its impact. Therefore, I decided to bite the bullet and the hardware and software prototyping done at UMD for demonstrating feasibility of a PRAM-based approach, known as XMT provides one such framework.

Maximizing impact remains the order of the day. IMO, parallel algorithms researchers should either develop benchmark code suites for XMT itself, or for future alternative frameworks that share critical features with XMT. If enough parallel algorithms researchers jointly (contribute and) assert importance of such a benchmark, vendors and hardware designers would listen and be inspired to innovate towards producing industry grade processors.

Bio: Uzi Vishkin has been Professor of Electrical and Computer Engineering and permanent member of the University of Maryland Institute for Advanced Computer Studies (UMIACS) since 1988.

Inspired by the possibility that transition to parallelism may turn into the only paradigm shift in core computing during his professional lifetime, he started his work on parallel computing in 1979 as a doctoral student. His initial focus was on parallel algorithms and parallel algorithmic thinking. The 1982 Shiloach-Vishkin work-depth methodology for presenting parallel algorithms provided the presentation framework in several parallel PRAM algorithms texts that also include a considerable number of symmetry breaking techniques, and parallel graph and string matching as well as other algorithms he co-authored. His integer sorting algorithms evolved into the map reduce paradigm. He is an ACM Fellow for, among other things, having “played a leading role in forming and shaping what thinking in parallel has come to mean in the fundamental theory of Computer Science”. He was also an ISI-Thompson Highly Cited Researcher.

This parallel algorithms theory provided the basis for his invention of the PRAM-On-Chip desktop supercomputer framework that scales to 1000 processors on chip, and beyond. He has led extensive hardware and software prototyping of this framework, refuting “common wisdom” that this cannot be done. Prototypes include a 64-processor computer that has already been programmed by nearly 1000 students in a single high-school.

 

Abstract: In this talk, I will give an overview of recent work on parallel dynamic graph algorithms and the closely related graph-streaming setting where a continuous stream of graph updates is mixed with graph queries. In particular, I will focus on (1) Apsen, a a graph-streaming framework that extends the interface of Ligra with operations for updating graphs and (2) the CPAM framework, which enables faster and more space-efficient graph streaming systems with better theoretical guarantees using a new parallel block-based purely-functional data structure. I will end by describing ongoing work on using Aspen to support new applications, and open problems at the interface of algorithm-engineering and theory in this area.

Bio: Laxman Dhulipala is an Assistant Professor in the Department of Computer Science at the University of Maryland, College Park. He is also a visiting faculty researcher at Google Research where he works on the Graph Mining team. Previously, he was a postdoc at MIT working with Julian Shun. He obtained his Ph.D. from Carnegie Mellon University, where he was advised by Guy Blelloch. His current research interests are on parallel clustering (graphs and spatial data), and efficient parallel algorithms for static, streaming, and dynamic graphs.