Article

Parallel search on video cards

Authors:

Andrea Di Blas,

Eric SedlarAuthors Info & Claims

HotPar'09: Proceedings of the First USENIX conference on Hot topics in parallelism

Page 9

Published: 30 March 2009 Publication History

Abstract

Recent approaches exploiting the massively parallel architecture of graphics processors (GPUs) to accelerate database operations have achieved intriguing results. While parallel sorting received significant attention, parallel search has not been explored. With p-ary search we present a novel parallel search algorithm for large-scale database index operations that scales with the number of processors and outperforms traditional thread-level parallel GPU and CPU implementations. With parallel architectures becoming omnipresent, and with searching being a fundamental functionality for many applications, we expect it to be applicable beyond the database domain. While GPUs do not appear to be ready to be adopted for general-purpose database applications yet, given their rapid development, we expect this to change in the near future. The trend towards massively parallel architectures, combining CPU and GPU processing, encourages development of parallel techniques on both architectures.

References

[1]

P. A. Boncz, S.Manegold, and M. L. Kersten, "Database architecture optimized for the new bottleneck: Memory access," in VLDB '99.

[2]

T. T. Team, "High-performance and scalability through application tier, in-memory data management," in VLDB'00.

[3]

A. Ailamaki, D. J. DeWitt, M. D. Hill, and D. A.Wood, "DBMSs on a modern processor: Where does time go?" in VLDB'99.

[4]

W. A. Wulf and S. A. McKee, "Hitting the memory wall: implications of the obvious," SIGARCH Comput. Archit. News, vol. 23, no. 1, pp. 20-24, 1995.

[5]

S. A. McKee, "Reflections on the memory wall," in Conf. on Computing Frontiers (CF'04).

[6]

C. Hampel, "Terabyte bandwidth initiative -- architectural considerations for next-generation memory systems," in Hot Chips 20, 2008.

[7]

nVidia, "GeForce 8 Series," 2007, http://www.nvidia.com/page/ geforce8.html.

[8]

B. He, K. Yang, R. Fang, M. Lu, N. Govindaraju, Q. Luo, and P. Sander, "Relational joins on graphics processors," in SIGMOD '08.

[9]

A. Munshi, "OpenCL -- parallel computing on the GPU and CPU," in SIGGRAPH '08.

[10]

D. Carmean, "Larrabee: A many-core x86 architecture for visual computing," in Hot Chips 20, 2008.

[11]

nVidia, "NVIDIA CUDA homepage," 2008, http://developer. nvidia.com/object/cuda.html.

[12]

M. J. Flynn, "Very high-speed computing systems," in Proc. of the IEEE, vol. 54(12), 1966, pp. 1901-1909.

[13]

J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Krueger, A. E. Lefohn, and T. J. Purcell, "A survey of general-purpose computation on graphics hardware," Computer Graphics Forum, vol. 26, no. 1, pp. 80-113, 2007.

[14]

N. K. Govindaraju, B. Lloyd, W. Wang, M. Lin, and D. Manocha, "Fast computation of database operations using graphics processors," in SIGMOD '04.

[15]

D. Callele, E. Neufeld, and K. DeLathouwer, "Sorting on a GPU," 2003, http://www.cs.usask.ca/faculty/callele/gpusort/ gpusort.html.

[16]

A. Greß and G. Zachmann, "GPU-ABiSort: Optimal parallel sorting on stream architectures," in IPDPS'06.

[17]

N. Govindaraju, J. Gray, R. Kumar, and D. Manocha, "GPUTera-Sort: High performance graphics co-processor sorting for large database management," in SIGMOD '06.

[18]

K. E. Batcher, "Sorting networks and their applications," in AFIPS Spring Joint Computing Conf., 1968.

[19]

N. Bandi, C. Sun, A. E. Abbadi, and D. Agrawal, "Hardware acceleration in commercial databases: A case study of spatial operations," in VLDB '04.

[20]

I. Buck and T. Purcell, "A Toolkit for Computation on GPUs," in GPU Gems, Chapter 37, R. Fernando, Ed. New York: Addison Wesley, 2004, pp. 621-636.

[21]

T. Kaldewey, A. D. Blas, J. Hagen, E. Sedlar, and S. A. Brandt, "Memory matters," in RTSS'06.

[22]

K. Schlegel, "Emerging technologies will drive self-service business intelligence," February 2008, Gartner Report. ID Number G00152770.

[23]

N. Firasta, M. Buxton, P. Jinbo, K. Nasri, and S. Kuo, "Intel avx: New frontiers in performance improvements and energy efficiency," 2008, Intel White Paper.

Cited By

Hajj IGómez-Luna JLi CChang LMilojicic DHwu WHsu WYang CLipasti MLee H(2016)KLAPThe 49th Annual IEEE/ACM International Symposium on Microarchitecture10.5555/3195638.3195654(1-12)Online publication date: 15-Oct-2016
https://dl.acm.org/doi/10.5555/3195638.3195654
Shahvarani AJacobsen HÖzcan FKoutrika GMadden S(2016)A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing PlatformsProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2882918(1523-1538)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2882918
Kim JKim SNam B(2013)Parallel multi-dimensional range query processing with R-trees on GPUJournal of Parallel and Distributed Computing10.1016/j.jpdc.2013.03.01573:8(1195-1207)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.jpdc.2013.03.015
Show More Cited By

Recommendations

Parallel volume rendering implementation on graphics cards using CUDA
Facing the multicore-challenge

The ever-increasing amounts of volume data require high-end parallel visualization methods to process this data interactively. To meet the demands, progamming on graphics cards offers an effective and fast approach to compute volume rendering methods ...
Massively parallel differential evolution--pattern search optimization with graphics hardware acceleration: an investigation on bound constrained optimization problems

This paper presents a novel parallel Differential Evolution (DE) algorithm with local search for solving function optimization problems, utilizing graphics hardware acceleration. As a population-based meta-heuristic, DE was originally designed for ...
Parallel neighbourhood search on many-core platforms

This paper presents a parallel search parallel move approach to parallelise neighbourhood search algorithms on many-core platforms. In this approach, a large number of searches are run concurrently and coordinated periodically. Iteratively, each search ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

HotPar'09: Proceedings of the First USENIX conference on Hot topics in parallelism

March 2009

18 pages

Publisher

USENIX Association

United States

Publication History

Published: 30 March 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hajj IGómez-Luna JLi CChang LMilojicic DHwu WHsu WYang CLipasti MLee H(2016)KLAPThe 49th Annual IEEE/ACM International Symposium on Microarchitecture10.5555/3195638.3195654(1-12)Online publication date: 15-Oct-2016
https://dl.acm.org/doi/10.5555/3195638.3195654
Shahvarani AJacobsen HÖzcan FKoutrika GMadden S(2016)A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing PlatformsProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2882918(1523-1538)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2882918
Kim JKim SNam B(2013)Parallel multi-dimensional range query processing with R-trees on GPUJournal of Parallel and Distributed Computing10.1016/j.jpdc.2013.03.01573:8(1195-1207)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.jpdc.2013.03.015
Yamamuro TOnizuka MHitaka TYamamuro M(2012)VAST-TreeProceedings of the 15th International Conference on Extending Database Technology10.1145/2247596.2247643(396-407)Online publication date: 27-Mar-2012
https://dl.acm.org/doi/10.1145/2247596.2247643
Kim CChhugani JSatish NSedlar ENguyen AKaldewey TLee VBrandt SDubey P(2011)Designing fast architecture-sensitive tree search on modern multicore/many-core processorsACM Transactions on Database Systems10.1145/2043652.204365536:4(1-34)Online publication date: 19-Dec-2011
https://dl.acm.org/doi/10.1145/2043652.2043655
Kim CChhugani JSatish NSedlar ENguyen AKaldewey TLee VBrandt SDubey PElmagarmid AAgrawal D(2010)FASTProceedings of the 2010 ACM SIGMOD International Conference on Management of data10.1145/1807167.1807206(339-350)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807167.1807206

View Options

View options

Media

Figures

Other

Tables

View Table of Contents