Paralel Algoritma - Matris Çarpımı

Bir matris, sabit sayıda satır ve sütun halinde düzenlenmiş sayısal ve sayısal olmayan veriler kümesidir. Matris çarpımı, paralel hesaplamada önemli bir çarpma tasarımıdır. Burada, matris çarpımının mesh ve hypercube gibi çeşitli iletişim ağlarında uygulanmasını tartışacağız. Mesh ve hypercube daha yüksek ağ bağlantısına sahiptir, bu nedenle halka ağ gibi diğer ağlardan daha hızlı algoritmaya izin verirler.

Mesh Ağı

Bir dizi düğümün p-boyutlu bir ızgara oluşturduğu bir topolojiye mesh topolojisi denir. Burada, tüm kenarlar ızgara eksenine paraleldir ve tüm bitişik düğümler kendi aralarında iletişim kurabilir.

Toplam düğüm sayısı = (satırdaki düğüm sayısı) × (sütundaki düğüm sayısı)

Bir örgü ağ aşağıdaki faktörler kullanılarak değerlendirilebilir -

Diameter
İkiye bölme genişliği

Diameter - Bir örgü ağda, en uzun distanceiki düğüm arasında çapıdır. Bir p-boyutlu ağ ağıkP düğümlerin çapı p(k–1).

Bisection width - İkiye bölme genişliği, ağ örgüsünü ikiye bölmek için bir ağdan kaldırılması gereken minimum kenar sayısıdır.

Mesh Ağı Kullanarak Matris Çarpımı

Çevreleyen bağlantıları olan bir 2D örgü ağ SIMD modelini düşündük. Belirli bir sürede n ² işlemci kullanarak iki n × n diziyi çarpmak için bir algoritma tasarlayacağız .

A ve B matrisleri sırasıyla a _ij ve b _ij öğelerine sahiptir. PE _ij işleme öğesi , bir _ij ve b _ij'yi temsil eder . A ve B matrislerini, her işlemcinin çarpması gereken bir çift elemanı olacak şekilde düzenleyin. A matrisinin elemanları sol yönde hareket edecek ve B matrisinin elemanları yukarı yönde hareket edecektir. A ve B matrisindeki elemanların pozisyonundaki bu değişiklikler, her bir işleme elemanını, PE'yi, çarpılacak yeni bir değer çifti sunar.

Algoritmadaki Adımlar

İki matrisi kademelendirin.
Tüm ürünleri hesapla, a _ik × b _kj
2. adım tamamlandığında toplamları hesaplayın.

Algoritma

Procedure MatrixMulti

Begin
   for k = 1 to n-1
	
   for all Pij; where i and j ranges from 1 to n
      ifi is greater than k then
         rotate a in left direction
      end if
		
   if j is greater than k then
      rotate b in the upward direction
   end if
	
   for all Pij ; where i and j lies between 1 and n
      compute the product of a and b and store it in c
   for k= 1 to n-1 step 1
   for all Pi;j where i and j ranges from 1 to n
      rotate a in left direction
      rotate b in the upward direction
      c=c+aXb
End

Hypercube Ağı

Bir hiperküp, kenarların kendi aralarında dik olduğu ve aynı uzunlukta olduğu n boyutlu bir yapıdır. N boyutlu bir hiperküp, n-küp veya n-boyutlu küp olarak da bilinir.

2 ^k düğümlü Hypercube'ün özellikleri

Çap = k
İkiye bölme genişliği = 2 ^{k – 1}
Kenar sayısı = k

Hypercube Network kullanarak Matris Çarpma

Hypercube ağlarının genel özellikleri -

İzin Vermek N = 2^mtoplam işlemci sayısı. İşlemciler P _0, P ₁ … ..P _{N-1 olsun} .
İ ve i ^b iki tam sayı olsun, 0 <i, i ^b <N-1 ve ikili gösterimi sadece b, 0 <b <k – 1 konumunda farklı olsun.
İki n × n matrisi, A matrisini ve B matrisini ele alalım.
Step 1- Matris A ve matris B'nin öğeleri, i, j, k konumundaki işlemcinin a _ji ve b _ik'ye sahip olacağı şekilde n ³ işlemciye atanır .
Step 2 - Pozisyondaki (i, j, k) tüm işlemciler ürünü hesaplar

C (i, j, k) = A (i, j, k) × B (i, j, k)
Step 3 - 0 ≤ i ≤ n-1 için C (0, j, k) = ΣC (i, j, k) toplamı, burada 0 ≤ j, k <n – 1.

Blok Matrisi

Blok Matrisi veya bölümlenmiş matris, her öğenin kendisinin ayrı bir matrisi temsil ettiği bir matristir. Bu ayrı bölümler olarak bilinirblock veya sub-matrix.