Istituto di Scienza e Tecnologie dell'Informazione     
Orlando S., Francesco L., Claudio S., Jensen C. S. GPU-based computing of repeated range queries over moving objects. In: PDP 2014 - 22nd Euromicro International Conference on Parallel, Distributed and Network-Based Processing (Torino, Italy, 12-14 February 2014). Proceedings, pp. 640 - 647. IEEE, 2014.
In this paper we investigate the use of GPUs to solve a data-intensive problem that involves huge amounts of moving objects. The scenario which we focus on regards objects that continuously move in a 2D space, where a large percentage of them also issues range queries. The processing of these queries entails a large quantity of objects falling into the range queries to be returned. In order to solve this problem by maintaining a suitable throughput, we partition the time into ticks, and defer the parallel processing of all the objects events (location updates and range queries) occurring in a given tick to the next tick, thus slightly delaying the overall computation. We process in parallel all the events of each tick by adopting an hybrid approach, based on the combined use of CPU and GPU, and show the suitability of the method by discussing performance results. The exploitation of a GPU allow us to achieve a speedup of more than 20 on several datasets with respect to the best sequential algorithm solving the same problem. More importantly, we show that the adoption of new bitmap-based intermediate data structure we propose to avoid memory access contention entails a 10 speedup with respect to naive GPU based solutions.
URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6787342
DOI: 10.1109/PDP.2014.27
Subject GPU
Range query

Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional