Welcome to the InfoSci Platform
Reference Hub1
Statically Optimal Binary Search Tree Computation Using Non-Serial Polyadic Dynamic Programming on GPU's

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

Mohsin Altaf Wani, Manzoor Ahmad
Copyright: © 2019 |Volume: 11 |Issue: 1 |Pages: 22
ISSN: 1938-0259|EISSN: 1938-0267|EISBN13: 9781522564904|DOI: 10.4018/IJGHPC.2019010104
Cite Article Cite Article

MLA

Wani, Mohsin Altaf, and Manzoor Ahmad. "Statically Optimal Binary Search Tree Computation Using Non-Serial Polyadic Dynamic Programming on GPU's." IJGHPC vol.11, no.1 2019: pp.49-70. http://doi.org/10.4018/IJGHPC.2019010104

APA

Wani, M. A. & Ahmad, M. (2019). Statically Optimal Binary Search Tree Computation Using Non-Serial Polyadic Dynamic Programming on GPU's. International Journal of Grid and High Performance Computing (IJGHPC), 11(1), 49-70. http://doi.org/10.4018/IJGHPC.2019010104

Chicago

Wani, Mohsin Altaf, and Manzoor Ahmad. "Statically Optimal Binary Search Tree Computation Using Non-Serial Polyadic Dynamic Programming on GPU's," International Journal of Grid and High Performance Computing (IJGHPC) 11, no.1: 49-70. http://doi.org/10.4018/IJGHPC.2019010104

Export Reference

Mendeley
Favorite Full-Issue Download

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.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.