Розподілені обчислення: ДАП-технологія розпаралелювання рекурсивних алгоритмів
Loading...
Date
2018
Authors
Малашонок, Геннадiй
Ciдько, Алла
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Описано нову технологію динамічного розпаралелювання рекурсивних алгоритмів з розподіленою
пам’яттю. Головним поштовхом до її створення було відкриття великого класу матричних рекурсивних алгоритмів за останні десятиліття. Усі вони, включно з алгоритмами В. Штрассена, є розвитком ідей, закладених у відомих працях А. А. Карацуби про швидке множення чисел і поліномів.
Основними об’єктами нової технології розпаралелювання є дроп, амін і пайн. Граф алгоритму розбивається на компактні підграфи (дропи), які можуть бути передані для обчислення на інші процесори. Для обчислення дропа проводиться розгортання його алгоритму і будується відповідна йому
структура даних (амін). Для збереження всіх амінів і їх станів у кожному процесорі створюється
список (пайн). Протягом обчислень, поки не завершено обрахунки конкретного аміна, цей амін зберігається в пайні. Після завершення обчислень уся пам’ять, відведена під амін, звільняється.
Іншою особливістю ДАП-технології є механізм розподілу дроп-завдань між процесорами. Для
управління процесом розподілу завдань ми використовуємо список доступних дроп-завдань, з глибиною вкладеності для кожного завдання. Ми також використовуємо список дочірніх процесорів
з інформацією про всі відправлені завдання та список вільних процесорів. Список дочірніх процесорів
оновлюється щоразу під час відправлення завдання і отримання результатів обчислень. Список
вільних процесорів ділиться порівну між усіма процесорами, які отримують завдання з найменшою
глибиною вкладеності.
Для управління обчисленнями та операціями обміну даних створюються два потоки. Перший
забезпечує обрахунок і відсилання результатів обчислень, а другий відповідає за управління і операції обміну даними. Диспетчерський потік є провідним, він контролює всі порти і стани, після чого
засинає, щоб дати можливість іншому потоку виконувати обчислення.
Крім того, передбачено механізм звільнення процесора. Якщо у процесора немає дроп-завдань,
то він додає себе в список вільних та пересилає цей список першому батьківському процесору. Такий
процесор може отримати нове дроп-завдання, а також він може отримати результат від
дочірнього процесора і продовжити обчислення відповідно до завдань активного аміна.
Для пояснення нової технології розпаралелювання наведено приклади побудови дроп-завдань для
алгоритму обернення трикутної матриці і для алгоритму множення матриць.
This article addresses the description of a new technology of dynamic parallelization of recursive algorithms on distributed memory. The main impetus for its creation was the discovery of a large class of matrix recursive algorithms in recent decades. All of them, including the Strassen algorithms, are the development of the ideas of Karatsuba’s well-known works on the rapid multiplication of numbers and polynomials. The main objects of the new parallelization technology are drop, amine, and pine. The algorithm graph is divided into compact subgraphs (drops) which can be transferred to other processors for calculation. To calculate the drop, the algorithm is unfolded and the corresponding data structure (amine) is constructed. To save all the amines and their states, a list (pine) is created in each processor. During the calculations, until the calculation of a particular amine is completed, this amine is retained on the pine. After completing the calculations, all the memory allocated for the amine is released. Another feature of ADP-technology is the mechanism of distribution of drop-orders by processors. To manage the process of job allocation, we use a list of available drop jobs, with the depth of nesting for each job. We also use the list of child processors with information about all sent tasks, as well as a list of free processors. This list of child processors is updated each time the job is sent and when the results of the calculations are received. The list of free processors is divided equally among all the processors that receive the task with the lowest depth of nesting. To manage calculations and data exchange operations, two threads are created. The first will provide calculations and sending out the results of calculations, and the second will take care of all the management and of all the data exchange. The control thread is the master; it controls all the ports and states and falls asleep to allow the second thread to perform calculations. In addition, there is a mechanism for releasing the processor. If the processor does not have drop jobs, it adds itself to the list of free processors and forwards this list to the first parent processor. Such a processor can receive a new drop-task, and it can also get the result from the child processor and continue the calculations in accordance with the tasks of the active amine. To explain the new parallelization technology, we provide examples of the construction of drop tasks for the inversion algorithm of the triangular matrix and for the matrix multiplication algorithm.
This article addresses the description of a new technology of dynamic parallelization of recursive algorithms on distributed memory. The main impetus for its creation was the discovery of a large class of matrix recursive algorithms in recent decades. All of them, including the Strassen algorithms, are the development of the ideas of Karatsuba’s well-known works on the rapid multiplication of numbers and polynomials. The main objects of the new parallelization technology are drop, amine, and pine. The algorithm graph is divided into compact subgraphs (drops) which can be transferred to other processors for calculation. To calculate the drop, the algorithm is unfolded and the corresponding data structure (amine) is constructed. To save all the amines and their states, a list (pine) is created in each processor. During the calculations, until the calculation of a particular amine is completed, this amine is retained on the pine. After completing the calculations, all the memory allocated for the amine is released. Another feature of ADP-technology is the mechanism of distribution of drop-orders by processors. To manage the process of job allocation, we use a list of available drop jobs, with the depth of nesting for each job. We also use the list of child processors with information about all sent tasks, as well as a list of free processors. This list of child processors is updated each time the job is sent and when the results of the calculations are received. The list of free processors is divided equally among all the processors that receive the task with the lowest depth of nesting. To manage calculations and data exchange operations, two threads are created. The first will provide calculations and sending out the results of calculations, and the second will take care of all the management and of all the data exchange. The control thread is the master; it controls all the ports and states and falls asleep to allow the second thread to perform calculations. In addition, there is a mechanism for releasing the processor. If the processor does not have drop jobs, it adds itself to the list of free processors and forwards this list to the first parent processor. Such a processor can receive a new drop-task, and it can also get the result from the child processor and continue the calculations in accordance with the tasks of the active amine. To explain the new parallelization technology, we provide examples of the construction of drop tasks for the inversion algorithm of the triangular matrix and for the matrix multiplication algorithm.
Description
Keywords
паралельне програмування, обчислювальний кластер, розподілена пам’ять, автоматичне розпаралелювання, динамічне розпаралелювання, DAP-розпаралелювання, стаття, parallel programming, computational cluster, distribute memory, automatic parallelization, dynamic parallelization, DAP-parallelization
Citation
Малашонок Г. І. Розподілені обчислення: ДАП-технологія розпаралелювання рекурсивних алгоритмів / Малашонок Г. І., Сідько А. А. // Наукові записки НаУКМА. Комп'ютерні науки. - 2018. - Т. 1. - С. 25-32.