GID 2014

Krzysztof Kaczmarski, Piotr Przymus, and Paweł Rzążewski

Improving High-Performance GPU Graph Traversal with Compression

Traversing huge graphs is a crucial part of many real-world problems, including graph databases. We show how to apply Fixed Length lightweight compression method for traversing graphs stored in the GPU global memory. This approach allows for a significant saving of memory space, improves data alignment, cache utilization and, in many cases, also processing speed. We tested our solution against the state-of-the-art implementation of BFS for GPU and obtained very promising results.

Dariusz Rafal Augustyn and Lukasz Warchal

GPU-Accelerated Method of Query Selectivity Estimation for Non Equi-Join Conditions Based on Discrete Fourier Transform

Selectivity factor is obtained by database query optimizer for estimating the size of data that satisfy a query condition. This allows to choose the optimal query execution plan. In this paper we consider the problem of selectivity estimation for inequality predicates based on two attributes, therefore the proposed solution allows to estimate the size of data that satisfy theta-join conditions. The proposed method is based on Discrete Fourier Transform and convolution theorem. DFT spectrums are used as representations of distribution of attribute values. We compute selectivity either performing Inverse DFT (for an inequality condition based on two attributes) or avoiding it (for a single-attribute range one). Selectivity calculation is a time-critical operation performed during an on-line query preparing phase. We show that by applying parallel processing capabilities of Graphical Processing Unit, the implementation of the method satisfies the assumed time constraint.

Peter Tim Strohm, Steffen Wittmer, Alexander Haberstroh and Tobias Lauer

GPU-Accelerated Quantification Filters for Analytical Queries in Multidimensional Databases

In online analytical processing (OLAP), filtering elements of a given dimensional attribute according to the value of a measure attribute is an essential operation, for example in top-k evaluation. Such filters can involve extremely large amounts of data to be processed, in particular when the filter condition includes “quantification” such as ANY or ALL, where large slices of an OLAP cube have to be computed and inspected. Due to the sparsity of OLAP cubes, the slices serving as input to the filter are usually sparse as well, presenting a challenge for GPU approaches which need to work with a limited amount of memory for holding intermediate results. Our CUDA solution involves a hashing scheme specifically designed for frequent and parallel updates, including several optimizations exploiting architectural features of Nvidia’s Fermi and Kepler GPUs.

GID 2013

Dariusz Rafal Augustyn and Lukasz Warchal

GPU-accelerated query selectivity estimation based on data clustering and Monte Carlo integration method developed in CUDA environment

Query selectivity is a parameter that allows to estimate the size of data satisfying a query condition. For complex range query condition it may be defined as multi integral over a multivariate probability density function (PDF). It describes a multidimensional attribute value distribution and may be estimated using the known approach based on a superposition of Gaussian clusters. But there is the problem of an efficient integration of the multivariate PDF. This may be solved by applying Monte Carlo (MC) method which exposes its advantages for high dimensions. To satisfy the time constraint of selectivity calculation, the parallelized MC integration method was proposed in the paper. The implementation of the method is based on CUDA technology. The paper also describes the application designated for obtaining the time-optimal parameter values of the method.

Sebastian Breß, Max Heimel, Norbert Siegmund, Ladjel Bellatreche, Gunter Saake

Exploring the Design Space of a GPU-aware Database Architecture

The vast amount of processing power and memory bandwidth provided by modern graphics cards make them an interesting platform for data-intensive applications. Unsurprisingly, the database research community has identified GPUs as effective co-processors for data processing several years ago. In the past years, there were many approaches to make use of GPUs at different levels of a database system. In this paper, we summarize the major findings of the literature on GPU-accelerated data processing. Based on this survey, we present key properties, important trade-offs and typical challenges of GPU-aware database architectures, and identify major open research questions.

Piotr Przymus and Krzysztof Kaczmarski

Dynamic compression strategy for time series database using GPU

Nowadays, we can observe increasing interest in processing and exploration of time series. Growing volumes of data and needs of efficient processing pushed research in new directions. GPU devices combined with fast compression and decompression algorithms open new horizons for data intensive systems. In this paper we present improved cascaded compression mechanism for time series databases build on Big Table–like solution. We achieved extremely fast compression methods with good compression ratio.

Benjamin E. Teitler, Jagan Sankaranarayanan, Hanan Samet, and Marco D. Adelfio

Online Document Clustering Using GPUs

An algorithm for performing online clustering on the GPU is proposed which makes heavy use of the atomic operations available on the GPU. The algorithm can cluster multiple documents in parallel in way that can saturate all the parallel threads on the GPU. The algorithm takes advantage of atomic operations available on the GPU in order to cluster multiple documents at the same time. The algorithm results in up to 3X speedup using a real time news document data set as well as on randomly generated data compared to a baseline algorithm on the GPU that clusters only one document at a time.

GID 2012

Dariusz Rafal Augustyn and Sebastian Zederowski

Applying CUDA technology in DCT-based method of query selectivity estimation

The problem of efficient calculation of query selectivity estimation is considered in this paper. The selectivity parameter allows database query optimizer to estimate the size of the data satisfying given condition, which is needed to choose the best query execution plan. Obtaining query selectivity in case of a multi-attribute selection condition requires a representation of multidimensional attributes values distribution. This paper describes in details solution of this problem, which utilizes Discrete Cosine Transform and CUDA-based algorithm for obtaining selectivity estimation. There are also some remarks about efficiency and advantages of this approach.

Pavel Bednár, Petr Gajdoš, Michal Krátký, and Peter Chovanec

Processing of Range Query Using SIMD and GPU

Onedimensional or multidimensional range query is one of the most important query of physical implementation of DBMS. The number of compared items (of a data structure) can be enormous especially for lower selectivity of the range query. The number of compare operations increases for more complex items (or tuples) with the longer length, e.g. words stored in a B-tree. Due to the possibly high number of compare operations executed during the range query processing, we can take into account hardware devices providing a parallel task computation like CPU's SIMD or GPU. In this paper, we show the performance and scalability of sequential, index, CPU's SIMD, and GPU variants of the range query algorithm. These results make possible a future integration of these computation devices into a DBMS kernel.

Sebastian Breß, Eike Schallehn, and Ingolf Geist

Towards Optimization of Hybrid CPU/GPU Query Plans in Database Systems

Current database research identified the computational power of GPUs as a way to increase the performance of database systems. Since GPU algorithms are not necessarily faster than their CPU counterparts, it is important to use the GPU only if it is beneficial for query processing. In a general database context, only few research projects address hybrid query processing, i.e., using a mix of CPU- and GPU-based processing to achieve optimal performance. In this paper, we extend our CPU/GPU scheduling framework to support hybrid query processing in database systems. We point out fundamental problems and provide an algorithm to create a hybrid query plan for a query using our scheduling framework.

Krzysztof Kaczmarski and Paweł Rzazewski

Thrust and CUDA in data intensive algorithms

Huge memory bandwidth and instruction throughput make GPU processors very attractive for many algorithms which can only utilize Single Instruction Multiple Data (SIMD) architecture. Databases and their data intensive operations may also benefit from parallel GPU threads and thread streams. Many libraries offer simple interfaces for GPU, which make memory and threads management as easy as possible. Trade-off in programmers' time, code structure and algorithm efficiency is critical for business applications. In this paper we evaluate the usage of Thrust library and its ability to manage millions of threads when compared to pure CUDA C program.