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

Автор(и)

  • Gennadi Malaschonok Національний університет «Києво-Могилянська академія», Україна
  • Alla Sidko Національний університет «Києво-Могилянська академія», Україна

DOI:

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

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

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

Анотація

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

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

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

Біографії авторів

Gennadi Malaschonok, Національний університет «Києво-Могилянська академія»

Доктор фізико-математичних наук, професор, завідувач кафедри мережних технологій факультету інформатики

malaschonok@ukma.edu.ua

Alla Sidko, Національний університет «Києво-Могилянська академія»

Студентка 4 курсу факультету інформатики

a.sidko@ukma.edu.ua

Посилання

  1. 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.
  2. Ilchenko E. A. (2015). Ob effektivnom metode rasparallelivania blochnykh rekurivnykh algoritmov. Vestnik Tambovskogo universiteta. Ser. Estestvennye i tehnichekie nauki, T.20, 5, 1173-1186.
  3. 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.
  4. Malashonok G. I. (2009). Upravlenie parallelnym vychislitelnym processom. Vestnik Tambovskogo universiteta. Ser. Estestvennye i tehnichekie nauki, T.14, 1, 269-274.
  5. 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.
  6. 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##

Як цитувати

[1]
G. Malaschonok і A. Sidko, «Розподілені обчислення: ДАП-технологія розпаралелювання рекурсивних алгоритмів», NRPCOMP, т. 1, с. 25–32, Жов 2018.