Інші моделі паралельного програмування

Передача повідомлень

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

 

Паралелізм даних

Ця модель заснована на застосуванні однієї операції до множини елементів структури даних.

Моделі програмування відрізняються гнучкістю, механізмами взаємодії між задачами, рівнем паралелізму і «зернистістю», масштабованістю, підтримкою модульності і т. д.

В моделі паралелізму даних «зернистість» обчислень мала, оскільки кожна операція над кожним елементом даних може обчислюватись незалежною задачею. Програміст повинен указати транслятору, як дані слід розподіляти між процесорами (між задачами).

 

Модель пам’яті, що розділяється

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

 

Лекція №2

Закон Амдала

За допомогою інформаційного графа можна оцінити максимальне прискорення, якого можна досягти при розпаралелюванні алгоритму там де це можливо. Допустимо, що програма виконується на машині, архітектура якої ідеально відповідає структурі інформаційного графа програми. Нехай час виконання алгоритму на послідовній машині Т₁:

T_s – час виконання послідовної частини алгоритму

Т_р – час виконання паралельної частини алгоритму

При виконанні тієї ж програми на ідеальній паралельній машині, N незалежних гілок паралельної частини розподіляються на N процесорів, тому час виконання цієї частини зменшується до величини , а повний час виконання програми складає:

Коефіцієнт прискорення, який показує в скільки разів швидше програма виконається на паралельній машині, ніж на послідовній визначається формулою:

S i P відносні частки (долі) послідовної і паралельної частини

 

Рис 2.1 Графік залежності коефіцієнта прискорення від числа процесорів і ступенів паралелізму алгоритма

Ця залежність називається законом Амдала.

Наведемо різні кількісні характеристики паралелізму. Ефективне використання процесорів характеризується величиною

В ідеальній ситуації K=N; E=1

Але на практиці це значення ефективності недосяжне.

Ступенем паралелізму називається кількість процесорів, що використовуються в кожен момент часу для виконання програми. Ступінь паралелізму може змінюватись в процесі виконання програми.

 

Дві парадигми паралельного програмування

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

 

Паралелізм даних

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

1) Операції керування даними

2) Операції над масивами в цілому, а також їх фрагментами

3) Умовні операції

4) Операції приведення

5) Операції зсуву

6) Операції сканування

7) Операції, що пов’язані з пересилкою даних.

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

1) Препроцесори

2) Предтранслятори

3) Транслятори, що розпаралелюють

 

Лекція №3

Паралелізм задач

Метод програмування заснований на паралелізмі задач передбачає розбиття обчислювальної задачі на декілька відносно самостійних під задач. Кожна під задача виконується на своєму процесорі. Для кожної під задачі пишеться своя власна програма на звичайній мові програмування (С або Fortran). Під задачі повинні обмінюватись результатами своєї роботи, отримувати вихідні дані. Практично такий обмін здійснюється викликом процедур спеціалізованої бібліотеки. Програміст при цьому може контролювати розподіл даних між різними процесами і під задачами, а також обмін даними.

Прикладом спеціалізованої бібліотеки є MPI (Message Passing Interface) і PVM (Parallel Virtual Machine). Ці бібліотеки розповсюджуються вільно і існують у вихідних кодах.