DOI: https://doi.org/10.18523/2617-3808.2018.25-32

Розподілені обчислення: ДАП-технологія розпаралелювання рекурсивних алгоритмів

Gennadi Malaschonok, Alla Sidko

Анотація


Описано нову технологію динамічного розпаралелювання рекурсивних алгоритмів з розподіленою пам’яттю. Головним поштовхом до її створення було відкриття великого класу матричних рекурсивних алгоритмів за останні десятиліття. Усі вони, включно з алгоритмами В. Штрассена, є розвитком ідей, закладених у відомих працях А. А. Карацуби про швидке множення чисел і поліномів.
Основними об’єктами нової технології розпаралелювання є дроп, амін і пайн. Граф алгоритму розбивається на компактні підграфи (дропи), які можуть бути передані для обчислення на інші процесори. Для обчислення дропа проводиться розгортання його алгоритму і будується відповідна йому структура даних (амін). Для збереження всіх амінів і їх станів у кожному процесорі створюється список (пайн). Протягом обчислень, поки не завершено обрахунки конкретного аміна, цей амін зберігається в пайні. Після завершення обчислень уся пам’ять, відведена під амін, звільняється.
Іншою особливістю ДАП­технології є механізм розподілу дроп­завдань між процесорами. Для управління процесом розподілу завдань ми використовуємо список доступних дроп­завдань, з глибиною вкладеності для кожного завдання. Ми також використовуємо список дочірніх процесорів з інформацією про всі відправлені завдання та список вільних процесорів. Список дочірніх процесорів оновлюється щоразу під час відправлення завдання і отримання результатів обчислень. Список вільних процесорів ділиться порівну між усіма процесорами, які отримують завдання з найменшою глибиною вкладеності.

Для управління обчисленнями та операціями обміну даних створюються два потоки. Перший забезпечує обрахунок і відсилання результатів обчислень, а другий відповідає за управління і операції обміну даними. Диспетчерський потік є провідним, він контролює всі порти і стани, після чого засинає, щоб дати можливість іншому потоку виконувати обчислення.

Крім того, передбачено механізм звільнення процесора. Якщо у процесора немає дроп­завдань, то він додає себе в список вільних та пересилає цей список першому батьківському процесору. Такий процесор може отримати нове дроп­завдання, а також він може отримати результат від дочірнього процесора і продовжити обчислення відповідно до завдань активного аміна.
Для пояснення нової технології розпаралелювання наведено приклади побудови дроп­завдань для алгоритму обернення трикутної матриці і для алгоритму множення матриць.


Ключові слова


паралельне програмування; обчислювальний кластер; розподілена пам’ять; автоматичне розпаралелювання; динамічне розпаралелювання; DAP-розпаралелювання

Повний текст:

PDF

Посилання


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.






Copyright (c) 2018 Gennadi Malaschonok, Alla Sidko

Creative Commons License
Ця робота ліцензована Creative Commons Attribution 4.0 International License.



2018-2019, National University of Kyiv-Mohyla Academy
2 Skovorody Str., Kyiv 04070, Ukraine

Creative Commons License
This journal is licensed under a
Creative Commons Attribution 4.0 International License