Для визначення точних характеристик
системи врахуємо співвідношення часових
параметрів (згідно з завданням). Насамперед,
зведемо часи виконання різних операцій
до спільного знаменника, тобто визначимо
базову операцію для знаходження часів
виконання інших операцій. Згідно завдання:
Tu = 10Ts = 1Tp = 5Tz = 6Tw.
Виразимо інші операції через
найменший час Ts:
,
,
,
2.1. Послідовне виконання
Оскільки кожен процесор завантажує
дані послідовно, то кількість результуючих
послідовних операцій завантаження буде
рівна сумі часів завантаження усіх процесорів.
Отже в даному випадку кількість операцій
завантаження.
Час завантаження:
TZ =N1*N2 + N2*N3 = (210*72+72*67)
*2* ts= 39888 * ts
Після операції завантаження
початкових даних в процесори запускається
цикл обробки даних, який включає в себе
як множення підматриць, так і пересилання
даних між процесорами.
Для послідовного алгоритму
загальна кількість операцій множення
та додавання буде рівна:
Час множення:
TU = N1*N2*N3 = (210*72*67)*10
* ts = 10130400 * ts
Час додавання:
TS = N1*(N2-1)*N3 = (210*71*67)
* ts= 998970* ts
Після виконання всіх кроків
в пам'яті кожного з процесорів отримуємо
результуючу часткову підматрицю. Отже
необхідно зібрати всі підматриці з кожного
процесора в загальну пам'ять результуючої
матриці С.
Вивантаження даних відбувається
в послідовному режимі. Звідси – кількість
операцій вивантаження буде рівна кількості
елементів результуючої матриці С.
Час вивантаження:
TW = N1*N3= (210*67)*10/6 * ts=23450*ts
Час пересилання даних не враховуємо,
оскільки для послідовних обчислень пересилання
на кільцевій структурі не відбувається. Для
обчислення загального часу виконання
множення матриць необхідно додати всі
знайдені часи.
Загальний час виконання послідовної
частини:
ТПОС = TZ + TU + TS + TW =(39888 + 10130400 + 998970 + 23450)
* ts =
= 11192708*ts
2.2. Паралельне виконання
Оскільки кожен процесор завантажує
дані паралельно, то кількість результуючих
послідовних операцій завантаження буде
рівна найбільшій кількості таких операцій
виконаних певним процесором. Очевидно,
що найдовше завантажуватиме саме 7-8-ий
процесор, оскільки розміри його вхідних
підматриць найбільші.
Час завантаження:
TZ =27*N2 + N2*9 = (27*72+72*9)
*2* ts= 5184 * ts
Після операції завантаження
початкових даних в процесори запускається
цикл обробки даних, який має 8 ітерацій,
які включають в себе як множення підматриць,
так і пересилання даних між процесорами
(підматриці Ві).
Загальний час виконання операцій
множення та додавання на чотирьох ітераціях
з врахуванням того, що найдовше буде виконуватись
частина, де кількість рядків підматриці
A=27, а кількість стовпців під матриці B=9
буде рівний:
TU1 =27*N2*9 = (27*72*9)
*10* ts= 174960 * ts
TS1 =27*(N2-1)*9 = (27*(72-1)*9)
*ts= 17253 * ts
Загальний час виконання операцій
множення та додавання на інших чотирьох
ітераціях з врахуванням того, що найдовше
буде виконуватись частина, де кількість
рядків підматриці A=26, а кількість стовпців
під матриці B=9 буде рівний:
TU2 =26*N2*9 = (26*72*9)
*10* ts= 168480 * ts
TS2 =26*(N2-1)*9 = (26*(72-1)*9)
*ts= 16614 * ts
Сумарна кількість операцій
множення та додавання:
Час множення:
TU = TU1*4+TU2*4= 4*(174960+168480)
* ts= 1373760 * ts
Час додавання:
TS = TS1*4+TS2*4= 4*(17253+16614)
* ts= 135468 * ts
Кількість операцій обміну
(включає посилання та прийом даних) на
кожній ітерації рівна кількості елементів
найбільшої з підматриць Ві, тобто 72х9:
TP1 =72*9*10* ts = 6480 * ts
Тоді загальна кількість операцій
обміну буде рівна сумі таких операцій
на семи ітераціях:
Час пересилання:
TP = TP1*7= 45360 * ts
Після виконання восьми ітерацій
в пам'яті кожного з процесорів отримуємо
результуючу часткову підматрицю Сі. Отже
необхідно зібрати всі підмасиви Сі з
кожного процесора в загальну пам'ять
результуючої матриці С. Вивантаження
даних відбувається в послідовному режимі
з першого процесора у 8 етапів.
На першому етапі вивантажується
частковий результат C1 на першому процесорі,
в той же час паралельно пересилаються
решта інших часткових результатів по
кільцю процесорів. На другому етапі вивантажується
той частковий результат, який на попередньому
етапі був пересланий в процесор P1 і знову
паралельні дані пересилаються по кільцю.
Такий алгоритм продовжується 8 ітерацій,
кожна з яких має свої особливості.
Детальний опис етапів:
1-6. Оскільки час вивантаження
є меншим за час пересилання (tP=6tw), то найдовше
буде виконуватись пересилання часткового
результату розміром 27х67:
TW1-6 =6*27*67*10* ts = 108540 * ts
7. Оскільки час вивантаження
є меншим за час пересилання (tP=6tw), то найдовше
буде виконуватись пересилання часткового
результату розміром 26х67:
TW7=26*67*10* ts = 17420 * ts
8. На цьому етапі виконується
тільки вивантаження часткового
результату:
TW8=26*67*10/6* ts = 2904 * ts
Час вивантаження:
TW = TW1-6 +TW7 +TW8= 108540 * ts +17420 * ts +2904 * ts = 128864* ts
Для визначення повного часу
необхідно визначити час всіх його складових,
де операції виконуються послідовно (вивантаження)
та паралельно (завантаження, обчислення,
обмін даними).
Загальний час виконання паралельної
частини:
ТПАР = TZ +TU +TS +TP +TW=5184 * ts+1373760 * ts+135468 * ts+45360 * ts+128864* ts=1688636* ts
ТПОС/ТПАР = 11192708*ts/1688636* ts=6,6.
Порівнюючи останні результати
бачимо, що перемноження однакових матриць
на одному процесорі приблизно в 6,6 разів
повільніше за множення на восьмипроцесорній
системі на основі кільцевої топології.
Для характеристики алгоритму
визначимо коефіцієнт К, який рівний відношенню
часу виконання загального алгоритму
до часу виконання паралельних операцій.
K = ТПАР /( TZ +TU +TS +TP) = 1688636* ts / (5184 * ts+1373760 * ts+135468 * ts+45360 * ts)=1,08.
Ефективність визначається
як відношення часу виконання задачі на
однопроцесорній системі, до часу потрібного
на виконання для багатопроцесорної на
кількість процесорів в ній.
E= TПОС / (ТПАР * Р) = 11192708* ts / (1688636* ts * 8)= 0,82.
3. Реалізація заданого
алгоритму
Завдання №2
3.1. Блок-схема роботи
програми
Алгоритм виконання роботи
програми розпочинається з відведення
пам'яті під матриці A, B, C. Далі програма
генерує елементи матриць А і В і записує
їх у файл Data. У файл PartData записуються підматриці
матриць A і В, які були утворені під час
виконання програми. Проводиться множення
підматриць і отримання часткових результатів,
а потім їхній збір. Вивід отриманого результату
перемноження матриць у файл Result. Завершення
роботи програми.
Блок-схема роботи програми
наведена на рис. 6.
Рис. 6. Загальна блок-схема програми.
3.2. Вибір середовища
Дана програма написана на мові
C++. Для розробки самого параллельного
алгоритму множення матриць було обрано
шлях використання інтерфейсу передачі
повідомлень (МРІ) між процесами, оскільки
він має наступні можливості:
- створення програм багатопроцесорної
обробки інформації;
- велика кількість функцій
для обміну повідомленнями між
процесами;
- синхронізація роботи
процесів;
- готова програмна реалізація
для платформи Windows та Microsoft Visual
Studio 2008 в якості бібліотеки
msmpi.lib.
МРІ (Message Passing Interface) - програмний
інтерфейс (API) для передачі інформації,
який дозволяє обмінюватися повідомленнями
між процесами, що виконують одну задачу. Розроблений
Вільямом Гроуппом, Евін Ласко та іншими.
MPI є найбільш поширеним стандартом інтерфейсу
обміну даними в паралельному програмуванні,
існують його реалізації для великого
числа комп'ютерних платформ. Використовується
при розробці програм для кластерів і
суперкомп'ютерів. Основним засобом комунікації
між процесами в MPI є передача повідомлень
один одному. Стандартизацією MPI займається
MPI Forum. У стандарті MPI описаний інтерфейс
передачі повідомлень, який повинен підтримуватися
як на платформі, так і в додатках користувача.
В даний час існує велика кількість безкоштовних
і комерційних реалізацій MPI. Існують реалізації
для мов Фортран 77/90, С та С++.
3. 3. Опис роботи програми
Розглянемо функціональний
опис програми:
int main(int argc, char* argv[]) – головна
функція програми, яка включає
в себе:
MPI_Init(&argc, &argv) – ініціалізація
MPI-програми;
MPI_Comm_size(MPI_COMM_WORLD, &ProcNum) –
визнчачення кількості процесів
у роботі програми;
MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank) –
визначення рангу процесу;
Якщо в нас запускається прогрма
на виконання, то послідовно виконується
такі функції:
SetRank() – отримання попереднього
і наступного рангу процесора
для пересилання по кільцевій
структурі;
Send() – тут генеруються
елементи матриць, розбиваються
на горизонтальні та вертикальні
підматриці, матриці записуються
в файл Data.txt, підматриці в файл
PartData.txt;
MPI_Send(A, (26+l1)*n2, MPI_INT, Ranks[p], 0, MPI_COMM_WORLD)
– відправляє повідомлення з
буфера A розмірністю (26+l1)*n2 процесу
з рангом Ranks[p];
MPI_Send(B, (8+l2)*n2, MPI_INT, Ranks[p], 1, MPI_COMM_WORLD)
- відправляє повідомлення з буфера B розмірністю
(8+l2)*n2 процесу з рангом Ranks[p];
MPI_Recv(A, (26+l1)*n2,MPI_INT,0,0, MPI_COMM_WORLD,
&Status) –
приймає повідомлення в буфер
A розмірністю (26+l1)*n2 від процеса з рангом
0;
MPI_Recv(B, (8+l2)*n2,MPI_INT,0,1, MPI_COMM_WORLD,
&Status) - приймає повідомлення в
буфер B розмірністю (8+l2)*n2 від процеса з
рангом 0;
Operate() – тут виконується
пермноження підматриць і пересилання
даних;
GatherResalt() – виконується
збір результату;
MPI_Send(C, 210*67, MPI_INT, 0, 0, MPI_COMM_WORLD)
- відправляє повідомлення з буфера C розмірністю
210*67 процесу з рангом 0;
MPI_Recv(temp, 210*67,MPI_INT, Ranks[p], 0, MPI_COMM_WORLD,
&Status) - приймає повідомлення в
буфер temp розмірністю 210*67 від процеса з
рангом Ranks[p];
MPI_Finalize() – завершення
роботи MPI-програми.
Рис. 7. Алгоритм роботи програми
3.4. Результат виконання
програми
На рис. 8 наведено скріншот
виконання програми, на рис. 9 - скріншот
файлу з елементами матриць А і B, на рис.
10 - скріншот файлу з підматрицями матриць
А і B, на рис. 11 - скріншот файлу з результатами
перемноження матриць А і В.
Рис. 8. Виконання програми
Рис. 9. Файл Data.txt
Рис. 10. Файл Data.txt
Рис. 11. Файл Result.txt
4. Розробка кластерної
системи
Завдання №3.
Кластер представляє собою
два або більше комп'ютерів (часто званих
вузлами), що об'єднуються за допомогою
мережевих технологій на базі шинної архітектури
або комутатора і постають перед користувачами
в якості єдиного інформаційно-обчислювального
ресурсу. В якості вузлів кластера можуть
бути обрані сервери, робочі станції і
навіть звичайні персональні комп'ютери.
Перевага кластеризації для підвищення
працездатності стає очевидним у разі
збою будь-якого вузла: при цьому другий
вузол кластеру може взяти на себе навантаження
несправного вузла, і користувачі не помітять
переривання в доступі.Кластеризація
може бути здійснена на різних рівнях
комп'ютерної системи, включаючи апаратне
забезпечення, операційні системи, програми-утиліти,
системи управління та програми. Чим більше
рівнів системи об'єднані кластерної технологією,
тим вище надійність, масштабованість
та керованість кластеру.
Рис. 12. Архитектура кластера
4.1. Базова інфраструктура
Треба для кластера окреме приміщення,
ізольоване від робочих місць користувачів.
Для свого охолодження обчислювальні
вузли простягають крізь корпус значний
потік повітря, а разом з ним - пил і бруд.
Окреме приміщення, де не буде відкриватися
вікно, а доступ сторонніх буде обмежений,
гарантує, що кількість пилу, що потрапляє
в вузли, буде мінімальним. Чим більше
об'єм приміщення, тим краще умови для
нормального функціонування кластера,
оскільки ризик різкого підвищення температури
через відключення систем кондиціонування
менше. Для кластера буде потрібно оперативний
набір запасних частин; до вузлів, до системного
і прикладного програмного забезпечення
будуть додаватися численні диски, документація
та гарантійні листи, тому бажано передбачити
спеціальне місце для зберігання допоміжних
матеріалів. Як і будь-який електроприлад,
кластер і пов'язана з ним апаратура виділяють
тепло, тому потрібен розрахунок потужності
необхідної системи охолодження повітря.
Невірний розрахунок параметрів температурного
режиму в приміщенні може доставити великі
неприємності в ході експлуатації кластерної
системи. Наступним необхідним для
розрахунку параметром є електроживлення.
Треба підрахувати потужність, споживану
усіма вузлами кластера та супутніми компонентами
проекту (джерелами безперебійного живлення,
файловим сховищем, комутаторами і т.п.).
Якщо встановлювати потужні джерела безперебійного
живлення, то для них потрібно спеціальна
проводка, так як у звичайні розетки вони
не включаються. Устаткування ставиться
потужне, стандартні і звичні рішення
можуть вже й не працювати. Важлива не
тільки потужність, що підводить електроживлення,
але також його надійність і гарантована
якість, особливо для систем, що працюють
у цілодобовому режимі. Треба звернути
увагу на перетин використовуваної проводки,
площа якої залежить від потужності проектованої
кластерної системи. Покриття підлоги
в приміщенні - це повинен бути спеціальний
антистатичний лінолеум. Бажано мати можливість
знеструмити все обладнання в приміщенні
з однієї точки , найкраще - біля входу.
Наприклад, з єдиного електричного щитка
, розташованого в цьому ж приміщенні.
Це дуже важливо для забезпечення безпеки
, насамперед, у разі виникнення екстрених
ситуацій . Крім обов'язкового захисту
кластера від хакерів, треба подбати і
про його фізичний захист і обмеження
доступу в приміщення. Безумовно , приміщення
має бути надійно закріплене, і вартість
відповідної підготовки потрібно включити
заздалегідь в проект. Ключі від приміщення
повинні бути тільки у відповідальних
осіб . Можливо, варто поставити сигналізацію
або організувати систему відеоспостереження
з можливістю відеоконтролю за приміщенням
через Інтернет. Вимоги до пожежної безпеки
у випадку з цілодобово працюючим кластером
вище вимог , що пред'являються до місць,
де на комп'ютерах працюють лише в робочі
години , отже, може знадобитися відповідне
доопрацювання приміщення. Як мінімум
, там повинен бути порошковий вогнегасник
і пожежна сигналізація, для серйозних
систем краще поставити автоматичну систему
пожежогасіння. 4.2. Проектування
архітектури кластерної системи