This figure shows five different benchmarks, whose proximity queries are parallelized by using CPUs and GPUs
within our hybrid parallel framework. Different computations of these queries are automatically distributed by our LPbased
scheduler without any parameter tuning. Compared to using a hexa-core CPU with six CPU threads, our method
achieves one order of magnitude performance improvement by using one additional hexa-core CPU and four different
GPUs with the CPU.
This figure shows the throughput, frames per second,
of ours and prior scheduling algorithms for the cloth benchmark (94K Tri.), as we add more
computing resources. (1C = a hexa-core CPU, 1G =
GTX285, 2G = 1G+Tesla2075, 3G = 2G+GTX480, 4G =
3G+GTX580)
Abstract
We present a novel, Linear Programming (LP) based scheduling algorithm that exploits heterogeneous multi-core
architectures such as CPUs and GPUs to accelerate a wide variety of proximity queries. To represent complicated performance
relationships between heterogeneous architectures and different computations of proximity queries, we propose a simple,
yet accurate model that measures the expected running time of these computations. Based on this model, we formulate an
optimization problem that minimizes the largest time spent on computing resources, and propose a novel, iterative LP-based
scheduling algorithm. Since our method is general, we are able to apply our method into various proximity queries used in five
different applications that have different characteristics. Our method achieves an order of magnitude performance improvement
by using four different GPUs and two hexa-core CPUs over using a hexa-core CPU only. Unlike prior scheduling methods, our
method continually improves the performance, as we add more computing resources. Also, our method achieves much higher
performance improvement compared with prior methods as heterogeneity of computing resources is increased. Moreover, for
one of tested applications, our method achieves even higher performance than a prior parallel method optimized manually for
the application. We also show that our method provides results that are close (e.g., 75%) to the performance provided by a
conservative upper bound of the ideal throughput. These results demonstrate the efficiency and robustness of our algorithm that
have not been achieved by prior methods. In addition, we integrate one of our contributions with a work stealing method. Our
version of the work stealing method achieves 18% performance improvement on average over the original work stealing method.
This result shows wide applicability of our approach.
@article{DSKim13,
author = {Duksu Kim and Jinkyu Lee and Junghwan Lee and Insik Shin and John Kim and Sung-Eui Yoon},
title = {Scheduling in Heterogeneous Computing Environments for Proximity Queries},
journal ={IEEE Transactions on Visualization and Computer Graphics},
volume = {19},
number = {9},
issn = {1077-2626},
year = {2013},
pages = {1513-1525},
doi = {http://doi.ieeecomputersociety.org/10.1109/TVCG.2013.71},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
