Theory-in-Practice Workshop

Synopsis

At this “Theory-in-Practice” workshop, we will see many new and exciting advances in the intersection between theory and practice. Topics will include high performance computing, large-scale graph algorithms, and parallel algorithms and data structures. In addition to talks, we will have many opportunities for participants to interact with the speakers and other attendees.

SPEAKERS

Kunal Agrawal (Washington U. in St. Louis), Michael Bender (Stony Brook), Laxman Dhulipala (U. of Maryland), Jeremy Fineman (Georgetown), Jakub Łącki (Google), Stefan Muller (llinois Tech), Harsha Simhadri (Microsoft), Uzi Vishkin (U. of Maryland)
 

 

 

TRANSPORTATION AND PARKING

Our North Campus Parking garage is right next to the Computer Science department in Mudd Hall (Third Floor 3514). Visitor’s parking is $9 a day and you can get a ticket from the ticket booth when you drive in and be sure to pay inside the first floor of the garage in order to obtain a ticket for exiting the garage.
 
Other methods of transportation can be found on this page.

 

Logistics

  • Dates: Monday, Sept. 12 – Tuesday, Sept. 13
  • Location: Northwestern University
  • Rooms: Mudd Library 3514
  • Registration: Click here to register
  • Streaming: via Panopto
 
 
 
 

Schedule FOR MONDAY, SEPT. 12

*watch the full morning event here

*watch the full after lunch event here

  • 9:30-9:50: Breakfast
  • 9:50-10:00: Opening Remarks
  • 10:00-10:45: Harsha Simhadri (video)
  • 10:45-11:30: Stefan Muller (video)
  • 11:30-11:50: Coffee Break
  • 11:50-12:35: Kunal Agrawal (video)
  • 12:35-2:00: Lunch Break
  • 2:00 – 2:45: Jakub Łącki (video)
  • 2:45 – 3:30: Uzi Vishkin (video)
  • 3:30 – 4:00: Coffee Break
  • 4:00-5:30: Individual/group meetings with students, faculty, postdoc attendees
  • 5:30pm: Reception

 

Schedule FOR TUESDAY, SEPT. 13

*Watch the full Tues. event here 

    • 9:30-10:00: Breakfast
    • 10:00-10:45: Michael Bender (video)
    • 10:45-11:30: Laxman Dhulipala (video)
    • 11:30-11:50: Coffee Break
    • 11:50-12:35: Jeremy Fineman (video)
    • 12:35-1:00: Lunch Break
    • 1:00-2:00: Panel

Titles and Abstracts

 
Speaker: Harsha Simhadri (Microsoft)
Title: Approximate Nearest Neighbor Search algorithms for web-scale search and recommendation
Abstract: Web-scale search and recommendation scenarios increasingly use Approximate Nearest Neighbor Search (ANNS) algorithms to index and retrieve objects based on the similarity of their learnt representations in a geometric space. Since these scenarios often span billions or trillions of objects, efficient and scalable ANNS algorithms are critical to making these systems practical. However, most algorithms studied in literature either focus on million-scale datasets or do not have features necessary for practical indices, e.g., support for real-time updates.
 
In this talk we discuss empirical progress on this problem. Specifically, we present DiskANN, the first external memory ANNS algorithm that can index a billion points and serve queries at interactive latencies (few milliseconds) on a commodity machine. This represents an order of magnitude more points indexed per machine than previous work. In addition, the index allows real-time updates and its in-memory performance compares well with other state of the art indices.
 

We will conclude with some open problems in this space — e.g., support for hybrid queries that involve a combination of similarity search and hard matches such as language or author — and some preliminary results. Further, proving any reasonable bounds on the complexity of DiskANN or related graph-based ANNS indices remains an open problem.

Joint work with Ravishankar Krishnaswamy, Sujas J Subramanya, Aditi Singh, Rohan Kadekodi, Devvrit, Shikhar Jaiswal, Magdalen Dobson, Siddharth Gollapudi, Neel Karia, Varun Sivasankaran.

Bio: Harsha Simhadri is a Principal Researcher at Microsoft Research. He enjoys developing new algorithms with a view towards future platforms and practical systems. Recent examples include algorithms for web-scale nearest-neighbor search deployed in various Microsoft search and recommendation scenarios, and new ML operators and architectures for tiny IoT and edge devices. He previously worked on parallel algorithms and run-times with provable guarantees for multi-core processors for his PhD thesis at Carnegie Mellon University.

 
Speaker: Stefan Muller (Illinois Tech)
Title: Static Prediction of Parallel Computation Graphs
Abstract: Many algorithms for analyzing parallel programs, for example to detect deadlocks or data races or to calculate the execution cost, are based on a model variously known as a cost graph, computation graph or dependency graph, which captures the parallel structure of threads in a program. In modern parallel programs, computation graphs are highly dynamic and depend greatly on the program inputs and execution details. As such, most analyses that use these graphs are either dynamic analyses or are specialized static analyses that gather a subset of dependency information for a specific purpose.

In this talk, I will introduce graph types, which compactly represent all of the graphs that could arise from program execution. Graph types are inferred from a parallel program using a graph type system and inference algorithm. I will describe how graph types are computed from a program, and how they can be used to visualize and give programmers feedback about the parallel structure of a program.

This talk is based on work originally presented at POPL 2022.

Bio: Stefan Muller is an assistant professor of Computer Science at the Illinois Institute of Technology, where he studies various aspects of language and type system design, primarily with applications to parallel computing. He completed his PhD at Carnegie Mellon University in 2018, working with advisor Umut Acar on theoretical techniques and runtime schedulers for interactive parallel programs. Prior to joining Illinois Tech in 2020, he was a postdoctoral fellow at Carnegie Mellon.

 
Speaker: Kunal Agrawal (Washington U. in St. Louis)
Title: Scheduling Algorithms for Real-time Systems
Abstract: More and more computational systems now interact with the physical world directly without human interaction — examples include autonomous vehicles, aeronautics systems, industrial systems, and smart grids. In many of these systems, the specifications of correctness include the timing properties of the system in addition to the functional properties. In addition, since failure of the system can cause catastrophic consequences in some cases, these timing properties must be verified and certified a priori, before the system deploys. This talk will give a general overview of some of the scheduling problems that arise in these systems as well as some open problems.

Bio: Kunal Agrawal is a professor of Computer Science and Engineering at Washington University in St. Louis. She is interested in problems that arise at the intersection of theory and practice generally, and more specifically in parallel algorithms and data structures, scheduling, caching and paging, and real-time systems.

 
Speaker: Jakub Łącki (Google)
Title: Scaling Hierarchical Agglomerative Clustering to Trillion-Edge Graphs
Abstract: Hierarchical agglomerative clustering (HAC) is a simple and widely popular clustering method known for its good empirical quality. However, the applications of HAC on large datasets have been limited by the high computational cost of the existing implementations. Addressing this limitation has been an elusive task, as the algorithm has been believed to be inherently sequential and computationally expensive.

In this talk we study the HAC problem on edge-weighted graphs assuming the widely-used average linkage similarity function. We first give conditional hardness results showing that HAC requires time that is super-linear in the input size, and cannot be parallelized efficiently, formalizing the commonly held intuitions about the algorithm. We then show how both of these limitations can be bypassed by allowing approximation. Namely, we show that 1+ε approximate HAC can be implemented in near-linear work and polylogarithmic depth.Finally, we show that our ideas lead to highly scalable HAC implementations. In a shared memory parallel setting (i.e., on a single machine) we obtain an over 50x speedup over the best existing baseline. Moreover, in the distributed setting, we demonstrate that our implementation scales to graphs containing trillions of edges.

 
Bio: Jakub Łącki is a research scientist working on the Graph Mining team in Google Research, New York. His research focuses on highly scalable algorithms for clustering and graph processing. He received his PhD from Univeristy of Warsaw in 2015, advised by Piotr Sankowski. Before joining Google he was a postdoctoral researcher at Sapienza University of Rome, working with Stefano Leonardi.
 
Speaker: Uzi Vishkin (U. of Maryland)
Title: Can parallel algorithms reverse the decline of general-purpose CPUs? 
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.

 
Speaker: Michael Bender (Stony Brook)
Title: Online Parallel Paging and Green Paging    
Abstract: We give provably good algorithms for online paging in multicore systems.
We solve this decades-old open problem by showing a connection to the problem of green paging.
 
 
Speaker: Laxman Dhulipala (U. of Maryland)
Title: Efficient Algorithms and Systems for Dynamic and Streaming Graphs
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.

 
Speaker: Jeremy Fineman (Georgetown)
Title: Parallel Algorithms for Directed Graphs
Abstract: This talk presents recent algorithmic advances for parallel algorithms on directed graphs, including single-source reachability (i.e., a graph search) and approximate single-source shortest paths. These problems can easily be solved sequentially in linear or nearly linear time. Until recently, it was unclear how to solve these problems in parallel without significantly increasing the total work. This talk will cover some of the new shortcutting approaches, which yield parallel algorithms having nearly linear work and almost square-root depth. 

Bio: Jeremy Fineman is an Associate Professor and Wagner Term Chair of Computer Science at Georgetown University. His main research interest is in algorithm design and analysis, with a focus on data structures, parallel algorithms, memory-efficient algorithms, and scheduling. He received his Ph.D. from MIT in 2009 and did a postdoc at CMU before starting at Georgetown in 2011.

 

About the Series

The IDEAL workshop series brings in experts on topics related to the foundations of data science to present their perspective and research on a common theme. Chicago area researchers with an interest in the foundations of data science.

This workshop is organized by Samir Khuller (NU) and Quanquan Liu (NU).