A Constraint-Based Approach to Automatic Data Partitioning

Speaker: Wonchan Lee, Stanford University
September 5, 2019

Presentation

Abstract

Although data partitioning is required to enable parallelism on distributed memory systems, data partitions are not first class objects in most distributed programming models. As a result, automatic parallelizers and application writers encode a particular partitioning strategy in the parallelized program, leading to a program not easily configured or composed with other parallel programs.

In this talk, we present a constraint-based approach to automatic data partitioning. By introducing abstractions for first-class data partitions, we express a space of correct partitioning strategies. Candidate partitions are characterized by partitioning constraints, which can be automatically inferred from data accesses in parallelizable loops. Constraints can be satisfied by synthesized partitioning code or user-provided partitions. We demonstrate that programs auto-parallelized in our approach are easily composed with manually parallelized parts and have scalability comparable to hand-optimized counterparts.

Biography

Wonchan Lee is a 6th Ph.D. student at the Computer Science Department at Stanford University advised by Prof. Alex Aiken. Lee has been actively contributing to Legion, a data-centric parallel programming system for distributed memory machines. His research focuses on compiler and runtime optimizations for implicitly parallel programming systems like Legion. His current interest is in Just-In-Time (JIT) specialization techniques for data partitioning and task graph construction.

Seminar Participation

Attending In Person

For select seminars, you may wish to attend in-person if you are in the vicinity of NASA Ames Research Center. These AMS seminars are held in Building N258 in Room 127, just off the front lobby. Sessions available to attend in-person will be indicated in the announcement information. In-person participants without NASA badges will need a valid visitor badge (US citizenship or permanent residency is required) to enter the facility.

Join Us Online

To attend an AMS seminar, click on the Microsoft Teams link in the seminar description. You can connect through the desktop Teams App if you have it, or you can select "Watch on the Web Instead" to enter the meeting as a guest. Please ensure that you've muted your microphone in Teams before you select "Join Now" to enter the meeting lobby.