hrcak mascot   Srce   HID

Izvorni znanstveni članak
https://doi.org/10.20532/cit.2019.1004579

A Parallelization of Non-Serial Polyadic Dynamic Programming on GPU

Tausif Diwan ; Indian Institute of Information Technology, Nagpur, India
Jitendra Tembhurne ; Indian Institute of Information Technology, Nagpur, India

Puni tekst: engleski, pdf (1 MB) str. 55-66 preuzimanja: 31* citiraj
APA 6th Edition
Diwan, T. i Tembhurne, J. (2019). A Parallelization of Non-Serial Polyadic Dynamic Programming on GPU. Journal of computing and information technology, 27 (2), 55-66. https://doi.org/10.20532/cit.2019.1004579
MLA 8th Edition
Diwan, Tausif i Jitendra Tembhurne. "A Parallelization of Non-Serial Polyadic Dynamic Programming on GPU." Journal of computing and information technology, vol. 27, br. 2, 2019, str. 55-66. https://doi.org/10.20532/cit.2019.1004579. Citirano 25.01.2020.
Chicago 17th Edition
Diwan, Tausif i Jitendra Tembhurne. "A Parallelization of Non-Serial Polyadic Dynamic Programming on GPU." Journal of computing and information technology 27, br. 2 (2019): 55-66. https://doi.org/10.20532/cit.2019.1004579
Harvard
Diwan, T., i Tembhurne, J. (2019). 'A Parallelization of Non-Serial Polyadic Dynamic Programming on GPU', Journal of computing and information technology, 27(2), str. 55-66. https://doi.org/10.20532/cit.2019.1004579
Vancouver
Diwan T, Tembhurne J. A Parallelization of Non-Serial Polyadic Dynamic Programming on GPU. Journal of computing and information technology [Internet]. 2019 [pristupljeno 25.01.2020.];27(2):55-66. https://doi.org/10.20532/cit.2019.1004579
IEEE
T. Diwan i J. Tembhurne, "A Parallelization of Non-Serial Polyadic Dynamic Programming on GPU", Journal of computing and information technology, vol.27, br. 2, str. 55-66, 2019. [Online]. https://doi.org/10.20532/cit.2019.1004579

Sažetak
Parallelization of Non-Serial Polyadic Dynamic Programming (NPDP) on high-throughput manycore architectures, such as NVIDIA GPUs, suffers from load imbalance, i.e. non-optimal mapping between the sub-problems of NPDP and the processing elements of the GPU. NPDP exhibits non-uniformity in the number of subproblems as well as computational complexity across the phases. In NPDP parallelization, phases are computed sequentially whereas subproblems of each phase are computed concurrently. Therefore, it is essential to effectively map the subproblems of each phase to the processing elements while implementing thread level parallelism. We propose an adaptive Generalized Mapping Method (GMM) for NPDP parallelization that utilizes the GPU for efficient mapping of subproblems onto processing threads in each phase. Input-size and targeted GPU decide the computing power and the best mapping for each phase in NPDP parallelization. The performance of GMM is compared with different conventional parallelization approaches. For sufficiently large inputs, our technique outperforms the state-of-the-art conventional parallelization approach and achieves a significant speedup of a factor 30. We also summarize the general heuristics for achieving better gain in the NPDP parallelization.

Ključne riječi
dynamic programming, parallel computing, GPU, CUDA, NPDP

Hrčak ID: 228266

URI
https://hrcak.srce.hr/228266

Posjeta: 61 *