Покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах
The 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 un...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | rus |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2016
|
| Теми: | |
| Онлайн доступ: | http://journal.iasa.kpi.ua/article/view/74674 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
Репозитарії
System research and information technologies| id |
journaliasakpiua-article-74674 |
|---|---|
| record_format |
ojs |
| spelling |
journaliasakpiua-article-746742018-03-30T15:27:05Z An enhanced scheduling algorithm for task planners in heterogeneous distributed computing systems Улучшеный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах Покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах Sergiyenko, Anatolij M. Simonenko, Valery P. Simonenko, A. V. schedule bipartite matching graph Hungarian algorithm task scheduler расписание паросочетание в двудольном графе Венгерский алгоритм планировщик задач розклад парування у двочастковому графі Угорський алгоритм планувальник завдань The 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. Рассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Представле-ны теоремы, позволяющие для двудольных графов, отображающих претендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с O(n3) до O(n1,5 log n). Подход применяется в алгоритме адаптивного мультианали-за, который основан на предварительном анализе и коррекции графа паросочетаний. При его применении к матрицам графов с коэффициентом заполнения меньше 30% алгоритм имеет статистическую временную сложность, которая близка к линейной. Розглянуто основи проектування просторових планувальників для глобальних, неоднорідних, розподілених обчислювальних систем. Подано теореми, що дають змогу для двочасткових графів, які відображають претендування заявок на ресурси, зменшити кількість варіантів розв’язків, що розглядаються, видаливши з матриці зв’язності безперспективні елементи. Це дозволило зменшити часову складність угорського алгоритму з O(n3) до O(n1,5 log n). Підхід застосовується в алгоритмі адаптивного мультианалізу, який полягає у попередньому аналізі та коригуванні графу паросполучень. У разі його застосування до матриць графів, які мають коефіцієнт заповнення менший за 30%, алгоритм має статистичну часову складність, яка близька до лінійної. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2016-06-21 Article Article application/pdf http://journal.iasa.kpi.ua/article/view/74674 10.20535/SRIT.2308-8893.2016.2.03 System research and information technologies; No. 2 (2016); 20-35 Системные исследования и информационные технологии; № 2 (2016); 20-35 Системні дослідження та інформаційні технології; № 2 (2016); 20-35 2308-8893 1681-6048 rus http://journal.iasa.kpi.ua/article/view/74674/70073 Copyright (c) 2021 System research and information technologies |
| institution |
System research and information technologies |
| collection |
OJS |
| language |
rus |
| topic |
schedule bipartite matching graph Hungarian algorithm task scheduler расписание паросочетание в двудольном графе Венгерский алгоритм планировщик задач розклад парування у двочастковому графі Угорський алгоритм планувальник завдань |
| spellingShingle |
schedule bipartite matching graph Hungarian algorithm task scheduler расписание паросочетание в двудольном графе Венгерский алгоритм планировщик задач розклад парування у двочастковому графі Угорський алгоритм планувальник завдань Sergiyenko, Anatolij M. Simonenko, Valery P. Simonenko, A. V. Покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах |
| topic_facet |
schedule bipartite matching graph Hungarian algorithm task scheduler расписание паросочетание в двудольном графе Венгерский алгоритм планировщик задач розклад парування у двочастковому графі Угорський алгоритм планувальник завдань |
| format |
Article |
| author |
Sergiyenko, Anatolij M. Simonenko, Valery P. Simonenko, A. V. |
| author_facet |
Sergiyenko, Anatolij M. Simonenko, Valery P. Simonenko, A. V. |
| author_sort |
Sergiyenko, Anatolij M. |
| title |
Покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах |
| title_short |
Покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах |
| title_full |
Покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах |
| title_fullStr |
Покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах |
| title_full_unstemmed |
Покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах |
| title_sort |
покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах |
| title_alt |
An enhanced scheduling algorithm for task planners in heterogeneous distributed computing systems Улучшеный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах |
| description |
The 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. |
| publisher |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| publishDate |
2016 |
| url |
http://journal.iasa.kpi.ua/article/view/74674 |
| work_keys_str_mv |
AT sergiyenkoanatolijm anenhancedschedulingalgorithmfortaskplannersinheterogeneousdistributedcomputingsystems AT simonenkovaleryp anenhancedschedulingalgorithmfortaskplannersinheterogeneousdistributedcomputingsystems AT simonenkoav anenhancedschedulingalgorithmfortaskplannersinheterogeneousdistributedcomputingsystems AT sergiyenkoanatolijm ulučšenyjalgoritmnaznačeniâdlâplanirovŝikovzadanijvneodnorodnyhraspredelennyhvyčislitelʹnyhsistemah AT simonenkovaleryp ulučšenyjalgoritmnaznačeniâdlâplanirovŝikovzadanijvneodnorodnyhraspredelennyhvyčislitelʹnyhsistemah AT simonenkoav ulučšenyjalgoritmnaznačeniâdlâplanirovŝikovzadanijvneodnorodnyhraspredelennyhvyčislitelʹnyhsistemah AT sergiyenkoanatolijm pokraŝenijalgoritmpriznačennâdlâplanuvalʹnikívzavdanʹvneodnorídnihrozpodílenihobčislûvalʹnihsistemah AT simonenkovaleryp pokraŝenijalgoritmpriznačennâdlâplanuvalʹnikívzavdanʹvneodnorídnihrozpodílenihobčislûvalʹnihsistemah AT simonenkoav pokraŝenijalgoritmpriznačennâdlâplanuvalʹnikívzavdanʹvneodnorídnihrozpodílenihobčislûvalʹnihsistemah AT sergiyenkoanatolijm enhancedschedulingalgorithmfortaskplannersinheterogeneousdistributedcomputingsystems AT simonenkovaleryp enhancedschedulingalgorithmfortaskplannersinheterogeneousdistributedcomputingsystems AT simonenkoav enhancedschedulingalgorithmfortaskplannersinheterogeneousdistributedcomputingsystems |
| first_indexed |
2024-04-08T15:04:58Z |
| last_indexed |
2024-04-08T15:04:58Z |
| _version_ |
1795779407026061312 |