Using shared memory as a cache in high performance cellular automata water flow simulations
DOI:
https://doi.org/10.7494/csci.2013.14.3.385Keywords:
cellular automata, gpu computation, modelling physical phenomenaAbstract
Graphics processors (GPU -- Graphic Processor Units) recently have gained a lot of interest as an efficient platform for general-purpose computation. Cellular Automata approach which is inherently parallel gives the opportunity to implement high performance simulations. This paper presents how shared memory in GPU can be used to improve performance for Cellular Automata models. In our previous works, we proposed algorithms for Cellular Automata model that use only a GPU global memory. Using a profiling tool, we found bottlenecks in our approach. We introduce modifications that takes an advantage of fast shared memory. The modified algorithm is presented in details, and the results of profiling and performance test are demonstrated. Our unique achievement is comparing the efficiency of the same algorithm working with a global and shared memory.Downloads
References
Wolfram S.: A New Kind of Science, Wolfram Media, Inc. 2002
Chopard B., Droz, M.: Cellular Automata Modeling of Physical Systems, Cambridge University Press, 1998
Owens J. D., Houston M., Luebke D., Green S., Stone J. E., Phillips J. C.: GPU computing. [in:] Proceedings of the IEEE, vol. 96(5), 2008, pp. 879–899,
GPU Computing Gems Jade Edition, Applications of GPU Computing Series, editor-in-chief Wen-mei W. Hwu, Elsevier, 2011
Kurdziel M., Boryczko K.: Dense affinity propagation on clusters of GPUs, [in:] Parallel Processing and Applied Mathematics : 9th international conference, PPAM 2011 : Toruń, Poland, September 11–14, 2011 : revised selected papers, Pt. 1 / eds. Roman Wyrzykowski, [et al.]. Lecture Notes in Computer Science, Springer-Verlag, vol. 7203, 2012, pp. 599–608
Marks M., Jantura J., Niewiadomska-Szynkiewicz E., Strzelczyk P., Góźdż K.: Heterogenous GPU&CPU cluster for high performance computing in cryptography, Computer Science, vol. 13(2), 2012, pp. 63-79
CUDA Zone url{http://www.nvidia.com/object/cuda_home_new.html}
Khronos Group url{http://www.khronos.org/opencl/}
Rybacki S., Himmelspach J., Uhrmacher A.M.: Experiments with Single Core, Multi-core, and GPU Based Computation of Cellular Automata, [in:] Advances in System Simulation, 2009. SIMUL'09. First International Conference on, 2009, pp.62-67
Gobron S., Finck D., Even Ph., Kerautret B.: Merging Cellular Automata for Simulating Surface Effects, [in:] Cellular Automata (eds. Yacoubi, S., Chopard, B., Bandini, S.), Lecture Notes in Computer Science, vol.4173, 2006, pp. 94-103
Gobron S., Coltekin A., Bonafos H., Thalmann, D.: GPGPU Computation and Visualization of Three-dimensional Cellular Automata, The Visual Computer, Springer Berlin/Heidelberg, vol.27(1), 2011, pp.67-81
Gobron S., Devillard F., Heit, B.: Retina Simulation using Cellular Automata and GPU Programming, The Machine Vision and Applications Journal, Springer Berlin/Heidelberg, vol.18(6), 2007, pp. 331-34
Bilotta G., Rustico E., Hérault A., Vicari A., Russo G., Del Negro C., Gallo G., Porting and optimizing MAGFLOW on CUDA. Annals Of Geophysics, vol. 54(5), 2011 pp. 580-591
Vicari A., Hérault A., Del Negro C., Coltelli M., Marsella M., Proietti C. Modeling of the 2001 lava flow at Etna volcano by a Celluar Automata approach, Environ. Modell. Softw., vol.22(10), 2007, pp. 1465-1471
Rustico E., Bilotta G., Hérault A., Del Negro C., Gallo G. Scalable multi-GPU implementation of the MAGFLOW simulator. Annals Of Geophysics, vol. 54(5). 2011, pp. 592-599
Ferrando N., Gosalvez M.A., Cerda J., Gadea R., Sato K.: Octree-based, GPU implementation of a continuous cellular automaton for the simulation of complex, evolving surfaces, Computer Physics Communications, vol. 182(3), 2011, pp.628-640
Quesada-Barriuso P., Heras D.B., Arguello, F., Efficient GPU Asynchronous Implementation of a Watershed Algorithm Based on Cellular Automata, Parallel and Distributed Processing with Applications (ISPA), 2012 IEEE 10th International Symposium on, 2012, pp.79-86
Caux J., Siregar P., Hill D.: Accelerating 3D Cellular Automata Computation with GP-GPU in the Context of Integrative Biology, [in:] Cellular Automata - Innovative Modelling for Science and Engineering, Alejandro Salcido (Ed.), InTech, 2011, ISBN: 978-953-307-172-5
Miao Q., Lv Yisheng, Zhu, F., A cellular automata based evacuation model on GPU platform, [in:] Intelligent Transportation Systems (ITSC), 2012 15th International IEEE Conference on, 2012 pp.764-768
Topa P., Młocek P.: GPGPU implementation of Cellular Automata model of water flow, [in:] Parallel Processing and Applied Mathematics : 9th international conference, PPAM 2011 : Toruń, Poland, September 11–14, 2011 : revised selected papers, Pt. 1 / eds. Roman Wyrzykowski, [et al.]. Lecture Notes in Computer Science, Springer-Verlag, vol.7203, 2012, pp. 630–639
Di Gregorio S., Serra R.: An empirical method for modelling and simulating some complex macroscopic phenomena by cellular automata, Future Generation Computer Systems, vol. 16(2-3),1999, pp. 259-271
Topa P.: River Flows Modelled by Cellular Automata [in:] Proceedings of 1st SGI Users Conference, Cracow, Poland, ACC Cyfronet UMM, 2000, pp. 384-391
Topa P.: A Distributed Cellular Automata Simulation on Cluster of PCs, [in:] Proceedings of the International Conference on Computational Science-Part I (ICCS '02), eds. Peter M. A. Sloot, [et al.], Lecture Notes in Computer Science, vol.2329, Springer Berlin/Heidelberg, 2002, pp. 97-106
Topa P., Paszkowski M.: Anastomosing Transportation Networks, [in:] Proceedings of 4th International Conference on Parallel Processing and Applied Mathematics 2001, eds. Wyrzykowski R., [et al.], Lecture Notes in Computer Sciences vol. 2328, , Springer-Verlag Berlin/Heidelberg, 2002, pp.904-911
Topa P., Dzwinel W., Yuen D.: A multiscale cellular automata model for simulating complex transportation systems, International Journal of Modern Physics C, vol. 17(10), 2006, pp. 1-23
Downloads
Published
How to Cite
Issue
Section
