Paralel Algoritmalar ve Performans
Paralel algoritma tasarımı, düşük iletişimle bol paralellik sergileyen hesaplamaları hedeflerken, performans analizi ek işlemcilerin ne kadar iyi kullanıldığını nicel olarak belirlemektedir.
Tanım
Paralel bir algoritma, bir problemin birden fazla işlemcinin işbirliği yaparak nasıl çözüldüğünü belirtmektedir; kalitesi, iş (toplam işlemler) ve derinlik (en uzun bağımlılık zinciri) ile p işlemci kullanmanın faydasını ölçen hızlanma ve verimlilik gibi performans metrikleriyle değerlendirilmektedir.
Kapsam
Bu konu, paralel algoritmaları tasarlamak ve analiz etmek için kullanılan modelleri—özellikle PRAM ve iş-derinlik (work-depth) analizini—ön ek toplamları (prefix sums / scan), indirgeme (reduction) ve sıralama gibi paralel temel öğelerin tasarımını ve hızlanma (speedup), verimlilik (efficiency), maliyet-optimizasyonu (cost-optimality), izoverimlilik (isoefficiency) ile Amdahl ve Gustafson'ın ölçeklendirme yasalarını içeren performans çerçevesini kapsamaktadır. Tüm programlama modellerinde paralel programlar hakkında akıl yürütmek için analitik temel sağlamaktadır.
Temel sorular
- Bir problemin içsel paralelliği, işi ve derinliği ile nasıl karakterize edilmektedir?
- Hızlanma, verimlilik ve ölçeklenebilirlik nasıl tanımlanmakta ve ölçülmektedir?
- Bir problemin seri kesri veya büyümesi, paralel ölçeklenebilirliğini nasıl belirlemektedir?
Temel kuramlar
- PRAM ve iş-derinlik (work-depth) analizi
- PRAM modeli, paylaşımlı belleğe ve senkron adımlara sahip paralel bir makineyi idealize etmekte olup, bir algoritmanın işini (toplam işlemler) ve derinliğini (kritik yol uzunluğu) analiz etmeyi desteklemektedir; bunlar birlikte elde edilebilir paralel süresini sınırlamaktadır.
- Hızlanma, verimlilik ve izoverimlilik
- Hızlanma, p işlemcinin bir problemi ne kadar daha hızlı çözdüğünü ölçmekte, verimlilik bunu işlemci başına normalleştirmekte ve izoverimlilik, verimliliği sabit tutmak için problem boyutunun işlemci sayısıyla nasıl büyümesi gerektiğini ifade ederek ölçeklenebilirliği yakalamaktadır.
- Amdahl ve Gustafson Yasaları
- Amdahl yasası, sabit boyutlu hızlanmayı seri kesirle sınırlarken, Gustafson yasası problemi makineyle ölçeklendirmenin neredeyse doğrusal hızlanmaya izin verdiğini gözlemlemekte, güçlü ve zayıf ölçeklendirmeyi birlikte çerçevelemektedir.
Klinik önem
İş-derinlik (work-depth) analizi ve ölçeklendirme yasaları, bir hesaplamanın ne zaman ve nasıl paralelleştirilmesi gerektiğini yönlendirmekte ve büyük ölçekteki davranışını tahmin etmektedir; bu da sıralama ve grafik çekirdeklerinden büyük simülasyonlara ve makine öğrenimi eğitimine kadar her şeyin tasarımına bilgi sağlamaktadır.
Tarihçe
Amdahl'ın 1967'deki argümanı ve Gustafson'ın 1988'deki karşı çıkışı hızlanma tartışmasını şekillendirmiştir; PRAM modeli ve iş-derinlik (work-depth) çerçevesi 1980'ler boyunca olgunlaşmış ve JaJa'nın 1992 tarihli metninde ile Grama ve meslektaşlarının ölçeklenebilirlik analizinde kodlanarak paralel bilişime teorik çekirdeğini kazandırmıştır.
Tartışmalar
- Güçlü ölçeklendirme ve zayıf ölçeklendirme
- Amdahl'ın güçlü ölçeklendirme görüşü (sabit problem, daha fazla işlemci) azalan getirileri öngörürken, Gustafson'ın zayıf ölçeklendirme görüşü (problemi işlemcilerle birlikte büyütme) sürekli hızlanmayı öngörmektedir; doğru ölçütün hangisi olduğu, problem boyutunun mu yoksa çözüm süresinin mi sabit olduğuna bağlıdır.
Öne çıkan isimler
- Joseph JaJa
- Gene Amdahl
- John Gustafson
- Vipin Kumar
İlgili konular
Temel eserler
- jaja1992
- amdahl1967
- gustafson1988
Sıkça sorulan sorular
- Paralel bir algoritmanın işi ile derinliği arasındaki fark nedir?
- İş, tüm işlemcilerde gerçekleştirilen toplam işlem sayısıdır; derinlik (veya açıklık), bağımlı işlemlerin en uzun zincirinin uzunluğudur. Derinlik, mümkün olan en iyi paralel çalışma süresini sınırlamakta ve iş-derinlik oranı ne kadar paralellik olduğunu göstermektedir.