Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers
Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers
复制标题
使用多面体编译器导出参数多路递归分治动态规划算法
DOI：
10.1145/3368826.3377916
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Harrison, Robert
中科院分区：
文献类型：
--
作者：
Javanmard, Mohammad Mahdi;Ahmad, Zafar;Kong, Martin;Pouchet, Louis-Noël;Chowdhury, Rezaul;Harrison, Robert
针对一类动态规划问题，提出了一种自动导出高效参数化多路递归分治算法的新框架。标准的双向或任何固定dr -way递归分治算法可能无法充分利用多核处理器。为了在给定的机器上有效地运行，r的值可能需要根据可用处理器的数量和内存层次结构中不同级别的内存/缓存的大小，在每个递归级别上有所不同。在给定机器上运行良好的一组右值在具有不同机器参数集的另一台机器上可能无法有效地工作。为了提高可移植性和效率，Multi-way Autogen生成了参数化的多路递归分治算法，其中r的值可以在每个递归级别上动态更改。我们给出了实验结果，证明了由我们的框架产生的并行程序的性能和可扩展性。
We present a novel framework to automatically derive highly efficient parametric multi-way recursive divide&conquer algorithms for a class of dynamic programming (DP) problems. Standard two-way or any fixedR-way recursive divide&conquer algorithms may not fully exploit many-core processors. To run efficiently on a given machine, the value ofRmay need to be different for every level of recursion based on the number of processors available and the sizes of memory/caches at different levels of the memory hierarchy. The set ofRvalues that work well on a given machine may not work efficiently on another machine with a different set of machine parameters. To improve portability and efficiency, Multi-way Autogen generates parametric multi-way recursive divide&conquer algorithms where the value ofRcan be changed on the fly for every level of recursion. We present experimental results demonstrating the performance and scalability of the parallel programs produced by our framework.
登录
查看更多内容
通信避免算法：并行系统的分析和代码生成
DOI：
--
发表时间：
2015
期刊：
International Conference on Parallel Architectures and Compilation Techniques
影响因子：
--
作者：
K. Murthy;J. Mellor
通讯作者：
J. Mellor
Z 多面体模型
DOI：
10.1145/1229428.1229478
发表时间：
2007
期刊：
Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming
影响因子：
--
作者：
Gautam Gupta;S. Rajopadhye
通讯作者：
S. Rajopadhye
DOI：
10.1145/349299.349323
发表时间：
2000-05
期刊：
--
影响因子：
--
作者：
Qing Yi;Vikram S. Adve;K. Kennedy
通讯作者：
Qing Yi;Vikram S. Adve;K. Kennedy
缓存自适应算法
影响因子：
3.7
作者：
M. A. Bender;Roozbeh Ebrahimi;Jeremy T. Fineman;Golnaz Ghasemiesfeh;Rob Johnson;Samuel McCauley
通讯作者：
Samuel McCauley
使用求解器辅助变换导出分治动态规划算法
DOI：
--
发表时间：
2016
期刊：
Conference on Object-Oriented Programming Systems, Languages, and Applications
影响因子：
--
作者：
Shachar Itzhaky;Rohit Singh;Armando Solar;Kuat Yessenov;Yongquan Lu;C. Leiserson;R. Chowdhury
通讯作者：
R. Chowdhury