Оцінки прискорення. Закони Амдаля і Густавсона - Барсіса
Раніше отримані оцінки для часу рішення задачі при використанні p процесорів. При цьому передбачалося, що завдання можна розділити на модулі, задавши граф залежностей, що визначає можливий порядок виклику модулів. Цікавим є розгляду випадку, коли завдання можна розділити на дві частини, з яких одна частина вимагає послідовного виконання, а друга може бути повністю распараллелена. Закони Амдаля і Густавсона - Барсіса дозволяють отримати оцінки для прискорення в залежності від частки послідовних обчислень в загальному часу рішення задачі. Закони відрізняються лише тим, як визначається частка послідовних обчислень.
закон Амдаля
Нехай час виконання завдання одним процесором можна уявити як суму часів вирішення послідовної частини і частини, що допускає розпаралелювання:
Розділивши обидві частини рівняння на, перейдемо до часткам часу:
Час виконання завдання p процесорами також представимо двома частинами:
Послідовну частку не можна зменшити збільшенням числа процесорів, тому. Для паралельної частини існує оцінка, так що має місце співвідношення:
Переходячи до прискорення, отримаємо:
Співвідношення (30) називається законом Амдаля. Воно говорить, що прискорення обмежена зверху величиною, яка від частки послідовних обчислень. Якщо, наприклад, послідовні обчислення займають 10% від загального часу обчислення, то за рахунок розпаралелювання не можна домогтися більш ніж десятикратного прискорення часу роботи, як багато процесорів б не залучалося.
Песимістичний характер закону Амдаля може бути згладжений, якщо згадати, що всі характеристики слід розглядати, як функції від n - параметра характеризує обсяг використовуваних даних. У цьому випадку закон Амдаля виглядає так:
На практиці часто буває, що послідовна частина завдання постійна і не залежить від обсягу даних. В цьому випадку q (n) - спадна функція, тоді для великих n можна домогтися гарного прискорення, не вступаючи в суперечність з законом Амдаля.
Закон Густавсона -Барсіса
Запишемо оптимальний час роботи при використанні p процесорів у вигляді суми часів двох частин - паралельної і послідовної:
З урахуванням того, що послідовна частина виконується p процесорами так само довго, як одним процесором, а час паралельної частини в оптимальному випадку можна зменшити в p разів, отримаємо:
Розділивши обидві частини рівняння на, перейдемо до часткам часу:
Розглянемо тепер відношення:
Два способи розпаралелювання
Говорячи про розпаралелювання, розрізняють два основних способи, що дозволяють проводити паралельні обчислення, - розпаралелювання за завданнями і розпаралелювання за даними.
Модель, розглянута вище, відповідала нагоди розпаралелювання за завданнями. У цій моделі різні модулі однієї програми могли виконуватися паралельно.
Розглянемо тепер альтернативну ситуацію, коли виконується розпаралелювання за даними. В цьому випадку деякий безліч даних необхідно обробити одним модулем.
Розпаралелювання за даними
Нехай необхідно вирішити задачу D на деякому кінцевому безлічі даних. Найчастіше, ефективний послідовний алгоритм вирішення цієї задачі можна отримати, якщо вдається звести рішення вихідної задачі до вирішення k подзадач -, де кожна подзадача означає рішення вихідної завдання D. але на підмножині даних. Найбільш ефективно, коли все підзадачі мають один і той же розмір.
Справедлива проста, але вкрай важлива в теорії алгоритмів
Якщо завдання D (X) можна звести до вирішення k подзадач однаковою розмірності і за лінійний час з рішень k подзадач можна отримати спільне рішення вихідної задачі, то тимчасова складність вирішення вихідної задачі T (n) дається формулою: