Паралельні алгоритми та їх складність

6.1 Паралельні алгоритми.

Паралельні алгоритми призначені для виконання на багатопроцесорних або багатопоточних системах з метою прискорення обчислень. Вони ділять задачу на незалежні підзадачі, які виконуються одночасно. Аналіз складності паралельних алгоритмів вимагає урахування як часової, так і просторової складності, а також таких факторів, як прискорення, ефективність і масштабованість.

Основні концепції паралельних алгоритмів:

• Паралелізм: Поділ задачі на декілька підзадач, які можуть виконуватись одночасно.
• Прискорення (Speedup): Відношення часу виконання послідовного алгоритму до часу виконання паралельного алгоритму.
• Ефективність (Efficiency): Відношення прискорення до кількості процесорів.
• Масштабованість (Scalability): Здатність паралельного алгоритму ефективно використовувати збільшуючу кількість процесорів.

Переваги паралельних алгоритмів:

• Прискорення виконання: Виконання завдань швидше завдяки розпаралелюванню роботи.
• Ефективне використання ресурсів: Оптимізація використання процесорів та ядер.
• Рішення великих задач: Можливість обробки великих об’ємів даних та складних обчислень, які неможливі або дуже повільні на одному процесорі.

Часова складність паралельних алгоритмів:

Часова складність паралельних алгоритмів вимірюється з урахуванням часу, витраченого на виконання всіх паралельних підзадач і синхронізацію між ними. Вона включає в себе:

• Теоретична часова складність: Ідеальний час виконання на нескінченній кількості процесорів.
• Реальна часова складність: Час виконання з урахуванням обмежень на кількість процесорів та накладних витрат на синхронізацію.

Просторова складність паралельних алгоритмів

Просторова складність паралельних алгоритмів враховує об’єм пам’яті, необхідної для зберігання даних та контексту кожного паралельного процесу. Важливо також враховувати накладні витрати на комунікацію між процесорами.

6.2 Приклад паралельного алгоритму

Паралельне сортування злиттям (Parallel Merge Sort):

Ділить масив на підмасиви, сортує їх паралельно і потім зливає.

Часова складність: O(n*log(n)/p), де n — розмір масиву, p — кількість процесорів.

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
            
# Приклад використання
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)
            

Але нам буде цікавий не сам алгоритм, а аналіз його «ефективності».

6.3 Аналіз паралельних алгоритмів

Основні концепції:

1. Аналіз прискорення (Speedup):
   • Відношення часу виконання послідовного алгоритму до часу виконання паралельного алгоритму.
   • Speedup = T_seq / T_par, де T_seq — час виконання послідовного алгоритму, T_par — час виконання паралельного алгоритму.
2. Ефективність (Efficiency):
   • Оцінка ефективності використання процесорів.
   • Efficiency = Speedup / P, де P — кількість процесорів.
3. Закон Амдала (Amdahl's Law):
   • Визначає максимальне прискорення, яке можна досягти при паралелізації задачі.
   • Speedup_max = 1 / (S + (1 - S) / P), де S — частка послідовної частини задачі, P — кількість процесорів.
4. Закон Густафсона (Gustafson's Law):
   • Визначає прискорення з урахуванням зміни розміру задачі при збільшенні кількості процесорів.
   • Speedup = P - α * (P - 1), де P — кількість процесорів, α — частка послідовної частини задачі.

6.4 Приклади паралельних алгоритмів та їх складність

Приклад 1: Паралельне сортування злиттям (Parallel Merge Sort)

Опис: Паралельне сортування злиттям ділить масив на підмасиви, сортує кожен підмасив паралельно, а потім зливає відсортовані підмасиви.

Аналіз складності:

• Часова складність: O((n log n) / P), де P — кількість процесорів.
• Просторова складність: O(n) для зберігання проміжних даних.

Приклад 2: Паралельний пошук в масиві (Parallel Search)

Опис: Задача пошуку елемента в масиві ділиться на кілька підзадач, кожна з яких виконується паралельно на окремому процесорі.

Аналіз складності:

• Часова складність: O(n / P), де P — кількість процесорів.
• Просторова складність: O(1), якщо використовується той же масив.

Приклад 3: Паралельне множення матриць (Parallel Matrix Multiplication)

Опис: Матриці діляться на блоки, і кожна пара блоків множиться паралельно на різних процесорах.

Аналіз складності:

• Часова складність: O(n^3 / P), де P — кількість процесорів.
• Просторова складність: O(n^2) для зберігання проміжних результатів.

6.5 Реалізація паралельних алгоритмів

Інструменти та бібліотеки:

1. OpenMP:
   • Бібліотека для C, C++ і Fortran, що надає засоби для розробки багатопотокових додатків.
2. MPI (Message Passing Interface):
   • Стандарт для паралельного програмування на розподілених системах, підтримуючи обмін повідомленнями між процесами.
3. CUDA:
   • Платформа та API від NVIDIA для розробки паралельних програм, що використовують графічні процесори (GPU).
4. Threading та multiprocessing у Python:
   • Модулі для створення багатопоточних та багатопроцесних програм у Python.

Паралельні алгоритми дозволяють значно прискорити обчислення за рахунок розпаралелювання задач на кілька процесорів або ядер. Аналіз складності паралельних алгоритмів включає оцінку прискорення, ефективності та використання законів Амдала і Густафсона для розуміння максимального прискорення, досягнутого при паралелізації.

Паралельні алгоритми знаходять застосування в різних сферах, від сортування та пошуку до складних математичних обчислень, і вимагають використання спеціалізованих інструментів та бібліотек для їх реалізації.

Важливо! Тобі не потрібно захоплюватися паралельними алгоритмами.

По-перше, через закон Амдала, вони не так сильно ефективні як здається.

По-друге, зараз сервери з 30 процесорами обробляють по 3000 запитів на хвилину, і ми все одно маємо n задач на 1 процесор, а не 1 задачу для n процесорів.

По-третє, реальні задачі, що потрібно прискорити за рахунок багатопроцесорності, всі переїхали на GPU (відеокарти), і їх код пишуть на низькорівневих мовах типу С.