DOI: https://doi.org/10.20535/SRIT.2308-8893.2016.2.03

Покращений алгоритм призначення для планувальників завдань в неоднорідних розподілених обчислювальних системах

Anatolij M. Sergiyenko, Valery P. Simonenko, A. V. Simonenko

Анотація


Розглянуто основи проектування просторових планувальників для глобальних, неоднорідних, розподілених обчислювальних систем. Подано теореми, що дають змогу для двочасткових графів, які відображають претендування заявок на ресурси, зменшити кількість варіантів розв’язків, що розглядаються, видаливши з матриці зв’язності безперспективні елементи. Це дозволило зменшити часову складність угорського алгоритму з O(n3) до O(n1,5 log n). Підхід застосовується в алгоритмі адаптивного мультианалізу, який полягає у попередньому аналізі та коригуванні графу паросполучень. У разі його застосування до матриць графів, які мають коефіцієнт заповнення менший за 30%, алгоритм має статистичну часову складність, яка близька до лінійної.

Ключові слова


розклад;парування у двочастковому графі;Угорський алгоритм;планувальник завдань

Повний текст:

PDF (Русский)

Посилання


Douglas T. Distributed computing in practice: The Condor experience / T. Douglas, T. Tannenbaum, M. Livny // Concurrency and Computation: Practice and Experience. — 2005. — N 2. — P. 323?356.

Tannenbaum Andrew S. Distributed Systems: Principles and Paradigms (2nd Edition) / Andrew S. Tanenbaum, Maarten van Steen. — Upper Saddle River, NJ, USA: Prentice-Hall, Inc. — 2006.

Metod operezhajuschego planirovanija dlja GRID / V.N. Kovalenko, E.I. Kovalenko, D.A. Korjagin, E.Z. Ljubimskij // Препринт ИПМ. — 2005. — № 112. — http://www.keldysh.ru/ papers/2005/prep112/prep2005_112.html.

Platform LSF 7 Update 6. An Overview of New Features for Platform LSF Administrators. Ofitsial'nyj sajt kompanii Platform Computing Corporation — 2009. — http://www.platform.com/workload-management/ whatsnew_lsf7u6. pdf.


Пристатейна бібліографія ГОСТ


1. Douglas T. Distributed computing in practice: The Condor experience / T. Douglas, T. Tannenbaum, M. Livny // Concurrency and Computation: Practice and Experience. — 2005. — N 2. — P. 323?356.

2. Tannenbaum Andrew S. Distributed Systems: Principles and Paradigms (2nd Edition) / 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 Administrators. Официальный сайт компании Platform Computing Corporation — 2009. — http://www.platform.com/workload-management/ whatsnew_lsf7u6. pdf.