Paralel algoritmalar Böl ve Yönet (Divide & Conquer) Algoritması

Paralel algoritmalar Böl ve Yönet (Divide & Conquer) Algoritması

Böl ve Yönet algoritması, orijinal problemi daha kolay çözmek için, problemi alt problemlere bölen, bölünen alt problemleri çözen, orijinal problemin çözümünü oluşturmak için, alt problemlerin çözümlerini birleştiren bir algoritmadır. Böl ve yönet paradigması program modülaritesini yükseltir, genellikle basit ve verimli algoritmalara yol açar. Bu nedenle sıralı algoritma tasarımcıları için güçlü bir araç olduğu kanıtlanmıştır. Böl ve yönet paralel algoritma tasarımı daha da önemli bir rol oynamaktadır. İlk adımda oluşturduğunuz alt problemler genellikle bağımsız olduğundan, bunlar paralel olarak çözülebilir. Genellikle alt problemler özyinelemeli olarak çözülür ve böylece bir sonraki bölme adımında paralel olarak çözülecek daha çok alt problem elde edilir. Ancak bilinmelidir ki, yüksek derecede bir paralel algoritma elde etmek için, böl ve yönet’in bölme ve birleştirme adımlarının paralelize (birlikte yürütülmesi) olması gerekir. Orijinal problemi mümkün olduğunca çok sayıda alt probleme bölerek, paralel olarak çözmek paralel algoritmalarda oldukça yaygındır. Paralel Böl ve Yönet örneği için, sıralı Merge Sort algoritması düşünün. Merge sort, n adet girilmiş elemanı alır ve onları sıralayarak geri verir. Bu algoritma, n elemanlı bir dizi iki parçaya bölünüp, bölünen her dizi öz yineli olarak sıralanıp ve sıralanmış yarı diziler tekrar birleştirilerek çalışır.