C / C++ Matris Çarpma Kodu ve Basit Hızlandırma Teknikleri

C / C++ Matris Çarpma Kodu ve Basit Hızlandırma Teknikleri

Bu gece paralel algoritmalar dersine çalışırken, kendimi birden matris çarpma makalelerinin içinde buldum. İleri derecede çalışmalarda Winograd ve Strassen yöntemleri önerilmekle beraber, burada bilinen tekniğin basit yollarla hızlandırılması üzerinde duracağım.

Öncelikle basit bir matris çarpma kodu verelim. Dikkat ederseniz buradaki kod özellikle yavaş çalışacak şekilde verilmiştir. J döngüsü en içeriye alınırsa kod çok daha hızlı çalışacaktır! Bu yazıdaki amacımız yerel belleğin daha efektif olarak nasıl kullanılabileceğini anlatmak.

Projeyi ve kodu, sayfanın en altında verilen bağlantıyı kullanarak indirebilirsiniz.

void f1(int *a, int *b, int *c)
{
    for (int i=0; i < n; ++i)
        for (int j=0; j < n; ++j)
            for (int k=0; k < n; ++k)
                c[i * n + j] += a[i * n + k] * b[k * n + j];
}

Şimdi ilginç bir iyileştirme yapalım. Burada uygulanan tekniğe, matristeki değişkenlerin yerelleştirilmesi deniyor. Böylece, matrisin ön belleğe alınan kısmı sürekli olarak değiştirilmiyor. Parçadaki tüm işlemler bittikten sonra diğer parçaya geçiliyor.

void f2(int *a, int *b, int *c)
{
    for (int ii=0; ii < n/8; ++ii)
        for (int jj=0; jj < n/8; ++jj)
            for (int kk=0; kk < n/8; ++kk)
                for (int i=8*ii; i < 8*(ii+1); ++i)
                    for (int j=8*jj; j < 8*(jj+1); ++j)
                        for (int k=8*kk; k < 8*(kk+1); ++k)
                            c[i * n + j] += a[i * n + k] *
                                            b[k * n + j];
}

Ne dersiniz, sizce işe yarayacak mı? Deneyin, görün! n=512'lik bir matris için yaklaşık 6 kat hızlanma olursa sakın şaşırmayın =] Gördüğünüz üzere, burada her bir matrisin 8x8x8 = 512'er tane int elemanını işledikten sonra diğer kısımlara geçiyoruz. Bu da büyük bir performans getirisi sağlıyor. Çünkü dizinin indisinin her artışında, ön bellekteki matris parçasını değiştirmiyoruz.

Bu kadarı bana yetmez diyen arkadaşlar, sözüm size. Azıcık da dilimizin güzelliklerini kullanalım, ne dersiniz? İşaretçilerle performansı iki kat daha hızlandırabiliriz! Kodu aşağıda.

void f3(int *a, int *b, int *c)
{
    for (int ii=0; ii < n/m; ++ii)
        for (int jj=0; jj < n/m; ++jj)
            for (int kk=0; kk < n/m; ++kk)
            {
                int *cc = &(c[ii*n * m + jj*m]);
                int *aa = &(a[ii*n * m + kk*m]);
                int *bb = &(b[kk*n * m + jj*m]);
                for (int i=0; i < m; ++i)
                {
                    for (int j=0; j < m; ++j)
                    {
                        for (int k=0; k < m; ++k, bb += n)
                            *cc += *aa++ * *bb;
                        aa -= m;
                        bb -= m*n;
                        ++cc;
                        ++bb;
                    }

                    cc -= m;
                    bb -= m;
                    aa += n;
                    cc += n;
        }
    }
}

10 kattan daha fazla hızlanma sağladık. Ama yine de yetersiz bulan arkadaşlar olabilir. Bu aşamayı kendimi çok zorlamadan aşmak istiyorum, kusuruma bakmayın. Basitçe OpenMP kütüphanesinden yararlanarak, sistemimizdeki tüm çekirdekleri kullanarak birkaç kat daha hızlanma sağlayabiliriz. f3 fonksiyonunun ilk satırına eklemeniz gereken kod aşağıda.

#pragma omp parallel for

Bu son eklemeyle beraber, benim masaüstü için (2 çekirdek) yaklaşık iki kat daha hızlandırabildim. Tüm fonksiyonların ortalama hızları aşağıda. Kolay gelsin.

f1  2658 ms
f2  432 ms
f3  231 ms
f4  121 ms

Proje olarak indirmek için tıklayınız!

Notlar: Matris Çarpımı, Hızlı Matris Çarpımı, referansların yerelliğini iyileştirmek, Matrix Multiplication, Fast Matrix Multiplication, improving the locality of the references


12 yıl 6 ay önce eklendi

Türkiye'nin Gölleri Basketbolun kuralları (kısaca) Türkiye'deki müzelerin isimleri Orman Haftası ile ilgili şiirleri Cin Çarpması Nedir ve Cin Nasıl Çıkarılır? BBC fikirlerini paylaşmak için 'darbe yanlıları'nı arıyor NGINX'te "502 Bad Gateway" hatası nasıl çözülür? PKK'ya karşı yıllara göre verilen şehit sayısı 2021 Miraç Kandili ne zaman Stereotip Nedir? Türksat 4A kanal frekans ayarları Âşık Edebiyatı Nazım Biçimleri Doğruluk ve Dürüstlük ile ilgili Atasözleri MySQL Dump/Restore, MysqlDump komutunu kullanarak veritabanını yedekleme Kurban Bayramında Kurban Edilecek Hayvanların Vasıfları Nelerdir? Maddelerin ayırt edici özellikleri Bilim adamlarından "yeni dünya" keşfi Yenilenebilir yakıta bir adım kaldı Süryaniler kimdir, nereden gelmişlerdir? C / C++ Matris Çarpma Kodu ve Basit Hızlandırma Teknikleri
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28