Fwd: Talk on automatic algorithm discovery.

[Hema Murthy]

FYI.

---------- Forwarded message ----------
From: rupesh0508 . <rupes...@gmail.com>
Date: 13 April 2016 at 19:17
Subject: Talk on automatic algorithm discovery.
To: sem...@cse.iitm.ac.in

Title: Automatic Discovery of Divide-and-Conquer Dynamic Programming Algorithms

Date: April 19, 2016.
Time: 14:00.
Venue: CS24.

Abstract:
The talk presents AUTOGEN — an algorithm that for a wide class of dynamic programming (DP) problems automatically discovers highly efficient cache-oblivious parallel recursive divide-and-conquer algorithms from inefficient iterative descriptions of DP recurrences. AUTOGEN analyzes the set of DP table locations accessed by the iterative algorithm when run on a DP table of small size, and automatically identifies a recursive access pattern and a corresponding provably correct recursive algorithm for solving the DP recurrence. We use AUTOGEN to autodiscover efficient algorithms for several well-known problems. Our experimental results show that several autodiscovered algorithms significantly outperform parallel looping and tiled loop-based algorithms. 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 relatively more stable. To the best of our knowledge, AUTOGEN is the first algorithm that can automatically discover
new nontrivial divide-and-conquer algorithms.

Speaker Bio:
Pramod Ganapathi, a fifth year PhD student at Stony Brook University working with Prof. Rezaul Chowdhury. He completed BTech from SJCE Mysore and then worked in IBM India for two years, His research interests are in developing frameworks to discover algorithms. He also claims that he is algoholic.

-rupesh.