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

Рассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Представлены теоремы, позволяющие для двудольных графов, отображающих претендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с O(n³) до O...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автори:	Сергиенко, А.М., Симоненко, В.П., Симоненко, А.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2016
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/134011
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах / А.М. Сергиенко, В.П. Симоненко, А.В. Симоненко // Системні дослідження та інформаційні технології. — 2016. — № 2. — С. 20-35. — Бібліогр.: 23 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-134011
record_format	dspace
spelling	irk-123456789-1340112018-06-11T03:04:20Z Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах Сергиенко, А.М. Симоненко, В.П. Симоненко, А.В. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Рассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Представлены теоремы, позволяющие для двудольных графов, отображающих претендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с O(n³) до O(n¹,⁵ log n). . Подход применяется в алгоритме адаптивного мультианализа, который основан на предварительном анализе и коррекции графа паросочетаний. При его применении к матрицам графов с коэффициентом заполнения меньше 30% алгоритм имеет статистическую временную сложность, которая близка к линейной. Розглянуто основи проектування просторових планувальників для глобальних, неоднорідних, розподілених обчислювальних систем. Подано теореми, що дають змогу для двочасткових графів, які відображають претендування заявок на ресурси, зменшити кількість варіантів розв’язків, що розглядаються, видаливши з матриці зв’язності безперспективні елементи. Це дозволило зменшити часову складність угорського алгоритму з O(n³) до O(n¹,⁵ log n). Підхід застосовується в алгоритмі адаптивного мультианалізу, який полягає у попередньому аналізі та коригуванні графу паросполучень. У разі його застосування до матриць графів, які мають коефіцієнт заповнення менший за 30%, алгоритм має статистичну часову складність, яка близька до лінійної. 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(n³) to O (n¹,⁵ logn). 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. 2016 Article Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах / А.М. Сергиенко, В.П. Симоненко, А.В. Симоненко // Системні дослідження та інформаційні технології. — 2016. — № 2. — С. 20-35. — Бібліогр.: 23 назв. — рос. 1681–6048 DOI: doi.org/10.20535/SRIT.2308-8893.2016.2.03 http://dspace.nbuv.gov.ua/handle/123456789/134011 004.383 ru Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
spellingShingle	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Сергиенко, А.М. Симоненко, В.П. Симоненко, А.В. Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах Системні дослідження та інформаційні технології
description	Рассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Представлены теоремы, позволяющие для двудольных графов, отображающих претендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с O(n³) до O(n¹,⁵ log n). . Подход применяется в алгоритме адаптивного мультианализа, который основан на предварительном анализе и коррекции графа паросочетаний. При его применении к матрицам графов с коэффициентом заполнения меньше 30% алгоритм имеет статистическую временную сложность, которая близка к линейной.
format	Article
author	Сергиенко, А.М. Симоненко, В.П. Симоненко, А.В.
author_facet	Сергиенко, А.М. Симоненко, В.П. Симоненко, А.В.
author_sort	Сергиенко, А.М.
title	Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах
title_short	Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах
title_full	Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах
title_fullStr	Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах
title_full_unstemmed	Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах
title_sort	улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2016
topic_facet	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
url	http://dspace.nbuv.gov.ua/handle/123456789/134011
citation_txt	Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах / А.М. Сергиенко, В.П. Симоненко, А.В. Симоненко // Системні дослідження та інформаційні технології. — 2016. — № 2. — С. 20-35. — Бібліогр.: 23 назв. — рос.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT sergienkoam ulučšennyjalgoritmnaznačeniâdlâplanirovŝikovzadanijvneodnorodnyhraspredelennyhvyčislitelʹnyhsistemah AT simonenkovp ulučšennyjalgoritmnaznačeniâdlâplanirovŝikovzadanijvneodnorodnyhraspredelennyhvyčislitelʹnyhsistemah AT simonenkoav ulučšennyjalgoritmnaznačeniâdlâplanirovŝikovzadanijvneodnorodnyhraspredelennyhvyčislitelʹnyhsistemah
first_indexed	2023-10-18T21:07:10Z
last_indexed	2023-10-18T21:07:10Z
_version_	1796151973106417664

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

Репозитарії

Схожі ресурси