Competitive Processors Allocation in 2D Mesh Connected Multicomputer Networks: A Dynamic Game Approach

Competitive Processors Allocation in 2D Mesh Connected Multicomputer Networks: A Dynamic Game Approach

Ayoub Alsarhan (Faculty of Prince Al-Hussein bin Abdullah II for Information Technology, Hashemite University, Zarqa, Jordan), Emad Eddien Awad Abdallah (Hashemite University, Zarqa, Jordan) and Ashraf H. Aljammal (Hashemite University, Zarqa, Jordan)
Copyright: © 2017 |Pages: 17
DOI: 10.4018/IJGHPC.2017040104

Abstract

“Partitionable parallel machine” is an efficient computing system for executing parallel applications. In this paper, the problem of processors sharing among multiple users is addressed where users' requests are executed in a 2D mesh-connected multicomputer simultaneously. The problem is formulated as an oligopoly market where users compete to rent free processors. The system consists of self-interested users with different needs and utility functions. Each user engages in an auction with others to achieve their needs of processors. The most significant challenge for the users is how to select the optimal number of requested processors for winning the auction. A noncooperative game is used to obtain the optimal processors allocation for users. Game theory is employed to address this challenge for competing users. Nash equilibrium is considered as the solution of this game. The numerical results reveal the dynamics of distributed dynamic adaptation of processors sharing strategies.
Article Preview

1. 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing