Кафедра мережних технологій

Permanent URI for this collection

https://ekmair.ukma.edu.ua/handle/123456789/12313

Browse

Browsing Кафедра мережних технологій by Subject "automatic parallelization"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Розподілені обчислення: ДАП-технологія розпаралелювання рекурсивних алгоритмів
    (2018) Малашонок, Геннадiй; Ciдько, Алла
    Описано нову технологію динамічного розпаралелювання рекурсивних алгоритмів з розподіленою пам’яттю. Головним поштовхом до її створення було відкриття великого класу матричних рекурсивних алгоритмів за останні десятиліття. Усі вони, включно з алгоритмами В. Штрассена, є розвитком ідей, закладених у відомих працях А. А. Карацуби про швидке множення чисел і поліномів. Основними об’єктами нової технології розпаралелювання є дроп, амін і пайн. Граф алгоритму розбивається на компактні підграфи (дропи), які можуть бути передані для обчислення на інші процесори. Для обчислення дропа проводиться розгортання його алгоритму і будується відповідна йому структура даних (амін). Для збереження всіх амінів і їх станів у кожному процесорі створюється список (пайн). Протягом обчислень, поки не завершено обрахунки конкретного аміна, цей амін зберігається в пайні. Після завершення обчислень уся пам’ять, відведена під амін, звільняється. Іншою особливістю ДАП-технології є механізм розподілу дроп-завдань між процесорами. Для управління процесом розподілу завдань ми використовуємо список доступних дроп-завдань, з глибиною вкладеності для кожного завдання. Ми також використовуємо список дочірніх процесорів з інформацією про всі відправлені завдання та список вільних процесорів. Список дочірніх процесорів оновлюється щоразу під час відправлення завдання і отримання результатів обчислень. Список вільних процесорів ділиться порівну між усіма процесорами, які отримують завдання з найменшою глибиною вкладеності. Для управління обчисленнями та операціями обміну даних створюються два потоки. Перший забезпечує обрахунок і відсилання результатів обчислень, а другий відповідає за управління і операції обміну даними. Диспетчерський потік є провідним, він контролює всі порти і стани, після чого засинає, щоб дати можливість іншому потоку виконувати обчислення. Крім того, передбачено механізм звільнення процесора. Якщо у процесора немає дроп-завдань, то він додає себе в список вільних та пересилає цей список першому батьківському процесору. Такий процесор може отримати нове дроп-завдання, а також він може отримати результат від дочірнього процесора і продовжити обчислення відповідно до завдань активного аміна. Для пояснення нової технології розпаралелювання наведено приклади побудови дроп-завдань для алгоритму обернення трикутної матриці і для алгоритму множення матриць.