Coordinated global and private job-flow scheduling in grid virtual organizations

https://doi.org/10.1016/j.simpat.2020.102228Get rights and content

Abstract

In this work, an approach for a preference-based job-flow scheduling in Grid virtual organizations is proposed and studied. Virtual organizations provide uniform rules of the resources sharing and consumption and should respect individual and common preferences of its stakeholders: users, resource providers and administrators. In most cases, a virtual organization’s stakeholders pursue contradictory market-based goals, which may be expressed in terms of time and cost. Still, mutually beneficial job-flow scheduling scenarios are possible in such multi-agent computing environments when the different optimization criteria are coordinated. For this purpose we consider different resources allocation heuristics and scenarios based on a simple linear combination of global (group) and private (user) job scheduling criteria. We study backfilling-based job queue scheduling procedure with a secondary preference-based optimization performed only on the resources allocation step. This approach allows us to respect backfilling-based jobs execution priorities together with more specific individual jobs criteria, including total execution cost or time minimization.

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)

  • R. Buyya et al.

    Economic models for resource management and scheduling in grid computing

    J. Concurr. Comput.

    (2002)
  • K. Kurowski et al.

    Multicriteria aspects of grid re-source management

  • R. Calheiros et al.

    Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms

    J. Softw.

    (2011)
  • V. Toporkov et al.

    Heuristic strategies for preference-based scheduling in virtual organizations of utility grids

    J. Ambient Intell. Humaniz. Comput.

    (2015)
  • S. Penmatsa et al.

    Cost minimization in utility computing systems

    J. Concurr. Comput.

    (2014)
  • K. Kim et al.

    Fair resource sharing in hierarchical virtual organizations for global grids

    Proc. 8th IEEE/ACM International Conference on Grid Computing

    (2007)
  • I. Rodero et al.

    Enabling interoperability among grid metaschedulers

    J. Grid Comput.

    (2013)
  • P. Skowron et al.

    Non-monetary fair scheduling cooperative game theory approach

    Proc. Twenty-fifth annual ACM Symposium on Parallelism in Algorithms and Architectures

    (2013)
  • A. Inoie 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)
There are more references available in the full text version of this article.

Cited by (0)

View full text