Coordinated global and private job-flow scheduling in grid virtual organizations
Introduction
Distributed and high performance computing systems (HPCS) represent complex environments with many different agents: users, resource providers, administrators, authorities, etc. Large heterogeneous computing environments, like Grid, incorporate multitude of geographically distributed computing nodes. While users of such systems are able to submit their individual jobs for the execution without any system, regularity or explicit restrictions. One of the most efficient way to organize relations between the HPCS participants is to use the so-called economic scheduling models [1], [2], [3], [4], [5], [6]. In this way, the questions of jobs’ execution order, their actual start times and the particular resources selection are solved based on market principles, including time and cost parameters. Users are represented by special brokers implementing requirements and individual preferences for the job’s execution quality.
More efficient in terms of the system resources usage models involve formation of the virtual organizations (VOs) [2], [4], [6], [7]. VOs provide uniform rules of the resources sharing and consumption based on the economic models. The presence of global job-flow scheduling policies and criteria make it possible to improve the shared resources usage efficiency.
In most cases, VO stakeholders pursue contradictory goals working in HPCSs. Users usually interested in the fastest possible completion times for their jobs by the least possible costs, whereas the resources providers pursue payload and profit maximization. VO policy may offer optimization tools to satisfy the stakeholders’ preferences as follows: follow users’ optimization criteria for selected jobs [6], [8], keep resources’ overall load balance [9], observe strict jobs execution order and maintain priorities [10], [11], [12], optimize overall scheduling performance by some general global criteria [13], etc.
Section snippets
Related works
In many models VO stakeholders preferences are usually ensured only partially by implementing only users’ private criteria in a market-based competitive environments [1], [6] or by optimizing the system-related criteria [11], [12]. However, an efficient resources distribution and scheduling organization may benefit all VO stakeholders by minimizing the jobs’ waiting time. From the other hand, VO policies in general should respect all members to function properly, and the most important aspect
Resources selection problem definition
Throughout the paper we consider a problem of an efficient job queue scheduling and resources allocation in computing environments with heterogeneous computing nodes. So as not to complicate the model, we assume there is one single job queue with predefined job priorities we should generally comply (like in backfilling [12]). At the same time, the heterogeneity of the considered computing environment implies that the constituent computing nodes differ in their fundamental characteristics, such
Simulation environment setup
The main results of this work were obtained through the simulation study. For this purpose we used a dedicated distributed computing environment simulator [4], [16], [17]. It implements a domain of heterogeneous computing nodes with a space-shared resources allocation policy and fully supports computing model described in Section 3.1.
For the reliable results we perform multiple simulations of homogeneous, but randomized scheduling scenarios. During each such a scenario new instances of the job
Conclusions and future work
In this paper we study the problem of coordinating multiple private and global criteria for a fair job-flow scheduling in HPCS and Grid virtual organizations. The main idea of the proposed approach is to follow a baseline job-flow scheduling procedure (for example, backfilling) and in addition to the primary scheduling criterion implement secondary optimization by using a combined criterion. In different backfilling-based scheduling scenarios we demonstrate how the computing system features and
Funding
This work was partially supported by the Council on Grants of the President of the Russian Federation for State Support of Young Scientists (grant YPhD-2979.2019.9), RFBR (grants 18-07-00456 and 18-07-00534), and by the Ministry on Education and Science of the Russian Federation (project no. 2.9606.2017/8.9).
Declaration of Competing Interest
None
References (18)
- et al.
Economic models for resource management and scheduling in grid computing
J. Concurr. Comput.
(2002) - et al.
Multicriteria aspects of grid re-source management
- et al.
Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms
J. Softw.
(2011) - et al.
Heuristic strategies for preference-based scheduling in virtual organizations of utility grids
J. Ambient Intell. Humaniz. Comput.
(2015) - et al.
Cost minimization in utility computing systems
J. Concurr. Comput.
(2014) - et al.
Fair resource sharing in hierarchical virtual organizations for global grids
Proc. 8th IEEE/ACM International Conference on Grid Computing
(2007) - et al.
Enabling interoperability among grid metaschedulers
J. Grid Comput.
(2013) - et al.
Non-monetary fair scheduling cooperative game theory approach
Proc. Twenty-fifth annual ACM Symposium on Parallelism in Algorithms and Architectures
(2013) - et al.
Pareto set, fairness, and nash equilibrium: a case study on load balancing
Proceedings of the 11th International Symposium on Dynamic Games and Applications
(2004)