Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах
Рассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Представлены теоремы, позволяющие для двудольных графов, отображающих претендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с O(n³) до O...
Gespeichert in:
| Veröffentlicht in: | Системні дослідження та інформаційні технології |
|---|---|
| Datum: | 2016 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2016
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/134011 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах / А.М. Сергиенко, В.П. Симоненко, А.В. Симоненко // Системні дослідження та інформаційні технології. — 2016. — № 2. — С. 20-35. — Бібліогр.: 23 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862592513008730112 |
|---|---|
| author | Сергиенко, А.М. Симоненко, В.П. Симоненко, А.В. |
| author_facet | Сергиенко, А.М. Симоненко, В.П. Симоненко, А.В. |
| citation_txt | Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах / А.М. Сергиенко, В.П. Симоненко, А.В. Симоненко // Системні дослідження та інформаційні технології. — 2016. — № 2. — С. 20-35. — Бібліогр.: 23 назв. — рос. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | Рассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Представлены теоремы, позволяющие для двудольных графов, отображающих претендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с 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.
|
| first_indexed | 2025-11-27T08:37:52Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-134011 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-11-27T08:37:52Z |
| publishDate | 2016 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Сергиенко, А.М. Симоненко, В.П. Симоненко, А.В. 2018-06-10T19:03:33Z 2018-06-10T19:03:33Z 2016 Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах / А.М. Сергиенко, В.П. Симоненко, А.В. Симоненко // Системні дослідження та інформаційні технології. — 2016. — № 2. — С. 20-35. — Бібліогр.: 23 назв. — рос. 1681–6048 DOI: doi.org/10.20535/SRIT.2308-8893.2016.2.03 https://nasplib.isofts.kiev.ua/handle/123456789/134011 004.383 Рассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Представлены теоремы, позволяющие для двудольных графов, отображающих претендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с 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. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах Покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах An enhanced scheduling algorithm for task planners in heterogeneous distributed computing systems Article published earlier |
| spellingShingle | Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах Сергиенко, А.М. Симоненко, В.П. Симоненко, А.В. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| title | Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах |
| title_alt | Покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах An enhanced scheduling algorithm for task planners in heterogeneous distributed computing systems |
| title_full | Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах |
| title_fullStr | Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах |
| title_full_unstemmed | Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах |
| title_short | Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах |
| title_sort | улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах |
| topic | Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| topic_facet | Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/134011 |
| work_keys_str_mv | AT sergienkoam ulučšennyialgoritmnaznačeniâdlâplanirovŝikovzadaniivneodnorodnyhraspredelennyhvyčislitelʹnyhsistemah AT simonenkovp ulučšennyialgoritmnaznačeniâdlâplanirovŝikovzadaniivneodnorodnyhraspredelennyhvyčislitelʹnyhsistemah AT simonenkoav ulučšennyialgoritmnaznačeniâdlâplanirovŝikovzadaniivneodnorodnyhraspredelennyhvyčislitelʹnyhsistemah AT sergienkoam pokraŝeniialgoritmpriznačennâdlâplanuvalʹnikívzavdanʹvneodnorídnihrozpodílenihobčislûvalʹnihsistemah AT simonenkovp pokraŝeniialgoritmpriznačennâdlâplanuvalʹnikívzavdanʹvneodnorídnihrozpodílenihobčislûvalʹnihsistemah AT simonenkoav pokraŝeniialgoritmpriznačennâdlâplanuvalʹnikívzavdanʹvneodnorídnihrozpodílenihobčislûvalʹnihsistemah AT sergienkoam anenhancedschedulingalgorithmfortaskplannersinheterogeneousdistributedcomputingsystems AT simonenkovp anenhancedschedulingalgorithmfortaskplannersinheterogeneousdistributedcomputingsystems AT simonenkoav anenhancedschedulingalgorithmfortaskplannersinheterogeneousdistributedcomputingsystems |