{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T11:26:49Z","timestamp":1761823609058,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,7,1]],"date-time":"2013-07-01T00:00:00Z","timestamp":1372636800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001868","name":"National Science Council Taiwan","doi-asserted-by":"publisher","award":["101-2115-M-007-004-MY2"],"award-info":[{"award-number":["101-2115-M-007-004-MY2"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005057","name":"National Tsing Hua University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005057","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>Box intersection checking is a common task used in many large-scale simulations. Traditional methods cannot provide fast box intersection checking with large-scale datasets. This article presents a parallel algorithm to perform Pairwise Box Intersection checking on Graphics processing units (PBIG). The PBIG algorithm consists of three phases: planning, mapping and checking. The planning phase partitions the space into small cells, the sizes of which are determined to optimize performance. The mapping phase maps the boxes into the cells. The checking phase examines the box intersections in the same cell. Several performance optimizations, including load-balancing, output data compression\/encoding, and pipelined execution, are presented for the PBIG algorithm. The experimental results show that the PBIG algorithm can process large-scale datasets and outperforms three well-performing algorithms.<\/jats:p>","DOI":"10.1145\/2499913.2499918","type":"journal-article","created":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T15:14:00Z","timestamp":1375370040000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Optimizing Pairwise Box Intersection Checking on GPUs for Large-Scale Simulations"],"prefix":"10.1145","volume":"23","author":[{"given":"Shih-Hsiang","family":"Lo","sequence":"first","affiliation":[{"name":"National Tsing Hua University"}]},{"given":"Che-Rung","family":"Lee","sequence":"additional","affiliation":[{"name":"National Tsing Hua University"}]},{"given":"I-Hsin","family":"Chung","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center"}]},{"given":"Yeh-Ching","family":"Chung","sequence":"additional","affiliation":[{"name":"National Tsing Hua University"}]}],"member":"320","published-online":{"date-parts":[[2013,7]]},"reference":[{"volume-title":"Proceedings of the IEEE Virtual Reality International Conference. IEEE","author":"Avril Q.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.04.008"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675628"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ANSS.2005.23"},{"key":"e_1_2_1_6_1","unstructured":"BULLET. 2011. Bullet Physics Library. (2011). http:\/\/bulletphysics.org\/wordpress\/.  BULLET. 2011. Bullet Physics Library. (2011). http:\/\/bulletphysics.org\/wordpress\/."},{"key":"e_1_2_1_7_1","unstructured":"CGAL. 2011. Computational geometry algorithms library. (2011). http:\/\/www.cgal.org.  CGAL. 2011. Computational geometry algorithms library. (2011). http:\/\/www.cgal.org."},{"key":"e_1_2_1_8_1","unstructured":"Chow A. L. 1980. Parallel algorithms for geometric problems. Ph.D. dissertation University of Illinois at Urbana-Champaign.   Chow A. L. 1980. Parallel algorithms for geometric problems. Ph.D. dissertation University of Illinois at Urbana-Champaign."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/199404.199437"},{"key":"e_1_2_1_10_1","unstructured":"CUDA. 2011. CUDA Programming Guide 4.0 NVIDIA. (2011). http:\/\/developer.nvidia.com\/cuda-downloads.  CUDA. 2011. CUDA Programming Guide 4.0 NVIDIA. (2011). http:\/\/developer.nvidia.com\/cuda-downloads."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207168308803364"},{"key":"e_1_2_1_12_1","unstructured":"EVE Online. 2003. EVE online game. (2003). http:\/\/www.eveonline.com\/.  EVE Online. 2003. EVE online game. (2003). http:\/\/www.eveonline.com\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1177\/154851290700400204"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.5009341"},{"volume-title":"GPU Gems 3","author":"Harada T.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","unstructured":"Harris M. Shubhabrata S. and Owens J. D. 2007. Parallel prefix sum (scan) with CUDA. In GPU Gems 3 Addison-Wesley Boston MA 851--876.  Harris M. Shubhabrata S. and Owens J. D. 2007. Parallel prefix sum (scan) with CUDA. In GPU Gems 3 Addison-Wesley Boston MA 851--876."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CIT.2010.206"},{"key":"e_1_2_1_18_1","unstructured":"Kettner L. Meyer A. and Zomorodian A. 2011. Intersecting sequences of dD iso-oriented boxes. http:\/\/www.cgal.org.  Kettner L. Meyer A. and Zomorodian A. 2011. Intersecting sequences of dD iso-oriented boxes. http:\/\/www.cgal.org."},{"key":"e_1_2_1_19_1","unstructured":"Lefohn A. Kniss J. and Owens J. 2005. Implementing efficient parallel data structures on GPUs. In GPU Gems 2 Addison-Wesley Boston MA 521--545.  Lefohn A. Kniss J. and Owens J. 2005. Implementing efficient parallel data structures on GPUs. In GPU Gems 2 Addison-Wesley Boston MA 521--545."},{"volume-title":"GPU Gems 3","author":"Le Grand S.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/DS-RT.2009.34"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/DS-RT.2011.34"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1866158.1866180"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGrid.2011.13"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626411000187"},{"volume":"1","volume-title":"IMA Conference on Mathematics of Surfaces","author":"Ming C. L.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90211-D"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921598.1921601"},{"key":"e_1_2_1_29_1","unstructured":"PBIG. 2013. Implementation of pairwise box intersection checking on graphics processing units. (2013). http:\/\/code.google.com\/p\/pbig\/.  PBIG. 2013. Implementation of pairwise box intersection checking on graphics processing units. (2013). http:\/\/code.google.com\/p\/pbig\/."},{"volume-title":"Proceedings of the Distributed Simulation Symposium. 13--26","author":"Petty M. D.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpat.2003.10.004"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044322.1044324"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.70715"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01933636"},{"volume-title":"Proceedings of the 4th IEEE International Workshop on Distributed Simulation and Real-Time Applications. IEEE","author":"Tan G.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90016-5"},{"volume-title":"Proceedings of the 15th Distributed Iinteractive Simulation Workshop. IEEE","author":"Van Hook D. J.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195902000785"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499913.2499918","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2499913.2499918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:00Z","timestamp":1750232040000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499913.2499918"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["10.1145\/2499913.2499918"],"URL":"https:\/\/doi.org\/10.1145\/2499913.2499918","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"type":"print","value":"1049-3301"},{"type":"electronic","value":"1558-1195"}],"subject":[],"published":{"date-parts":[[2013,7]]},"assertion":[{"value":"2012-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}