One model of optimal resource allocation in homogeneous multiprocessor system

A.Yu. Doroshenko, O.P. Ignatenko, P.A. Ivanenko

Abstract


This paper deals with the control model of optimal recourse allocation in homogeneous multiprocessor system. We proposed an approach to developing optimal control using fluid models theory domain. We obtain analytic solution for time depending of parallel execution parameters. Results are validated by experimentation for matrix multiplication example.

Problems in programming 2011; 1: 29-38


References


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

Foster I., Kesselman C. The Grid: Blueprint for a new Computing Infrastructure. Morgan Kaufmann, 2004. – 676 p.

Shivaratri N.G., Krueger P., Singhal M. (1992, December). Load distribution for locally distributed systems. IEEE Computer 8 (12), P. 33 – 44.

Chronopoulos A.T., Penmatsa S., Yu N. Scalable Loop Self-Scheduling Schemes for Heterogeneous Clusters // Proc. of IEEE Intern. Conf. on Cluster Computing, Chicago, Illinois, USA, 2002. – P. 353 – 359.

Tantawi A.N., Towsley D. Optimal static load balancing in distributed computer systems // J. of the ACM, 32 (2), 1995. – P. 445 – 465.

Tang X., Chanson S.T. Optimizing static job scheduling in a network of heterogeneous computers // Proc. of the Intern. Conf. on Parallel Processing, 2002. – P. 373 – 382.

Ross K.W., Yao D.D. Optimal load balancing and scheduling in a distributed computer system // Journal of the ACM, 38 (3), 1991. – P. 676 – 690.

Grosu D., Chronopoulos A.T. A game-theoretic model and algorithm for load balancing in distributed systems // In Proc. of the 16th IEEE Intern. Parallel and Distributed Processing Symposium, Ft Lauderdale, Florida, USA, 2002. – P. 146 – 153.

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

Kwok Y.K., Hwang K., Song S. Selfish grids: Game-theoretic modeling and nas/psa benchmark evaluation // IEEE Trans. on Parallel and Distributed Systems, 18 (5), 2007. – P. 621 – 636.

Ghosh P., Roy N., Das S.K., Basu K. A pricing strategy for job allocation in mobile grids using a non-cooperative bargaining theory framework // J. of Parallel and Distributed Computing, 65 (11), 2005. – P. 1366 – 1383.

Kwok Y.K., Song S., Hwang K. Selfish grid computing: Game-theoretic modelling and nas performance results // In Proc. of the CCGrid, 2005. – P. 1143 – 1150.

Hui C.C., Chanson S.T. (1999, July-Sept.). Improved strategies for dynamic load balancing. IEEE Concurrency, 7 (3), 1999. – P. 58 – 67.

Campos L.M., Scherson I. Rate of change load balancing in distributed and parallel systems // Parallel Computing, 26 (9), 2000. – P. 1213 – 1230.

Corradi A., Leonardi L., Zambonelli F. Diffusive load-balancing policies for dynamic applications // IEEE Concurrency, 7 (1), 1999. – P. 22 – 31.

Lee S.H., Hwang C.S. A dynamic load balancing approach using genetic algorithm in distributed systems // In Proc. of the IEEE Intl. Conf. on Evolutionary Computation, 1998. – P. 639 – 644.

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

Meyn S. Control Techniques for Complex Networks. – Cambridge University Press, 2007. – 582 p.

Милютін А.А., Дмитрук А.В., Осмоловский М.П. Принцип максимума в оптимальном управлении. – М.: Изд-во МГУ, 2004. – 168 с.


Refbacks

  • There are currently no refbacks.