An enhanced scheduling algorithm for task planners in heterogeneous distributed computing systems
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2016.2.03Keywords:
schedule, bipartite matching graph, Hungarian algorithm, task schedulerAbstract
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(n3) to O(n1,5 log n). 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.References
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.
