Program for the spring quarter of 2023.

4/6: Parsel: A (De-)compositional Framework for Algorithmic Reasoning with Language Models

Time: Thursday, April 6, 2023, 12 noon - 1pm
Location: Gates 415

Speaker: Eric Zelikman

Abstract: Despite recent success in large language model (LLM) reasoning, LLMs struggle with hierarchical multi-step reasoning tasks like generating complex programs. In these cases, humans often start with a high-level algorithmic design and implement each part gradually. We introduce Parsel, a framework enabling automatic implementation and validation of complex algorithms with code LLMs, taking hierarchical function descriptions in natural language as input. We show that Parsel can be used across domains requiring hierarchical reasoning, including code synthesis, theorem proving, and robotic planning. We demonstrate that generating and compiling Parsel solutions on competition-level problems in the APPS dataset improves pass rates over AlphaCode and Codex by over 2x, typically with a substantially smaller sample budget. We also find that generating robotic plans in Parsel improves executability. Lastly, we explore how Parsel addresses prior LLM limitations and discuss how Parsel may be useful for students and professional programmers.

4/13: Organizational Lunch

Time: Thursday, April 13, 2023, 12 noon - 1pm
Location: Gates 415

Organizational lunch. Come sign up to give a talk during the quarter.

Food:

4/20: Maple: A Domain-Specific Language for Mapping Task-Based Applications

Time: Thursday, April 20, 2023, 12 noon - 1pm
Location: Gates 415

Speaker: Anjiang Wei

Abstract: In distributed programming, deciding where tasks run and where data is placed, or mapping, is crucial to application performance. To make mapping decisions, existing frameworks either employ heuristics within the system implementation or expose a low-level application interface opaque to programmers unfamiliar with the underlying runtime implementation. To improve the productivity of writing mappers for distributed programs without sacrificing programmability, we propose a domain-specific language Maple for task-based programming systems with explicit mapping control. In Maple, users can create machine models and apply transformation primitives to express complex mapping for bulk launches of tasks on a distributed machine. Our experiments demonstrate that Maple is expressive enough to implement mappers that achieve state-of-the-art performance across nine applications, and reduces the lines of code needed to write these mappers by an average of 92.9%, compared to mappers written in the low-level C++ interface of Legion.

Food:

4/27: Addressing the Environment Problem

Time: Thursday, April 27, 2023, 12 noon - 1pm
Location: Gates 415

Speaker: Matthew Sotoudeh

Abstract: Program analysis tools need to make assumptions about the environment the program will be run in: what might the hardware return when the address 0x20200034 (GPIO_lev) is read? Is the caller allowed to pass a null as an argument to this function? Etc. Over-approximating the environment leads to uselessness, under-approximating to inaccuracy. I will demo a C interpreter & program analysis framework attempting to hit a nicer balance. We have used the tool to automatically extract device init routines from Linux kernel patches, replacing an ongoing month-long manual effort in our group.

Food:

5/4: Distinct Elements in Streams: An Algorithm for the (Text) Book.

Time: Thursday, May 4, 2023, 12 noon - 1pm
Location: Gates 415

Speaker: Kuldeep Meel

Abstract: Given a data stream of m elements, the Distinct Elements problem is to estimate the number of distinct elements in the stream. Distinct Elements has been a subject of theoretical and empirical investigations over the past four decades resulting in space-optimal algorithms for it. However, all the current state-of-the-art algorithms are often difficult to analyze or impractical. I will present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with a knowledge of basic probability theory. In addition to the simplicity, the approach has significant theoretical and practical implications: our approach allowed us to resolve the open problem of (Discrete) Klee's Measure Problem in the streaming setting and build a state-of-the-art DNF counter in practice.

Food:

5/11: KDRSolvers: Flexible, Scalable Task-Oriented Linear Solvers

Time: Thursday, May 11, 2023, 12 noon - 1pm
Location: Gates 415

Speaker: David Zhang

Abstract: Solving large systems of linear equations is, arguably, the most important workload in scientific computing -- in fact, the TOP500 supercomputer ranking is based solely on who can solve linear equations the fastest. Computational scientists have developed several mature libraries for this problem, including PETSc, Trilinos, and HYPRE, that target MPI applications. However, the restrictive nature of the MPI bulk-synchronous programming model limits their expressivity, flexibility, and composability. In this talk, I'll show how a task-oriented parallel programming system, like Legion, can be used to implement a next-generation solver library that is both faster and provides new capabilities, such as user-extensible matrix data types and dynamic load balancing.

Food:

5/18: Automated Mapping of Task-Based Programs onto Distributed and Heterogeneous Machines

Time: Thursday, May 18, 2023, 12 noon - 1pm
Location: Gates 415

Speaker: Thiago Teixeira

Abstract: In a parallel and distributed application, a mapping is a selection of a processor for each computation or task and memories for the data collections each task accesses. Finding high-performance mapping is challenging, particularly on heterogeneous hardware with multiple choices for processors and memories. We show that fast mappings are sensitive to the machine, application, and input. We present Automap, a system that automatically tunes the mapping to the hardware used without user intervention or code modification. Automap utilizes a novel search algorithm called constrained coordinate-wise descent (CCD) that explicitly balances the trade-off between running computations fast and minimizing data movement. With CCD, Automap discovers mappings up to 2.41x faster than custom, hand-written mappers.

Food:

5/25: Fast Instruction Selection for Fast Digital Signal Processing

Time: Thursday, May 25, 2023, 12 noon - 1pm
Location: Gates 415

Speaker: AJ Root

Abstract: We present FPIR: a portable and performant language for fixed-point digital signal processing; and Pitchfork: a two-stage system that first lifts legacy C-style code into FPIR before lowering FPIR to target-specific instructions on multiple backends. FPIR is specifically designed to enable automatic synthesis of interesting and powerful lifting and lowering rules. We show that our approach improves run-time performance of portably-written fixed-point signal processing code in Halide across a range of benchmarks, by geomean 1.31x on x86 with AVX2, 1.82x on ARM Neon, and 2.46x on Hexagon HVX compared to a standard LLVM-based compiler flow, while maintaining or improving existing compile times, and decreasing the amount of code required to implement each backend.

Food:

6/1: Discrete Adversarial Attack to Models of Code

Time: Thursday, June 1, 2023, 12 noon - 1pm
Location: Gates 415

Speaker: Ke Wang

Abstract: The pervasive brittleness of deep neural networks has attracted significant attention in recent years. A particularly interesting finding is the existence of adversarial examples, imperceptibly perturbed natural inputs that induce erroneous predictions in state-of-the-art neural models. In this talk, I introduce a different type of adversarial examples specific to code models, called discrete adversarial examples, which are created through program transformations that preserve the semantics of original inputs. In particular, I present a novel, general method that is highly effective in attacking a broad range of code models. From the defense perspective, I lay out a theoretical foundation for the application of adversarial training — the most successful algorithm for training robust classifiers — to defend code models against discrete adversarial attack. Motivated by the theoretical results, I discuss a simple realization of adversarial training that substantially improves the robustness of code models against adversarial attacks in practice. Finally, I report a comprehensive evaluation on both the attack and defense methods. Results show that the discrete attack is significantly more effective than state-of-the-art whether or not defense mechanisms are in place to aid models in resisting attacks. In addition, the realization of adversarial training improves the robustness of all evaluated models by the widest margin against state-of-the-art adversarial attacks as well as my own.

Food:

6/8: Mosaic: An Interoperable Compiler for Tensor Algebra

Time: Thursday, June 8, 2023, 12 noon - 1pm
Location: Gates 415

Speaker: Manya Bansal

Abstract: We introduce Mosaic, a sparse tensor algebra compiler that binds tensor (sub-)expressions to external functions of other tensor algebra libraries and compilers. Users can extend Mosaic by adding new functions and can bind a sub-computation to a function using a scheduling API. Mosaic substitutes the bound (sub-)expressions with the specified function call and automatically fills in the rest of the unbound code using a default code generator. Mosaic also offers a search system that can automatically map an expression to a set of registered external functions. Both the explicit binding and automatic search are verified by Mosaic. We demonstrate the benefits of our approach by showing that calling hand-written CPU and specialized hardware functions can provide speedup of up to 206x (for an SDDMM expression) and 173x (for an SpMV expression), respectively, over a homogeneous compiler. Mosaic's external function interface is simple and general. Currently, 38 external functions have been added to Mosaic, with each addition averaging 20 lines of code.

Food:

6/15: Indexed Streams: A Formal Intermediate Representation for the Fused Execution of Contraction Operations

Time: Thursday, June 15, 2023, 12 noon - 1pm
Location: Gates 415

Speaker: Scott Kovach

Abstract: We introduce indexed streams, a formal operational model and intermediate representation that describes the fused execution of a contraction language that encompasses both sparse tensor algebra and relational algebra. We prove that the indexed stream model is correct with respect to a functional semantics. We also develop a compiler for contraction expressions that uses indexed streams as an intermediate representation. The compiler is only 540 lines of code, but we show that its performance can match both the TACO compiler for sparse tensor algebra and the SQLite and DuckDB query processing libraries for relational algebra.

Food: