Paralel alqoritmlər və onların mürəkkəbliyi

6.1 Paralel alqoritmlər.

Paralel alqoritmlər çoxprosessorlu və ya çoxaxınlı sistemlərdə hesablama sürətini artırmaq məqsədilə icra üçün nəzərdə tutulub. Onlar tapşırığı müstəqil subtapşırıqlara bölürlər və eyni zamanda icra edirlər. Paralel alqoritmlərin mürəkkəbliyini analiz edərkən həm zaman, həm də məkan mürəkkəbliyi ilə yanaşı, sürətləndirmə, effektivlik və genişlənəbilənlik kimi faktorlar da nəzərə alınmalıdır.

Paralel alqoritmlərin əsas konsepsiyaları

• Paralellik: Tapşırığın bir neçə subtapşırığa bölünməsi, hansı ki, eyni zamanda icra edilə bilər.
• Sürətləndirmə (Speedup): Ardıcıl alqoritmin yerinə yetirilmə vaxtının paralel alqoritmin yerinə yetirilmə vaxtına nisbəti.
• Effektivlik (Efficiency): Sürətləndirmənin prosessorların sayına nisbəti.
• Genişlənəbilənlik (Scalability): Paralel alqoritmin prosessorların sayını artırmaqla effektiv istifadəsi bacarığı.

Paralel alqoritmlərin üstünlükləri:

• Tapşırığın yerinə yetirilmə sürəti: İşin paralelləşdirilməsi vasitəsilə tapşırıqlar daha sürətli yerinə yetirilir.
• Resursların effektiv istifadəsi: Prosessorların və nüvələrin istifadəsinin optimallaşdırılması.
• İri tapşırıqların həlli: Böyük həcmli məlumatları və mürəkkəb hesablama işlərini həll etmək imkanı, hansı ki bir prosessorda mümkün deyil və ya çox yavaş olur.

Paralel alqoritmlərin zaman mürəkkəbliyi

Paralel alqoritmlərin zaman mürəkkəbliyi bütün paralel subtapşırıqların icra vaxtını və aralarındakı sinxronizasiyanı nəzərə alır. Buna daxildir:

• Nəzəri zaman mürəkkəbliyi: Sonsuz sayda prosessorda ideal icra vaxtı.
• Real zaman mürəkkəbliyi: Prosessorların sayına məhdudiyyətlər və sinxronizasiya üçün əlavə xərcləri nəzərə alaraq icra vaxtı.

Paralel alqoritmlərin məkan mürəkkəbliyi

Paralel alqoritmlərin məkan mürəkkəbliyi hər bir paralel prosesin məlumatlarını və kontekstini saxlamaq üçün lazım olan yaddaş həcmini nəzərə alır. Prosessorlar arasında ünsiyyət üçün əlavə xərclər də nəzərə alınmalıdır.

6.2 Paralel alqoritmə nümunə

Paralel birləşmə sıralaması (Parallel Merge Sort):

Massivi alt massivlərə bölür, onları paralel olaraq sıralayır və sonra birləşdirir.

Zamana görə mürəkkəblik: O(n*log(n)/p), burada n — massiv ölçüsü, p — prosessorların sayı.

from multiprocessing import Pool

def merge_sort_parallel(arr, num_processes=None):
    if len(arr) <= 1:
        return arr
    if num_processes is None:
        num_processes = Pool()._processes
    with Pool(processes=num_processes) as pool:
        size = len(arr) // 2
        left, right = arr[:size], arr[size:]
        left, right = pool.map(merge_sort_parallel, [left, right])
        return merge(left, right)
            
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
            
# İstifadə nümunəsi
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)
            

Amma bizi alqoritmin özü yox, onun «effektivliyinin» analizi daha çox maraqlandıracaq.

6.3 Parallel alqoritmlərin analizi

Əsas konsepsiyalar:

1. Sürətləndirmənin analizi (Speedup):
   • Ardıcıl alqoritmin icra müddətinin paralel alqoritmin icra müddətinə nisbəti.
   • Speedup = T_seq / T_par, burada T_seq — ardıcıl alqoritmin icra müddəti, T_par — paralel alqoritmin icra müddəti.
2. Səmərəlilik (Efficiency):
   • Prosessorların istifadəsinin səmərəliliyinin qiymətləndirilməsi.
   • Efficiency = Speedup / P, burada P — prosessorların sayı.
3. Amdahl Qanunu (Amdahl's Law):
   • Bir vəzifənin paralelizasiyasında əldə edilə biləcək maksimum sürətləndirməni müəyyən edir.
   • Speedup_max = 1 / (S + (1 - S) / P), burada S — vəzifənin ardıcıl hissəsinin nisbəti, P — prosessorların sayı.
4. Gustafson Qanunu (Gustafson's Law):
   • Vəzifənin ölçüsünün dəyişməsi ilə əlaqədar prosessorların sayının artmasına görə sürətləndirməni müəyyən edir.
   • Speedup = P - α * (P - 1), burada P — prosessorların sayı, α — vəzifənin ardıcıl hissəsinin nisbəti.

6.4 Parallel alqoritmlərin nümunələri və onların mürəkkəbliyi

Nümunə 1: Parallel Merge Sort (Paralel birləşmə ilə sıralama)

Təsvir: Parallel Merge Sort massivləri alt massivelərə ayırır, hər bir alt massivi paralel olaraq sıralayır və daha sonra sıralanmış alt massiveləri birləşdirir.

Mürəkkəblik analizi:

• Vaxt mürəkkəbliyi: O((n log n) / P), burada P — prosessorların sayıdır.
• Məkan mürəkkəbliyi: O(n) ara nəticələri saxlamaq üçün.

Nümunə 2: Paralel axtarış (Parallel Search)

Təsvir: Massivdə elementin axtarış tapşırığı bir neçə alt tapşırığa bölünür, hər biri ayrıca prosessorda paralel şəkildə icra edilir.

Mürəkkəblik analizi:

• Vaxt mürəkkəbliyi: O(n / P), burada P — prosessorların sayıdır.
• Məkan mürəkkəbliyi: O(1), əgər eyni massiv istifadə olunursa.

Nümunə 3: Paralel Matris vurma (Parallel Matrix Multiplication)

Təsvir: Matrislər bloklara bölünür və hər bir blok cütü ayrı-ayrı prosessorlarda paralel vurulur.

Mürəkkəblik analizi:

• Vaxt mürəkkəbliyi: O(n^3 / P), burada P — prosessorların sayıdır.
• Məkan mürəkkəbliyi: O(n^2) ara nəticələri saxlamaq üçün.

6.5 Paralel alqoritmlərin reallaşdırılması

Alətlər və kitabxanalar:

1. OpenMP:
   • C, C++ və Fortran üçün kitabxana, çox axınlı tətbiqlərin hazırlanması üçün imkanlar təqdim edir.
2. MPI (Message Passing Interface):
   • Paylanmış sistemlərdə paralel proqramlaşdırma üçün standart, proseslər arasında məlumat mübadiləsini dəstəkləyir.
3. CUDA:
   • NVIDIA tərəfindən təqdim olunan platforma və API, qrafik prosessorlardan (GPU) istifadə edən paralel proqramların hazırlanması üçün.
4. Python-da Threading və multiprocessing:
   • Python-da çox axınlı və çox prosesli proqramlar yaratmaq üçün modullar.

Paralel alqoritmlər vəzifələrin bir neçə prosessor və ya nüvəyə paylanması sayəsində hesablamaları əhəmiyyətli dərəcədə sürətləndirməyə imkan verir. Paralel alqoritmlərin mürəkkəbliyinin təhlili, paralelizasiya zamanı əldə edilə bilən maksimum sürətlənməni başa düşmək üçün Amdahl və Gustafson qanunları daxil olmaqla, sürətlənmə, effektivlik və digər parametrlərin qiymətləndirilməsini əhatə edir.

Paralel alqoritmlər müxtəlif sahələrdə - sıralama və axtarışdan tutmuş mürəkkəb riyazi hesablamalara qədər tətbiq edilir və onların həyata keçirilməsi üçün ixtisaslaşmış alətlərin və kitabxanaların istifadə olunmasını tələb edir.

Vacibdir! Paralel alqoritmlərə çox aludə olmaq sizə lazım deyil. Birincisi, Amdahl qanununa görə, onlar elə də effektiv deyil, göründüyü kimi. İkincisi, hal-hazırda 30 prosessorlu serverlər 3000 sorğu dəqiqədə işləyir və biz hələ də 1 prosessor üçün n vəzifə alırıq, n prosessor üçün 1 vəzifə deyil.

Üçüncüsü, paralelləşmə hesabına sürətləndirilməsi lazım olan real məsələlər artıq GPU-ya (videokartlara) köçüb və onların kodu aşağı səviyyəli dillərdə, məsələn, C-də yazılır.