Statically optimal binary search tree computation using non-serial polyadic dynamic programming on GPU's
Authors: Wani, M.A. and Ahmad, M.
Journal: International Journal of Grid and High Performance Computing
Volume: 11
Issue: 1
Pages: 49-70
eISSN: 1938-0267
ISSN: 1938-0259
DOI: 10.4018/IJGHPC.2019010104
Abstract: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.
Source: Scopus