Döngü düzeyinde paralellik - Loop-level parallelism

Döngü düzeyinde paralellik bir biçimdir paralellik içinde yazılım programlama paralel görevleri çıkarmakla ilgilenen döngüler. Döngü düzeyinde paralellik fırsatı genellikle verilerin depolandığı bilgi işlem programlarında ortaya çıkar. rasgele erişim veri yapıları. Sıralı bir programın veri yapısı üzerinde yinelediği ve birer birer endeksler üzerinde çalıştığı durumlarda, döngü düzeyinde paralelliği kullanan bir program birden çok İş Parçacığı veya süreçler aynı anda endekslerin bazılarında veya tamamında işleyen. Böyle bir paralellik, hızlanma genel olarak programın genel yürütme süresine Amdahl kanunu.

Açıklama

Her bir yinelemenin diğerlerinden bağımsız olduğu basit döngüler için döngü düzeyinde paralellik olabilir utanç verici derecede paralel Paralelleştirme yalnızca her yinelemeyi işlemek için bir işlem atamayı gerektirdiğinden. Bununla birlikte, birçok algoritma sıralı olarak çalışacak şekilde tasarlanmıştır ve paralel işlemler sırasında başarısız olur. yarış kod içindeki bağımlılık nedeniyle. Sıralı algoritmalar bazen küçük değişikliklerle paralel bağlamlara uygulanabilir. Yine de genellikle gerektirirler süreç senkronizasyonu. Senkronizasyon, aracılığıyla örtük olabilir ileti geçişi veya açıkça, senkronizasyon ilkelleri aracılığıyla semaforlar.

Misal

Bir listede işleyen aşağıdaki kodu düşünün L uzunluk n.

for (int i = 0; i 
Döngünün her yinelemesi, değeri şu anki indeksinden alır L, ve 10 artırır. If ifadesi S1 alır T yürütme zamanı, sonra döngü zaman alır n * T döngü yapıları tarafından alınan zamanı göz ardı ederek sıralı olarak yürütmek için. Şimdi bir sistemi düşünün p işlemciler nerede p> n. Eğer n iş parçacıkları paralel olarak çalışır, hepsini yürütme zamanı n adımlar azaltılır T.
Daha az basit durumlar tutarsızlık yaratır, yani serileştirilemez sonuçlar. Aynı listede işleyen aşağıdaki döngüyü düşünün L.
for (int i = 1; i 
Her yineleme, geçerli dizini önceki artı on sayısının değeri olacak şekilde ayarlar. Sıralı olarak çalıştırıldığında, her yineleme, önceki yinelemenin zaten doğru değere sahip olacağı garanti edilir. Birden çok iş parçacığı ile, süreç çizelgeleme ve diğer hususlar, yürütme emrinin bir yinelemenin ancak bağımlılığı karşılandıktan sonra yürütüleceğini garanti etmesini engeller. Daha önce de olabilir ve beklenmedik sonuçlara yol açabilir. Serileştirilebilirlik, önceki yinelemelere olan bağımlılığı korumak için senkronizasyon eklenerek geri yüklenebilir.
Koddaki bağımlılıklar








Kod içinde bulunabilecek birkaç tür bağımlılık vardır.[1][2]
Tür
Gösterim
Açıklama
Gerçek (Akış) Bağımlılığı
S1 -> T S2
S1 ve S2 arasındaki gerçek bağımlılık, S1'in daha sonra S2 tarafından okunan bir konuma yazdığı anlamına gelir.
Bağımlılık Karşıtı
S1 -> A S2
S1 ve S2 arasındaki bir anti-bağımlılık, S1'in daha sonra S2 tarafından yazılan bir konumdan okuduğu anlamına gelir.
Çıktı Bağımlılığı
S1 -> O S2
S1 ve S2 arasındaki çıkış bağımlılığı, S1 ve S2'nin aynı konuma yazması anlamına gelir.
Giriş Bağımlılığı
S1 -> I S2
S1 ve S2 arasındaki giriş bağımlılığı, S1 ve S2'nin aynı konumdan okuduğu anlamına gelir.
Bir döngünün paralel çalıştırıldığında sıralı davranışını korumak için Gerçek Bağımlılık korunmalıdır. Bağımlılık Karşıtı ve Çıktı Bağımlılığı, her işleme kendi değişken kopyalarını (özelleştirme olarak bilinir) verilerek ele alınabilir.[1]
Gerçek bağımlılık örneği
S1: int a, b; S2: a = 2; S3: b = a + 40;
S2 -> T S3, S2 değişkene yazdığı için S2'nin S3'e gerçek bir bağımlılığı olduğu anlamına gelir a, S3'ün okuduğu.
Bağımlılık karşıtı örnek
S1: int a, b = 40; S2: a = b - 38; S3: b = -1;
S2 -> A S3Bu, S2'nin S3'e bağımlı olmayan bir bağımlılığı olduğu anlamına gelir çünkü S2 değişkenden okur b S3 yazmadan önce.
Çıktı bağımlılığı örneği
S1: int a, b = 40; S2: a = b - 38; S3: a = 2;
S2 -> O S3Bu, S2'nin S3'e bir çıktı bağımlılığı olduğu anlamına gelir çünkü her ikisi de değişkene yazar a.
Girdi bağımlılığı örneği
S1: int a, b, c = 2; S2: a = c - 1; S3: b = c + 1;
S2 -> I S3yani S2'nin S3'e bir girdi bağımlılığı olduğu anlamına gelir çünkü hem S2 hem de S3 değişken c.
Döngülerde bağımlılık








Döngü ile taşınan ve döngüden bağımsız bağımlılık
Döngüler iki tür bağımlılığa sahip olabilir:
Döngü-taşınan bağımlılık
Döngüden bağımsız bağımlılık
Döngüden bağımsız bağımlılıkta, döngülerin yinelemeler arası bağımlılığı vardır, ancak yinelemeler arasında bağımlılıkları yoktur. Her yineleme bir blok olarak ele alınabilir ve diğer senkronizasyon çabaları olmadan paralel olarak gerçekleştirilebilir.
İki uzunluklu n dizisinin değerlerini takas etmek için kullanılan aşağıdaki örnek kodda, döngüden bağımsız bir bağımlılık vardır. S1 -> T S3.
for (int i = 1; i 
Döngü-taşınan bağımlılıkta, bir döngünün yinelemesindeki ifadeler, döngünün başka bir yinelemesindeki ifadelere bağlıdır. Döngü-Taşınan Bağımlılık, daha önce görülen bağımlılık notasyonunun değiştirilmiş bir sürümünü kullanır.
Döngü-taşınan bağımlılık örneği burada S1 [i] -> T S1 [i + 1], nerede ben geçerli yinelemeyi gösterir ve i + 1 sonraki yinelemeyi gösterir.
for (int i = 1; i 
Döngü taşınan bağımlılık grafiği
Döngü ile taşınan bağımlılık grafiği, yinelemeler arasındaki döngüde taşınan bağımlılıkları grafik olarak gösterir. Her yineleme, grafikte bir düğüm olarak listelenir ve yönlendirilmiş kenarlar, her yineleme arasındaki gerçek, anti ve çıktı bağımlılıklarını gösterir.
Türler








Döngüleri paralel hale getirmek için çeşitli metodolojiler vardır.
DAĞITILMIŞ Döngü
DOALL Paralellik
DOACROSS Paralelliği
HELIX [3]
DOPIPE Paralelliği
Her uygulama, iş parçacığının nasıl senkronize edileceğine göre biraz farklılık gösterir. Ek olarak, paralel görevler bir şekilde bir süreçle eşleştirilmelidir. Bu görevler statik veya dinamik olarak tahsis edilebilir. Araştırmalar, yük dengelemenin bazı dinamik ayırma algoritmalarıyla statik olarak yapıldığından daha iyi başarılabileceğini göstermiştir.[4]
Sıralı bir programı paralelleştirme süreci aşağıdaki ayrı adımlara bölünebilir.[1] Aşağıdaki her somut döngü paralelleştirme bunları örtük olarak gerçekleştirir.
Tür
Açıklama
Ayrışma
Program, sömürülecek en küçük uyum birimi olan görevlere bölünmüştür.
Görev
Görevler süreçlere atanır.
Orkestrasyon
Veri erişimi, iletişim ve süreçlerin senkronizasyonu.
Haritalama
Süreçler işlemcilere bağlıdır.
DAĞITILMIŞ döngü
Bir döngü döngü-taşınan bağımlılığa sahip olduğunda, paralelleştirmenin bir yolu, döngüyü birkaç farklı döngüye dağıtmaktır. Birbirine bağımlı olmayan ifadeler, bu dağıtılmış döngülerin paralel olarak yürütülebilmesi için ayrılır. Örneğin, aşağıdaki kodu göz önünde bulundurun. 
için (int i = 1; i 
Döngünün döngü taşıma bağımlılığı vardır S1 [i] -> T S1 [i + 1] ancak S2 ve S1 döngüden bağımsız bir bağımlılığa sahip değildir, bu nedenle kodu aşağıdaki gibi yeniden yazabiliriz. 
loop1: for (int i = 1; i 
Artık loop1 ve loop2'nin paralel olarak yürütülebileceğini unutmayın. Veri seviyesinde paralellikte olduğu gibi farklı veriler üzerinde tek bir talimatın paralel olarak gerçekleştirilmesi yerine, burada farklı döngüler farklı veriler üzerinde farklı görevler gerçekleştirir. Diyelim ki S1 ve S2'nin uygulama zamanı ${displaystyle Ts1}$ ve ${displaystyle Ts2}$ daha sonra yukarıdaki kodun sıralı biçimi için yürütme süresi ${displaystyle n * (Ts1 + Ts2)}$Şimdi, iki ifadeyi böldüğümüz ve onları iki farklı döngüye koyduğumuz için, bize bir yürütme süresi verir. ${displaystyle n * Ts1 + Ts2}$. Bu tür paralelliği, işlev veya görev paralelliği olarak adlandırıyoruz.
DOALL paralelliği
DOALL paralelliği, bir döngü içindeki ifadeler bağımsız olarak yürütülebildiğinde (döngüde taşınan bağımlılığın olmadığı durumlar) mevcuttur.[1] Örneğin, aşağıdaki kod diziden okumaz ave dizileri güncellemez M.Ö. Hiçbir yinelemenin başka herhangi bir yinelemeye bağımlılığı yoktur.
for (int i = 0; i 
Diyelim ki S1'in bir yürütme zamanı ${displaystyle Ts1}$ daha sonra yukarıdaki kodun sıralı biçimi için yürütme süresi ${displaystyle n * Ts1}$Şimdi DOALL Paralellik, tüm yinelemeler bağımsız olduğunda var olduğu için, hızlandırma, tüm yinelemeleri paralel olarak yürüterek elde edilebilir, bu da bize bir yürütme süresi verir. ${displaystyle Ts1}$, sıralı yürütmede bir yineleme için geçen süredir.
Basitleştirilmiş bir sözde kod kullanan aşağıdaki örnek, her yinelemeyi bağımsız olarak yürütmek için bir döngünün nasıl paralelleştirilebileceğini gösterir.
begin_parallelism (); for (int i = 0; i 
DOACROSS paralelliği
DOACROSS Paralelliği, bir döngünün yinelemelerinin, bağımsız olarak gerçekleştirilebilen hesaplamaları çıkararak ve bunları aynı anda çalıştırarak paralelleştirildiği durumlarda mevcuttur.[5]
Döngüde taşınan bağımlılığı zorlamak için senkronizasyon mevcuttur.
Bağımlılıkla aşağıdaki senkronize döngüyü düşünün S1 [i] -> T S1 [i + 1].
for (int i = 1; i 
Her döngü yinelemesi iki eylem gerçekleştirir
Hesaplamak a [i - 1] + b [i] + 1
Değeri şuna atayın: a [i]
Değeri hesaplamak a [i - 1] + b [i] + 1ve sonra atamanın gerçekleştirilmesi iki satıra ayrılabilir (S1 ve S2 ifadeleri):
S1: int tmp = b [i] + 1; S2: a [i] = a [i - 1] + tmp;
İlk satır, int tmp = b [i] + 1;döngü-taşınan bağımlılığı yoktur. Döngü daha sonra geçici değeri paralel olarak hesaplayarak ve ardından atamayı senkronize ederek paralel hale getirilebilir. a [i].
post (0); for (int i = 1; i 
Diyelim ki S1 ve S2'nin yürütme zamanı ${displaystyle Ts1}$ ve ${displaystyle Ts2}$ daha sonra yukarıdaki kodun sıralı biçimi için yürütme süresi ${displaystyle n * (Ts1 + Ts2)}$, DOACROSS Paralelizmi mevcut olduğu için, hızlandırma, bize bir yürütme süresi veren ardışık düzen içinde yinelemeler yürütülerek elde edilebilir. ${displaystyle Ts1 + n * Ts2}$.
DOPIPE paralelliği
DOPIPE Parallelism, döngü yinelemesinin birden çok senkronize döngüye dağıtıldığı döngüde taşınan bağımlılık için boru hatlı paralellik uygular.[1] DOPIPE'nin amacı, bir önceki aşamadan yeterli veri mevcut olur olmaz bir aşamanın başlatıldığı bir montaj hattı gibi davranmaktır.[6]
Bağımlılıkla aşağıdaki eşzamanlı kodu düşünün S1 [i] -> T S1 [i + 1].
için (int i = 1; i 
S1 sıralı olarak yürütülmelidir, ancak S2'nin döngüde taşınan bağımlılığı yoktur. S2, seri olarak S1'in ihtiyaç duyduğu tüm hesaplamaları yaptıktan sonra DOALL Parallelism kullanılarak paralel olarak yürütülebilir. Ancak, bu yapılırsa hızlanma sınırlıdır. Daha iyi bir yaklaşım, söz konusu S1 bittiğinde her S1'e karşılık gelen S2'nin yürütülmesi için paralel hale getirmektir.
Ardışık paralellik uygulanması, aşağıdaki döngü setiyle sonuçlanır; burada ikinci döngü, birinci döngü karşılık gelen indeksi bitirir bitirmez bir indeks için yürütülebilir.
için (int i = 1; i 
Diyelim ki S1 ve S2'nin uygulama zamanı ${displaystyle Ts1}$ ve ${displaystyle Ts2}$ daha sonra yukarıdaki kodun sıralı biçimi için yürütme süresi ${displaystyle n * (Ts1 + Ts2)}$, Şimdi DOPIPE Paralelizmi mevcut olduğu için, hızlandırma, bize bir yürütme süresi veren ardışık bir şekilde yinelemeleri gerçekleştirerek elde edilebilir. ${displaystyle n * Ts1 + (n / p) * Ts2}$, burada p, paralel işlemci sayısıdır.
Ayrıca bakınız








Veri paralelliği
Görev paralelliği
Paralellik gibi farklı bellek modellerini kullanan paylaşılan ve dağıtılmış ve İleti geçişi
Referanslar








^ a b c d e Solihin, Yan (2016). Paralel Mimarinin Temelleri. Boca Raton, FL: CRC Press. ISBN  978-1-4822-1118-4.
^ Goff, Gina (1991). "Pratik bağımlılık testi". Programlama dili tasarımı ve uygulaması üzerine ACM SIGPLAN 1991 konferansının bildirileri - PLDI '91. s. 15–29. doi:10.1145/113445.113448. ISBN  0897914287.
^ Murphy, Niall. "DOACROSS döngülerinde paralelliği keşfetmek ve kullanmak" (PDF). Cambridge Üniversitesi. Alındı 10 Eylül 2016.
^ Kavi, Krishna. "DOALL ve DOACROSS Döngülerinin Paralelleştirilmesi-Bir Anket". Alıntı dergisi gerektirir | günlük = (Yardım)
^ Unnikrishnan, Priya (2012), "DOACROSS Paralelleştirmeye Pratik Bir Yaklaşım", Euro-Par 2012 Paralel İşleme, Bilgisayar Bilimleri Ders Notları, 7484, s. 219–231, doi:10.1007/978-3-642-32820-6_23, ISBN  978-3-642-32819-0
^ "DoPipe: Simülasyonu Paralelleştirmek İçin Etkili Bir Yaklaşım" (PDF). Intel. Alındı 13 Eylül 2016.