Застосування алгоритмів рангового підходу при плануванні розподілу задач в багатопроцесорних системах

Голубничий, Д. Ю.; Головченко, О. С.

Публікація:
Застосування алгоритмів рангового підходу при плануванні розподілу задач в багатопроцесорних системах

dc.contributor.author	Голубничий, Д. Ю.
dc.contributor.author	Головченко, О. С.
dc.date.accessioned	2025-06-12T09:49:19Z
dc.date.available	2025-06-12T09:49:19Z
dc.date.issued	2024
dc.description.abstract	Розглядається застосування алгоритмів рангового підходу при плануванні розподілу задач у багатопроцесорних системах, що на сьогодні є досить актуальною проблемою, пов’язаною з еволюцією обчислювальних пристроїв, масовим переходом до багатоядерних процесорних архітектур, широким використанням інтернет ресурсів, а разом із тим попитом на сервери та дата-центри. Наводяться докази можливості зведення завдання планування розподілу задач у багатопроцесорних системах до багаторазового вирішення задачі цілочисельного програмування з булевими змінними (ЦЛП з БЗ). Автори розглядають два наближені алгоритми вирішення задачі ЦЛП з БЗ на прикладі класичної задачі про ранець. Обидва алгоритми базуються на засадах рангового підходу. Дія обох заснована на роботі загальної процедури побудови векторів рішень А0 з використанням правил відсікання безперспективних шляхів L1, L2, L3. Розглядаються логіка роботи кожної з трьох стратегій та програмні варіанти їх реалізації. Встановлено, що стратегії L1 та L2 можуть реалізовуватися через сортування або лінійний пошук підходящих векторів для побудови векторів наступного рангу. Для стратегії L3, що у стандартному вигляді пропонує відсікання шляхів, базуючись на їхньому максимальному потенційному прирості функціоналу, запропоновано модифікацію, яка до зволяє відсікати більшу кількість шляхів, не виконуючи перевірки для кожного з них. Наведено результати експериментальних досліджень, згідно з якими при використанні наближених алгоритмів А1 та А2 отримувана відповідь, як правило, не виходить за межі 10 % похибки від точної незалежно від обраної програмної реалізації. При цьому вдається знизити кількість векторів, що аналізуються, до 170000 супроти 2150 – в разі повного перебору. Використання запропонованої модифікації для стратегії L3 дозволяє зменшити кількість векторів, що аналізуються, в середньому ще на 40000. Зроблено висновок про те, що серед запропонованих алгоритмів найбільш вигідним є використання А2, реалізованого з використанням стратегії L1 через лінійний пошук, та модифікованої стратегії L3.
dc.identifier.citation	Голубничий Д. Ю. Застосування алгоритмів рангового підходу при плануванні розподілу задач в багатопроцесорних системах / Д. Ю. Голубничий, О. С. Головченко // Радіотехніка : Всеукр. міжвід. наук.-техн. зб. – Харьків, 2024. – Вип. 219. – С. 16–27. - DOI: 10.30837/rt.2024.4.219.02.
dc.identifier.doi	https://doi.org/10.30837/rt.2024.4.219.02
dc.identifier.uri	https://openarchive.nure.ua/handle/document/31521
dc.language.iso	uk
dc.publisher	ХНУРЕ
dc.subject	алгоритми пошуку
dc.subject	ранговий підхід
dc.subject	розподіл задач
dc.subject	стратегії відсікання безперспективних шляхів
dc.subject	цілочисельне лінійне програмування з булевими змінними
dc.title	Застосування алгоритмів рангового підходу при плануванні розподілу задач в багатопроцесорних системах
dc.type	Article
dspace.entity.type	Publication