Duration: 55:59

854 views

2

We present novel techniques to utilize the high computational power of graphics processing units (GPUs) to significantly accelerate many of the traditional general purpose algorithms on CPUs. As graphics processors are primarily designed to perform fast display of geometric primitives, we abstract many of the essential database and data mining algorithms using basic graphics operations. Our algorithms use efficient data representations and utilize the inherent parallelism in the single instruction multiple data (SIMD) units and the vector processing functionalities of the GPUs to efficiently evaluate the boolean combinations of predicates, aggregates, and join queries. Graphics processors are optimized for processing data streams. We present deterministic algorithms to efficiently estimate quantiles and frequencies in large data streams. We utilize the high computational power and the memory bandwidth on a GPU to perform sorting on a GPU. The sorting algorithm is used as a main computational component for the construction of epsilon-approximate quantile and frequency summaries. We have applied our algorithm to data streams consisting of more than 100 million elements on a 3.4GHz PC with a NVIDIA 6800 Ultra GPU and achieved 2-4 times performance improvement over optimized CPU-based algorithms. Our recent research focuses on using GPUs for sorting very large databases composed of hundreds of gigabytes of data using low-end commodity PCs. Experimental studies on the SortBenchmark indicate that external sorting is highly memory-intensive. As the GPUs internally have a dedicated memory interface, we present an efficient hybrid sorting algorithm to perform the computation on both the GPU and CPU, in parallel. Experimental results on a low-end PC with a NVIDIA 7800 GTX graphics co-processor indicate higher performance than optimized CPU-based algorithms on a high-end PC with 3.6 GHz Dual Xeon processors.