Araştırma Makalesi
BibTex RIS Kaynak Göster

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

Yıl 2020, Cilt: 36 Sayı: 1, 119 - 127, 26.04.2020

Ahmet Duran Mehmet Tunçel Hayati Ünsal Özer

Öz

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.

Anahtar Kelimeler

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

Destekleyen Kurum

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

Proje Numarası

4006072019

Teşekkür

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

Kaynakça

  • [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.

Yıl 2020, Cilt: 36 Sayı: 1, 119 - 127, 26.04.2020

Ahmet Duran Mehmet Tunçel Hayati Ünsal Özer

Öz

Proje Numarası

4006072019

Kaynakça

  • [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.
Toplam 22 adet kaynakça vardır.

Ayrıntılar

Birincil Dil Türkçe
Bölüm Makaleler
Yazarlar

Ahmet Duran

Mehmet Tunçel Bu kişi benim

Hayati Ünsal Özer Bu kişi benim

Proje Numarası 4006072019
Yayımlanma Tarihi 26 Nisan 2020
Yayımlandığı Sayı Yıl 2020 Cilt: 36 Sayı: 1

Kaynak Göster

APA Duran, A., Tunçel, M., & Özer, H. Ü. (2020). GPU Programlama ile Yüksek Boyutlu Yoğun Matrislerle Kronecker Çarpım Hesaplaması. Erciyes Üniversitesi Fen Bilimleri Enstitüsü Fen Bilimleri Dergisi, 36(1), 119-127.
AMA Duran A, Tunçel M, Özer HÜ. GPU Programlama ile Yüksek Boyutlu Yoğun Matrislerle Kronecker Çarpım Hesaplaması. Erciyes Üniversitesi Fen Bilimleri Enstitüsü Fen Bilimleri Dergisi. Nisan 2020;36(1):119-127.
Chicago Duran, Ahmet, Mehmet Tunçel, ve Hayati Ünsal Özer. “GPU Programlama Ile Yüksek Boyutlu Yoğun Matrislerle Kronecker Çarpım Hesaplaması”. Erciyes Üniversitesi Fen Bilimleri Enstitüsü Fen Bilimleri Dergisi 36, sy. 1 (Nisan 2020): 119-27.
EndNote Duran A, Tunçel M, Özer HÜ (01 Nisan 2020) GPU Programlama ile Yüksek Boyutlu Yoğun Matrislerle Kronecker Çarpım Hesaplaması. Erciyes Üniversitesi Fen Bilimleri Enstitüsü Fen Bilimleri Dergisi 36 1 119–127.
IEEE A. Duran, M. Tunçel, ve H. Ü. Özer, “GPU Programlama ile Yüksek Boyutlu Yoğun Matrislerle Kronecker Çarpım Hesaplaması”, Erciyes Üniversitesi Fen Bilimleri Enstitüsü Fen Bilimleri Dergisi, c. 36, sy. 1, ss. 119–127, 2020.
ISNAD Duran, Ahmet vd. “GPU Programlama Ile Yüksek Boyutlu Yoğun Matrislerle Kronecker Çarpım Hesaplaması”. Erciyes Üniversitesi Fen Bilimleri Enstitüsü Fen Bilimleri Dergisi 36/1 (Nisan 2020), 119-127.
JAMA Duran A, Tunçel M, Özer HÜ. GPU Programlama ile Yüksek Boyutlu Yoğun Matrislerle Kronecker Çarpım Hesaplaması. Erciyes Üniversitesi Fen Bilimleri Enstitüsü Fen Bilimleri Dergisi. 2020;36:119–127.
MLA Duran, Ahmet vd. “GPU Programlama Ile Yüksek Boyutlu Yoğun Matrislerle Kronecker Çarpım Hesaplaması”. Erciyes Üniversitesi Fen Bilimleri Enstitüsü Fen Bilimleri Dergisi, c. 36, sy. 1, 2020, ss. 119-27.
Vancouver Duran A, Tunçel M, Özer HÜ. GPU Programlama ile Yüksek Boyutlu Yoğun Matrislerle Kronecker Çarpım Hesaplaması. Erciyes Üniversitesi Fen Bilimleri Enstitüsü Fen Bilimleri Dergisi. 2020;36(1):119-27.
 Kapak Resmi İndir

✯ Etik kurul izni gerektiren, tüm bilim dallarında yapılan araştırmalar için etik kurul onayı alınmış olmalı, bu onay makalede belirtilmeli ve belgelendirilmelidir.
✯ Etik kurul izni gerektiren araştırmalarda, izinle ilgili bilgilere (kurul adı, tarih ve sayı no) yöntem bölümünde, ayrıca makalenin ilk/son sayfalarından birinde; olgu sunumlarında, bilgilendirilmiş gönüllü olur/onam formunun imzalatıldığına dair bilgiye makalede yer verilmelidir.
✯ Dergi web sayfasında, makalelerde Araştırma ve Yayın Etiğine uyulduğuna dair ifadeye yer verilmelidir.
✯ Dergi web sayfasında, hakem, yazar ve editör için ayrı başlıklar altında etik kurallarla ilgili bilgi verilmelidir.
✯ Dergide ve/veya web sayfasında, ulusal ve uluslararası standartlara atıf yaparak, dergide ve/veya web sayfasında etik ilkeler ayrı başlık altında belirtilmelidir. Örneğin; dergilere gönderilen bilimsel yazılarda, ICMJE (International Committee of Medical Journal Editors) tavsiyeleri ile COPE (Committee on Publication Ethics)’un Editör ve Yazarlar için Uluslararası Standartları dikkate alınmalıdır.
✯ Kullanılan fikir ve sanat eserleri için telif hakları düzenlemelerine riayet edilmesi gerekmektedir.