Розподілені обчислення: ДАП-технологія розпаралелювання рекурсивних алгоритмів
DOI:
https://doi.org/10.18523/2617-3808.2018.25-32Ключові слова:
паралельне програмування, обчислювальний кластер, розподілена пам’ять, автоматичне розпаралелювання, динамічне розпаралелювання, DAP-розпаралелюванняАнотація
Описано нову технологію динамічного розпаралелювання рекурсивних алгоритмів з розподіленою пам’яттю. Головним поштовхом до її створення було відкриття великого класу матричних рекурсивних алгоритмів за останні десятиліття. Усі вони, включно з алгоритмами В. Штрассена, є розвитком ідей, закладених у відомих працях А. А. Карацуби про швидке множення чисел і поліномів.
Основними об’єктами нової технології розпаралелювання є дроп, амін і пайн. Граф алгоритму розбивається на компактні підграфи (дропи), які можуть бути передані для обчислення на інші процесори. Для обчислення дропа проводиться розгортання його алгоритму і будується відповідна йому структура даних (амін). Для збереження всіх амінів і їх станів у кожному процесорі створюється список (пайн). Протягом обчислень, поки не завершено обрахунки конкретного аміна, цей амін зберігається в пайні. Після завершення обчислень уся пам’ять, відведена під амін, звільняється.
Іншою особливістю ДАПтехнології є механізм розподілу дропзавдань між процесорами. Для управління процесом розподілу завдань ми використовуємо список доступних дропзавдань, з глибиною вкладеності для кожного завдання. Ми також використовуємо список дочірніх процесорів з інформацією про всі відправлені завдання та список вільних процесорів. Список дочірніх процесорів оновлюється щоразу під час відправлення завдання і отримання результатів обчислень. Список вільних процесорів ділиться порівну між усіма процесорами, які отримують завдання з найменшою глибиною вкладеності.
Для управління обчисленнями та операціями обміну даних створюються два потоки. Перший забезпечує обрахунок і відсилання результатів обчислень, а другий відповідає за управління і операції обміну даними. Диспетчерський потік є провідним, він контролює всі порти і стани, після чого засинає, щоб дати можливість іншому потоку виконувати обчислення.
Крім того, передбачено механізм звільнення процесора. Якщо у процесора немає дропзавдань, то він додає себе в список вільних та пересилає цей список першому батьківському процесору. Такий процесор може отримати нове дропзавдання, а також він може отримати результат від дочірнього процесора і продовжити обчислення відповідно до завдань активного аміна.
Для пояснення нової технології розпаралелювання наведено приклади побудови дропзавдань для алгоритму обернення трикутної матриці і для алгоритму множення матриць.
Посилання
- Ilchenko E. A. (2013). Ob odnom algoritme upravlenia parallelnymi vychisleniami s decentralizovannym upravleniem. Vestnik Tambovskogo universiteta. Ser. Estestvennye i tehnichekie nauki, T.18, 4, 1198-1206.
- Ilchenko E. A. (2015). Ob effektivnom metode rasparallelivania blochnykh rekurivnykh algoritmov. Vestnik Tambovskogo universiteta. Ser. Estestvennye i tehnichekie nauki, T.20, 5, 1173-1186.
- Malashonok G. I., & Valeev Ju. D. (2008). Organizacia parallelnykh vychislenii v rekursivnykh simvolno-chislennykh algoritmakh. Trudy konferencii PaVT’2008 (Sankt-Peterburg). Cheliabinsk. JuUrGU, 153-165.
- Malashonok G. I. (2009). Upravlenie parallelnym vychislitelnym processom. Vestnik Tambovskogo universiteta. Ser. Estestvennye i tehnichekie nauki, T.14, 1, 269-274.
- Abramov S., Adamovitch A., & Kovalenko M. (1997). T-system: programming environment providing automatic dynamic parallelizing on IP-network of Unix-computers. Report on 4-th International Russian-Indian seminar and exibition (Moscow). Sept. 15-25.
- Abramov S., Adamovich A., Nyukhin A., Moskovsky A., Roganov V., Shevchuk E., Shevchuk Yu., & Vodomerov A. (2005). OpenTS: An Outline of Dynamic Parallelization Approach. Malyshkin V. (Ed.) PaCT 2005. Parallel Computing Technologies, LNCS 3606. Springer, Нeidenberg, 303-312.
##submission.downloads##
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2018 Gennadi Malaschonok, Alla Sidko
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори, які публікуються у цьому журналі, погоджуються з такими умовами:
а) Автори зберігають за собою авторські права на твір на умовах ліцензії CC BY 4.0 Creative Commons Attribution International License, котра дозволяє іншим особам вільно поширювати (копіювати і розповсюджувати матеріал у будь-якому вигляді чи форматі) та змінювати (міксувати, трансформувати, і брати матеріал за основу для будь-яких цілей, навіть комерційних) опублікований твір на умовах зазначення авторства.
б) Журнал дозволяє автору (авторам) зберігати авторські права без обмежень.
в) Автори мають право укладати самостійні додаткові угоди щодо поширення твору (наприклад, розміщувати роботу в електронному репозитарії), за умови збереження посилання на його першу публікацію. (Див. Політика Самоархівування)
г) Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у репозитаріях) тексту статті, як до подання його до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
