Улучшеный алгоритм назначения для планировщиков заданий в неоднородных распределенных вычислительных системах
Anatolij M. Sergiyenko, Valery P. Simonenko, A. V. Simonenko
Sistemnì Doslìdženâ ta Informacìjnì Tehnologìï · 2016
doi:10.20535/srit.2308-8893.2016.2.03 (opens in a new tab)
We email you when a new notice or a question about this paper appears.
Abstract
Рассмотрены основы проектирования пространственных планировщиков для глобальных, неоднородных, распределенных вычислительных систем. Представле-ны теоремы, позволяющие для двудольных графов, отображающих претендование заявок на ресурсы, уменьшить временную сложность венгерского алгоритма с O(n3) до O(n1,5 log n). Подход применяется в алгоритме адаптивного мультианали-за, который основан на предварительном анализе и коррекции графа паросочетаний. При его применении к матрицам графов с коэффициентом заполнения меньше 30% алгоритм имеет статистическую временную сложность, которая близка к линейной.
Abstract licence: CC BY-ND
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.