Using shared memory as a cache in cellular automata water flow simulations on GPUs

• Autorzy: Topa P. , Młocek P.
• Języki publikacji: EN

Abstrakty

EN

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. With this paper, we will 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.

Słowa kluczowe

EN

cellular automata; GPU computation; modelling physical phenomena

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2013
• Tom: Vol. 14 (3)
• Strony: 385--401
• Opis fizyczny: Bibliogr. 25 poz., rys., wykr., tab.

Twórcy

autor

Topa P.

• AGH University of Science and Technology, Department of Computer Science, Krakow, Poland
• Institute of Geological Sciences, Polish Academy of Sciences, Research Centre in Krakow, Krakow, Poland

autor

Młocek P.

• AGH University of Science and Technology, Department of Computer Science, Krakow, Poland

Bibliografia

• [1] Wolfram S.:A New Kind of Science. Wolfram Media, Inc. 2002.
• [2] Chopard B., Droz, M.:Cellular Automata Modeling of Physical Systems.Cambridge University Press, 1998.
• [3] Owens J.D., Houston M., Luebke D., Green S., Stone J.E., Phillips J.C.:GPUcomputing.In Proceedings of the IEEE, vol. 96(5), 2008, pp. 879–899.
• [4] GPU Computing Gems Jade Edition. Applications of GPU Computing Series, editor-in-chief Wen-mei W. Hwu, Elsevier, 2011.
• [5] 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.
• [6] Marks M., Jantura J., Niewiadomska-Szynkiewicz E., Strzelczyk P., Gd K.: Het- erogenous GPU&CPU cluster for high performance computing in cryptography, Computer Science, vol. 13(2):63–79, 2012.
• [7] CUDA Zone http://www.nvidia.com/object/cuda_home_new.html
• [8] Khronos Group http://www.khronos.org/opencl/
• [9] 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.
• [10] Gobron S., Finck D., Even Ph., Kerautret B.: Merging Cellular Automata for Simulating Surface Effects, In Cellular Automata, Yacoubi S., Chopard B., Bandini S. eds., Lecture Notes in Computer Science, vol. 4173, 2006, pp. 94–103.
• [11] 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):67–81, 2011.
• [12] Gobron S., Devillard F., Heit, B.: Retina Simulation using Cellular Automata and GPU Programming, The Machine Vision and Applications Journal, Springer Berlin/Heidelberg, 18(6):331–34, 2007.
• [13] Bilotta G., Rustico E., Herault A., Vicari A., Russo G., Del Negro C., Gallo G., Porting and optimizing MAGFLOW on CUDA. Annals of Geophysics, 54(5):580–591, 2011.
• [14] Vicari A., Herault 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., 22(10):1465–1471, 2007.
• [15] Rustico E., Bilotta G., Hrault A., Del Negro C., Gallo G. Scalable multi-GPU implementation of the MAGFLOW simulator. Annals Of Geophysics, 54(5):592–599, 2011.
• [16] 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, 182(3):628–640, 2011.
• [17] Quesada-Barriuso P., Heras D.B., Arguello, F.: Efficient GPU Asynchronous Implementation of a Watershed Algorithm Based on Cellular Automata: In Parallel and Distributed Processing with Applications (ISPA), 2012 IEEE 10th International Symposium on, 2012, pp. 79–86.
• [18] 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.
• [19] 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.
• [20] Topa P., Mocek P.: GPGPU implementation of Cellular Automata model of water flow. In Parallel Processing and Applied Mathematics : 9th international conference, PPAM 2011 ,Torun, 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.
• [21] Di Gregorio S., Serra R.: An empirical method for modelling and simulating some complex macroscopic phenomena by cellular automata. Future Generation Computer Systems, 16(2–3):259–271, 1999.
• [22] Topa P.: River Flows Modelled by Cellular Automata. In Proceedings of 1st SGI Users Conference, Cracow, Poland, ACC Cyfronet UMM, 2000, pp. 384–391
• [23] 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.
• [24] 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.
• [25] Topa P., Dzwinel W., Yuen D.: A multiscale cellular automata model for simulating complex transportation systems, International Journal of Modern Physics C, 17(10):1–23, 2006.