PPoPP 2016
Sat 12 - Wed 16 March 2016 Barcelona, Spain
Mon 14 Mar 2016 15:35 - 16:00 at Mallorca+Menorca - Algorithms Chair(s): Lawrence Rauchwerger

We present 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.

Mon 14 Mar

Displayed time zone: Belfast change

14:20 - 16:00
AlgorithmsMain conference at Mallorca+Menorca
Chair(s): Lawrence Rauchwerger Texas A&M University
14:20
25m
Talk
Articulation Point Guided Redundancy Elimination for Betweenness Centrality
Main conference
Lei Wang Institute of Computing Technology, Chinese Academy of Science, Fan Yang Institute of Computing Technology, Chinese Academy of Science, Liangji Zhuang Institute of Computing Technology, Chinese Academy of Science, Huimin Cui Institute of Computing Technology, Chinese Academy of Sciences, Fang Lv Institute of Computing Technology, Chinese Academy of Sciences, Xiaobing Feng ICT CAS
Link to publication DOI
14:45
25m
Talk
Multi-Core On-The-Fly SCC DecompositionArtifact Evaluation
Main conference
Vincent Bloemen University of Twente, Alfons Laarman Vienna University of Technology, Jaco van de Pol University of Twente
Link to publication DOI
15:10
25m
Talk
A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization
Main conference
Ramakrishnan Kannan Georgia Institute of Technology, Grey Ballard Sandia National Laboratories, Haesun Park Georgia Institute of Technology
Link to publication DOI
15:35
25m
Talk
Autogen: Automatic Discovery of Cache-Oblivious Parallel Recursive Algorithms for Solving Dynamic ProgramsArtifact Evaluation
Main conference
Rezaul Chowdhury Stony Brook University, Pramod Ganapathi Stony Brook University, Jesmin Jahan Tithi Intel, CA, USA, Charles Bachmeier MIT, Bradley Kuszmaul MIT, Charles E. Leiserson MIT, Armando Solar-Lezama MIT, Yuan Tang Fudan University
Link to publication DOI