Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах

Скорочена інформація про документ
dc.contributor.authorСергиенко, Анатолий Михайлович
dc.contributor.authorСимоненко, Валерий Павлович
dc.contributor.authorСимоненко, Андрей Валерьевич
dc.contributor.authorСергієнко, Анатолій Михайлович
dc.contributor.authorСімоненко, Валерій Павлович
dc.contributor.authorСімоненко, Андрій Валерійович
dc.contributor.authorSergiyenko, Anatolij Mykhailovych
dc.contributor.authorSimonenko, Valery Pavlovych
dc.contributor.authorSimonenko, Andriy Valerijovych
dc.date.accessioned2017-03-03T11:45:14Z
dc.date.available2017-03-03T11:45:14Z
dc.date.issued2016
dc.description.abstractenThe basics of designing the spatial schedulers are considered which are used in global heterogeneous GRID-systems. Several theorems are proven, which consider the bipartite graphs of task requests and resource relations. These theorems help to reduce the number of decision options by removing the unpromising elements in the adjacency matrix. This reduces the time complexity of the Hungarian algorithm from O(n3) to O(n1,5 log n). This approach is used in the adaptive multianalysis algorithm, which is based on a preliminary analysis and correction of the bipartite graph matrix. Its application to the matrices, which are filled to less than 30% of their volume, the scheduling algorithm has the statistical time complexity, which is close to linear.uk
dc.description.abstractruРассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Представлены теоремы, позволяющие для двудольных графов, отображающих претендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с O(n3) до O(n1,5 log n). Подход применяется в алгоритме адаптивного мультианализа, который основан на предварительном анализе и коррекции графа паросочетаний. При его применении к матрицам графов с коэффициентом заполнения меньше 30% алгоритм имеет статистическую временную сложность, которая близка к линейной.uk
dc.description.abstractukРозглянуто основи проектування просторових планувальників для глобальних, неоднорідних, розподілених обчислювальних систем. Подано теореми, що дають змогу для двочасткових графів, які відображають претендування заявок на ресурси, зменшити кількість варіантів розв’язків, що розглядаються, видаливши з матриці зв’язності безперспективні елементи. Це дозволило зменшити часову складність угорського алгоритму з O(n3) до O(n1,5 log n). Підхід застосовується в алгоритмі адаптивного мультианалізу, який полягає у попередньому аналізі та коригуванні графу паросполучень. У разі його застосування до матриць графів, які мають коефіцієнт заповнення менший за 30%, алгоритм має статистичну часову складність, яка близька до лінійної.uk
dc.format.pagerangeС. 20-35uk
dc.identifier.citationСергиенко А. М. Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах / А. М. Сергиенко, В. П. Симоненко, А. В. Симоненко // Системні дослідження та інформаційні технології : міжнародний науково-технічний журнал. – 2016. – № 2. – С. 20–35. – Бібліогр.: 23 назви.uk
dc.identifier.doihttps://doi.org/10.20535/SRIT.2308-8893.2016.2.03
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/19179
dc.language.isoruuk
dc.publisherНТУУ "КПІ"uk
dc.publisher.placeКиївuk
dc.source.nameСистемні дослідження та інформаційні технології : міжнародний науково-технічний журналuk
dc.status.pubpublisheduk
dc.subjectрасписаниеru
dc.subjectпаросочетание в двудольном графеru
dc.subjectВенгерский алгоритмru
dc.subjectпланировщик задачru
dc.subjectрозкладuk
dc.subjectпарування у двочастковому графіuk
dc.subjectУгорський алгоритмuk
dc.subjectпланувальник завданьuk
dc.subjectscheduleen
dc.subjectbipartite matching graphen
dc.subjectHungarian algorithmen
dc.subjecttask scheduleren
dc.subject.udc004.383uk
dc.titleУлучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системахuk
dc.title.alternativeПокращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системахuk
dc.title.alternativeAn enhanced scheduling algorithm for task planners in heterogeneous distributed computing systemsuk
dc.typeArticleuk
thesis.degree.level-uk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
GM_03Sergiyenko.pdf
Розмір:
533.02 KB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
7.8 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Системні дослідження та інформаційні технології: міжнародний науково-технічний журнал, № 2