An enhanced scheduling algorithm for task planners in heterogeneous distributed computing systems

Authors

DOI:

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

Keywords:

schedule, bipartite matching graph, Hungarian algorithm, task scheduler

Abstract

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.

Author Biographies

Anatolij M. Sergiyenko, Department of computer engineering at NTUU "KPI", Kyiv

Anatolij Mykhailovych Sergiyenko,

doctor of technical sciences, senior scientist of the department of computer engineering at NTUU "KPI", Kyiv, Ukraine

Research interests: computer architecture, computer design automation, programmable gate arrays, specialized computers, digital signal processing.

Valery P. Simonenko, Department of computer engineering at NTUU "KPI", Kyiv

Valery Pavlovych Simonenko,

doctor of technical sciences, professor of the department of computer engineering at NTUU "KPI", Kyiv, Ukraine

Research interests: computer architecture, parallel computing systems, operating systems, system programming.

A. V. Simonenko, Department of computer engineering at NTUU "KPI", Kyiv

Andriy Valerijovych Simonenko,

researcher of the department of computer engineering at NTUU "KPI", Kyiv, Ukraine

Research interests: computer architecture, parallel computing systems, operating systems, system programming.

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.

Published

2016-06-21

Issue

Section

Decision making and control in economic, technical, ecological and social systems