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

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

Full description

Saved in:

Bibliographic Details
Date:	2016
Main Authors:	Сергиенко, А.М., Симоненко, В.П., Симоненко, А.В.
Format:	Article
Language:	Russian
Published:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2016
Series:	Системні дослідження та інформаційні технології
Subjects:	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
Online Access:	http://dspace.nbuv.gov.ua/handle/123456789/134011
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах / А.М. Сергиенко, В.П. Симоненко, А.В. Симоненко // Системні дослідження та інформаційні технології. — 2016. — № 2. — С. 20-35. — Бібліогр.: 23 назв. — рос.

Institution

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	2025-07-09T20:07:50Z
last_indexed	2025-07-09T20:07:50Z
_version_	1837201276628107264
fulltext	© А.М. Сергиєнко, В.П. Симоненко, А.В. Симоненко, 2016 20 ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 TIДC ПРОБЛЕМИ ПРИЙНЯТТЯ РІШЕНЬ І УПРАВЛІННЯ В ЕКОНОМІЧНИХ, ТЕХНІЧНИХ, ЕКОЛОГІЧНИХ І СОЦІАЛЬНИХ СИСТЕМАХ УДК 004.383 DOI: 10.20535/SRIT.2308-8893.2016.2.03 УЛУЧШЕННЫЙ АЛГОРИТМ НАЗНАЧЕНИЯ ДЛЯ ПЛАНИРОВЩИКОВ ЗАДАНИЙ В НЕОДНОРОДНЫХ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ А.М. СЕРГИЄНКО, В.П. СИМОНЕНКО, А.В. СИМОНЕНКО Рассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Пред- ставлены теоремы, позволяющие для двудольных графов, отображающих пре- тендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с )( 3nO до )log( 5,1 nnO . Подход применяется в алгоритме адап- тивного мультианализа, который основан на предварительном анализе и кор- рекции графа паросочетаний. При его применении к матрицам графов с коэф- фициентом заполнения меньше 30% алгоритм имеет статистическую временную сложность, которая близка к линейной. ВВЕДЕНИЕ Распределенные вычислительные системы являются новым поколением вы- числительные систем, которые используются в основном для научных вы- числений. По мере развития таких систем возникают проблемы эффектив- ного распределения задач в них [1, 2, 5]. Одной из проблем большой распределенной системы является вовлечение в вычислительный процесс максимально большего количества ресурсов и, соответственно, распределе- ние большего количества задач по ресурсам. В большинстве систем [3, 6, 11] используются планировщики потокового типа, что определяют либо слу- чайный выбор узла для задачи, либо выбор узла в соответствии с системой приоритетов. Можно назвать следующие знаковые проекты, получившие известность: PBS [7], LSF [4], NQE [7], I-SOFT [8], EASY [9], LoadLeveler [10]. При этом влияние назначения заявки на ресурс при последующих на- значениях не учитывается. Неэффективность такого подхода особенно сильно проявляется в гло- бальных вычислительных системах, так как в системах такого типа ресурсы и заявки являются неоднородными. Идея рассматриваемого подхода заключается в разделении составления расписания на предварительный анализ исходной информации, определение стратегии поиска решения и поиск варианта решения с использованием ре- зультатов анализа. Этап предварительного анализа существенно уменьшает время решения по сравнению с классическими методами решения задачи планирования [12]. Улучшенный алгоритм назначения для планировщиков заданий в неоднородных … Системні дослідження та інформаційні технології, 2016, № 2 21 Требования заявок на захват ресурсов вычислительной системы можно разделить на обязательные xC , ,,,1 px K= и оптимизирующие yO , ky ,,1K= . С помощью обязательных требований x-го типа }1,0{, ∈ji xC ана- лизируется принципиальная возможность предоставления i-й заявке j-го ре- сурса [13]. Оптимизирующие требования y-го типа ]1,0[, ∈ji yO определяют степень предпочтения (приоритет) j-го ресурса для назначения на него i-й заявки по требованиям ji yO , . Для определения приоритета j-го ресурса для назначения на него i-й заявки по всем требованиям можно использовать вы- ражение ∏∏ == = p x ji yy p x ji xji ORCO 1 , 1 , , , (1) где yR — весовой коэффициент оптимизирующего требования y-го типа. Если система планирования учитывает обязательные и оптимизирую- щие требования, то коэффициент претендования в матрице связности вычи- сляется из выражения (1) и находится в диапазоне ]1,0[, ∈jiO , а при диспет- черизации с учетом только обязательных требований ∏ = = p x ji xji CO 1 , , и }1,0{, ∈jiO . В этом случае матрица связности, отображающая претендова- ние заявок на ресурсы, примет булевый вид. Единичный элемент в этой матрице означает, что ресурс подходит для размещения заявки, т.е. есть достаточный объем памяти, процессор имеет необходимые производитель- ность, программы, данные и т.д. Для системы из N ресурсов в некоторый момент времени имеется M работ. Пул M задач, для которых система выделяет ресурсы, может быть ограничен наличием свободных ресурсов, т.е. при условии NM = . Требо- вания работ на захват ресурсов представлены булевой матрицей связности (МС) ],[ jiC , .,,1 Ni K= Необходимо определить отношения работа − ре- сурс )},{( ji WVA = , },...,2,1{ NVVi =∈ , },...,2,1{ NWWi =∈ так, чтобы ),,1],[(, jijiji WVWVCWV ≠=∀ . Введем дополнительные условия: ресурс может обслужить только одну заявку; процесс обслуживания заявки не может быть прерван; каждая работа имеет индивидуальные характеристики и может претендовать на захват то- лько некоторых системных ресурсов; нет очереди к ресурсам; одна работа может быть обслужена только одним ресурсом. При этом отсутствие очере- дей определяется тем, что на данном уровне планирования планировщик более высокого уровня выбирает из общего потока заявок такое количество заявок, которое соответствует количеству свободных ресурсов. Единичный элемент в МС C соответствует паре (ресурс(j), задача(i)) или ),( jj JR соответствует выполнению всех K обязательных требований, предъявляемых к системе обработки заявки на этом ресурсе. Нулевой эле- мент МС означает невозможность обслуживания. При такой постановке решение задачи распределения заявок по ресурсам сводится к задаче поиска максимального паросочетания в невзвешенном двудольном графе. Для ее решения традиционно применяется алгоритм направленного поиска (АНП) на основе метода Карпа–Хопкрофта. А.М. Сергиєнко, В.П. Симоненко, А.В. Симоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 22 В работе рассмотрены основы АНП с алгоритмом адаптивного муль- тианализа (АМА), который обеспечивает ускоренный поиск максимального паросочетания. ЭЛЕМЕНТЫ ТЕОРИИ УСКОРЕНИЯ РАСПРЕДЕЛЕНИЯ РАБОТ ПО РЕСУРСАМ В НЕОДНОРОДНЫХ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ В основу наиболее известных алгоритмов [15−23] поиска максимального паросочетания в произвольном графе положены два основных подхода [16]: сведение задачи к поиску максимального потока в сети и поиска увеличи- вающего пути от свободных вершин. В основу поиска увеличивающего че- редующегося пути положена схема Диница [16] и разработанный на его ос- нове алгоритм Хопкрофта–Карпа [22]. Наилучшие известные алгоритмы, реализующие этот подход, имеют полиномиальную временную сложность. Однако эти алгоритмы и реализующие их программы имеют сложную структуру или предназначены для частных случаев и не обеспечивают при- емлемых временных показателей, что ограничивает применение их в систе- мах диспетчирования параллельных систем. Для алгоритмов, использующих поиск увеличивающего чередующего- ся пути, правильность выбора начального варианта паросочетания в значи- тельной степени влияет на количество шагов при поиске такого пути. Мно- гие авторы [15−19] подчеркивают, что уникальные свойства двудольного графа позволяют уменьшить временную сложность алгоритмов. Для выявления особенностей двудольного графа, влияющих на времен- ную сложность, выполнено статистическое исследование программной мо- дели базового алгоритма Хопкрофта−Карпа с временной сложностью )( 5,2nO , .Nn = Результаты моделирования приведены на рис. 1 для графов размерности 10. I II III В ре мя , t ic k Рис. 1. Зависимость времени решения задачи поиска максимального паросочетания от коэффициента заполнения МС при N = 10 Улучшенный алгоритм назначения для планировщиков заданий в неоднородных … Системні дослідження та інформаційні технології, 2016, № 2 23 При моделировании время вычисления максимального паросочетания вычислялось в относительных временных единицах (тиках). Как видно из этого графика, время решения задачи назначения зависит от коэффициента заполнения МС C и ее размерности N. При этом в графике можно выделить три зоны (I, II, III) с существенно различным временем решения. Исследова- ния показали зависимость размера и положения этих зон от размерности задачи (рис. 2). Значительные различия временных затрат в выделенных зо- нах обусловило необходимость исследования в них свойств двудольного графа. Кроме этого, анализ базового алгоритма показал зависимость време- ни решения задачи от правильности выбора исходного (базового) варианта решения. Анализ алгоритмов поиска максимального паросочетания, а также ана- лиз процесса поиска решения в выделенных зонах показывает, что наибо- льшие трудности, влияющие на время поиска максимального паросочета- ния, возникают в двудольных графах, в которых перманент МС близок к единице или равен нулю. Эти трудности вызваны тем, что поиск макси- мального паросочетания основан на центральной теореме Кенига–Холла о существовании паросочетания [15, 16] и теореме Бержа [17]. Поэтому все известные алгоритмы предусматривают попытки поиска увеличивающегося пути от свободных вершин после генерирования базового варианта даже в том случае, если этого пути нет, что существенно увеличивает время поиска. ЭЛЕМЕНТЫ ТЕХНОЛОГИИ ПРЕДВАРИТЕЛЬНОГО АНАЛИЗА СТРУКТУРЫ ДВУДОЛЬНОГО ГРАФА Чтобы упростить решение задачи поиска максимального паросочетания, предлагается разделить его на несколько этапов [13, 14], когда собственно решению предшествует быстрый анализ исходной информации и выработка рекомендаций для ее дальнейшего решения. Добавление дополнительных шагов значительно меньшей временной сложности, чем сам алгоритм, не влияет на временную сложность алгоритма в целом, однако позволяет Рис. 2. Зависимость времени решения задачи планирования от ее размерности 5 30 0 50 100 150 200 250 300 350 400 5 15 25 35 45 55 65 75 85 100 Размерность Коэффициент заполнения МС В ре мя , t ic k Размерность задачи А.М. Сергиєнко, В.П. Симоненко, А.В. Симоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 24 уменьшить размерность решения задачи за счет выделения назначений, ко- торые обязательно нужно выполнить и выделить назначения, которые вы- полнять не нужно, и за счет этого избежать лишних проверок на возмож- ность включения их в решение. Кроме этого, на этапе подготовки исходной информации возможно вы- числение мощности максимального паросочетания. Имея численное значе- ние такой мощности, можно избежать поиска увеличивающего пути от сво- бодных вершин при достижении расчетной мощности паросочетания на очередном шаге поиска решения. Задача назначения требует определения условий возможности ее реше- ния, т.е. возможности полного распределения всех заявок по ресурсам. Не- обходимые условия существования такого решения формулируются сле- дующим образом: ∑ = ≠ N i jiC 1 0],[ , ,,,1 Mi K= ∑ = ≠ M i jiC 1 0],[ , .,,1 Ni K= (2) Анализ появления конфликтных ситуаций и условий их возникновения показывает, что выполнение условий (2) необходимо для получения вариан- та размещения, но недостаточно, так как они не оценивают взаимосвязи возможных мест размещения заявок и влияния возможного назначения на последующие. При выполнении исследований используются следующие определения. Определение 1. Задан невзвешенный двудольный граф )( ,E,VVG JR= , где },...,,{ 21 NR RRRV = , },...,,{ 21 NJ JJJV = — вершины графа, отвечающие ресурсам и задачам соответственно; },...,,{ 21 dEEEE = — дуги графа, ),( ** JREk = , где RVR ∈* и JVJ ∈* , ,,,1 dk K= 20 Nd ≤≤ . Матрица RJC называется матрицей связности графа G , если ,,...,1,,...,1.),(при0 ,),(при1 ],[ NjNiEJR EJR jiC ji ji RJ == ⎩ ⎨ ⎧ ∉ ∈ = Определение 2. Подмножество },...,,{ 21 naaaA = , ),( kk k JRa = , R k VR ∈ , J k VJ ∈ , ,,,1 nk K= Nn∈ называется паросочетанием графа G или его матрицы RJС , если )},(),...,,{( 11 nn JRJRA = , },...,{ 1 n R RRA = , },...,{ 1 n J JJA = , nk ,,1K= и RR VA ⊆ , JJ VA ⊆ . Другими словами, подмножество A ребер графа G = (V,E) называется паросочетанием, если никакие два ребра из А не имеют общей вершины. Определение 3. Пара ),( kk k JRa = , nk ,,1K= называется назначени- ем для ресурса R k VR ∈ и для задания J k VJ ∈ . Определение 4. Пусть },...,{ 1 zAAX = , Nz∈ — множество результа- тов всех возможных паросочетаний для графа ),( EVG = или его матри- Улучшенный алгоритм назначения для планировщиков заданий в неоднородных … Системні дослідження та інформаційні технології, 2016, № 2 25 цы RJС . Паросочетание A называется максимальным паросочетанием или решением для данного графа G , если * \|\| nA = и \|}\|,...,\|{\|max 1* zAAn = . ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ ВЫДЕЛЕНИЯ ОБЯЗАТЕЛЬНЫХ НАЗНАЧЕНИЙ Анализ свойств невзвешенного двудольного графа при решении задачи по- иска максимального паросочетания, а также анализ известных алгоритмов позволяют сформулировать следующую теорему. Теорема 1. Если в матрице ],[ jiCRJ графа )( ,E,VVG JR= существует решение A мощностью Nn = и существует такое назначение ),( qp , что 1],[ =qpCRJ , 0],[ =jpCRJ , qNj \},,1{ K∈ и/или 0],[ =qiCRJ , pNi \},,1{ K∈ , тогда это назначение ),( qp всегда участвует в решении A, т.е. Aqp ∈),( . Если для невзвешенного двудольного графа существует совершенное паросочетание и в графе есть вершина со степенью один, то ребро, инци- дентное этой вершине, и вершины, инцидентные этому ребру обязательно входят в совершенное паросочетание. Определение 5. Назначение ),( qp по теореме 1 называется обязатель- ным. Следствие. Если существует решение A , то задачу назначения можно разделить на две части: в первой части участвуют только обязательные на- значения ),( qp , во второй части — оставшиеся назначения из новой матри- цы связности RJC , которую получают после удаления строк и столбцов, со- ответствующих обязательным назначениям, определенным по теореме 1. Причем ввиду редукции графа и соответствующей коррекции МС это след- ствие может применяться рекуррентно. Теорема 1. Любая из вершин в невзвешенном двудольном графе, имеющая степень, равную единице, всегда участвует в одном из вариантов максимального паросочетания. Теорема 1 справедлива как для вершин-заявок, так и для вершин- ресурсов. В том случае, если вершины со степенью 1 образуют веер, то тео- рема 1* справедлива для любой вершины, входящей в веер и каждая из них может быть взята в паросочетание, а проверку остальных вершин на воз- можность получения увеличивающего пути выполнять не следует. Теорема 2. Если в матрице ],[ jiCRJ существует веер FAE : )},(),...,,{( 1 qRqRE f FA = , 1],[ =qRC k RJ , fk ,,1K= и 0],[ =kk RJ JRC , qJ k ≠ или )},(,...),,{( 1 f FA JpJpE = , 1],[ =k RJ JpC , fk ,,1K= и 0],[ =kk RJ JRC , pJ k ≠ , тогда любая из вершин из FAE вхо- А.М. Сергиєнко, В.П. Симоненко, А.В. Симоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 26 дит в один из вариантов максимального паросочетания, совершенное паро- сочетание не может быть получено и мощность максимального паросочета- ния определяется из выражения .1+−< fNM Следствие 1. Мощность решения задачи поиска максимального паро- сочетания может быть уменьшена на количество пар вершин, определенных по теоремам 1 и 1 , и поиск паросочетания должен вестись в новом су- графе. Следствие 1. Размерность решения задачи поиска максимального па- росочетания должна быть уменьшена на количество вершин, входящих в веер, а поиск паросочетания должен вестись в новом суграфе. Следствие 2. Смежные ребра, инцидентные вершинам, определенным по теореме 1, должны быть удалены из дальнейшего рассмотрения, а исход- ный граф редуцирован и преобразован в новый суграф. Следствие 3. Смежные ребра, инцидентные вершинам, определенным по теореме 2, должны быть удалены из дальнейшего рассмотрения, а исход- ный граф редуцирован и преобразован в новый суграф. ТЕОРЕТИЧЕСКИЕ ПРЕДПОСЫЛКИ ВЫДЕЛЕНИЯ КОНФЛИКТНЫХ НАЗНАЧЕНИЙ Базовый или начальный вариант решения задачи назначения обычно выпол- няется случайным образом. Анализ свойств двудольного графа показывает, что наряду с обязательными назначениями в нем можно выделить кон- фликтные, попадание которых в решение неминуемо приводит к появлению свободных вершин, а значит и к дополнительным шагам при формировании окончательного решения. Для выявления конфликтных назначений предла- гается выполнить анализ исходного графа, а именно его МС. В результате выполнения этой операции находятся все основные под- матрицы в МС ,JRJR CIC −=′ где I — квадратная матрица единичных элементов. Это соответствует выделению в исходной МС нулевых подмат- риц. Локализация таких подматриц реализуется целевой перестановкой строк и столбцов МС. При разработке алгоритма назначения учитывались следующие очевидные утверждения. Утверждение 1. Так как каждая строка МС представляет собой отра- жение возможного распределения заявок на ресурсы, то перемена местами двух строк МС с запоминанием нового расположения заявок не влияет на качественную характеристику МС и исходного графа. Утверждение 2. Так как каждый столбец МС представляет собой от- ражение претендования заявок на захват данного ресурса, то перемена мес- тами двух столбцов МС с запоминанием нового расположения ресурсов не влияет на качественную характеристику МС и исходного графа. Утверждения 1 и 2 не требуют доказательств, так как они следуют из определения изоморфности графов, полученных путем перестановки любых вершин. При эквивалентном преобразовании МС путем перестановки строк и столбцов делается попытка выполнить квазиназначения и получить один Улучшенный алгоритм назначения для планировщиков заданий в неоднородных … Системні дослідження та інформаційні технології, 2016, № 2 27 из вариантов решения задачи назначения соответствующего элементам главной диагонали МС. Это не противоречит одному из определений мак- симального паросочетания [15]: максимальное паросочетание — это макси- мальное множество единиц матрицы связности, у которых не совпадают ко- ординаты. Алгоритм изоморфного преобразования исходного графа основан на упорядочении МС. Строки упорядочиваются по возрастанию, а столбцы — по убыванию сумм единиц с попыткой получить единичную главную диа- гональ, что соответствует квазиназначению данной заявки на ресурс. Следу- ет отметить, что для уменьшения временной сложности алгоритма сами пе- рестановки не выполняются, а запоминается новый порядок строк и столбцов по результатам сортировки. В основу алгоритма положены мо- дифицированный метод разложения ориентированного графа на максималь- но сильносвязанные подграфы и алгоритм поиска минимального подмноже- ства сочленения, предложенные Мальгранжем [15]. Теорема 3. Если после эквивалентного преобразования удается полу- чить терм-ранг МС, равный рангу МС, то все заявки имеют места назначе- ния, соответствующие единицам в главной диагонали, и найдено полное паросочетание, получен один из вариантов решения задачи назначения зая- вок на ресурсы. Доказательство. Задача о паросочетании по определению, приведен- ном в работе [15], состоит в нахождении в исходном графе G максимального паросочетания. Если мощность паросочетания равна ]2/[V , т.е. наиболь- шему возможному значению в графе c V вершинами, то паросочетание на- зывается полным. Так как терм-ранг матрицы равен ]2/[V , то утверждение верно. Теорема 4. Если в матрице ],[ jiCRJ можно выделить подматрицу ],[ lkCMM , ,,,1 Tk K= NSNl ,),1( K+−= , где NTS >+ и MMC — нулевая матрица, тогда задача назначения не имеет полного решения (рис. 3, а−в). Доказательство. Предположим, что существует полное решение )},(,...),,{( 11 nn JRJRA = , .Nn = Так как решение полное, имеем == },...,{ 1 n R RRA },,2,1{},...,{ 1 NRRV NR K== ; == },...,{ 1 n J JJA .},,2,1{},...,{ 1 NJJV NJ K== Рассмотрим вершины },...,{ 1 TRT RRV = , которые принадлежат подмат- рице MMC . Поскольку они также входят в состав полного решения A, всегда имеем T соответствующих пар )},(),...,,{( ** 11 TT JRJR в A и 1],[ * =kkRJ JRC , для ,,,1 Tk K= JJTT VVJJ ⊂=},...,{ ** 1 . Очевидно, что для таких T ресурсов kR имеются по крайней мере T заданий * kJ , которые имеют доступ к ним. Поскольку MMC — нулевая матрица, имеем =],[ lkCMM 0],[ =lkCRJ . Это означает, что есть S вершин-заданий * kJ , которые не имеют доступа к T ресур- А.М. Сергиєнко, В.П. Симоненко, А.В. Симоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 28 сам .kR Поэтому осталось максимально SN − заданий, которые возможно имеют доступ к T ресурсам .kR Однако, исходя из условия, что NTS >+ , получа- ем ,SNT −> что является противоречием. Поэтому предложение о суще- ствовании полного решения A неверно. Теорема 4 справедлива не только для матрицы MMC , которая находит- ся над главной диагональю матрицы СRJ, но также для любой позиции MMC в СRJ. Из утверждений 1 и 2 очевидно, что всегда существует такое эквива- лентное преобразование матрицы, когда матрица MMC может быть перене- сена из любой позиции в правый верхний угол матрицы СRJ. Примечание. Доказательство теоремы 4 можно выполнить на основе теоремы Фробениуса–Кенига и Минка о вычислении перманента 0,1-матрицы. Teoрема 5. Если в матрице СRJ можно выделить подматрицу ],[ lkCMN , ,,,1 Tk K= NSNl ,),1( K+−= , где S + T = N и MNC — нулевая матрица, тогда },...,1{ SNRi −∈ , },...,1{ NTJ j +∈ , AJR ji ∉),( и все элементы ),( ji JR должны быть обнулены и исключены из рассмотре- ния при поиске полного решения (рис. 4). Доказательство. Предположим, что в СRJ имеется подматрица СMT, в которой есть элемент 1],[ =jiCMT и Aji ∈),( , },,1{* NTi K+∈ , },...,1{* SNJ −∈ . Выделение подматрицы MTС делит МС на подматрицы: ,TS × ,)( TSN ×− .)( STN ×− Так как по условию ,NTS =+ то подматри- цы TSN ×− )( и STN ×− )( — квадратные. Тогда предположение, что Aji ∈),( ** , где },...,1{* NTi +∈ , },...,1{* SNj −∈ , приводит к тому, что в подматрице NSN ×− )( должны присутствовать 1+T назначений, входя- щих в .A Но так как SNT −>+1 и ,NTS =+ то это предположение не- верно. Аналогичное доказательство можно привести и для подматрицы STN ×− )( . Рис. 3. К теореме 4: а — исходная МС; б — МС после преобразования; в — МС после коррекции: — конфликтная зона 1 1 0 1 0 1 0 2 0 1 1 1 1 1 3 1 0 1 0 1 0 4 0 1 1 1 1 1 5 1 0 1 0 1 0 6 1 0 1 0 1 0 1 2 3 4 5 6 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 6 1 1 1 0 0 0 1 1 1 1 0 0 0 5 1 1 1 0 0 0 3 1 1 1 0 0 0 2 1 1 0 1 1 1 4 1 1 0 1 1 1 3 5 1 4 2 6 S T а б в Улучшенный алгоритм назначения для планировщиков заданий в неоднородных … Системні дослідження та інформаційні технології, 2016, № 2 29 Teoрема 6. Если в матрице ],[ jiCMT можно выделить несколько под- матриц, удовлетворяющих теореме 5, то все соответствующие им подмат- рицы, симметричные относительно главной диагонали, являются конфликт- ными и должны быть обнулены (рис. 5, а−д). Доказательство теоремы аналогично доказательству теоремы 5 и спра- ведливо для каждой подматрицы отдельно. Теорема 7. Если в матрице СRJ существует подматрица MTC такая, что 0],[ =lkCMT , ,,,1 Tk K= NSNl ,),1( K+−= , кроме элемента 1]1,[ =+− SNTCMT , причем ,1+=+ NTS тогда назначение )1,( +− SNT является ключевым и всегда входит в состав одного из вариантов решения. Доказательство. Из условия теоремы в подматрице СMT можно выде- лить две подматрицы 1MNC и 2MNC такие, что ,0],[1 =lkCMN ,1,,1 −= Tk K NSNl ,,1K+−= ; ,0],[2 =lkCMN ,1,,1 −= Tk K NSNl ,,2 K+−= . (3) Применив теорему 6 для этих подматриц, получаем две подматрицы * 1MNC и * 2MNC , симметричные им относительно главной диагонали, которые являются конфликтными и должны быть обнулены. Тогда Р е с у р с ы 3 1 5 4 2 6 6 1 5 3 2 4 З а д а ч и Р е с у р с ы 1 2 3 4 5 6 1 2 3 4 5 6 З а д а ч и 1 1 0 1 0 1 0 2 0 1 1 1 1 1 3 1 0 1 1 1 0 4 1 1 1 1 0 1 5 1 0 1 1 1 0 6 1 0 1 1 1 0 1 2 3 4 5 6 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 6 1 1 1 1 0 0 1 1 1 1 0 0 0 5 1 1 1 1 0 0 3 1 1 1 1 0 0 2 1 0 1 1 1 1 4 1 1 0 1 1 1 3 1 5 4 2 6 S T а б в г д Рис. 4. К теореме 5: исходная МС: а — МС после преобразования; б — МС после коррекции; в — исходный граф; г — граф после редукции А.М. Сергиєнко, В.П. Симоненко, А.В. Симоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 30 0],[* 1 =lkCMN , ,,, NTk K= ;,,1 SNl −= K 0],[* 2 =lkCMN , ,,,1 NTk K+= .1,,1 +−= SNl K (4) Рассмотрим строку T и столбец .1+− SN Из условия теоремы, а так- же (3) и (4) имеем: ,1]1,[ =+− SNTCRJ ,0],[ =kTCRJ Nk ,,1K= и ,Tk ≠ ,0]1,[ =+− SNkCRJ Nk ,,1K= и .1≠k Но по теореме 1 и следствию 1 тео- ремы 2 назначение )1,( +− SNT является обязательным и всегда участвует в составе одного из вариантов решения максимального паросочетания. Следствие. Если МС представляет собой нижнюю диагональную мат- рицу, то задача имеет единственное решение, соответствующее единичной главной диагонали (рис. 6, а–д). Доказательство следует из теорем 5, 6. На основе теорем 1–7 и их следствий разработан алгоритм адаптивного мультианализа (АМА), который принадлежит к категории алгоритмов по- шагового конструирования решения задачи назначения [13, 14]. ОЦЕНКА ВРЕМЕННОЙ СЛОЖНОСТИ МОДИФИЦИРОВАННОГО ВЕНГЕРСКОГО АЛГОРИТМА Основой алгоритма направленного поиска решения задачи о назначениях является венгерский метод, имеющий временную сложность ),( 3nO где n — количество вершин графа матрицы RJC заданий-ресурсов. Тради- Р е с у р с ы 1 2 3 4 5 6 1 2 3 4 5 6 З а д а ч и Р е с у р с ы 3 1 5 4 2 6 6 1 5 3 2 4 З а д а ч и 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 6 1 1 1 0 0 0 1 1 1 1 0 0 0 5 1 1 1 0 0 0 3 1 1 1 1 0 0 2 1 0 1 1 1 1 4 1 1 0 1 1 1 3 1 5 4 2 6 1 1 0 1 0 1 0 2 0 1 1 1 1 1 3 1 0 1 1 1 0 4 1 1 1 1 0 1 5 1 0 1 0 1 0 6 1 0 1 0 1 0 1 2 3 4 5 6 а б в г д г д Рис. 5. К теореме 6: а — исходная МС; б — МС после преобразования; в — МС после коррекции; г — исходный граф; д — граф после преобразования и коррекции Улучшенный алгоритм назначения для планировщиков заданий в неоднородных … Системні дослідження та інформаційні технології, 2016, № 2 31 ционный АНП основан на методе Карпа–Хопкрофта. Его временная слож- ность известна из работы [22] и оценивается как ),( 5,0 mnO где m — коли- чество дуг графа. Но с учетом того, что ,2nmn ≤≤ алгоритм Карпа– Хопкрофта имеет временную сложность ).( 5,2nO Однако для процедуры поиска максимального паросочетания используется разработанный алго- ритм поиска максимального паросочетания вместо традиционного, который был использован в венгерском методе. Для оценки временной сложности АНП, т. е., венгерского метода с ис- пользованием АМА вместо алгоритма Карпа–Хопкрофта, выполним оценку временной сложности венгерского метода без алгоритма Карпа–Хопкрофта и оценку временной сложности АМА отдельно. Временная сложность венгерского метода без алгоритма Карпа- Хопкрофта. Алгоритм АНП состоит из 4 главных процедур. Проведем оценку временной сложности для каждой из них: 1. Процедура подготовки данных и поля определения поиска имеет временную сложность )(EO или в худшем случае ).( 2nO 2. Процедура определения внешней границы зоны поиска имеет временную сложность ).2( nO 3. Процедура ориентированного поиска оптимального расписания в выделенной линии поиска имеет временную сложность ),(XO которую определим позже. а б в 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 2 0 1 1 1 1 1 3 1 0 1 1 1 0 4 1 0 1 1 1 1 5 1 0 1 0 1 0 6 0 0 1 0 0 0 1 2 3 4 5 6 6 1 0 0 0 0 0 1 1 1 0 0 0 0 5 1 1 1 0 0 0 3 1 1 1 1 0 0 4 1 0 1 1 1 0 2 1 1 0 1 1 1 3 5 1 4 6 2 Р е с у р с ы 1 2 3 4 5 6 1 2 3 4 5 6 З а д а ч и Р е с у р с ы 3 5 1 4 6 2 6 1 5 3 4 2 З а д а ч и г д Рис. 6. К теореме 7: а — исходная МС; б — МС после преобразования; в — МС после коррекции; г — исходный граф; д — граф после коррекции А.М. Сергиєнко, В.П. Симоненко, А.В. Симоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 32 4. Процедура определения новой линии поиска имеет временную сложность )2( 2nnO + для маркировки и )3( 2nO для перестановки. В итоге ее общая временная сложность равна ),(YO где .5 2nnY += Для уменьше- ния временной сложности этой процедуры в АНП формируются дополни- тельные векторы степеней вершин и линии поиска. В этом случае .752 2 nnnnY =++= При сравнительной оценке различных алгоритмов процедура формиро- вания исходных данных исключается из рассмотрения, так как ее временная сложность одинакова. При поиске решения имеется цикл из процедур 4 и 3. Допустим что этот цикл выполняется z раз и имеет временную сложность Z. Так как венгерский метод имеет временную сложность ),( 3nO то временная сложность процедур внутреннего цикла будет равна ./)( 3 WnO Поскольку для процедуры 3 используется алгоритм Карпа–Хопкрофта, то )( 5,0 mnOX = или ),( 5,0nOX = ).5( 2nnOY += С другой стороны, временную сложность W можно принять как )()),((max 5,0 mnOYXOW == или )( 5,2nO . Отсюда ).,(max/)( 3 YXZnO = Таким образом, .)()(/)( 5,05,23 nOnOnOZ == Временная сложность АНП без процедуры 3, т.е. без алгоритма Карпа– Хопкрофта, оценивается как ,))5(2( 25,02 nnnnnO +++ а в общем случае — .)),(max( 5,05,02 nmnnnO + Без учета операций подготовки исходной инфор- мации временная сложность АНП равна .)),(max( 5,05,0 nmnnO Временная сложность АНП с АМА. Временная сложность алгоритма АНП, реализованного на основе предложенного метода пошагового конст- руирования, состоит из суммы оценок сложности шагов 1–4. Сложность процедуры подготовки исходной информации и анализа (шаг 1) зависит от количества ребер в исходном графе, а так как при этом выполняются обыч- ные операции по формированию матрицы связности или списков инцидент- ности, то сложность выполнения этого шага равна о(m). Ввиду того, что в предлагаемом алгоритме, кроме матрицы связности, формируются еще и векторы степеней вершин графа, то временная слож- ность этой процедуры увеличивается на .)2( nO Тогда общая временная сложность выполнения этой процедуры равна .)2( nmO + При выполнении грубого анализа ищутся изолированные вершины и для этого необходим одноразовый просмотр векторов, что определяет временную сложность вы- полнения этого шага как .)(nO Выполнение шага 2 для поиска обязательных назначений имеет вре- менную сложность )(nO и в случае каждого обнаружения вершины со сте- пенью 1 граф подвергается редукции с временной сложностью .)2( nO В случае единственного решения после выполнения n шагов получается полное решение. Тогда временная сложность нахождения полного решения равна .)2/)1(( mnnO +− Общая временная сложность этой процедуры рав- няется .)3()2( nOnnO =+ Улучшенный алгоритм назначения для планировщиков заданий в неоднородных … Системні дослідження та інформаційні технології, 2016, № 2 33 Временная сложность выполнения шага 3 определяется выбранным ал- горитмом сортировки одномерного массива и сложностью анализа преобра- зованной МC и ее коррекции и равна .)2/log2( mnnO + Общая временная сложность АНП ).)log3(23(АНП nnmOX ++= Ввиду того, что на общую оценку сложности алгоритма влияет выполнение шагов 1 и 4, а значение m в худшем случае равно n2, то сложностью остальных ша- гов можно пренебречь. Тогда временная сложность алгоритма АНП равна ).)log3(( nnmO ++ Однако анализ алгоритмов, выполняющих поиск макси- мального паросочетания на основе теоремы Бержа, и примеров [18, 19, 20], с помощью которых обычно иллюстрируется работоспособность предлагае- мых алгоритмов, позволяет сделать вывод, что для большинства вариантов не требуется выполнение шага 4 и, следовательно, сложность описанного алгоритма получения решения можно уменьшить для этого вида графов до )(mO при использовании списков инцидентности, а при использовании МС — до 2)(nO . Таким образом, временная сложность венгерского метода в общем случае )),(max( 5,0 nXnO или ,)/),(max( 5,2 mnXnO где == АНПXX .)log( nnmO += Тогда временная сложность АНП с АМА равна )log( 5,2 nnO при nm = , или )log( 5,1 nnO при .2nm = Следует отметить, что временная сложность АНП с АМА определялась для худшего случая, т.е. когда МС является заполненной. Но и в этом случае временная сложность АНП равна ,)log( 5,1 nnO что меньше .)( 3nO Достоверность расчета временной сложности проверялась на про- граммной модели. Результаты статистического исследования представлены на рис. 7. Ввиду того, что АНП является адаптивным алгоритмом, а поиск максимального паросочетания выполнялся в разреженной матрице с коэф- фициентом заполнения меньше 30%, то статистическая временная слож- ность АНП меньше )log( 5,1 nnO и близка к линейной. 0 20 40 60 80 100 120 20 40 60 80 100 120 140 160 180 200 Сложность O(n1,5logn) Время решения задачи В ре мя , t ic k Количество процессоров Рис. 7. Сравнение времен решения задачи планирования А.М. Сергиєнко, В.П. Симоненко, А.В. Симоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 2 34 ВЫВОДЫ Анализ наиболее известных подходов решения задач назначения (метод от- жега и решение задачи с помощью оценочных функций) показывает, что они не могут быть приняты в качестве базовых для динамического плани- ровщика, так как в первом случае временные параметры процесса поиска решения не удовлетворяют ограничениям по времени планирования, а во втором случае при приемлемом времени планирования качество планирова- ния ухудшается. Наиболее приемлемым является метод направленного по- иска, позволяющий осуществить поиск решения наилучшим способом, за- висящим от исходной информации. Венгерский алгоритм поиска максимального паросочетания во взве- шенном двудольном графе удовлетворяет предъявленным требованиям, так как обеспечивает направленный поиск решения, соответствует отношению работа–ресурс в предлагаемой модели системы пространственного планиро- вания. Классический венгерский алгоритм в каждой итерации выполняет поиск максимального паросочетания для невзвешенного двудольного графа с использованием алгоритма Карпа–Хопкрофта и имеет временную слож- ность ).( 3nO Она определяется алгоритмом Карпа–Хопкрофта с временной сложностью ).( 5,2nO Замена алгоритма Карпа–Хопкрофта другим алгоритмом с меньшей временной сложностью позволит снизить общую временную сложность вен- герского алгоритма. Элементы теории построения адаптивного поиска мак- симального паросочетания являются основой этого решения, так как поиск максимального паросочетания для невзвешенного двудольного графа выпо- лняется при степени заполнения МС не более 30%, что позволяет применить предложенные алгоритмы выполнения обязательных назначений и принцип исключающего планирования. Использование принципа исключающего планирования способствует в значительной степени повысить эффективность системы динамического планирования с сохранением качества решения в заданных пределах. Предложенные в работе процедуры подготовки исходных данных для планирования в реальном времени позволяют использовать модифициро- ванный венгерский алгоритм в качестве базового для пространственного планировщика нижнего уровня систем реального времени. ЛИТЕРАТУРА 1. Douglas T. Distributed computing in practice: The Condor experience / T. Douglas, T. Tannenbaum, M. Livny // Concurrency and Computation: Practice and Ex- perience. — 2005. — N 2. — P. 323−356. 2. Tannenbaum Andrew S. Distributed Systems: Principles and Paradigms (2nd Edi- tion) / Andrew S. Tanenbaum, Maarten van Steen. — Upper Saddle River, NJ, USA: Prentice-Hall, Inc. — 2006. 3. Метод опережающего планирования для ГРИД / В.Н. Коваленко, Е.И. Кова- ленко, Д.А. Корягин, Э.З. Любимский // Препринт ИПМ. — 2005. — № 112. — http://www.keldysh.ru/ papers/2005/prep112/prep2005_112.html. 4. Platform LSF 7 Update 6. An Overview of New Features for Platform LSF Adminis- trators. Официальный сайт компании Platform Computing Corporation — 2009. — http://www.platform.com/workload-management/ whatsnew_lsf7u6. pdf. Улучшенный алгоритм назначения для планировщиков заданий в неоднородных … Системні дослідження та інформаційні технології, 2016, № 2 35 5. Microsoft Windows Compute Cluster Server 2003. Руководство пользователя — 2006. — https://msdb.ru/Downloads/ WindowsServer2003/CCS/CCS2003 Guide_Rus.pdf. 6. TORQUE Resource Manager Guide. Официальный сайт компании Cluster Re- sources Inc. — 2009. — http://www.clusterresources.com/products/torque- resource-manager.php. 7. PBS Works. Официальный сайт компании Altair Engineering, Inc. — 2006. — http://www.pbsworks.com/. 8. Ding X. BWS: balanced work stealing for time-sharing multicores / X. Ding, K. Wang, P.B. Gibbons, X. Zhang // Proceedings of the 7-th ACM European Cconference on Computer Systems. — EuroSys '12. — New York, NY, USA: ACM. — 2012. — P. 365–378. 9. What is Condor? Официальный сайт продукта Condor. — 2006. — http://www. cs.wisc.edu/condor/ description.html. 10. IBM Tivoli Workload Scheduler LoadLeveler. Официальный сайт компании «Интерфейс» — 2007. — http://www.interface.ru/home.asp?artId=6283. 11. Maui Scheduler Administrator’s Guide. Официальный сайт компании Cluster Re- sourcesInc. — 2008. — http:// www. clusterresources. com/products /maui/ docs/index.shtml. 12. Moab Workload Manager. Официальный сайт компании Cluster Resources Inc. — 2008. — http://www.clusterresources.com/products/moab-cluster-suite/ workload-manager.php. 13. Симоненко А.В. Выбор стратегии пространственного планирования в парал- лельных вычислительных системах / А.В. Симоненко // Інформатика, управління та обчислювальна техніка. — К., 2001. — 35. — С. 104−108. 14. Симоненко А.В. Система пространственного распределения заданий в распре- делённых вычислительных системах / А.В. Симоненко, С.В. Пих, Н.В. Слуцкий, В.В. Воробйов // Інформатика, управління та обчислювальна техніка. — 2012. — 56. — С. 170. 15. Kaufmann A. Introduction a la combinatorique en vue des applications / A. Kaufmann. — Dunod, Paris. —1968. 16. Пападимитриу К. Комбинаторная оптимизация. Алгоритмы и сложность / К. Пападимитриу, K. Стайглиц. — М.: Mир. — 1985. 17. Berge C. Theorie des graphes et ses application / C. Berge. — Dunod, Paris. — 1958. 18. Casavant T.L. A taxonomy of scheduling in general-purpose distributed computing systems // IEEE Trans. Softw.Eng.14 ,(1988) / T.L. Casavant, J.G. Kuhl .— P. 141–154. 19. Blazevicz J. Scheduling independent multiprocessor tasks on a uniform k-processor system / J. Blazevicz, M. Drozdowski, G. Schmidt, D. De Werra // Parallel Com- puter. — 1994. — 20. — P. 15−28. 20. Elsadek A.A. Heuristic model for task allocation in a heterogeneous distributed sys- tems / A.A. Elsadek, B.E. Wells // proc. of PDPTA’96, California USA. — 1996. — 2. — P. 659−671. 21. Freund R.F. Generational Scheduling for Heterogeneous Computing Systems / R.F. Freund, B.R. Carter, D. Watson et al. // proc. of PDPTA’96, California USA, —1996. — 2. — P. 769−778. 22. Hopcroft J.E. An n2.5 Algorithm for Maximum Matchings in Bipartite Graphs // SIAM J. Comput. 2(4) / J.E. Hopcroft, R.M. Karp. — 1973. — P. 225−231. 23. Tan M., Antonio J.K, et. al. Scheduling and data relocation for sequentially executed subtasks in a heterogeneous computing system / M. Tan, J.K. Antonio et. al. // HCW’95. — 1995. — P. 109−120. Поступила 07.12.2015

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

Institution

Similar Items