Toward efficient architecture-independent algorithms for dynamic programs
Mohammad Mahdi Javanmard, Pramod Ganapathr, Rathish Das, Zafar Ahmad, Stephen L. Tschudi, Rezaul Chowdhury · 2019
Recursive divide-&-conquer algorithms are known for solving dynamic programming (DP) problems efficiently on shared-memory multicore machines. In this work, we extend them to run efficiently also on manycore GPUs and distributed-memory machines without changing their basic structure.