Hepsi bir arada (paralel desen) - All-to-all (parallel pattern) - Wikipedia

Dört işlemci ve m = 1 ile hepsi bir arada iletişim için bir görselleştirme.

İçinde paralel hesaplama, hepsi bir arada (Ayrıca şöyle bilinir dizin işlemi veya toplam değişim) bir toplu operasyon, burada her işlemcinin diğer işlemcilere ayrı bir mesaj gönderdiği.

Başlangıçta her işlemci p her biri m boyutunda mesajlar ve amaç, işlemci j'nin i'inci mesajını işlemci i'nin j-inci mesajı ile değiş tokuş etmektir.

İletişim turlarının sayısı ve genel iletişim hacmi, hepsi bir arada algoritmanın kalitesini değerlendirmek için ölçülerdir. Bu makale boyunca tek bağlantı noktalı tam çift yönlü bir makineyi ele alıyoruz. Böyle bir makinede, hepsi bir arada bir algoritma en azından ${ displaystyle lceil log _ {2} n rceil}$ iletişim turları. Ayrıca minimum ${ displaystyle sol lceil { frac {m (n-1)} {k}} sağ rceil}$ veri birimleri aktarılır. Her iki önlem için de optimum eşzamanlı olarak elde edilemez.^[1]

Bağlı olarak ağ topolojisi (tamamen bağlı, hiperküp, yüzük ), farklı hepsi bir arada algoritmalar gereklidir.

Topolojiye dayalı hepsi bir arada algoritmalar

Bir halka topolojisinde bir all-to-all algoritmasının görselleştirilmesi.

Bir ağ topolojisinde hepsi bir arada algoritmanın görselleştirilmesi.

Tek portlu bir makine düşünüyoruz. Verilerin ağ üzerinden yönlendirilme şekli, temelindeki topolojisine bağlıdır. Ortak ağ topolojileri için hepsi bir arada algoritmalara bir göz atıyoruz.

Hypercube

Bir hiperküp iki işlemcinin, indizlerinin birbirine yaklaşma mesafesi bir ise, bir bağlantıyı paylaştığı bir ağ topolojisidir. Hepsi bir arada algoritma fikri, aynı alt kübe ait mesajları birleştirmek ve ardından bunları dağıtmaktır.

Yüzük

Bir all-to-all algoritması halka topolojisi çok sezgiseldir. Başlangıçta bir işlemci komşularından birine m (p-1) boyutunda bir mesaj gönderir. İletişim tüm işlemcilerde aynı yönde gerçekleştirilir. İşlemci bir mesaj aldığında kendisine ait olan kısmı çıkarır ve mesajın geri kalanını bir sonraki komşuya iletir. (P-1) iletişim turlarından sonra, her mesaj hedefine dağıtılır.

Bu algoritmanın aldığı süre ${ displaystyle (t_ {s} + { frac {1} {2}} t_ {w} mp) (p-1)}$ .^[2] Buraya ${ displaystyle t_ {s}}$ bir iletişimin başlangıç maliyetidir ve ${ displaystyle t_ {w}}$ bir birim veriyi iletmenin maliyetidir. Bu terim, mesajların yarısı bir yönde ve diğer yarısı diğer yönde gönderildiğinde daha da geliştirilebilir. Bu şekilde, mesajlar hedeflerine daha erken ulaşır.

Örgü

Bir örgü bakarız ${ displaystyle { sqrt {p}} times { sqrt {p}}}$ örgü. Bu algoritma, herhangi bir ağ için kolayca uyarlanabilir. Bir ağdaki hepsi bir arada algoritma iki iletişim aşamasından oluşur. İlk olarak, her işlemci mesajları gruplandırır. ${ displaystyle { sqrt {p}}}$ her biri içeren gruplar ${ displaystyle { sqrt {p}}}$ mesajlar. Hedef işlemcileri aynı satırı paylaşıyorsa, mesajlar aynı gruptadır. Daha sonra, satırlar arasında hepsi bir arada işlem gerçekleştirilir. Her işlemci artık kendi sütununda işlemcilerle ilgili tüm bilgileri tutar. Yine, mesajların yeniden düzenlenmesi gerekiyor. Başka bir hepsi bir arada işlemden sonra, bu sefer sütunlarla ilgili olarak, her işlemci kendi mesajlarıyla sonuçlanır.

Bu algoritma için toplam iletişim süresi ${ displaystyle (2t_ {s} + t_ {w} mp) ({ sqrt {p}} - 1)}$ . Ek olarak, mesajların yerel olarak yeniden düzenlenmesi için süre, algoritmanın genel çalışma süresine eklenir.

1 faktörlü algoritma

1 faktörlü algoritmanın görselleştirmesi.

Yine tek portlu bir makine düşünüyoruz. Önemsiz bir algoritma, her işlemci için ağa asenkron mesajlar (p-1) göndermektir. Bu algoritmanın performansı, ağın ikiye bölme genişliği nedeniyle ortaya çıkan tıkanıklık nedeniyle zayıftır.^[3] Daha karmaşık algoritmalar, gönderme işlemlerinin sayısını azaltmak için mesajları birleştirir ve tıkanıklığı kontrol etmeye çalışır.

Büyük mesajlar için, bir başlangıç maliyeti, yükü iletme maliyetiyle karşılaştırıldığında küçüktür. Mesajları doğrudan hedeflerine göndermek daha hızlıdır. Aşağıdaki algoritmada, (p-1) bire bir yönlendirme kullanılarak bir hepsi bir arada algoritma gerçekleştirilir.

  // p tek: // pe indeksi  ${ displaystyle j in {0, noktalar, p-1 }}$   i için: = 0'dan p-1'e PE ile veri alışverişi yapın  ${ displaystyle (i-j) , mod , p}$

  // p çift: // pe indeksi  ${ displaystyle j in {0, noktalar, p-1 }}$   i için: = 0 ila p-2 boşta: = ${ displaystyle { frac {p} {2}} i , mod , (p-1)}$    Eğer j = p-1 ise o zaman boşta PE ile veri değiş tokuşu, eğer j = boş ise veri değiş tokuşu pe p-1 ile veri değiş tokuşu PE ile veri değişimi  ${ displaystyle (i-j) mod (p-1)}$

Algoritmanın farklı bir davranışı vardır, p tek ya da çift olsun. P'nin tuhaf olması durumunda, her yinelemede bir işlemci boştadır. Çift bir p için bu boş işlemci, p-1 indeksi ile işlemci ile iletişim kurar. Toplam geçen süre ${ displaystyle (p-1) (t_ {s} + t_ {w} m)}$ eşit bir p için ve ${ displaystyle p (t_ {s} + t_ {w} m)}$ tuhaf bir p için sırasıyla.

İşlemci j ile işlemci eşleştirmek yerine ${ displaystyle (i-j) { bmod {p}}}$ iterasyonunda, bir eşlemeyi belirlemek için özel veya j ve i'yi de kullanabiliriz. Bu yaklaşım, p'nin ikinin kuvveti olmasını gerektirir. Ağın temelindeki topolojiye bağlı olarak, bir yaklaşım diğerinden daha üstün olabilir. Bir hiperküp veya yağ ağacında ikili bire bir yönlendirme gerçekleştirirken özel veya yaklaşım daha üstündür.^[4]

Referanslar

^ Bruck, Jehoshua; Ho, Ching-Tien; Kipnis, Shlomo; Weathersby, Derrick (1997). "Çok Noktalı İleti Aktarma Sistemlerinde Herkesten Herkese İletişim için Etkin Algoritmalar" (PDF). Paralel ve Dağıtık Sistemlerde IEEE İşlemleri. 8 (11): 1143–1156. doi:10.1109/71.642949.
^ Grama, Ananth (2003). Paralel hesaplamaya giriş.
^ Hambrusch, Susanne E .; Hameed, Farooq; Khokhar, Ashfaq A. (Mayıs 1995). "Kaba taneli ağ mimarilerinde iletişim işlemleri". Paralel Hesaplama. 21 (5): 731–751. doi:10.1016 / 0167-8191 (94) 00110-V.
^ Thakur, Rajeev; Choudhary, Alok (26-29 Nisan 1994). Solucan Deliği Yönlendirmeli Ağlarda Hepsi Bir Arada İletişim. 8. Uluslararası Paralel İşleme Sempozyumu Bildiriler Kitabı. Cancun, Meksika.

[1] Bruck, Jehoshua; Ho, Ching-Tien; Kipnis, Shlomo; Weathersby, Derrick (1997). "Çok Noktalı İleti Aktarma Sistemlerinde Herkesten Herkese İletişim için Etkin Algoritmalar" (PDF). Paralel ve Dağıtık Sistemlerde IEEE İşlemleri. 8 (11): 1143–1156. doi:10.1109/71.642949.

[2] Grama, Ananth (2003). Paralel hesaplamaya giriş.

[3] Hambrusch, Susanne E .; Hameed, Farooq; Khokhar, Ashfaq A. (Mayıs 1995). "Kaba taneli ağ mimarilerinde iletişim işlemleri". Paralel Hesaplama. 21 (5): 731–751. doi:10.1016 / 0167-8191 (94) 00110-V.

[4] Thakur, Rajeev; Choudhary, Alok (26-29 Nisan 1994). Solucan Deliği Yönlendirmeli Ağlarda Hepsi Bir Arada İletişim. 8. Uluslararası Paralel İşleme Sempozyumu Bildiriler Kitabı. Cancun, Meksika.

[1]

[2]

[3]

[4]