R-tree is an important spatial data structure used in EDA as well as other fields. Although there has been a huge literature of parallel R-tree query, as far as we know, our work is the first successful one to parallelize R-tree query on the GPU. We also propose the first R-tree construction method on the GPU. Unlike the other parallel construction methods, our method does not depend on a partition algorithm and guarantees the same quality as the sequential construction. Experiments show that more than 30× speedup on R-tree query and more than 20× speedup on R-tree construction are achieved.
|Proceedings of the ASP-DAC Asia South Pacific Design Automation Conference
|17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012
|30/01/12 → 2/02/12
- Graphics processing unit
- Parallel processing