Paralel Algoritma - Modeller

Paralel bir algoritma modeli, verileri ve işleme yöntemini bölmek için bir strateji düşünülerek ve etkileşimleri azaltmak için uygun bir strateji uygulanarak geliştirilir. Bu bölümde, aşağıdaki Paralel Algoritma Modellerini tartışacağız -

Veri paralel modeli
Görev grafiği modeli
Çalışma havuzu modeli
Ana köle modeli
Üretici tüketici veya satış hattı modeli
Hibrit model

Veri Paralel

Veri paralel modelinde, görevler süreçlere atanır ve her görev farklı veriler üzerinde benzer türde işlemler gerçekleştirir. Data parallelism birden çok veri öğesine uygulanan tek işlemin bir sonucudur.

Paralel veri modeli, paylaşılan adres alanlarına ve mesaj iletme paradigmalarına uygulanabilir. Veri-paralel modelde, etkileşim giderleri, ayrıştırmayı koruyan bir yerellik seçerek, optimize edilmiş toplu etkileşim rutinleri kullanılarak veya örtüşen hesaplama ve etkileşim yoluyla azaltılabilir.

Veri paralel model problemlerinin temel özelliği, problemin boyutuyla birlikte veri paralelliğinin yoğunluğunun artması ve bu da daha büyük problemleri çözmek için daha fazla işlemin kullanılmasını mümkün kılmasıdır.

Example - Yoğun matris çarpımı.

Görev Grafik Modeli

Görev grafiği modelinde, paralellik bir task graph. Bir görev grafiği ya önemsiz ya da önemsiz olabilir. Bu modelde, görevler arasındaki korelasyon, yerelliği desteklemek veya etkileşim maliyetlerini en aza indirmek için kullanılır. Bu model, görevlerle ilişkili veri miktarının kendileriyle ilişkili hesaplama sayısına kıyasla çok büyük olduğu sorunları çözmek için uygulanır. Görevler, görevler arasında veri hareketinin maliyetini iyileştirmeye yardımcı olmak için atanır.

Examples - Paralel hızlı sıralama, seyrek matris çarpanlara ayırma ve böl ve yönet yaklaşımıyla türetilen paralel algoritmalar.

Burada problemler atomik görevlere bölünür ve bir grafik olarak uygulanır. Her görev, bir veya daha fazla önceki göreve bağımlı olan bağımsız bir iş birimidir. Bir görevin tamamlanmasından sonra, bir öncül görevin çıktısı bağımlı göreve aktarılır. Öncül görevi olan bir görev, yalnızca önceki görevin tamamı tamamlandığında yürütülmeye başlar. Grafiğin son çıktısı, son bağımlı görev tamamlandığında alınır (yukarıdaki şekilde Görev 6).

Çalışma Havuzu Modeli

İş havuzu modelinde, yükün dengelenmesi için görevler dinamik olarak süreçlere atanır. Bu nedenle, herhangi bir işlem potansiyel olarak herhangi bir görevi yürütebilir. Bu model, görevlerle ilişkili veri miktarı, görevlerle ilişkili hesaplamadan nispeten daha küçük olduğunda kullanılır.

Süreçlere istenilen önceden görev atanması yoktur. Görevlerin atanması merkezileştirilmiş veya dağıtılmıştır. Görevlere yönelik işaretçiler, fiziksel olarak paylaşılan bir listeye, bir öncelik sırasına veya bir karma tablo veya ağaçta kaydedilir veya fiziksel olarak dağıtılmış bir veri yapısına kaydedilebilir.

Görev başlangıçta mevcut olabilir veya dinamik olarak oluşturulabilir. Görev dinamik olarak oluşturulursa ve merkezi olmayan bir görev ataması yapılırsa, tüm işlemlerin tüm programın tamamlandığını gerçekten algılaması ve daha fazla görev aramayı bırakması için bir sonlandırma algılama algoritması gerekir.

Example - Paralel ağaç araması

Master-Slave Modeli

Master-slave modelinde, bir veya daha fazla master proses, görevi üretir ve onu slave proseslerine tahsis eder. Aşağıdaki durumlarda görevler önceden tahsis edilebilir:

usta, görevlerin hacmini tahmin edebilir veya
rastgele bir atama, yükü dengelemek için tatmin edici bir iş yapabilir veya
kölelere farklı zamanlarda daha küçük görevler atanır.

Bu model genel olarak eşit derecede uygundur shared-address-space veya message-passing paradigms, çünkü etkileşim doğal olarak iki yol.

Bazı durumlarda, bir görevin aşamalar halinde tamamlanması gerekebilir ve sonraki aşamalardaki görev oluşturulmadan önce her aşamadaki görevin tamamlanması gerekir. Master-slave modeli şu şekilde genelleştirilebilir:hierarchical veya multi-level master-slave model burada üst düzey yönetici, görevlerin büyük bölümünü, görevleri kendi yardımcıları arasında daha fazla alt bölümlere ayıran ve görevin bir bölümünü kendi başına gerçekleştirebilen ikinci düzey yöneticiye besler.

Master-slave modelinin kullanımıyla ilgili önlemler

Ustanın bir tıkanıklık noktası olmamasını sağlamak için özen gösterilmelidir. Görevler çok küçükse veya çalışanlar nispeten hızlıysa bu gerçekleşebilir.

Görevler, bir görevi yerine getirme maliyeti iletişim maliyetine ve senkronizasyon maliyetine hakim olacak şekilde seçilmelidir.

Eşzamansız etkileşim, üst üste gelen etkileşimin ve iş üretimiyle ilişkili hesaplamanın usta tarafından yapılmasına yardımcı olabilir.

Boru Hattı Modeli

Aynı zamanda producer-consumer model. Burada bir dizi veri, her biri üzerinde bazı görevler gerçekleştiren bir dizi işlemden geçirilir. Burada, yeni verilerin gelmesi, kuyruktaki bir işlem tarafından yeni bir görevin yürütülmesini üretir. Süreçler, doğrusal veya çok boyutlu diziler, ağaçlar veya döngüleri olan veya olmayan genel grafikler şeklinde bir kuyruk oluşturabilir.

Bu model bir üretici ve tüketici zinciridir. Kuyruktaki her işlem, kuyrukta kendisinden önce gelen işlem için bir dizi veri öğesinin tüketicisi ve kuyrukta onu izleyen işlem için bir veri üreticisi olarak kabul edilebilir. Kuyruğun doğrusal bir zincir olması gerekmez; yönlendirilmiş bir grafik olabilir. Bu modele uygulanabilen en yaygın etkileşim minimizasyon tekniği, hesaplama ile örtüşen etkileşimdir.

Example - Paralel LU çarpanlara ayırma algoritması.

Hibrit Modeller

Bir problemi çözmek için birden fazla modele ihtiyaç duyulduğunda bir hibrit algoritma modeli gereklidir.

Bir hibrit model, hiyerarşik olarak uygulanan birden çok modelden veya paralel bir algoritmanın farklı aşamalarına sıralı olarak uygulanan birden çok modelden oluşabilir.

Example - Paralel hızlı sıralama