Top algoritması - Cannons algorithm

İçinde bilgisayar Bilimi, Cannon algoritması bir dağıtılmış matris çarpımı için algoritma iki boyutlu için ağlar ilk olarak 1969'da Lynn Elliot Cannon.[1][2]

Özellikle içinde düzenlenmiş bilgisayarlar için uygundur. N × N örgü.[3] Cannon'un algoritması homojen 2D ızgaralarda iyi çalışsa da, onu heterojen 2D ızgaralara genişletmenin zor olduğu görülmüştür.[4]

Algoritmanın temel avantajı, depolama gereksinimlerinin sabit kalması ve işlemci sayısından bağımsız olmasıdır.[2]

Ölçeklenebilir Evrensel Matris Çarpma Algoritması (SUMMA)[5]daha az çalışma alanı gerektiren ve kare 2D ızgara ihtiyacının üstesinden gelen daha pratik bir algoritmadır. Tarafından kullanılır ScaLAPACK, PLAPACK, ve Elemental kütüphaneler.

Algoritmaya genel bakış

İkiyi çarparken n×n A ve B matrislerine ihtiyacımız var n×n işleme düğümleri p 2D bir ızgarada düzenlenmiştir. Başlangıçta pben, j sorumludurben, j ve Bben, j.

// PE (i, j) k: = (i + j) mod N; a: = a [i] [k]; b: = b [k] [j]; c [i] [j]: = 0; (l: = 0; l 

İşlemcilerin bilgi işlem için aynı verilere erişmemesi için her İşlemci Öğesi (PE) için her yinelemede k'yi seçmemiz gerekir. .

Bu nedenle, aynı satır / sütundaki işlemciler farklı dizinlerle toplamaya başlamalıdır. Eğer örneğin PE (0,0) hesaplar ilk adımda PE (0,1) seçer ilk. Seçimi k: = (i + j) mod n için PE (i, j) ilk adım için bu kısıtlamayı karşılar.

İlk adımda, giriş matrislerini önceki kurala göre işlemciler arasında dağıtıyoruz.

Sonraki yinelemelerde yeni bir k ': = (k + 1) mod n her işlemci için. Bu şekilde, her işlemci matrislerin farklı değerlerine erişmeye devam edecektir. Gerekli veriler daha sonra her zaman komşu işlemcilerdedir. A PE (i, j) o zaman ihtiyacı var itibaren PE (i, (j + 1) mod n) ve itibaren PE ((i + 1) mod n, j) sonraki adım için. Bunun anlamı şudur ki döngüsel olarak sola geçirilmelidir ve ayrıca döngüsel olarak yukarı doğru. Çarpımların sonuçları her zamanki gibi özetlenir. N adımdan sonra, her işlemci tüm bir kez ve toplamı böylece aranır .

Her işlemcinin ilk dağıtımından sonra, yalnızca bir sonraki adımın verilerinin depolanması gerekir. Bunlar önceki meblağın ara sonucudur, a ve bir . Bu, üç matrisin yalnızca işlemciler arasında eşit olarak dağıtıldıktan sonra bellekte depolanması gerektiği anlamına gelir.

Genelleme

Pratikte, matris elemanlarından çok daha az işlemciye sahibiz. Matris elemanlarını alt matrislerle değiştirebiliriz, böylece her işlemci daha fazla değeri işler. Skaler çarpma ve toplama, sıralı matris çarpımı ve toplamı haline gelir. Alt matrislerin genişliği ve yüksekliği .

Algoritmanın çalışma zamanı , nerede matrislerin ilk adımda ilk dağıtım zamanıdır, ara sonuçların hesaplanması ve ve sırasıyla bir bağlantı kurmak ve bayt iletimi için geçen süreyi ifade eder.

Algoritmanın bir dezavantajı, küçük mesaj boyutlarına sahip birçok bağlantı kurulumunun olmasıdır. Her mesajda daha fazla veri iletebilmek daha iyi olacaktır.

Ayrıca bakınız

Referanslar

  1. ^ Lynn Elliot Cannon, Kalman Filtre Algoritmasını uygulamak için bir hücresel bilgisayar, Teknik rapor, Ph.D. Tez, Montana Eyalet Üniversitesi, 14 Temmuz 1969.
  2. ^ a b Gupta, H .; Sadayappan, P .: Hiperküplerde İletişim Verimli Matris Çarpma, dbpubs.stanford.edu
  3. ^ 4.2 Dağıtılmış Bellek Makinesinde Matris Çarpımı, www.phy.ornl.gov
  4. ^ Jean-François Pineau, Heterojen ana-çalışan platformlarında iletişime duyarlı zamanlama, Doktora tezi, Ekim 2010.
  5. ^ Robert A. van de Geijn ve Jerrell Watts, SUMMA: ölçeklenebilir evrensel matris çarpım algoritması, Eşzamanlılık: Uygulama ve Deneyim. Cilt 9, Sayı 4, sayfalar 255–274, Nisan 1997.

Dış bağlantılar