@inproceedings{97151864420745f0a2c67bde01a96514,
title = "Toward efficient architecture-independent algorithms for dynamic programs",
abstract = "Recursive divide-\&-conquer algorithms are known for solving dynamic programming (DP) problems eficiently on shared-memory multicore machines. In this work, we extend them to run eficiently also on manycore GPUs and distributed-memory machines without changing their basic structure. Our GPU algorithms work eficiently even when the data is too large to fit into the host RAM. These are external-memory algorithms based on recursive r-way divide and conquer, where r (≥ 2) varies based on the current depth of the recursion. Our distributed-memory algorithms are also based on multi-way recursive divide and conquer that extends naturally inside each shared-memory multicore/manycore compute node. We show that these algorithms are work-optimal and have low latency and bandwidth bounds. We also report empirical results for our algorithms.",
keywords = "Communication eficiency, Distributed, Divide-\&-conquer, Dynamic program, GPU, I/O eficiency, Recursive",
author = "Javanmard, \{Mohammad Mahdi\} and Pramod Ganapathr and Rathish Das and Zafar Ahmad and Stephen Tschudi and Rezaul Chowdhury",
note = "Publisher Copyright: {\textcopyright} 2019 Copyright held by the owner/author(s).; 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019 ; Conference date: 16-02-2019 Through 20-02-2019",
year = "2019",
month = feb,
day = "16",
doi = "10.1145/3293883.3299109",
language = "English",
series = "Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP",
publisher = "Association for Computing Machinery",
pages = "413--414",
booktitle = "PPoPP 2019 - Proceedings of the 24th Principles and Practice of Parallel Programming",
}