Бекетов Олексій Геннадійович Методи автоматизованого розпаралелювання циклічних операторів для гетерогенних архітектур обчислювальних систем

Краткое описание

Бекетов Олексій Геннадійович, молодший науковий співробітник Інституту програмних систем НАН України. Назва дисертації: «Методи автоматизованого розпаралелювання циклічних операторів для гетерогенних архітектур обчислювальних систем». Шифр та назва спеціальності 01.05.03 математичне та програмне забезпечення обчислювальнихмашинісистем. Спецрада Д26.001.09 Київського національного університету імені Тараса Шевченка

Міністерство освіти та науки України
Київський національний університет імені Тараса Шевченка
Кваліфікаційна наукова праця
на правах рукопису
Бекетов Олексій Геннадійович
УДК 004.424
ДИСЕРТАЦІЯ
Методи автоматизованого розпаралелювання циклічних операторів
для гетерогенних архітектур обчислювальних систем
01.05.03 – математичне та програмне забезпечення
обчислювальних машин і систем
Подається на здобуття наукового ступеня
кандидата технічних наук
Дисертація містить результати власних досліджень. Використання
ідей, результатів і текстів інших авторів мають посилання на відповідне
джерело ________ О.Г. Бекетов
Науковий керівник: Дорошенко Анатолій Юхимович
професор, доктор фізико-математичних наук
Київ – 2020

ЗМІСТ
АНОТАЦІЯ................................................................................................................. 2
ЗМІСТ.......................................................................................................................... 6
ВСТУП......................................................................................................................... 9
РОЗДІЛ 1. ОГЛЯД ПІДХОДІВ ТА МЕТОДІВ ОПТИМІЗАЦІЇ ЦИКЛІВ... 14
1.1. Проблематика ............................................................................................... 14
1.2. Висновки....................................................................................................... 22
РОЗДІЛ 2. МОДЕЛЬ ТА МЕТОД РОЗПАРАЛЕЛЮВАННЯ ЦИКЛІЧНИХ
ОПЕРАТОРІВ ДЛЯ ГРАФІЧНИХ ПРИСКОРЮВАЧІВ................................ 23
2.1. Постановка.................................................................................................... 23
2.2. Архітектура графічного прискорювача ..................................................... 25
2.3. Модель цільової платформи ....................................................................... 28
2.4. Формальний алгоритм перетворень........................................................... 30
2.5. Індексація кроків циклу............................................................................... 47
2.6. Особливості алгоритму у випадку зі спільними даними......................... 52
2.7. Вибір апаратного середовища .................................................................... 55
2.7.1. GPU кластер............................................................................................... 55
2.7.2. СPU кластер............................................................................................... 56
2.8. Аналіз побудованої моделі ......................................................................... 58
2.9. Визначення параметрів виконання ............................................................ 60
2.9.1. Випадок системи з одним СPU та одним GPU ...................................... 61
2.9.2. Схема виконання для системи з двома керуючими потоками та одним
прискорювачем з асинхронною передачею даних та одним буфером обміну
............................................................................................................................... 66
2.9.3 Схема виконання для системи з двома керуючими потоками та одним
прискорювачем з асинхронною передачею даних та двома буферами обміну
............................................................................................................................... 68
2.9.4. Системи із двома прискорювачами......................................................... 69
2.9.5. Вибір оптимальної конфігурації обчислювальної системи.................. 70
2.10. Висновки..................................................................................................... 70
РОЗДІЛ 3. РОЗРОБКА ПРОГРАМНОГО ІНСТРУМЕНТАРІЮ ДЛЯ
АВТОМАТИЗОВАНОГО ПЕРЕТВОРЕННЯ ГНІЗДА ЦИКЛУ ТА ЙОГО
ЗАСТОСУВАННЯ ДО ПРИКЛАДНИХ ЗАДАЧ............................................... 71
3.1. Загальна схема перетворення алгоритму................................................... 71
3.2. Основні етапи перетворень......................................................................... 73
3.3. Експериментальна реалізація системи перетворень ................................ 74
3.4. Застосування до прикладних задач ............................................................ 75
3.4.1. Задача метеорологічного прогнозування ............................................... 75
3.4.1.1. Порівняння із послідовною програмою............................................... 82
3.4.1.2. Порівняння із іншими засобами........................................................... 84
3.4.2. Задача множення матриць........................................................................ 86
3.4.3. Задача N тіл................................................................................................ 89
3.4.4. Задача знаходження розв’язків системи лінійних алгебраїчних рівнянь
методом Холецького........................................................................................... 91
ВИСНОВКИ ............................................................................................................. 93
СПИСОК ЛІТЕРАТУРИ........................................................................................ 94
ДОДАТКИ............................................................................................................... 101
Додаток А. Лістинг експерименту із множення матриць............................. 101
Додаток Б. Список опублікованих робіт за темою дисертації..................... 109

Список литературы

ВИСНОВКИ
У дисертаційній роботі розроблено, формалізовано, обґрунтовано та
реалізовано методи автоматизації перетворення вкладених циклів для
прикладних програм, що включає в себе наступні результати:
1. Вперше розроблено метод розпаралелювання програм з вкладеними
циклічними операторами, що надають можливість здійснювати обробку
великих обсягів даних, незважаючи на обмеження оперативної пам’яті
графічних прискорювачів.
2. Запропоновано метод розпаралелювання вкладених циклічних операторів
на гетерогенній архітектурі, що вдосконалює відомі розпаралелюючі системи
на випадок параметризовної кількості прискорювачів.
3. Створено програмну систему, що реалізує розроблені методи
автоматизації розпаралелювання циклічних операторів. Проведено чисельний
експеримент з використання методів на відомих тестових задачах, який довів їх
переваги.
Розроблену програмну систему застосовано та впроваджено для
автоматизації програмування задач чисельного прогнозування погоди в
Українському гідрометеорологічному інституті ДСНС України та НАН
України.