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

Simple item page
dc.contributor.authorМалашонок, Геннадiй
dc.contributor.authorCiдько, Алла
dc.date.accessioned2018-11-06T14:01:48Z
dc.date.available2018-11-06T14:01:48Z
dc.date.issued2018
dc.description.abstractОписано нову технологію динамічного розпаралелювання рекурсивних алгоритмів з розподіленою пам’яттю. Головним поштовхом до її створення було відкриття великого класу матричних рекурсивних алгоритмів за останні десятиліття. Усі вони, включно з алгоритмами В. Штрассена, є розвитком ідей, закладених у відомих працях А. А. Карацуби про швидке множення чисел і поліномів. Основними об’єктами нової технології розпаралелювання є дроп, амін і пайн. Граф алгоритму розбивається на компактні підграфи (дропи), які можуть бути передані для обчислення на інші процесори. Для обчислення дропа проводиться розгортання його алгоритму і будується відповідна йому структура даних (амін). Для збереження всіх амінів і їх станів у кожному процесорі створюється список (пайн). Протягом обчислень, поки не завершено обрахунки конкретного аміна, цей амін зберігається в пайні. Після завершення обчислень уся пам’ять, відведена під амін, звільняється. Іншою особливістю ДАП-технології є механізм розподілу дроп-завдань між процесорами. Для управління процесом розподілу завдань ми використовуємо список доступних дроп-завдань, з глибиною вкладеності для кожного завдання. Ми також використовуємо список дочірніх процесорів з інформацією про всі відправлені завдання та список вільних процесорів. Список дочірніх процесорів оновлюється щоразу під час відправлення завдання і отримання результатів обчислень. Список вільних процесорів ділиться порівну між усіма процесорами, які отримують завдання з найменшою глибиною вкладеності. Для управління обчисленнями та операціями обміну даних створюються два потоки. Перший забезпечує обрахунок і відсилання результатів обчислень, а другий відповідає за управління і операції обміну даними. Диспетчерський потік є провідним, він контролює всі порти і стани, після чого засинає, щоб дати можливість іншому потоку виконувати обчислення. Крім того, передбачено механізм звільнення процесора. Якщо у процесора немає дроп-завдань, то він додає себе в список вільних та пересилає цей список першому батьківському процесору. Такий процесор може отримати нове дроп-завдання, а також він може отримати результат від дочірнього процесора і продовжити обчислення відповідно до завдань активного аміна. Для пояснення нової технології розпаралелювання наведено приклади побудови дроп-завдань для алгоритму обернення трикутної матриці і для алгоритму множення матриць.uk_UA
dc.description.abstractThis 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.en_US
dc.identifier.citationМалашонок Г. І. Розподілені обчислення: ДАП-технологія розпаралелювання рекурсивних алгоритмів / Малашонок Г. І., Сідько А. А. // Наукові записки НаУКМА. Комп'ютерні науки. - 2018. - Т. 1. - С. 25-32.uk_UA
dc.identifier.issn2617-7323
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/14635
dc.identifier.urihttps://doi.org/10.18523/2617-3808.2018.25-32
dc.language.isoukuk_UA
dc.relation.sourceНаукові записки НаУКМА. Комп'ютерні науки. - 2018. - Т. 1uk_UA
dc.statusfirst publisheduk_UA
dc.subjectпаралельне програмуванняuk_UA
dc.subjectобчислювальний кластерuk_UA
dc.subjectрозподілена пам’ятьuk_UA
dc.subjectавтоматичне розпаралелюванняuk_UA
dc.subjectдинамічне розпаралелюванняuk_UA
dc.subjectDAP-розпаралелюванняuk_UA
dc.subjectстаттяuk_UA
dc.subjectparallel programmingen_US
dc.subjectcomputational clusteren_US
dc.subjectdistribute memoryen_US
dc.subjectautomatic parallelizationen_US
dc.subjectdynamic parallelizationen_US
dc.subjectDAP-parallelizationen_US
dc.titleРозподілені обчислення: ДАП-технологія розпаралелювання рекурсивних алгоритмівuk_UA
dc.title.alternativeDistributed computing: DAP-technology for parallelizing recursive algorithmsen_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Malashonok_Rozpodileni_obchyslennia_DAP_tekhnolohiia_rozparaleliuvannia.pdf
Size:
474.02 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Том 1
Кафедра мережних технологій