Automatic Derivation of Efficient Parallel Recursive Divide-&-Conquer Algorithms for Dynamic Programs

Speaker: Rezaul Chowdhury , Stony Brook University

Date: Monday, October 19, 2020

Time: 2:00 PM to 3:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/meeting/register/tJUrdOqopj8uHdO4gUyVMnfglOFEqIye_Je0 (Registration required, if you haven't registered for this series before)

Event Type: Seminar

Room Description:

Host: Julian Shun, MIT CSAIL

Contact: Julian Shun, jshun@mit.edu, lindalynch@csail.mit.edu

Relevant URL: http://fast-code.csail.mit.edu/

Speaker URL: https://www3.cs.stonybrook.edu/~rezaul/

Speaker Photo:
None

Reminders to: fast-code-seminar@lists.csail.mit.edu, seminars@csail.mit.edu, pl@csail.mit.edu, commit@lists.csail.mit.edu, toc-students@csail.mit.edu, toc-postdocs@csail.mit.edu, toc-faculty@csail.mit.edu

Reminder Subject: TALK: Automatic Derivation of Efficient Parallel Recursive Divide-&-Conquer Algorithms for Dynamic Programs

ABSTRACT: This talk is about AutoGen -- an algorithm that given any correct blackbox implementation (e.g., inefficient serial iterative code) of a dynamic programming (DP) recurrence from a wide class of DP problems automatically derives a provably correct and efficient cache-oblivious parallel recursive divide-and-conquer algorithm for evaluating that recurrence. AutoGen analyzes the set of DP table locations accessed by the blackbox implementation when run on a DP table of small size and identifies a recursive access pattern and a corresponding provably correct recursive algorithm for solving the DP recurrence.

Our experimental results show that implementations of several autogenerated algorithms significantly outperform standard parallel looping and tiled loop-based codes. Also, these algorithms are less sensitive to fluctuations of memory and bandwidth compared with their looping counterparts, and their running times and energy profiles remain more stable.

AutoGen is one of the two major outcomes from a collaborative project between MIT (CAP and SuperTech), Stony Brook (TEALab) and Fudan University. The other one is the Bellmania system which uses deductive reasoning to derive provably correct efficient parallel recursive divide-and-conquer implementations of DP recurrences.

AutoGen and Bellmania are arguably more advanced systems than the Pochoir stencil compiler -- an earlier collaboration between MIT (SuperTech), Fudan University, and Stony Brook (TEALab). Pochoir produces a highly optimized parallel stencil code from a simple specification of a stencil. While Pochoir already knows the algorithm (i.e., the trapezoidal decomposition algorithm) it wants to produce an implementation for, AutoGen and Bellmania do not and hence must find the algorithm first.

BIO: Rezaul Chowdhury is an Associate Professor of Computer Science at Stony Brook University and a core faculty member of the Institute for Advanced Computational Science (IACS). His research interests are in the fields of algorithm design and algorithm engineering and their intersections with other sciences. He is particularly interested in the scheduling and theoretical/practical performance analysis of parallel cache-efficient algorithms. His research interests also include computational biology and bioinformatics, particularly protein-protein docking and fast energetics computation. He received an NSF CAREER Award in 2015.

IMPORTANT NOTE FOR ATTENDEES: If you have already registered for the Fast Code Seminars on Zoom since July 27, 2020, please use the Zoom link that you have received. This link will stay the same for subsequent Fast Code seminars this semester. Zoom does not recognize a second registration, and will not send out the link a second time. If you have any problems with registration, please contact jshun@mit.edu and lindalynch@csail.mit.edu by 1:30pm on the day of the seminar, so that we can try to resolve it before the seminar begins.

Research Areas:
Algorithms & Theory, Programming Languages & Software

Impact Areas:
Big Data

See other events that are part of the Fast Code 2020 - 2021.

Created by Julian J. Shun at Monday, October 12, 2020 at 8:42 PM.