Paralel algoritmaların analizi - Analysis of parallel algorithms

Bu makale, analiz nın-nin paralel algoritmalar. Sıradan, sıralı algoritmaların analizinde olduğu gibi, tipik olarak asimptotik kaynak tüketimini sınırlar (esas olarak hesaplama için harcanan zaman), ancak analiz, hesaplamaları gerçekleştirmek için işbirliği yapan çok sayıda işlemci biriminin varlığında gerçekleştirilir. Böylece, bir hesaplamanın sadece kaç "adım" alacağı değil, aynı zamanda işlemci sayısı arttıkça ne kadar hızlı olacağı da belirlenebilir. Analiz yaklaşımı, önce işlemci sayısını baskılayarak (veya soyutlayarak) çalışır. Bir sonraki arka plan paragrafı, işlemci sayısının soyutlanmasının ilk olarak nasıl ortaya çıktığını açıklıyor.

Sözde bir çalışma zamanı (WT) (bazen iş derinliği veya çalışma aralığı olarak da adlandırılır) çerçevesi ilk olarak Shiloach ve Vishkin tarafından tanıtıldı ^[1]paralel algoritmaları kavramsallaştırmak ve açıklamak için. WT çerçevesinde, paralel bir algoritma ilk olarak paralel turlar açısından tanımlanır. Her tur için, gerçekleştirilecek işlemler karakterize edilir, ancak birkaç konu bastırılabilir. Örneğin, her turdaki işlem sayısının net olması gerekmez, işlemcilerden bahsedilmesi gerekmez ve işlemcilerin işlere atanmasına yardımcı olabilecek herhangi bir bilginin hesaba katılması gerekmez. İkinci olarak, bastırılmış bilgiler sağlanır. Bastırılmış bilginin dahil edilmesi, aslında, Brent'e bağlı bir zamanlama teoreminin ispatı tarafından yönlendirilir,^[2] Bu makalenin sonraki bölümlerinde açıklanacaktır. WT çerçevesi yararlıdır çünkü paralel bir algoritmanın ilk tanımını büyük ölçüde basitleştirebilirken, bu ilk açıklama tarafından bastırılan ayrıntıları eklemek genellikle çok zor değildir. Örneğin, WT çerçevesi, paralel algoritmalar kitaplarında temel sunum çerçevesi olarak benimsenmiştir ( Paralel rastgele erişimli makine PRAM modeli) ^[3]ve ,^[4] yanı sıra sınıf notlarında.^[5] Aşağıdaki genel bakış, WT çerçevesinin açıklamaları WT çerçevesinde bulunmadığında bile daha genel paralel algoritmaları analiz etmek için WT çerçevesinin nasıl kullanılabileceğini açıklamaktadır.

Genel Bakış

Hesaplamaların aşağıdaki özelliklere sahip bir makinede yürütüldüğünü varsayalım. $p$ işlemciler. İzin Vermek $T p$ Hesaplamanın başlangıcı ile sonu arasında geçen süreyi belirtir. Hesaplamanın analizi çalışma süresi aşağıdaki kavramlara odaklanır:

iş tarafından yürütülen bir hesaplamanın $p$ işlemciler, işlemcilerin gerçekleştirdiği toplam ilkel işlem sayısıdır.^[6] İşlemcileri senkronize etmekten kaynaklanan iletişim ek yükünü göz ardı ederek, bu hesaplamayı tek bir işlemci üzerinde çalıştırmak için kullanılan zamana eşittir. $T 1$ .
derinlik veya açıklık nedeniyle sırayla gerçekleştirilmesi gereken en uzun işlem serisinin uzunluğudur. veri bağımlılıkları ( kritik yol). Derinlik aynı zamanda kritik yol uzunluğu hesaplamanın.^[7] Derinlik / açıklığın en aza indirilmesi, paralel algoritmaların tasarlanmasında önemlidir, çünkü derinlik / açıklık, olası en kısa yürütme süresini belirler.^[8] Alternatif olarak, aralık, zaman olarak tanımlanabilir $T \infty$ sonsuz sayıda işlemciye sahip ideal bir makine kullanarak harcadı.^[9]
maliyet hesaplamanın miktarı $pT p$ . Bu, tüm işlemciler tarafından hem hesaplama hem de bekleme için harcanan toplam süreyi ifade eder.^[6]

İş, süre ve maliyet tanımlarından birkaç faydalı sonuç çıkar:

Çalışma kanunu. Maliyet her zaman en azından iştir: $pT p \geq T 1$ . Bu gerçeğinden kaynaklanıyor $p$ işlemciler en fazla performans gösterebilir $p$ paralel işlemler.^[6]^[9]
Açıklık kanunu. Sonlu bir sayı $p$ işlemcilerin sayısı sonsuz bir sayıdan daha iyi performans gösteremez, bu nedenle $T p \geq T \infty$ .^[9]

Bu tanımları ve yasaları kullanarak aşağıdaki performans ölçüleri verilebilir:

Hızlanma sıralı yürütmeye kıyasla paralel yürütmeyle elde edilen hız kazancıdır: $S p = T 1 ∕ T p$ . Hızlanma olduğunda $Ω (n)$ giriş boyutu için $n$ (kullanarak büyük O notasyonu ), hızlanma doğrusaldır ve bu, basit hesaplama modellerinde optimaldir çünkü çalışma yasası şunu belirtir: $T 1 ∕ T p \leq p$ (süper doğrusal hızlanma nedeniyle pratikte ortaya çıkabilir bellek hiyerarşisi Etkileri). Durum $T 1 ∕ T p = p$ mükemmel doğrusal hızlanma olarak adlandırılır.^[9] Doğrusal hızlanma sergileyen bir algoritmanın, ölçeklenebilir.^[6]
Verimlilik işlemci başına hızlanma, $S p ∕ p$ .^[6]
Paralellik oran $T 1 ∕ T \infty$ . Herhangi bir sayıda işlemcide olası maksimum hızlanmayı temsil eder. Aralık yasasına göre, paralellik hızlanmayı sınırlar: eğer $p > T 1 ∕ T \infty$ , sonra:

${ displaystyle { frac {T_ {1}} {T_ {p}}} leq { frac {T_ {1}} {T _ { infty}}}$ .^[9]

gevşeklik dır-dir $T 1 ∕ (pT \infty)$ . Birden az bir gevşeklik, (açıklık yasasına göre) mükemmel doğrusal hızlanmanın mümkün olmadığı anlamına gelir. $p$ işlemciler.^[9]

Sınırlı sayıda işlemci üzerinde yürütme

Paralel algoritmaların analizi genellikle sınırsız sayıda işlemcinin mevcut olduğu varsayımı altında gerçekleştirilir. Bu gerçekçi değildir, ancak bir sorun değildir, çünkü paralel olarak çalışabilen herhangi bir hesaplama $N$ işlemciler çalıştırılabilir $p < N$ her işlemcinin birden fazla iş birimini yürütmesine izin vererek işlemciler. Bir sonuç çağrıldı Brent kanunu Zamanla böyle bir "simülasyon" yapılabileceğini belirtir $T p$ , sınırlanmış^[10]

{ displaystyle T_ {p} leq T_ {N} + { frac {T_ {1} -T_ {N}} {p}},}

veya daha az kesin olarak,^[6]

{ displaystyle T_ {p} = O sol (T_ {N} + { frac {T_ {1}} {p}} sağ).}

Yasa sınırlarının alternatif bir ifadesi $T p$ yukarıda ve aşağıda

{ displaystyle { frac {T_ {1}} {p}} leq T_ {p} leq { frac {T_ {1}} {p}} + T _ { infty}}

.

açıklığın (derinlik) $T \infty$ ve iş $T 1$ birlikte hesaplama süresinde makul sınırlar sağlar.^[2]

Referanslar

^ Shiloach, Yossi; Vishkin, Uzi (1982). "Bir Ö(n² günlükn) paralel maksimum akış algoritması ". Algoritmalar Dergisi. 3 (2): 128–146. doi:10.1016 / 0196-6774 (82) 90013-X.
^ ^a ^b Brent, Richard P. (1974-04-01). "Genel Aritmetik İfadelerin Paralel Değerlendirilmesi". ACM Dergisi. 21 (2): 201–206. CiteSeerX 10.1.1.100.9361. doi:10.1145/321812.321815. ISSN 0004-5411. S2CID 16416106.
^ JaJa, Joseph (1992). Paralel Algoritmalara Giriş. Addison-Wesley. ISBN 978-0-201-54856-3.
^ Keller, Jorg; Kessler, Cristoph W .; Traeff, Jesper L. (2001). Pratik PRAM Programlama. Wiley-Interscience. ISBN 978-0-471-35351-5.
^ Vishkin, Uzi (2009). Paralel Düşünme: Bazı Temel Veri Paralel Algoritmalar ve Teknikler, 104 sayfa (PDF). 1992'den beri Maryland Üniversitesi, College Park, Tel Aviv Üniversitesi ve Technion'da verilen paralel algoritmalarla ilgili ders notları.
^ ^a ^b ^c ^d ^e ^f Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). Paralel Algoritmalar. CRC Basın. s. 10. CiteSeerX 10.1.1.466.8142.
^ Blelloch, Guy (1996). "Paralel Algoritmaları Programlama" (PDF). ACM'nin iletişimi. 39 (3): 85–97. CiteSeerX 10.1.1.141.5884. doi:10.1145/227234.227246. S2CID 12118850.
^ Michael McCool; James Reinders; Arch Robison (2013). Yapısal Paralel Programlama: Verimli Hesaplama Modelleri. Elsevier. sayfa 4–5.
^ ^a ^b ^c ^d ^e ^f Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Algoritmalara Giriş (3. baskı). MIT Press ve McGraw-Hill. sayfa 779–784. ISBN 0-262-03384-4.
^ Gustafson, John L. (2011). "Brent Teoremi". Paralel Hesaplama Ansiklopedisi. s. 182–185. doi:10.1007/978-0-387-09766-4_80. ISBN 978-0-387-09765-7.

[shiloach-1] Shiloach, Yossi; Vishkin, Uzi (1982). "Bir Ö(n² günlükn) paralel maksimum akış algoritması ". Algoritmalar Dergisi. 3 (2): 128–146. doi:10.1016 / 0196-6774 (82) 90013-X.

[brent-2] Brent, Richard P. (1974-04-01). "Genel Aritmetik İfadelerin Paralel Değerlendirilmesi". ACM Dergisi. 21 (2): 201–206. CiteSeerX 10.1.1.100.9361. doi:10.1145/321812.321815. ISSN 0004-5411. S2CID 16416106.

[jaja-3] JaJa, Joseph (1992). Paralel Algoritmalara Giriş. Addison-Wesley. ISBN 978-0-201-54856-3.

[kkt-4] Keller, Jorg; Kessler, Cristoph W .; Traeff, Jesper L. (2001). Pratik PRAM Programlama. Wiley-Interscience. ISBN 978-0-471-35351-5.

[uv-5] Vishkin, Uzi (2009). Paralel Düşünme: Bazı Temel Veri Paralel Algoritmalar ve Teknikler, 104 sayfa (PDF). 1992'den beri Maryland Üniversitesi, College Park, Tel Aviv Üniversitesi ve Technion'da verilen paralel algoritmalarla ilgili ders notları.

[casanova-6] ^ ^a ^b ^c ^d ^e ^f Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). Paralel Algoritmalar. CRC Basın. s. 10. CiteSeerX 10.1.1.466.8142.

[cacm-7] Blelloch, Guy (1996). "Paralel Algoritmaları Programlama" (PDF). ACM'nin iletişimi. 39 (3): 85–97. CiteSeerX 10.1.1.141.5884. doi:10.1145/227234.227246. S2CID 12118850.

[spp-8] Michael McCool; James Reinders; Arch Robison (2013). Yapısal Paralel Programlama: Verimli Hesaplama Modelleri. Elsevier. sayfa 4–5.

[clrs-9] ^ ^a ^b ^c ^d ^e ^f Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Algoritmalara Giriş (3. baskı). MIT Press ve McGraw-Hill. sayfa 779–784. ISBN 0-262-03384-4.

[10] Gustafson, John L. (2011). "Brent Teoremi". Paralel Hesaplama Ansiklopedisi. s. 182–185. doi:10.1007/978-0-387-09766-4_80. ISBN 978-0-387-09765-7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Paralel hesaplama
Genel	Dağıtılmış bilgi işlem Paralel hesaplama Büyük ölçüde paralel Bulut bilişim Yüksek performanslı bilgi işlem Çoklu işlem Manycore işlemci GPGPU Bilgisayar ağı Sistolik dizi
Seviyeler	Bit Talimat Konu Görev Veri Hafıza Döngü Boru hattı
Çoklu kullanım	Geçici Eşzamanlı (SMT) Spekülatif (SpMT) Önleyici Kooperatif Kümelenmiş Çok İplikli (CMT) Donanım keşif
Teori	PRAM modeli PEM Modeli Paralel algoritmaların analizi Amdahl kanunu Gustafson yasası Maliyet etkinliği Karp – Flatt metriği Yavaşla Hızlanma
Elementler	İşlem Konu Lif Talimat penceresi Dizi veri yapısı
Koordinasyon	Çoklu işlem Bellek tutarlılığı Önbellek tutarlılığı Önbellek geçersiz kılma Bariyer Senkronizasyon Uygulama kontrol noktası belirleme
Programlama	Akış işleme Dataflow programlama Modeller Örtük paralellik Açık paralellik Eşzamanlılık Engellemeyen algoritma
Donanım	Flynn'in taksonomisi SISD SIMD SIMT MISD MIMD Dataflow mimarisi Ardışık düzenlenmiş işlemci Superscalar işlemci Vektör işlemci Çok işlemcili simetrik asimetrik Hafıza paylaşılan dağıtılmış dağıtılmış paylaşılan UMA NUMA KOMA Büyük ölçüde paralel bilgisayar Bilgisayar kümesi Şebeke bilgisayarı Donanım ivmesi
API'ler	Ateji PX Boost Şapel HPX Cazibe ++ Cilk Coarray Fortran CUDA Orman perisi C ++ AMP Global Diziler GPUOpen MPI OpenMP OpenCL OpenHMPP OpenACC Paralel Uzantılar PVM POSIX Konuları RaftLib UPC TBB ZPL
Problemler	Otomatik paralelleştirme Kilitlenme Deterministik algoritma Utanç verici derecede paralel Paralel yavaşlama Yarış kondisyonu Yazılım kilitleme Ölçeklenebilirlik Açlık
Kategori: Paralel hesaplama