Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers

Mohammad Mahdi Javanmard; Zafar Ahmad; Martin Kong; Louis Noël Pouchet; Rezaul Chowdhury; Robert Harrison

doi:10.1145/3368826.3377916

Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers

Mohammad Mahdi Javanmard
, Zafar Ahmad
, Martin Kong
, Louis Noël Pouchet
, Rezaul Chowdhury
, Robert Harrison

Stony Brook University
University of Oklahoma
Colorado State University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

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 fixed R-way recursive divide- &-conquer algorithms may not fully exploit many-core processors. To run efficiently on a given machine, the value of R may 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 of R values 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 of R can 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.

Original language	English
Title of host publication	CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization
Editors	Jason Mars, Lingjia Tang, Jingling Xue, Peng Wu
Publisher	Association for Computing Machinery, Inc
Pages	317-329
Number of pages	13
ISBN (Electronic)	9781450370479
DOIs	https://doi.org/10.1145/3368826.3377916
State	Published - Feb 22 2020
Event	18th ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2020 - San Diego, United States Duration: Feb 22 2020 → Feb 26 2020

Publication series

Name	CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization

Conference

Conference	18th ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2020
Country/Territory	United States
City	San Diego
Period	02/22/20 → 02/26/20

Keywords

Dynamic Programming
Index Set Splitting
Manycore
Multi-way Recursive Divide-&-Conquer
Parametric Tiling
Polyhedral Compilation

Access to Document

10.1145/3368826.3377916

Cite this

Javanmard, M. M., Ahmad, Z., Kong, M., Pouchet, L. N., Chowdhury, R., & Harrison, R. (2020). Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers. In J. Mars, L. Tang, J. Xue, & P. Wu (Eds.), CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization (pp. 317-329). (CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization). Association for Computing Machinery, Inc. https://doi.org/10.1145/3368826.3377916

Javanmard, Mohammad Mahdi ; Ahmad, Zafar ; Kong, Martin et al. / Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers. CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization. editor / Jason Mars ; Lingjia Tang ; Jingling Xue ; Peng Wu. Association for Computing Machinery, Inc, 2020. pp. 317-329 (CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization).

@inproceedings{c44fbf293d004a0fb64c3183b77ffc62,

title = "Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers",

abstract = "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 fixed R-way recursive divide- \&-conquer algorithms may not fully exploit many-core processors. To run efficiently on a given machine, the value of R may 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 of R values 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 of R can 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.",

keywords = "Dynamic Programming, Index Set Splitting, Manycore, Multi-way Recursive Divide-\&-Conquer, Parametric Tiling, Polyhedral Compilation",

author = "Javanmard, \{Mohammad Mahdi\} and Zafar Ahmad and Martin Kong and Pouchet, \{Louis No{\"e}l\} and Rezaul Chowdhury and Robert Harrison",

note = "Publisher Copyright: {\textcopyright} 2020 Copyright held by the owner/author(s).; 18th ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2020 ; Conference date: 22-02-2020 Through 26-02-2020",

year = "2020",

month = feb,

day = "22",

doi = "10.1145/3368826.3377916",

language = "English",

series = "CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization",

publisher = "Association for Computing Machinery, Inc",

pages = "317--329",

editor = "Jason Mars and Lingjia Tang and Jingling Xue and Peng Wu",

booktitle = "CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization",

}

Javanmard, MM, Ahmad, Z, Kong, M, Pouchet, LN, Chowdhury, R & Harrison, R 2020, Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers. in J Mars, L Tang, J Xue & P Wu (eds), CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization. CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization, Association for Computing Machinery, Inc, pp. 317-329, 18th ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2020, San Diego, United States, 02/22/20. https://doi.org/10.1145/3368826.3377916

Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers. / Javanmard, Mohammad Mahdi; Ahmad, Zafar; Kong, Martin et al.
CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization. ed. / Jason Mars; Lingjia Tang; Jingling Xue; Peng Wu. Association for Computing Machinery, Inc, 2020. p. 317-329 (CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers

AU - Javanmard, Mohammad Mahdi

AU - Ahmad, Zafar

AU - Kong, Martin

AU - Pouchet, Louis Noël

AU - Chowdhury, Rezaul

AU - Harrison, Robert

PY - 2020/2/22

Y1 - 2020/2/22

N2 - 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 fixed R-way recursive divide- &-conquer algorithms may not fully exploit many-core processors. To run efficiently on a given machine, the value of R may 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 of R values 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 of R can 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.

AB - 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 fixed R-way recursive divide- &-conquer algorithms may not fully exploit many-core processors. To run efficiently on a given machine, the value of R may 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 of R values 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 of R can 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.

KW - Dynamic Programming

KW - Index Set Splitting

KW - Manycore

KW - Multi-way Recursive Divide-&-Conquer

KW - Parametric Tiling

KW - Polyhedral Compilation

UR - https://www.scopus.com/pages/publications/85082125593

U2 - 10.1145/3368826.3377916

DO - 10.1145/3368826.3377916

M3 - Conference contribution

AN - SCOPUS:85082125593

T3 - CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization

SP - 317

EP - 329

BT - CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization

A2 - Mars, Jason

A2 - Tang, Lingjia

A2 - Xue, Jingling

A2 - Wu, Peng

PB - Association for Computing Machinery, Inc

T2 - 18th ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2020

Y2 - 22 February 2020 through 26 February 2020

ER -

Javanmard MM, Ahmad Z, Kong M, Pouchet LN, Chowdhury R , Harrison R. Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers. In Mars J, Tang L, Xue J, Wu P, editors, CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization. Association for Computing Machinery, Inc. 2020. p. 317-329. (CGO 2020 - Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization). doi: 10.1145/3368826.3377916

Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilers

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this