Resource allocation on computational grids using a utility model and the knapsack problem

Abstract

This work introduces a utility model (UM) for resource allocation on computational grids and formulates the allocation problem as a variant of the 0–1 multichoice multidimensional knapsack problem. The notion of task-option utility is introduced, and it is used to effect allocation policies. We present a variety of allocation policies, which are expressed as functions of metrics that are both intrinsic and external to the task and resources. An external user-defined credit-value metric is shown to allow users to intervene in the allocation of urgent or low priority tasks. The strategies are evaluated in simulation against random workloads as well as those drawn from real systems. We measure the sensitivity of the UM-derived schedules to variations in the allocation policies and their corresponding utility functions. The UM allocation strategy is shown to optimally allocate resources congruent with the chosen policies.

Introduction

Grid computing [1], [2] can be viewed as a wide-area distributed system. Grid concepts and technologies were developed in order to enable resource sharing within scientific collaborations. One underlying challenge in grid computing is the coordination of resource sharing.

Allocating resources on computational grids is a complex procedure involving coordinated resource sharing and meeting the requirements of users and resource owners. Notable previous research includes the matchmaking framework [3] implemented in Condor-G [4]. The matchmaking procedure evaluates job and resource Rank and Requirements expressions to find ideal matches. Economic approaches to grid resource allocation were introduced by Buyya et al. [5] and were implemented in Nimrod-G [6] and Gridbus [7], [8]. Additional notable research in this area includes a variety of makespan minimizing heuristics [9], [10], [11], [12], and the GrADS metascheduler [13].

In this work, we improve upon the existing research by introducing a novel grid resource allocation strategy which is composed of a utility model (UM) and a formulation of the allocation as a knapsack problem. The utility model, previously introduced by Khan et al for network routing and admission control [14], is used to objectively describe the grid resource allocation options; it is developed from the idea that the allocation options vary in their perceived value, or utility, to a user or resource owner. Using the UM, the allocation problem can be naturally formulated as a variant of the 0–1 multichoice multidimensional knapsack problem (MMKP); the MMKP finds the set of allocation options which optimizes the global utility sum. In contrast with previous usage of the knapsack problem for task scheduling [28], the combined utility/knapsack approach presented in this paper allows Quality of Service (QoS) measures to be objectively defined and implemented on the grid.

Resource allocation strategies can be classified according to two criteria [15]. The first criterion involves the description of the grid, which can be either state-based or model-based. The second criterion involves task behaviour; in a preemptive environment, tasks assigned to hosts are allowed to be paused and migrated to other hosts, while in a non-preemptive environment, tasks are required to perform all of their execution on a single host.

In this work we assume a state-based preemptive form of a grid. That is, there exists a mechanism through which resource states and task metadata can be identified. Tasks are assumed to be checkpointable and malleable, meaning that tasks can be paused to be migrated between processors and that the number of processors used in parallel can be varied.

Whereas a significant number of grid applications are neither checkpointable nor malleable, indications are that grid deployments will soon incorporate system software that make these assumptions realistic. For example, by building a grid using virtual machine technologies such as Xen [16], the grid could allow application images to be easily paused and migrated to a new host. Additionally, the independent nature of many grid applications allows malleability to be achieved by executing more than one instance of an application on a single host. For example, a 64 process task can be executed on 32 processors by submitting 2 processes to each processor, if memory limits permit. It is important to note that the techniques presented in this work are also applicable as an admission control system in non-checkpointing environments. In such grids, the system will use the utility/knapsack approach to optimize the initial allocation of each task. However, without checkpointing, newly arriving high priority tasks will not be able to preempt lower priority tasks; thus, the system will not achieve the same overall performance as when checkpointing is available.

The remainder of this paper is organized as follows. In Section 2 we introduce the notion of utility in relation to grid resource allocation. Next, in Section 3 we formulate resource allocation on the grid as a variant of the 0–1 multichoice multidimensional knapsack problem. We then introduce allocation policies and their utility functions (Section 4) and demonstrate these strategies using random and real task workloads (Section 5). In Section 6 we measure the sensitivity of the task schedules to changes in the allocation policies. Finally, in Section 7 we reflect on our findings and conclude.