Наявність послідовних частин коду. Закон амдаля і його наслідки.

Нехай f - це частка послідовних обчислень, 0< f <1. Максимальне прискорення S, досяжне на обчислювальній системі з P процесорів, можна оцінити за допомогою наступної формули, закона Амдала:

S (7.1)

 

Закон Амдала має наступні наслідки: Завжди при будь-якому скільки завгодно великому числі процесорів, незалежно від якості реалізації паралельної частини коду.

S < . (7.2)

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

f , (7.3)

тобто якщо, наприклад, необхідно на 10 процесорах дістати прискорення в 9 разів, то необхідно, щоб 99 % коду виконувалося паралельно (f 1.2 %).

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

Наприклад, якщо, треба вірішити задачу, якого прискорення можна досягти при збільшенні швидкості виконання комунікаційних операцій в 10 разів, якщо в даний момент комунікації займають 20% часу, то згідно з законом Амдала, рішення буде:

S=1/(0,2/10+0,8)=1,25

 

Хід роботи:

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

 

Таблиця 7.1

Варіанти для виконання лабораторної роботи

 

№ Варіанта	Число процесорів	Процент послідовного коду, %
					50

Контрольні запитання:

1. Закон Амдала. Ефективність використання процесорів, ступінь паралелізму.

2. У чому полягає суть закону Амдала? Що таке прискорення?

3. Сформулюйте слідство із закону Амдала.

4. Що показує графік залежності коефіцієнта прискорення від числа процесорів і ступеню паралелізму алгоритму.

5. У вас є програма і доступ, до 256-процесорного комп'ютера. Чи виконуватиметься програма в 256 разів швидше, ніж на одному процесорі?

6. У якому випадку не можливо отримати 50% прискорення роботи програми?

Лабораторна робота №8. Багатозадачний режим роботи комп’ютерної системи.

Мета: Організація багатозадачного режиму комп’ютерних систем за допомогою матричного множення.

Теоретичні відомості

Завдання множення матриці на матрицю, обчислюється співвідношенням (8.1):

(8.1)

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

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

Інший широко використовуваний підхід для побудови паралельних способів виконання матричного множення, полягає у використанні блокового представлення матриць, при якому початкові матриці A і B і результуюча матриця С, розглядаються у вигляді наборів блоків, як правило квадратного виду деякого розміру m×n. Тоді операцію множення матриць А і В, у блочному виді можливо представити наступним чином(8.2):

А₁₁ А₁₂ … А_1к В₁₁ В₁₂ … В_1к С₁₁ С₁₂ … С_1к

_{... ×... =...} (8.2)

А_к1 А_к2 … А_кк В_к1 В_к2 … В_кк С_к1 С_к2 … С_кк

 

де кожен блок С_ij, матриці С, визначається відповідно до виразу (8.3):

(8.3)

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

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

У системі Paralab, реалізовані паралельний алгоритм множення матриць при стрічковій схемі розділення даних і два методи, алгоритм Фокса і Кеннона, для блоково-представлених матриць.

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

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

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

 

Хід роботи:

1. Реалізуйте за допомогою системи Paralab, задачу матричного множення при стрічковій схемі, і пропускної здатністю мережі – 1Гбіт.

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

3. До звіту внесіть графік залежності часу від розмірів масиву.

 

Таблиця 7.1

Варіанти для виконання лабораторної роботи

 

№ Варіанта	Топологія	Число вузлів	Латентність
	Решітка
	Кільце
	Повний граф
	Решітка
	Кільце
	Повний граф
	Решітка
	Кільце
	Повний граф
	Решітка
	Кільце
	Повний граф		120

Контрольні запитання:

1. Поясніть яким чином проводиться паралельне обчислювання матриць.

2. Поясніть на що впливає латентність у обчислюванні множення матриць.

3. Які методи паралельного обчислювання матриць ви знаєте? У чому полягає їх суть.

4. Що таке стрічкова схема обчислювання матриць.

5. Опишіть алгоритми Фокса і Кеннона.

 

 

Рекомендована література.

1. Хорошевский В.Г. Архитектура вычислительных систем.

2. Столлінгс У. «Структурная организация и архитектура компьютерных систем.» М, СПб, Київ, «Вільямс», 2002.

3. Бройдо В.Л. «Вычислительные системы, сети и телекоммуникации.» - С-П: Пітер, 2002.

4. Столінгс В. «Компьютерные системы передачи данных». - С-П: Пітер, 2002.

5. Таненбаум Е. «Компьютерные сети». - С-П: Пітер, 2002.

6. Таненбаум Е. «Архитектура компьютеров». - С-П: Пітер, 2002.

 

 

Рибалов Б.О., Лозович О.М.

КОМП’ЮТЕРНІ СИСТЕМИ