Ana sayfa Bilgisayar Matris-Matris Çarpımında Cannon Algoritması (MPI ile)

Matris-Matris Çarpımında Cannon Algoritması (MPI ile)

240
PAYLAŞ
Matris-Matris Çarpımında Cannon Algoritması (MPI ile)

Cannon Algoritması Nedir ?

Cannon Algoritması, Lynn Elliot Cannon tarafından 1969 yılında açıklanan ve iki boyutlu kafeslerde (mesh) matris çarpımı için kullanılan dağıtılmış bir Matris-Matris Çarpımı algoritmasıdır.

Cannon Algoritması sayesinde herhangi bir zamanda, her bir işlemci  farklı A (i, k) ve B (k, j) ikilileri kullanır ve böylece hiçbir işlemci, hiç bir zaman, herhangi bir matrisin birden fazla bloğunu tutamaz.

C(i,j) = toplam(A(i,k)B(k,j)) olarak tanımlanmıştır.

Cannon Algoritması anahtar fikri, A(i, k) ve B (k, j) bloklarını uygun bir şekilde kaydırarak, her seferde sadece bir blok için hesaplama yapmaktır.

Artılar ve Eksiler

  • Çok basit (sistolik dizilerden))
  • A ve B matrisleri için bir data dağılımı ile başlar
  • Homojen 2D gridlerde iyi çalışır fakat heterojen 2D gridlere uygulanması problemlidir.

amaç sadece komşudan komşuya iletişime sahip olmaktır.

  • A dairesel bir şekilde yatay olarak, A'nın diagonalleri her zaman işlemcilerin ilk sutünunda olacak şekilde kaydırılır.
  • B dairesel bir şekilde dikey olarak, B'nın diagonalleri her zaman işlemcilerin ilk satırında olacak şekilde kaydırılır.
  • Bu işleme preskewing adı verilir.

Cannon Algoritması Adımları

Adım 1: A ve B'nin hizalaması

  • A(i,j)'nin sola doğru dairesel bir şekilde kaydırılması.
  • B(i,j)'nin yukarı doğru dairesel bir şekilde kaydırılması.

1

Adım 2: Lokal Matris-Matris Çarpımı

C(i,j) = C(i,j) + A(i,(i+j)) + B((i+j),j)

Adım 3: A'nın her bloğu sola bir sola kayar ve B'nin her bloğu bir adım yukarı taşınır.

3
sonrasında da lokal matris-matris çarpımı yapılır.

Adım 4: Adım 3 sqrt(p-1) kere tekrar edilir.

MPI Kodu