| Abstract |
The multi-core trend in CPUs and general purpose graphics processing
units (GPUs) offers new opportunities for the database community.
The increase of cores at exponential rates is likely to affect
virtually every server and client in the coming decade, and presents
database management systems with a huge, compelling disruption that
will radically change how processing is done. This paper presents a
new parallel indexing data structure for answering queries that takes
full advantage of the increasing thread-level parallelism emerging in
multi-core architectures. In our approach, our Data Parallel
Bin-based Index Strategy (DP-BIS) first bins the base data, and then
partitions and stores the values in each bin as a separate, bin-based
data cluster. In answering a query, the procedures for examining the
bin numbers and the bin-based data clusters offer the maximum possible
level of concurrency; each record is evaluated by a single thread and
all threads are processed simultaneously in parallel.
We implement and demonstrate the effectiveness of DP-BIS
on two multi-core architectures: a multi-core CPU and a GPU. The
concurrency afforded by DP-BIS allows us to fully utilize the
thread-level parallelism provided by each architecture--for example,
our GPU-based DP-BIS implementation simultaneously evaluates over
12,000 records with an equivalent number of concurrently executing
threads. In comparing DP-BIS's performance across these architectures,
we show that the GPU-based DP-BIS implementation requires
significantly less computation time to answer a query than the
CPU-based implementation. We also demonstrate in our analysis that
DP-BIS provides better overall performance than the commonly utilized
CPU and GPU-based projection index. Finally, due to data encoding, we
show that DP-BIS accesses significantly smaller amounts of data than
index strategies that operate solely on a column's base data; this
smaller data footprint is critical for parallel processors that
possess limited memory resources (e.g. GPUs).
|
|---|
