Елементи теорії паралельних обчислень

Размещено на http://www.allbest.ru/

Елементи теорії паралельних обчислень

План

1. Моделювання і аналіз паралельних обчислень

2. Навчальний приклад обчислення часткових сум послідовності числових значень

3. Оцінка максимально досяжного паралелізму

3.1 Закон Амдаля

3.2 Закон Густавсона-Баріса

1. Моделювання і аналіз паралельних обчислень

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

Модель обчислень у вигляді графа "операції - операнди"

Для опису існуючих інформаційних залежностей в алгоритмах рішення задач, що вибираються, можна використати модель у вигляді графа "операції-операнди". Для простоти вважатимемо, що тривалість виконання будь-яких обчислювальних операцій однакова і дорівнює 1 (одиниця виміру). Приймемо, що передача даних між обчислювальними пристроями виконується миттєво без будь-яких затрат часу (наприклад, за наявності спільної розділеної пам'яті в паралельній обчислювальній системі). Аналіз комунікаційної трудомісткості паралельних алгоритмів приводиться далі.

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

(7.1.1)

де є множиною вершин графа, що є виконуваними операціями алгоритму, а є множиною дуг графа (дуга належить графу тільки в тому випадку, якщо операція не показує результату виконання операції ). Для прикладу на рис. 7.1 показаний граф алгоритму визначення площі прямокутника, заданого координатами двох протилежних кутів. В цьому прикладі, для виконання вибраного алгоритму розв'язку задачі можна використати різні схеми обчислення і побудовані різні обчислювальні моделі. Далі буде показано, що різні схеми обчислень мають різні можливості для розпаралелювання і, тим самим, при побудові моделі обчислень можна поставити задачі вибору обчислювальної схеми алгоритму, що найбільш підходить для паралельного обчислення.

Рис. 7.1. Приклад обчислювальної моделі алгоритму у вигляді графа "операції-операнди"

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

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

Нехай є кількістю процесорів, використовуваних для виконання алгоритму. Тоді для паралельного виконання обчислень слід задати множину (розклад)

, (7.1.2)

в якому для кожної операції вказується номер використовуваного для виконання операції процесора та тривалість виконання операції . Для того щоб розклад міг бути реалізований, необхідно виконання таких вимог при задаванні множини :

1) , тобто один і той же процесор не повинен призначатися різним операціям в один і той же момент часу;

2) , тобто до призначеного моменту виконання операції всі необхідні дані вже повинні бути обчислені.

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

. (7.1.3)

Для вибраної схеми обчислень бажано використання розкладу, який забезпечує мінімальну тривалість виконання алгоритму

. (7.1.4)

Зменшення тривалості виконання можна забезпечити шляхом підбору найкращої обчислювальної схеми

. (7.1.5)

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

. (7.1.6)

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

, (7.1.7)

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

, (7.1.8)

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

, (7.1.9)

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

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

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

. (7.1.10)

Теорема 2. Нехай для деякої вершини виведення в обчислювальній схемі алгоритму існує шлях з кожної вершини введення. Крім того, нехай вхідна ступінь вершин схеми (кількість вхідних дуг) не перевищує 2. Тоді мінімально можлива тривалість виконання паралельного алгоритму обмежена знизу значенням

, (7.1.11)

де - кількість вершин введення в схемі алгоритму.

Теорема 3. При зменшенні кількості використовуваних процесорів тривалість виконання алгоритму збільшується пропорційно величині зменшення кількості процесорів, тобто

паралельний обчислення амдаль густавсон

. (7.1.12)

Теорема 4. Для будь-якої кількості використовуваних процесорів справедлива така верхня оцінка для тривалості виконання паралельного алгоритму

. (7.1.13)

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

. (7.1.14)

При меншій кількості процесорів тривалість виконання алгоритму може перевищувати більш ніж в 2 рази найкращу тривалість обчислень при наявній чисельності процесорів, тобто

. (7.1.15)

Наведені твердження дають змогу дати наступні рекомендації з правил формування паралельних алгоритмів: при виборі обчислювальної схеми алгоритму повинен використовуватися граф з мінімально можливим діаметром; для паралельного виконання доцільна кількість процесорів визначається величиною ~ ; тривалість виконання паралельного алгоритму обмежується зверху величинами, наведеними в теоремах 4 та 5.

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

(7.1.16)

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

Ефективність (efficiency). використання паралельним алгоритмом процесорів при розв'язку задачі визначається співвідношенням

, (7.1.17)

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

1). За певних обставин прискорення може виявитися більша чисельність використовуваних процесорів - в цьому випадку кажуть про існування понад лінійного (superliner) прискорення. На практиці понад лінійне прискорення можливе. Однією з причин цього може бути неоднорідність умов виконання послідовної та паралельної програм. Так за умови розв'язку задачі на одному процесорі виявляється недостатньо оперативної пам'яті для зберігання всіх оброблюваних даних, тоді стає необхідним використання більше повільної зовнішньої пам'яті (у випадку використання кількох процесорів оперативної пам'яті може виявитися достатньо за рахунок розділення даних між процесорами). Ще однією причиною понад лінійного прискорення може бути нелінійний характер залежності складності рішення задачі від об'єму оброблюваних даних. Так, наприклад, відомий алгоритм бульбочкового сортування характеризується квадратичною залежністю кількості необхідних операцій від числа впорядкованих даних. Як результат, при розподілі сортувального масиву між процесорами може бути отримано прискорення, що перевищує чисельність процесорів. Джерелом понад лінійного прискорення може бути також відмінність обчислювальних схем послідовного та паралельного методів.

2) При уважному аналізуванні можна звернути увагу, що спроби підвищення якості паралельних обчислень за одним з показників (прискоренню чи ефективності) можуть призвести до погіршення ситуації за другим показником, оскільки показники якості паралельних обчислень часто суперечливі. Так, наприклад, підвищення прискорення може бути забезпеченим за рахунок збільшення чисельності процесорів, що призводить, як правило, до падіння ефективності. І навпаки, підвищення ефективності досягається в багатьох випадках при зменшенні чисельності процесорів (в граничному випадку ідеальна ефективність легко забезпечується в разі використання одного процесора). Як результат, розробка методів паралельних обчислень часто передбачає вибір певного компромісного варіанту з врахуванням бажаних показників прискорення та ефективності.

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

.= (7.1.18)

В зв'язку з цим можна означити поняття вартісно-оптимального (cost-optimal) паралельного алгоритму як методу, вартість якого пропорційна тривалості виконання найкращого паралельного алгоритму.

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

2. Навчальний приклад обчислення часткових сум послідовності числових значень

Розглянемо задачу знаходження часткових сум послідовності числових значень

, (7.1.19)

де - кількість підсумованих значень (назва задачі - prefix sum problem) . Вивчення можливих паралельних методів розв'язку цієї задачі здійснимо на основі більш простого варіанту її постановки - з задачі обчислення загальної суми наявного набору значень (частковий випадок загальної задачі редукції)

. (7.1.20)

Послідовний алгоритм знаходження суми. Традиційний алгоритм розв'язку цієї задачі полягає в послідовності знаходження суми елементів числового набору

, (7.1.21)

(7.1.22)

Обчислювальну схему цього алгоритму можна подати наступним чином, рис. 7.2:



Рис. 7.2. Послідовна обчислювальна схема алгоритму знаходження суми

, (7.1.23)

де є множиною операцій (вершини означають операції введення, кожна вершина , відповідає добавленню значення до накопичуваної суми ) а

(7.1.24)

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

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

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

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



Рис. 7.3. Каскадна схема алгоритму знаходження суми

Цю обчислювальну схему можна визначити як граф (нехай )

, (7.1.25)

де є вершини графа (- операції введення, - операції знаходження суми першої ітерації, і т.д.) а множина дуг графа визначається співвідношеннями:

. (7.1.26)

Нескладно оцінити, кількість ітерацій каскадної схеми , яка виявляється рівною величині

, (7.1.27)

а загальна кількість операцій знаходження суми

(7.1.28)

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

. (7.1.29)

Оскільки вважається, що тривалість виконання будь-яких операцій однакова і одинична, то , тому показники прискорення та ефективності каскадної схеми алгоритму знаходження суми можна оцінити, як

, (7.1.30)

, (7.1.31)

де - необхідна чисельність процесорів для виконання каскадної схеми.

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

за умови .

Модифікована каскадна схема. Отримання асимптотичної ненульової ефективності можна забезпечити в разі використання модифікованої каскадної схеми. Для спрощення побудови оцінок можна припустити . Тоді в новому варіанті каскадної схеми всі обчислення виконуються в два послідовно виконуваних етапи знаходження суми, рис. 7.4:



Рис. 7.4. Модифікована каскадна схема знаходження суми

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

- на другому етапі для отриманих сум окремих груп застосовується звичайна каскадна схема.

Тоді для виконання першого етапу потрібно паралельних операцій з використанням процесорів. Для виконання другого етапу необхідно

(7.1.32)

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

. (7.1.33)

З врахуванням отриманих оцінок показники прискорення та ефективності модифікованої каскадної схеми визначаються співвідношеннями:

, (7.1.34)

. (7.1.35)

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

за умови .

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

(7.1.36)

пропорційна тривалості виконання послідовного алгоритму.

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

.

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

- перед початком обчислень створюється копія вектора значень суми (;

- далі на кожній ітерації сумування , формується допоміжний вектор шляхом зсуву праворуч вектор на позицій (які вивільняються при зсуві позиції ліворуч встановлюються в нульове значення); ітерація алгоритму завершується паралельною операцією знаходження суми векторів та .

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

(7.1.38)

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

Рис. 7. 5. Схема паралельного алгоритму обчислення всіх часткових сум (величини означають суми значень від до елементів числової послідовності)

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

. (7.1.39)

. (7.1.40)

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

3. Оцінка максимально досяжного паралелізму

Оцінка якості паралельних обчислень передбачає знання найкращих (максимально досяжних) значень показників прискорення та ефективності, проте отримання ідеальних величин для прискорення та для ефективності може бути забезпечено не для всіх обчислювальних трудомістких задач. Так. для учбового прикладу, що розглядається, мінімально досяжний час паралельного обчислення суми числових значень складає . Корисними для розв'язку цієї задачі можуть бути теоретичні твердження наведені вище. Розглянемо також закономірності, корисні при побудові оцінок максимально досяжного паралелізму.

3.1 Закон Амдаля

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

. (7.1.41)

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

Закон Амдаля характеризує одну з самих серйозних проблем в галузі паралельного програмування (алгоритмів без певної частки послідовних команд практично не існує). проте часто часка послідовних дій характеризує не можливість паралельного рішення задач, а послідовні властивості застосовуваних алгоритмів. Тому частка послідовних обчислень може бути істотно знижена при виборі методів, придатніших для розпаралелювання

Розгляд закону Амдаля відбувається в припущенні, що частка послідовних розрахунків є сталою величиною і не залежить від параметра , який визначає обчислювальну складність розв'язуваної задачі. Проте для великого ряду задач частка є спадною функцією від , і в цьому випадку прискорення для фіксованої кількості процесорів може бути збільшено за рахунок збільшення обчислювальної складності розв'язуваної задачі. Проте для більшості задач частка є спадною функцією від , і в цьому випадку прискорення для фіксованої кількості процесорів може бути збільшено за рахунок збільшення обчислювальної складності розв'язуваної задачі. Це зауваження можна сформулювати як твердження, що прискорення є зростаючою функцією від параметра (це твердження називається ефектом Амдаля). Так, в навчальному прикладі, обчислення суми значень при використанні фіксованої чисельності процесорів сумарний набір даних може бути розділений на блоки розміру , для яких спочатку паралельно можна обчислити часткові суми, а далі ці суми можна скласти з використанням каскадної схеми. Тривалість послідовної частини виконуваних операцій (мінімально можлива тривалість паралельного виконання) в цьому випадку складає

, (7.1.42)

що призводить до оцінки частки послідовних розрахунків як величини

. (7.1.43)

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

3.2 Закон Густавсона-Баріса

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

, (7.1.44)

де та - тривалість послідовної та паралельної частин виконуваних обчислень, відповідно, тобто

, . (7.1.45)

З врахуванням введеної величини можна отримати

, , (7.1.46)

що дає змогу побудувати оцінку для прискорення

, (7.1.47)

яка після спрощення приводиться до типу закону Густавсона-Барсіса (Gustafson - Barsis's law)

. (7.1.48)

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

, (7.1.49)

що відповідає послідовній частці

. (7.1.50)

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

При розгляді закону Густавсона-Барсіса слід враховувати те, що із збільшенням чисельності використовуваних процесорів темп зменшення тривалості паралельного розв'язку задач може спадати (після перевищення певного порогу). Проте за рахунок зменшення тривалості обчислень складність розв'язуваних задач може бути збільшена (для навчальної задачі підсумовування може бути збільшений розмір набору значень, що складається). Оцінку отримуваного при цьому прискорення можна визначити з використанням сформульованих закономірностей. Така аналітична оцінка корисна, оскільки розв'язок складніших варіантів задач на одному процесорі може виявитися достатньо трудомістким, навіть неможливим, наприклад, в силу нехватки оперативної пам'яті. З врахуванням цих обставин оцінку прискорення, отримувану у відповідності з законом Густавсона-Барсіса , ще називають прискоренням масштабування (scaled speedup), оскільки ця характеристика може показати, наскільки ефективно можна організувати паралельні обчислення при збільшенні складності розв'язуваних задач.

Размещено на Allbest.ru

...