Ana sayfa Bilgisayar C ile Matris-Matris Çarpımı ve Indeks Farklılıkları

C ile Matris-Matris Çarpımı ve Indeks Farklılıkları

588
PAYLAŞ
C ile Matris-Matris Çarpımı ve Indeks Farklılıkları

Matris-Matris Çarpımı ve Indeks Farklılıklarının Etkisi

Merhaba sevgili keçi ailesi, bu yazımızda C ile Matris-Matris Çarpımı yaparken kullandığımız indeks farklılıklarının kodumuzun performansı üzerinde nasıl bir etki yapacağını araştıracağız.
Matris-Matris Çarpımı yapabilmek için kullanabileceğiniz 6 farklı indeksleme çeşidi mevcut bulunmaktadır. Bunlar;

  •  IJK indeksleme
  •  JIK indeksleme
  •  KIJ indeksleme
  •  IKJ indeksleme
  •  JKI indeksleme
  •  KJI indeksleme

1) IJK indeksleme;
 

IJK indeksi ile yapılacak Matris-Matris Çarpımı için kod-taslağı(pseudo-code) aşağıdaki gibidir;
/* ijk */
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
sum = 0.0;
for (k=0; k<n; k++)
sum += a[i][k] * b[k][j];
c[i][j] = sum;
}
}

Bu taslağı aşağıdaki resim ile kolayca ifade edebiliriz;

1-2-300x270

Resim.1: IJK indeksi ile Matris-Matris Çarpımı

Her bir iç döngüdeki ıskalama sayısı bu indeks için aşağıda görülebilir;
A = 0.25
B = 1
C = 0

2) JIK indeksleme;

JIK indeksi ile yapılacak Matris-Matris Çarpımı için kod-taslağı(pseudo-code) aşağıdaki gibidir;

/* ijk */
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
sum = 0.0;
for (k=0; k<n; k++)
sum += a[i][k] * b[k][j];
c[i][j] = sum;
}
}

Bu taslağı aşağıdaki resim ile kolayca ifade edebiliriz;

1-3

Resim.2: IJK  indeksi ile Matris-Matris Çarpımı

Her bir iç döngüdeki ıskalama sayısı bu indeks için aşağıda görülebilir;

A = 0.25
B = 1
C = 0

3) KIJ indeksleme;

KIJ indeksi ile yapılacak Matris-Matris Çarpımı için kod-taslağı(pseudo-code) aşağıdaki gibidir;

/* kij */
for (k=0; k<n; k++) {
for (i=0; i<n; i++) {
r = a[i][k];
for (j=0; j<n; j++)
c[i][j] += r * b[k][j];
}
}

Bu taslağı aşağıdaki resim ile kolayca ifade edebiliriz;

1-4

Resim.3: KIJ indeksi ile Matris-Matris Çarpımı

Her bir iç döngüdeki ıskalama sayısı bu indeks için aşağıda görülebilir;

A = 0
B = 0.25
C = 0.25

4) IKJ indeksleme;

IKJ indeksi ile yapılacak Matris-Matris Çarpımı için kod-taslağı(pseudo-code) aşağıdaki gibidir;

/* ikj */
for (i=0; i<n; i++) {
for (k=0; k<n; k++) {
r = a[i][k];
for (j=0; j<n; j++)
c[i][j] += r * b[k][j];
}}

Bu taslağı aşağıdaki resim ile kolayca ifade edebiliriz;

1-5

Resim.4: IKJ indeksi ile Matris-Matris Çarpımı

Her bir iç döngüdeki ıskalama sayısı bu indeks için aşağıda görülebilir;

A = 0
B = 0.25
C = 0.25

5) JKI indeksleme;

JKI indeksi ile yapılacak Matris-Matris Çarpımı için kod-taslağı(pseudo-code) aşağıdaki gibidir;

/* jki */
for (j=0; j<n; j++) {
for (k=0; k<n; k++) {
r = b[k][j];
for (i=0; i<n; i++)
c[i][j] += a[i][k] * r;
}}

Bu taslağı aşağıdaki resim ile kolayca ifade edebiliriz;

1-7

Resim.5: JKI indeksi ile Matris-Matris Çarpımı

Her bir iç döngüdeki ıskalama sayısı bu indeks için aşağıda görülebilir;

A = 1
B = 0
C = 1

6) KJI indeksleme;

KJI Iindeksi ile yapılacak Matris-Matris Çarpımı için kod-taslağı(pseudo-code) aşağıdaki gibidir;

/* kji */
for (k=0; k<n; k++) {
for (j=0; j<n; j++) {
r = b[k][j];
for (i=0; i<n; i++)
c[i][j] += a[i][k] * r;
}}

Bu taslağı aşağıdaki resim ile kolayca ifade edebiliriz;

1-7

Resim.6: KJI indeksi ile Matris-Matris Çarpımı

Her bir iç döngüdeki ıskalama sayısı bu indeks için aşağıda görülebilir;

A = 1
B = 0
C = 1

Şimdi incelediğimiz bu indeksleme yöntemlerinin kısa bir özetini sunalım;

ijk (& jik):
• 2 loads, 0 stores
• ıskalama/iter = 1.25

kij (& ikj):
• 2 loads, 1 store
• ıskalama/iter = 0.5

jki (& kji):
• 2 loads, 1 store
• ıskalama/iter = 2.0

Test Sonuçları

Test sistemimiz ile yaptığımız ölçümleri sizlerle paylaşıyoruz. Burada Wall Clock Time ( dakika cinsinden zaman ) vs Matris Boyutu (nxm) cinsinden bir karşılaştırma yaptık. İlgilenenler için kodumuzu Gentoo/Linux işletim sisteminde gcc ile derledik ve Intel i7 4790 işlemcisini kullandık.

matrix

Resim.7: Test Sonuçları

Matris boyutu büyüdükçe yanlış indeks seçiminin bizlere ne kadar pahalıya patladığına lütfen dikkat edin. Yüksek boyutlu bir Matris-Matris Çarpımı işlemi için ikj indeksleme yerine kji seçtiğimizi bir düşünelim, normalde yaklaşık 40 dakika sürmesi gereken bir işi yaklaşık 440 dakikada yapacaktık. Bunun ne kadar büyük bir kayıp olduğu sanırım aşikar. Sonuç olarak kij (& ikj) ikilisinden birini seçmek bizlere en iyi sonucu veriyor ve C programlama dili için bariz en iyi indeksleme yöntemi olduğunu kanıtlıyor. Peki bu durum neden böyle ? Bu sorunun cevabı için lütfen takipte kalın,

Keçi ile kalın !