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

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

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

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

(2.1.1)

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

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

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

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

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

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

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

,

(2.1.2)

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

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

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

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

.

(2.1.3)

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

.

(2.1.4)

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

.

(2.1.5)

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

.

(2.1.6)

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

,

(2.1.7)

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

,

(2.1.8)

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

,

(2.1.9)

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

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

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

.

(2.1.10)

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

,

(2.1.11)

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

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

.

(2.1.12)

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

.

(2.1.13)

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

.

(2.1.14)

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

.

(2.1.15)

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

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

(2.1.16)

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

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

,

(2.1.17)

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

1). За певних обставин прискорення може виявитися більша чисельність використовуваних процесорів - в цьому випадку кажуть про існування понад лінійного (superliner) прискорення.

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

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

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

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

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

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

.=

(2.1.18)

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

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

Література

1. Бурков А.В. Проектирование информационных систем по технологии клиент – сервер в «Microsoft SQL Server 2008» и «Microsoft Visual Studio 2008» 194с.

2. Бучек Г.ASP.NET. Учебный курс — СПб.: Питер, 2002. — 512 с.: ил.

3. Вийера Р. Програмирование баз данных Microsoft SQL Server 2005 для профессионалов / Р. Вийера // 2008. 256с.

4. Волоха А. В. Microsoft SQL Server 2005. Новые возможности. — СПб.: Питер, 2006. — 304 с.: ил.

5. Дж.Боуман, С.Эмерсон, М.Дарновски - Практическое руководство по SQL

6. Станек Уильям Р. Microsoft SQL Server 2005. Справочник администратора / Пер. с англ. — М.: Издатель ство «Рус ская Ре дак ция», 2008. — 544 с.: ил.

Дата добавления: 2014-01-04