Paralel algoritmalar

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.

Örnek çözümü göster

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]))

Kendini test et

Hızlanma (speedup) nasıl tanımlanır?
```
speedup = T_1 / T_p
```
- T_p · T_1
- T_1 / T_p
- p · T_p
- T_1 + T_p
Cevabı göster

T_1 / T_p — Hızlanma T_1 / T_p ile tanımlanır.

paralel azaltma

for i in range(0, len(arr), ____):
    new_arr.append(arr[i] + arr[i + 1])

Cevabı göster

for i in range(0, len(arr), 2):
    new_arr.append(arr[i] + arr[i + 1])

Paralel kavramlar

PRAM

Teorik model
hızlanma

T_1 / T_p
Amdahl

Serbest sınır
azaltma

Komşu çift

Sıradaki ders: MapReduce

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler