Paralel algoritmalar
- Algoritmalar kursu
- Uzman seviye
- Ders 34/41
- 4 dk
PRAM paralel modelini öğrenirsin.
Paralel algoritmalar
Paralel algoritmalar, bir problemi aynı anda birden çok işlemcide çözmeyi hedefler. PRAM (Parallel Random Access Machine), paralel algoritmaları modellemek için kullanılan teorik makine modelidir.
PRAM'de birden çok işlemci ortak bir belleğe eşzamanlı erişir. İşlemci sayısı p, problemin boyutu n ise paralel süre T_p, genellikle T_1 / p'ye yakındır.
Hızlanma (speedup) T_1 / T_p ile, verim T_1 / (p · T_p) ile tanımlanır.
Amdahl yaşası
Amdahl yaşası, bir problemin paralelleştirilemeyen bölümünün hızlanma üst sınırını belirler. Eğer problemin p oranı paralelse, maksimum hızlanma 1 / ((1 - p) + p / n) ile verilir; burada n işlemci sayısıdır.
Örneğin %95 paralel bir problem sonsuz işlemcide en fazla 20 kat hızlanabilir. Bu yaşa, paralelleştirmenin sınırlarını gösterir.
Verimli paralel algoritma tasarımı, paralelleştirilemeyen bölümü en aza indirmeyi gerektirir.
Uygulama parallel_sum fonksiyonu
parallel_sum(arr) yaz. Paralel azaltma simülasyonuyla toplamı döndür: her adımda komşu çiftleri topla. print(parallel_sum([1, 2, 3, 4, 5, 6, 7, 8])) ile 36 yazdır.
Başlangıç kodu
def parallel_sum(arr):
# Paralel azaltma simülasyonuÖrnek çözüm
def parallel_sum(arr):
# Paralel azaltma simülasyonu
while len(arr) > 1:
new_arr = []
for i in range(0, len(arr), 2):
if i + 1 < len(arr):
new_arr.append(arr[i] + arr[i + 1])
else:
new_arr.append(arr[i])
arr = new_arr
return arr[0]
print(parallel_sum([1, 2, 3, 4, 5, 6, 7, 8]))Beklenen çıktı
36
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Hızlanma (speedup) nasıl tanımlanır?
speedup = T_1 / T_p- T_p · T_1
- T_1 / T_p Doğru cevap
- p · T_p
- T_1 + T_p
Açıklama: Hızlanma T_1 / T_p ile tanımlanır.
2 paralel azaltma
for i in range(0, len(arr), ____):
new_arr.append(arr[i] + arr[i + 1])for i in range(0, len(arr), 2):
new_arr.append(arr[i] + arr[i + 1])Açıklama: Çift adımlı tarama paralel azaltma simülasyonu.
3 Paralel kavramlar
| Kavram | Anlamı |
|---|---|
PRAM |
Teorik model |
hızlanma |
T_1 / T_p |
Amdahl |
Serbest sınır |
azaltma |
Komşu çift |