GPU Programlama ile Yüksek Boyutlu Yoğun Matrislerle Kronecker Çarpım Hesaplaması

Year 2020, Volume: 36 Issue: 1, 119 - 127, 26.04.2020

Ahmet Duran Mehmet Tunçel Hayati Ünsal Özer

Abstract

Sayısal
lineer cebir içinde yer alan ve birçok bilimsel hesaplama yöntemi içinde
kullanılan önemli matris işlemlerinden biri Kronecker (tensör) çarpımıdır. Bu
tip çarpımda işleme giren yoğun matris boyutu arttıkça hafıza ve zaman maliyeti
çözülmesi gereken önemli bir problem olarak karşımıza çıkmaktadır. Bu çalışmamızda
GPU üzerinde paralel programlama uygulaması yaparak seri programlamada
karşılaşılan zaman maliyetini azaltmaya çalışırız. Bunun için GPU
paralelleştirme algoritması tasarlarız. Rasgele sayı üreten fonksiyon ile
değerleri ondalık sayılar olan gerekli büyük yoğun (dense) matrisler üretiriz
ve CUDA iş parçacıklarıyla uygulama yaparız. CPU ile GPU paralel programlama
uygulamasını karşılaştırırız. GPU programlama teknolojisinin bu uygulama için
avantaj ve sınırlamalarını tartışırız.

Keywords

Kronecker Çarpımı, GPU Programlama, Paralel Programlama, Sayısal Lineer Cebir, Yoğun Matris İşlemleri

Supporting Institution

Ulusal Yüksek Başarımlı Hesaplama Merkezi (UHeM)

Project Number

4006072019

Thanks

Bu çalışmada kullanılan hesaplama kaynakları Ulusal Yüksek Başarımlı Hesaplama Merkezi (UHeM), 4006072019 numaralı desteğiyle sağlanmıştır.

References

• [1] H.V. Henderson, F. Pukelsheim, S.R. Searl, “On the history of the Kronecker product”, Linear Multilinear Algebra, Taylor&Francis, 14, 113-120, 1983.
• [2] J. Liu, E.Z. Psarakis, Y. Feng, I. Stamos, “A Kronecker Product Model for Repeated Pattern Detection on 2D Urban Images”, Transactions on Pattern Analysis and Machine Intelligence, IEEE, 2018.
• [3] Y. Shen, T. Xiao, H. Li, S. Yi, X. Wang, “End-to-End Deep Kronecker-Product Matching for Person Re-Identification”, The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), ss. 6886-6895, 2018.
• [4] R. Kumar, B. Bhaduri, “Optical image encryption usink Kronecker product and hybrid phase masks”, Optics & Laser Technology, Elsevier 95, 51-55, 2017.
• [5] P. Maan, H. Singh, A.C. Kumar, “Optical Asymmetric Cryptosystem Based on Kronecker Product, Hybrid Phase Mask and Optical Vortex Phase Masks in the Phase Truncated Hybrid Transform Domain”, 3D Reseach, Springer, 10:18, 2019.
• [6] M. Syed Ali, J. Yogambiagi, “Synchonization of complex dynamical networks with hybrid coupling delays on time scales by handling multitude Kronecker product terms”, Applied Mathematics and Computation, Elsevier, Vol. 291, ss. 244-258, 2016.
• [7] S. Moreno, J. Neville, S. Kirshner, “Tied Kronecker Product Graph Models to Capture Variance in Network Populations”, Transaction on Knowledge Discovery from Data (TKDD), ACM, Vol. 12, Is. 3, No. 35, 2018.
• [8] M. Boussé, G. Goovaerts, N. Vervliet, O. Debals, S. Van Huffel, L. De Lathauwer, “Irregular hearthbeat classification using Kronecker Product Equations”, 39th Annual Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), ss. 438-441, Seogwipo, South Korea, 2017.
• [9] I. Roth, A. Flinth, R. Kueng, J. Eisert, G. Wunder, “Hierarchical restricted isometry property for Kronecker product measurement” , 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton) IEEE, Moticello, IL, USA, 2018.
• [10] M.E. Hochstanbasch, K. Meerbergen, E. Mengi, B. Plestenjak, “Subspace Methods for 3-Parameter Eigenvalue Problems”, arXiv:1802.07386 [math.NA], 2018, https://arxiv.org/abs/1802.07386 (E. T. 27.03.2019)
• [11] A. Sharma, P. Suryanarayana, “On real-space Density Functional Theory for non-orthogonal crystal systems: Kronecker product formulation of the kinetic energy operatör”, Chemical Physics Letters, Elsevier, Vol. 700, ss. 156-162, 2018.
• [12] G. Montúfar, J. Morton, “Dimensions of Marginals of Kronecker Product Models”, Journal on Applied Algebra and Geometry, SIAM, Vol. 1, ss. 126-151, 2017.
• [13] C. Van Loan, “The ubiquitous Kronecker product”, Journal of Computational and Applied Mathematics, Elsevier, 123: 85-100, 2000.
• [14] C. Van Loan, C.F. Pitsianis, “Approximation with Kronecker Product”, In: Moonen M.S., Golub G.H., De Moor B.L.R., (eds), Linear Algebra for Large Scale and real-Time Applications. NATO ASI Series, Springer, vol 232: 293-314, 1993.
• [15] A. Duran, H.Ü. Özer, M. Tunçel, “Yüksek Boyutlu Kronecker Çarpımı için İş Parçacığı Tabanlı Paralel Programlama Uygulaması”, 2. Uluslararası İstatistik, Matematik ve Analitik Yöntemler Kongresi, İstanbul, 2019
• [16] UHeM, Ulusal Yüksek Başarımlı Hesaplama Merkezi, http://www.uhem.itu.edu.tr/
• [17] N. M. Zarges, “Evaluation of On-Node GPU Interconnects for Training Deep Neural Networks”, B.S. Thesis, Technical University of Munich, 2019, https://mediatum.ub.tum.de/doc/1471320/1471320.pdf
• [18] NVIDIA TESLA K-Series, Datasheet, Ekim 2013 https://computing.llnl.gov/tutorials/linux_clusters/gpu/Tesla-K10K40-datasheet.pdf
• [19] A. Duran, S. Piskin, M. Tuncel, “Evaluating the maturity of OpenFOAM simulations on GPGPU for bio-fluid applications”, Proceedings of the Emerging Technology (EMiT) Conference, ss 11-14, Barcelona Supercomputing Center, Spain, 2-3 June 2016
• [20] F. Li, Y. Ye, Z. Tian, X. Zhang. “CPU versus GPU: which can perform matrix computation faster—performance comparison for basic linear algebra subprograms”. Neural Computing and Applications, 1-13, 2018.
• [21] T. H. Cormen, C. E. Leisorson, R. L. Rivest, C. Stein, Introduction to Algorithms, The MIT Press, London, England, 2009.
• [22] L. N. Trefethen, D. Bau, Numerical Linear Algebra, SIAM, Philadelphia, USA, 1997.