Article Preview
Top1. Introduction
Partitionable parallel systems are used for executing parallel jobs. Parallel jobs usually require large number of processors (Yoo, & Das, 2002; Srinivasan et el., 2004; Kumar et el., 2003; Krueger et el., 1994; Maad, & Coghlan, 2010). In parallel systems, processor allocation scheme (PAS) selects the set of free processors for the incoming sequence of parallel tasks. The task is to assign processors for the parallel job if the available number of processor is sufficient. Otherwise, the job (request) is added to the queue. Job scheduling scheme manages all jobs in the queue and it selects the next job for execution (Krueger et el., 1994; Singh, & Vidyarthi, 2015). In the literature of parallel computing systems, a number of efficient processor allocation schemes have been proposed for allocating free processors to each incoming task in efficient decision time (Li, & Cheng, 1991; Chuang, & Tzeng, 1994; Chiu, & Chen, 1999). These schemes can be classified into: contiguous and noncontiguous processor allocation schemes (Zhu, 1992). In contiguous strategy, the allocated processors for a task are physically contiguous while in noncontiguous schemes the request can be served on multiple disjoint processors. Contiguous processor allocation schemes suffer from external processor fragmentation problem. External processor fragmentation occurs when the available number of processors is adequate to serve the request but the allocation scheme fails to assign the free processors for a parallel job (Zhu, 1992). To improve processors utilization, non-contiguous allocation schemes are proposed in (Li, & Cheng, 1991; Chuang, & Tzeng, 1994; Chiu, & Chen, 1999). In non-contiguous processor allocation scheme, free processors are allocated to the new job even if they are not physically contiguous.
In this paper, we present a solution to the processors allocation problem using a game theory model (Herbert, 2009) with the objective of maximizing users’ profits. We consider a 2D mesh connected multicomputer network where free processors are rented to the users for executing their parallel tasks for a short period of time. We formulate this problem as an oligopoly market in which users compete with each other in terms of the amount of commodity supplied to the market to gain the maximum profit. In this case, the users are analogous to the firms who compete for the free processors available in the mesh network. The cost of renting processors is determined using pricing function. A noncooperative game is proposed to analyze this situation and the Nash equilibrium is considered as the solution of this game.
Game theory is a straightforward methodology to solve this problem where users’ objectives are in conflict. The main objective of using game theory for this problem is to maximize the profit of all users, based on the equilibrium adopted by all users. Moreover, the revenue of the service provider is maximized by using game theory. Specifically, the pricing function used by the user can be optimized to maximize the gained profit. A static game is formulated to model the competition among users where all users can completely observe the strategies adopted by others and the corresponding payoffs. Nash equilibrium is obtained as the outcome for this game. However, in some practical systems, users have not complete information about the game. To model this scenario, we use a dynamic game where users select their strategies based on the pricing information obtained from the PAS. Each user adjusts its request of processors based on the price information.