Конспект лекцій зі спеціальності 8.05010201 "Комп'ютерні системи і мережі". Розроблено відповідно до робочої програми навчальної дисципліни "Паралельні та розподілені обчислення". Призначені для самостійної роботи при вивченні дисципліни студентами денної та заочної форм навчання. ЗМІСТ ВСТУП……………………………………………………………………...…. 6 1 ПРИНЦИПИ ПОБУДОВИ ПАРАЛЕЛЬНИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ………………………….……………………. 7 1.1 Шляхи досягнення паралелізму………………………………………… 7 1.2 Класифікація обчислювальних систем……………………………..……8 1.2.1 Мультипроцесори ……………………………………………………… 9 1.2.2 Мультикомп'ютери ……………………………..…………………… 11 1.3 Характеристика типових схем комунікації в багатопроцесорних обчислювальних системах……………………………………….………………... 12 1.3.1 Приклади топологій мережі передачі даних………………… 13 1.3.2 Топологія мережі обчислювальних кластерів………………14 1.3.3 Характеристики топології мережі……………………………………. 15 1.4 Контрольні запитання………………………………...………………… 15 2 ОЦІНКА КОМУНІКАЦІЙНОЇ ТРУДОМІСТКОСТІ ПАРАЛЕЛЬНИХ АЛГОРИТМІВ………………………………………………. 17 2.1 Загальна характеристика механізмів передачі даних…………………17 2.1.1 Алгоритми маршрутизації……………………………………………. 17 2.1.2 Методи передачі даних……………………………………………….. 17 2.2 Аналіз трудомісткості основних операцій передачі даних…………18 2.2.1 Передача даних між двома процесорами мережі…………………… 19 2.2.2 Передача даних від одного процесора всім іншим процесорам мережі………………………………………………………………………………. 19 2.2.3 Передача даних від всіх процесорів всім процесорам мережі……...21 2.2.4 Узагальнена передача даних від одного процесора всім іншим процесорам мережі………………………………………………………………… 23 2.2.5. Узагальнена передача даних від всіх процесорів всім процесорам мережі………………………………………………………………………………. 23 2.2.6 Циклічний зсув………………………………………………………... 24 2.3 Контрольні запитання…………………………………………………... 26 3 ПАРАЛЕЛЬНЕ ПРОГРАМУВАННЯ НА ОСНОВІ МРІ…………… 28 3.1 MPI: основні поняття і визначення…………………………………….. 29 3.1.1 Поняття паралельної програми………………………………………. 29 3.1.2 Операції передачі даних……………………………………………… 30 3.1.3 Поняття комунікаторів………………………………………………... 30 3.1.4 Типи даних…………………………………………………………….. 31 3.1.5 Віртуальні топології…………………………………………………... 31 3.2 Введення в розробку паралельних програм з використанням MPI…..31 3.2.1 Основи MPI……………………………………………………………. 31 3.2.1.1 Ініціалізація і завершення MPI програм…………………………… 31 3.2.1.2 Визначення кількості та рангу процесів…………………………... 32 3.2.1.3 Передача повідомлень………………………………………………. 33 3.2.1.4 Прийом повідомлень………………………………………………... 34 3.2.1.5 Перша паралельна програма з використанням MPI………………. 35 3.2.2 Визначення часу виконання MPI-програми…………………………. 37 3.2.3 Початок роботи з колективними операціями передачі даних……… 38 3.2.3.1 Передача даних від одного процесу всім процесам програми…38 3.2.3.2 Передача даних від всіх процесів одному процесу. Операції редукції……………………………………………………………………………... 40 3.2.3.3 Синхронізація обчислень…………………………………………… 42 3.3 Контрольні запитання…………………………………………………... 43 4 МЕТОДИ ПАРАЛЕЛЬНИХ ОБЧИСЛЕНЬ………………………….. 44 4.1 Принципи розробки паралельних методів…………………………….. 44 4.2 Моделювання паралельних програм…………………………………... 46 4.3 Етапи розробки паралельних алгоритмів……………………………… 47 4.3.1 Поділ обчислень на незалежні частини……………………………… 48 4.3.2 Виділення інформаційних залежностей……………………………... 50 4.3.3 Масштабування набору підзадач…………………………………….. 51 4.3.4 Розподіл підзадач між процессорами………………………………... 52 4.4 Контрольні запитання…………………………………………………... 54 5 ПАРАЛЕЛЬНІ АЛГОРИТМИ МАТРИЧНО-ВЕКТОРНОГО МНОЖЕННЯ……………………………………………………………………... 55 5.1 Вступ……………………………………………………………………... 55 5.2 Принципи розпаралелювання………………………………………….. 55 5.3 Постановка задачі……………………………………………………….. 57 5.4 Послідовний алгоритм………………………………………………….. 57 5.5 Поділ даних……………………………………………………………… 58 5.6 Множення матриці на вектор при поділі даних по рядках…………... 58 5.6.1. Виділення інформаційних залежностей…………………………...... 59 5.6.2 Масштабування і розподіл підзадач по процессорам………………. 59 5.6.3 Аналіз ефективності…………………………………………………... 60 5.6.4 Програмна реалізація…………………………………………………. 61 5.6.5 Результати обчислювальних експериментів………………………… 65 5.7 Множення матриці на вектор при поділі даних по стовпцях………… 67 5.7.1 Визначення підзадач і виділення інформаційних залежностей…67 5.7.2. Масштабування і розподіл підзадач по процесорам……………….. 67 5.8 Множення матриці на вектор при блочному поділі даних…………... 68 5.8.3 Масштабування і розподіл підзадач по процесорам……………....... 68 5.9 Контрольні запитання…………………………………………………... 68 6 ПАРАЛЕЛЬНІ АЛГОРИТМИ МАТРИЧНОГО МНОЖЕННЯ…… 69 6.1 Постановка задачі……………………………………………………….. 69 6.2 Послідовний алгоритм………………………………………………..… 69 6.3 Множення матриць при стрічкової схемі поділу даних……………… 70 6.3.1 Визначення підзадач………………………………………………….. 70 6.3.2. Виділення інформаційних залежностей…………………………….. 71 6.3.3 Масштабування і розподіл підзадач по процессорам………………. 72 8.3.4. Аналіз ефективності………………………………………………….. 73 6.4 Алгоритм Фокса множення матриць при блочному поділі даних…...74 6.4.1 Визначення під задач…………………………………………………. 75 6.4.2 Виділення інформаційних залежностей……………………………... 76 6.4.3 Масштабування і розподіл підзадач по процессорам………………. 78 6.4.4 Аналіз ефективності…………………………………………………... 79 6.5 Контрольні запитання…………………………………………………... 79 ЛІТЕРАТУРА……………………………………………………………..... 80