Statically Optimal Binary Search Tree Computation Using Non-Serial Polyadic Dynamic Programming on GPU's

Autor:	Mohsin Altaf Wani, Manzoor Ahmad
Rok vydání:	2019
Předmět:	Dynamic programming Computer Networks and Communications Computer science Optimal binary search tree Computation Parallel computing
Zdroj:	International Journal of Grid and High Performance Computing. 11:49-70
ISSN:	1938-0267 1938-0259
DOI:	10.4018/ijghpc.2019010104
Popis:	Modern GPUs perform computation at a very high rate when compared to CPUs; as a result, they are increasingly used for general purpose parallel computation. Determining if a statically optimal binary search tree is an optimization problem to find the optimal arrangement of nodes in a binary search tree so that average search time is minimized. Knuth's modification to the dynamic programming algorithm improves the time complexity to O(n2). We develop a multiple GPU-based implementation of this algorithm using different approaches. Using suitable GPU implementation for a given workload provides a speedup of up to four times over other GPU based implementations. We are able to achieve a speedup factor of 409 on older GTX 570 and a speedup factor of 745 is achieved on a more modern GTX 1060 when compared to a conventional single threaded CPU based implementation.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::788be90e3779b7f9f374c9ac1fd717bd https://doi.org/10.4018/ijghpc.2019010104 Zobrazit plný text záznamu