Skip to content

Latest commit

 

History

History
185 lines (118 loc) · 11.3 KB

index.md

File metadata and controls

185 lines (118 loc) · 11.3 KB
layout title
default
Blelloch Fest

Blelloch Fest

We will be celebrating Guy Blelloch's 60th birthday (and his 30th anniversary of joining CMU) on Saturday October 15th, 2022 in Pittsburgh at the Gates Hillman Center (GHC). The event will include talks from Guy's colleagues, friends, and students. The talks will revolve around Guy's interests in parallel languages, cost-models, and algorithms.

Information about Attending:

The event will be taking place in GHC 6115. The doors to the building and upper-floor elevators will be open on this day.

Parking should be free on Saturday if you park at either:

You can also see these annotated maps of how to get from the Morewood Gardens Lot to GHC and from the East Campus Garage to GHC.

Wi-Fi info can be found here.

Virtual Participation: We will stream and record the event on zoom here: https://umd.zoom.us/my/laxman?pwd=eTdMaHZ2amppazAzalRvSE9uWUFSUT09 .

Schedule and Speaker List

  • Morning Session

    • 8:30--9:00 --- Breakfast at GHC

    • 9:00--9:20 --- Highlights from 35 Papers with Guy (Phil Gibbons)

    • 9:20--9:40 --- Parallelizing Sequential Iterative Algorithms using Parallel Data Structures (Yihan Sun)

    • 9:40--10:00 --- Data-Oblivious Algorithms for Multicores (Elaine Shi)

    • 10:00--10:40 --- Coffee Break

    • 10:40--11:00 --- Fast and Fair Lock-Free Locks (Naama Ben-David)

    • 11:00--11:20 --- Parallel Hierarchical Agglomerative Graph Clustering (Laxman Dhulipala)

    • 11:20--11:40 --- Parallel External-Memory Algorithms: Theory to Practice (Harsha Simhadri)

  • Lunch

    • 12:00--2:00 --- Lunch at Cafe Carnegie
    • 2:00--3:00 --- Walk in Schenley Park

  • Afternoon Session

    • 3:00--3:20 --- Verification of Cost in Dependent Type Theory (Bob Harper)

    • 3:20--3:40 --- ALADDIN, Consciousness and Free Will from a TCS perspective (Lenore Blum and Manuel Blum)

    • 3:40--4:00 --- Parallel Batch-Dynamic Graph Algorithms (Julian Shun)

    • 4:00--4:40 --- Coffee Break

    • 4:40--5:00 --- The Unbearable Lightness of Parallel Functional Programming from NESL to MPL (Umut Acar)

    • 5:00--5:20 --- Computational Models for Modern Architecture (Yan Gu)

    • 5:20--5:40 --- The Yug of Guy, and A Trifle (Siddhartha Chatterjee)

    • 5:40--6:00 -- Blelloch 101 — In-class Quiz (Charles Leiserson)

    • 6:00--6:20 -- (Guy Blelloch)

  • 7:00 -- Dinner at Lucca Ristorante

Titles and Abstracts

Highlights from 35 Papers with Guy (Phil Gibbons)

Abstract: Guy and I have co-authored 35 conference and journal publications, spanning 27 years. This talk will highlight this body of joint work: the good, the bad, and the ugly.

Parallelizing Sequential Iterative Algorithms using Parallel Data Structures (Yihan Sun)

Abstract: Designing parallel algorithms in general is hard, and therefore many simple problems in the sequential setting become more complicated in parallel. Some recent research (including many of Guy's papers!) reveals an interesting observation: many sequential iterative algorithms are inherently "parallel" when the dependences among iterations are carefully analyzed. Such algorithms are usually practical and easy to understand, due to their simplicity and connections to sequential algorithms.

This talk will review some recent advances in parallelizing sequential iterative algorithms. In particular, for some problems, we will show how parallel data structures can be used to greatly simplify the algorithm, and enable efficient work and low span.

Data-Oblivious Algorithms for Multicores (Elaine Shi)

Abstract: I will talk about privacy-preserving algorithms in the binary fork-join model, which is the de facto model of computation for modern multi-core processors proposed by Guy Blelloch and others. I will also discuss applications of these techniques to privacy-preserving algorithms in other models such as Massively Parallel Computation. (Joint work with Vijaya Ramachandran)

Title: Fast and Fair Lock-Free Locks (Naama Ben-David)

Abstract: Locks are frequently used in concurrent systems to simplify code and ensure safe access to contended parts of memory. However, they are also known to cause bottlenecks in concurrent code, leading practitioners and theoreticians to sometimes opt for more intricate lock-free implementations. In this talk, I’ll give an overview of joint work with Guy which shows that, despite the seeming contradiction, it is possible to design practically and theoretically efficient lock-free locks. I’ll discuss how we model and reason about concurrent systems theoretically, and present a lock-free lock algorithm with good bounds on running time and fairness.

Parallel Hierarchical Agglomerative Graph Clustering (Laxman Dhulipala)

Abstract: I will share some recent work on designing practical parallel algorithms for hierarchical agglomerative graph clustering. Although the problem is P-complete, we give a near-linear work RNC algorithm for a natural approximate version of the problem that can quickly process massive graphs. Along the way I will talk about some stories from working with Guy.

Parallel External-Memory Algorithms: Theory to Practice (Harsha Simhadri)

Abstract: I will present some results from my work with Guy and Phil on designing and analyzing IO-efficient algorithms for parallel machines in the fork-join model and extensions thereof. I will then talk about how this work inspired some recent empirical results on designing IO-efficient algorithms for "large scale ML systems" including ANNS indices. I will highlight some key ideas that seem to work exceptionally well in practice for ANNS indices, but with no theoretical analysis yet.

Verification of Cost in Dependent Type Theory (Bob Harper)

Abstract: Dependent type theory is a natural setting for expressing and proving the behavior of programs, chiefly by equational reasoning. In standard formulations of type theory any two sorting algorithms would be equal, simply because they sort. But then what would it mean to specify that one sort is more efficient than another? Recent developments in type theory provide a natural way to reconcile cost and behavior of programs. I'm not aware of previous work that used Spira's algorithm (which is designed for a quite different probabilistic model, and for the APSP problem) in a parallel setting.

ALADDIN, Consciousness and Free Will from a TCS perspective (Lenore Blum and Manuel Blum)

Abstract: Lenore will say some words about the NSF ALADDIN Center which she co-directed with Guy. Then Lenore and Manuel will say some words about what they have been working on for the past several years.

Parallel Batch-Dynamic Graph Algorithms (Julian Shun)

Abstract: As many real-world graphs change rapidly, it is crucial to design dynamic algorithms that efficiently maintain graph statistics upon updates, since the cost of re-computation from scratch can be prohibitive. Furthermore, due to the high frequency of updates, we can improve performance by using parallelism to process batches of updates at a time. We will present some of our research on designing parallel batch-dynamic graph algorithms to address these needs. Our research is inspired by Guy’s pioneering work on formalizing the batch-dynamic setting and designing efficient algorithms in it.

The Unbearable Lightness of Parallel Functional Programming from NESL to MPL (Umut Acar)

Abstract: In early 1990's Guy Blelloch and his students developed NESL, a parallel functional programming language. NESL is a strongly typed, purely functional language that supported nested parallelism, the ability to invoke parallel functions recursively, had a cost model, and an efficient implementation. After the "winter" of 1990's and early 2000's, parallelism is ever more important today and for the foreseeable future and NESL will forever be remembered as a fundamental advance that has illuminated the way forward. In this talk, I present the MPL (MaPLe) compiler that allows writing functional parallel programs by extending the Standard ML language with nested parallelism. Unlike NESL, MaPLe is not pure and supports side effects, which appears to be important for efficiency and performance, but it otherwise follows the path illuminated by NESL: it is functional, it is strongly typed, it supports nested parallelism, it has a cost model, and an implementation that is bounded by it. (Joint work with Guy Blelloch, Jatin Arora, Matthew Fluet, Stefan Muller, Ram Raghunathan, Sam Westrick, and Rohan Yadav.)

Computational Models for Modern Architecture (Yan Gu)

Abstract: Guy has designed many computational models for modern computer architecture that have been widely used. In this talk, I will talk about my stories when working on these models with Guy, as well as some later work based on them.

The Yug of Guy, and A Trifle (Siddhartha Chatterjee)

Abstract: The talk will be in two parts. First, I will share some reflections on Guy through anecdotes during my time at CMU. Second, I will present a cute little divisibility problem that I worked on recently. ("Trifle" can be interpreted either as something trivial, or as a dessert.)

Blelloch 101 — In-class quiz (Charles E. Leiserson, CMU Ph.D 1981)

Abstract: Every experienced educator knows the trick: If you're not prepared to teach a lesson, give the class a test.

Organizing Committee

  • Umut Acar
  • Naama Ben-David
  • Laxman Dhulipala
  • Yan Gu
  • Julian Shun
  • Virginia Williams