Методи та засоби ефективної обробки паралельних задач в комп’ютерних кластерних системах (стр. 1 )

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

На правах рукопису

Стіренко Сергій Григорович

УДК 004.382.2, 004.75

МЕТОДИ ТА ЗАСОБИ ЕФЕКТИВНОЇ ОБРОБКИ ПАРАЛЕЛЬНИХ ЗАДАЧ В КОМП’ЮТЕРНИХ КЛАСТЕРНИХ СИСТЕМАХ

Спеціальність 05.13.05 - Комп’ютерні системи та компоненти

Дисертація на здобуття наукового ступеня

доктора технічних наук

Науковий консультант:

Луцький Георгій Михайлович,

доктор технічних наук, професор

Київ - 2015 р.

ЗМІСТ

ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ…………………………………….…………	8
ВСТУП ……………………………………………………………………………..………….	9
РОЗДІЛ 1. АНАЛІЗ ІСНУЮЧИХ РІШЕНЬ..………………..….…………………	23
1.1. Загальний огляд підходів до організації обчислень в сучасних паралельних комп’ютерних системах ………………………….………………...	23
1.2. Процес обробки завдання в паралельній обчислювальній системі ….	28
1.3. Загальна характеристика технологій програмування паралельних комп’ютерних систем…………………………………….………………...…..	31
1.4. Моделі взаємодії паралельних процесів ……………………………..…….	33
1.5. Модель програмування з явним створенням потоків……………………	35
1.6. Модель програмування зі структурним створенням потоків……….…	40
1.7. Модель програмування з неявним поділом задачі……………….………	44
1.8. Транзакційна пам’ять……………………………….………….…………..	45
1.9. Низькорівнева передача повідомлень ………………………………………	46
1.10. Модель програмування без блокувань………………..…………………..	47
1.11. Порівняння моделей програмування………………...…………………….	50
1.12. Загальний огляд пiдходiв до органiзацiї збереження даних при паралельних обчисленнях…………………………………………………..……..	52
1.13. Явне розпаралелювання з використанням директив компiлятора	56
1.14. Низькорiвневий iнтерфейс передачi повідомлень………….……….	62
1.15. Концепцiя вiдвантаження обчислень…………………..…………….	69
1.16. Технологiя вiдкладених обчислень …………………….……………	77
1.17. Порiвняльний аналiз технологiй програмування паралельних систем	83
Висновки до розділу 1………………………………….………………….	85
РОЗДІЛ 2. ТЕОРЕТИЧНІ ОСНОВИ ПОБУДОВИ ВИСОКОЕФЕКТИВНИХ ЗАСОБІВ ДИНАМІЧНОГО БАЛАНСУВАННЯ НАВАНТАЖЕННЯ…………………………..………….	90
2.1. Постановка задачі……………………………………………….………	90
2.2. Критерії ефективності розв’язання задачі та оцінка збалансованості навантаження……………………………………………..……………...….	90
2.3. Аналіз задач, що вирішуються на високопродуктивних обчислювальних системах………………..…………………………..…….	95
2.4. Динамічне балансування навантаження при розв’язанні задачі…….	101
2.5. Критерії вибору моделі програмування паралельних компютерних систем………………………………………………………………..……….	104
2.6. Недоліки моделі низькорівневої передачі повідомлень………..…….	106
2.7. Високорівневі абстракції для паралельних комп’ютерних систем з локальною пам’яттю………………………………………………..……….	108
2.8. Високорівнева передача повідомлень…………..……..……….…….	109
2.8.1. Загальні визначення……………………….….…….….……….	109
2.8.2. Узагальнений оператор поділу…………..….………………….	112
2.8.3. Вхідні дані для підзадачі. Поняття проміжку..……….………	112
2.8.4. Оператор обчислення..……………………………….…………	113
2.8.5. Оператор поділу проміжків…………………..……..….………	114
2.8.6. Поняття шляху поділу підзадачі……………...…….….………	116
2.8.7. Оператор об’єднання результатів……………..……..…………	117
2.8.8. Визначення завдання………………………………….…………	118
2.9. Підхід до балансування навантаження в реалізації моделі виcокорівневої передачі повідомлень……………….…………….……….	118
2.10. Способи організації попереднього поділу задачі………….……….	120
2.10.1. Загальні зауваження…………………………………….…..….	120
2.10.2. Поділ на підзадачі однакового порядку…………….……….	121
2.10.3. Поділ на підзадачі різного порядку………….……………….	124
2.11. Способи початкової розсилки підзадач………………….………….	126
2.11.1. Загальні зауваження………………………..………………….	126
2.11.2. Розсилка підзадач однакового порядку……………………….	126
2.11.3. Розсилка підзадач різного порядку………………………….	128
2.12. Способи організації основного циклу обчислень………………….	129
2.12.1. Загальні зауваження………………………….……………….	129
2.12.2. Без балансування навантаження………………...…………….	129
2.12.3. Балансування навантаження з перерозподілом від одного процесу………………….…………………………………..………….	131
2.12.4. Балансування навантаження з перерозподiлом вiд одного процесу та додатковим подiлом………………………..…………….	135
2.12.5. Балансування навантаження з перерозподiлом мiж усiма процесами та додатковим подiлом………………………..………….	135
2.12.6. Балансування навантаження з перерозподiлом мiж усiма процесами, додатковим подiлом та врахуванням топологiї…….......	136
2.13. Допустимi комбiнацiї способiв органiзацiї окремих етапiв балансування навантаження……………………………..………………….	136
Висновки до розділу 2……………………………………………………….	139
РОЗДІЛ 3. ТЕОРИТИЧНІ ОСНОВИ МЕХАНІЗМУ ВІДКЛАДЕННЯ ПОЧАТКУ ПЕРЕДАЧІ ДАНИХ……………………………………………….	142
3.1. Формулювання задачi визначення моменту початку передачi даних	142
3.2. Оцiнка ефективностi…………………………………………...……….	146
3.3. Вiдкладення передачi даних……………………………….………….	152
3.4. Пiдходи до органiзацiї вiдкладення передачi даних………………….	159
3.5. Пакетна системи виконання задач……………………….…………….	166
3.6. Динамiчна змiна зернистостi…………………………….…………….	171
3.7. Оцiнка швидкостi вводу-виводу……………………………………….	175
3.8. Пiдходи до динамiчної змiни зернистостi…………………………….	178
Висновки до розділу 3……………………………………………………….	181
Роздiл 4. Проведення експериментiв та аналiз результатів…………………………………………….………..……………….	185
4.1. Особливостi реалiзацiї запропонованих пiдходiв в кластерних системах……………………………………………………….……………..………….	185
4.2. Задачi, що використовувались в експериментах……….…………..…….	187
4.3. Проведення експериментів……………………………………..…………….	189
4.4. Ефективнiсть розв’язання задач без балансування навантаження….	190
4.5. Балансування навантаження з перерозподiлом вiд одного процесу………………………………………………………………………………….	195
4.6. Балансування навантаження з перерозподiлом вiд одного процесу та додатковим подiлом…………………………………………..………………….	201
4.7. Балансування навантаження з перерозподiлом мiж усiма процесами та додатковим подiлом……………………………………………………………….	204
4.8. Балансування навантаження з врахуванням топології………………….	208
4.9. Особливостi реалiзацiї моделі системи пакетної обробки задач …….	208
4.10. Задачi, що використовувались в експериментах ………………..…….	210
4.11. Час очiкування введення та виведення ……………………..……..…….	212
4.12. Використання пам’ятi у вузлах системи…………………..………..…….	213
4.13. Вплив на коефiцiєнт ефективностi…………………………………..…….	215
4.14. Перевiрка гiпотез щодо пiдходiв до змiни зернистостi………..…….	218
Висновки до розділу 4……………………………………………………………….	219
РОЗДІЛ 5. РЕАЛІЗАЦІЇ ДЛЯ КЛАСТЕРНИХ СИСТЕМ ТА АНАЛІЗ РЕЗУЛЬТАТІВ ЕКСПЕРІМЕНТІВ…..……………………….…….……………….	225
5.1. Особливостi реалiзацiї в кластерних системах……………….………….	225
5.2. Типи задач, для яких виконувалось тестування………………………….	228
5.3. Методика тестування…………………………………………….…………….	232
5.4. Використання пам’ятi у вузлах системи……………………..…………….	234
5.5. Час очiкування введення та виведення…………………………………….	236
5.6. Вплив на коефiцiєнт ефективностi……………………………………….….	238
5.7. Перевiрка гiпотез щодо способiв обчислення часу передачi даних….	243
Висновки роздiлу 5…………………………………………………………..……….	248
Розділ 6. Топологічна організація компютерної системи………………………….…………………………..……..………….	255
6.1. Автоматизація синтезу топології…………………………………………….	256
6.2. Математична постановка задачи…………………………………………….	258
6.3. Алгоритми синтезу без урахування відмов……………………………….	261
6.4. Алгоритм синтезу відмовостійкої топології………………….………….	262
6.5. Інтерфейс передачі повідомлень MPI………………..…………………….	265
6.5.1. Передача з блокуванням та без блокування……..……………….	267
6.5.2. Колективні взаємодії……………………..…………………………….	268
6.6. Віртуальні топології MPI…………………………………………….……….	269
6.7. Особливості реалізації аналізатора………………………………………….	271
6.7.1. Підхід до аналізу паралельних програм………..………………….	271
6.7.2. Підходи до трасування програм…………….……………………….	274
6.7.3. Поліпшення автоматичного інструментування………………….	275
6.7.4. Генерація матриці інформаційних потоків……………………….	277
6.7.5. Діаграма пропускних спроможностей процесів……………….	279
6.8. Синтез топології з коментарями………………………….………………….	281
6.9. Синтез складної топології…………………………………………………….	284
6.9.1. Чисельне інтегрування………………………………..……………….	286
6.9.2. Множення матриць………….…………………………….…………….	288
6.9.3. Введення даних…………………………..…….……………………….	289
6.9.4. Множення вектора на розріджену матрицю (SpMV)………….	292
6.10. Компіляція і збірка………………………….………………………………….	295
Висновки до розділу 6……………………………………………………………….	299
ВИСНОВКИ……………………………..……………………………….……….	302
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ……………………………….……….	304

ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ