Публікація: Застосування алгоритмів рангового підходу при плануванні розподілу задач в багатопроцесорних системах
Завантаження...
Дата
2024
Назва журналу
ISSN журналу
Назва тома
Видавництво
ХНУРЕ
Анотація
Розглядається застосування алгоритмів рангового підходу при плануванні розподілу задач у багатопроцесорних системах, що на сьогодні є досить актуальною проблемою, пов’язаною з еволюцією обчислювальних пристроїв, масовим переходом до багатоядерних процесорних архітектур, широким використанням інтернет ресурсів, а разом із тим попитом на сервери та дата-центри. Наводяться докази можливості зведення завдання планування розподілу задач у багатопроцесорних системах до багаторазового вирішення задачі цілочисельного програмування з булевими змінними (ЦЛП з БЗ). Автори розглядають два наближені алгоритми вирішення задачі ЦЛП з БЗ на прикладі класичної задачі про ранець. Обидва алгоритми базуються на засадах рангового підходу. Дія обох заснована на роботі загальної процедури побудови векторів рішень А0 з використанням правил відсікання безперспективних шляхів L1, L2, L3. Розглядаються логіка роботи кожної з трьох стратегій та програмні варіанти їх реалізації. Встановлено, що стратегії L1 та L2 можуть реалізовуватися через сортування або лінійний пошук підходящих векторів для побудови векторів наступного рангу. Для стратегії L3, що у стандартному вигляді пропонує відсікання шляхів, базуючись на їхньому максимальному потенційному прирості функціоналу, запропоновано модифікацію, яка до зволяє відсікати більшу кількість шляхів, не виконуючи перевірки для кожного з них. Наведено результати експериментальних досліджень, згідно з якими при використанні наближених алгоритмів А1 та А2 отримувана відповідь, як правило, не виходить за межі 10 % похибки від точної незалежно від обраної програмної реалізації. При цьому вдається знизити кількість векторів, що аналізуються, до 170000 супроти 2150 – в разі повного перебору. Використання запропонованої модифікації для стратегії L3 дозволяє зменшити кількість векторів, що аналізуються, в середньому ще на 40000. Зроблено висновок про те, що серед запропонованих алгоритмів найбільш вигідним є використання А2, реалізованого з використанням стратегії L1 через лінійний пошук, та модифікованої стратегії L3.
Опис
Ключові слова
алгоритми пошуку, ранговий підхід, розподіл задач, стратегії відсікання безперспективних шляхів, цілочисельне лінійне програмування з булевими змінними
Бібліографічний опис
Голубничий Д. Ю. Застосування алгоритмів рангового підходу при плануванні розподілу задач в багатопроцесорних системах / Д. Ю. Голубничий, О. С. Головченко // Радіотехніка : Всеукр. міжвід. наук.-техн. зб. – Харьків, 2024. – Вип. 219. – С. 16–27. - DOI: 10.30837/rt.2024.4.219.02.