Game-theory analysis of multi-processor schedulers. Simulation model

O.P. Ignatenko, V.I. Odobesku

Abstract


This paper deals with a game model of users performing parallel computing in a heterogeneous multiprocessor system. The proposed approach is applied to the problem of matrix multiplication on the system with the scheduler of min-min type. The user’s action is to choose the size of the blocks into which the matrix is cut. Each user tries to optimize own finish time, which leads to conflict. Using the game theoretic approach, we build game model and found the conditions of Nash equilibrium existence in the scheduling game of two users. Simulation program was built to provide experimental data.

Problems in programming 2018; 2-3: 075-082


Keywords


parallel scheduling; game theory; fluid model; Nash equilibrium; simulation

References


Srinivasa Prasanna G.N., Musicus B. Generalized Multiprocessor Scheduling Using Optimal Control. Proc. SPAA. 1991. P. 216-228.

https://doi.org/10.1145/113379.113399

Grosu D., Chronopoulos A.T. Noncooperative load balancing in distributed systems. Journal of Parallel and Distributed Computing. 2005. 65 (9). P. 1022-1034.

https://doi.org/10.1016/j.jpdc.2005.05.001

Nazarathy Y., Weiss G. A Fluid Approach to Large Volume Job Shop Scheduling. Journal of Scheduling. 2010. 13(5), P. 509-529.

https://doi.org/10.1007/s10951-010-0174-0

Anatoly, Doroshenko, Ignatenko Oleksii, and Ivanenko Pavlo. One model of optimal resource allocation in homogeneous multiprocessor system. Problems in programming. 1 (2011): 29-39.

Andon, F.I., and O.P. Ignatenko. "Modeling conflict processes on the internet." Cybernetics and Systems Analysis 49.4 (2013): 616-623.

https://doi.org/10.1007/s10559-013-9548-6

Ignatenko O. Game theoretic analysis of multi-processor schedulers: matrix multiplication example. Proc. 3th Int. Conf. "ICT in Education, Research and Industrial Applications. Integration, Harmonization and Knowledge Transfer" (ICTERI 2017), Kyiv, Ukraine (15-18 May, 2017). 2017. P. 88-95.




DOI: https://doi.org/10.15407/pp2018.02.075

Refbacks

  • There are currently no refbacks.