MARO - MinDrift affinity routing for resource management in heterogeneous computing systems

ABSTRACT

This paper deals with designing effective resource management strategies for systems of heterogeneous computers. Each computer is represented as an abstract server, capable of serving different task demands at different rates. We consider a system with I types of independent Poisson task demand arrival streams and J parallel servers with independent non-identical processing time distributions for each arrival type. The decision of routing each type i task immediately upon arrival to a server j is made by comparing the state information of a subset of the J servers. We show that choosing the subset according to a linear programming (LP) problem which maximizes the system capacity can not only significantly reduce the amount of state information required in making the routing decision, but also yield shorter total mean queue length (and hence mean time in system) compared with the policies requiring global state information. In addition, we explore means of limiting flexibility to further reduce the required state information.

REFERENCES

• 1: I. Al-Azzoni and D. G. Down. Linear Programming Based Affinity Scheduling for Heterogeneous Computing Systems. Proceedings of the 2007 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'07), 2007.
• 2: Sigrún Andradóttir , Hayriye Ayhan , Douglas G. Down, Dynamic Server Allocation for Queueing Networks with Flexible Servers, Operations Research, v.51 n.6, p.952-968, November 2003 [doi>10.1287/opre.51.6.952.24913]
• 3: C. Anglano, J. Brevik, M. Canonico, D. Nurmi and R. Wolski. Fault-aware Scheduling for Bag-of-Tasks Applications on Desktop Grids. Proceedings of the 7th International Conference on Grid Computing, pages 56--63, 2006.
• 4: Henri Casanova , Dmitrii Zagorodnov , Francine Berman , Arnaud Legrand, Heuristics for Scheduling Parameter Sweep Applications in Grid Environments, Proceedings of the 9th Heterogeneous Computing Workshop, p.349, May 01-01, 2000
• 5: Ian Foster , Carl Kesselman , Steven Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, v.15 n.3, p.200-222, August 2001 [doi>10.1177/109434200101500302]
• 6: R. F. Freund , M. Gherrity , S. Ambrosius , M. Campbell , M. Halderman , D. Hensgen , E. Keith , T. Kidd , M. Kussow , J. D. Lima , F. Mirabile , L. Moore , B. Rust , H. J. Siegel, Scheduling Resources in Multi-User, Heterogeneous, Computing Environments with SmartNet, Proceedings of the Seventh Heterogeneous Computing Workshop, p.3, March 30-30, 1998
• 7: Jong-Kook Kim , Sameer Shivle , Howard Jay Siegel , Anthony A. Maciejewski , Tracy D. Braun , Myron Schneider , Sonja Tideman , Ramakrishna Chitta , Raheleh B. Dilmaghani , Rohit Joshi , Aditya Kaul , Ashish Sharma , Siddhartha Sripada , Praveen Vangari , Siva Sankar Yellampalli, Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment, Journal of Parallel and Distributed Computing, v.67 n.2, p.154-169, February, 2007 [doi>10.1016/j.jpdc.2006.06.005]
• 8: A taxonomy and survey of grid resource management systems for distributed computing, Software—Practice & Experience, v.32 n.2, p.135-164, February 2002 [doi>10.1002/spe.432]
• 9: Muthucumaru Maheswaran , Shoukat Ali , Howard Jay Siegel , Debra Hensgen , Richard F. Freund, Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems, Proceedings of the Eighth Heterogeneous Computing Workshop, p.30, April 12-12, 1999
• 10: Michael Mitzenmacher, How Useful Is Old Information?, IEEE Transactions on Parallel and Distributed Systems, v.11 n.1, p.6-20, January 2000 [doi>10.1109/71.824633]
• 11: Michael Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1094-1104, October 2001 [doi>10.1109/71.963420]
• 12: A. Sharifnia. Instability of the Join-the-Shortest-Queue and FCFS Policies in Queueing Systems and Their Stabilization. Operations Research, 45(2):309--314, 1997.
• 13: Thomas Sterling , Ewing Lusk , William Gropp, Beowulf Cluster Computing with Linux, MIT Press, Cambridge, MA, 2003
• 14: Alexander L. Stolyar, Optimal Routing In Output-Queued Flexible Server Systems, Probability in the Engineering and Informational Sciences, v.19 n.2, p.141-189, April 2005 [doi>10.1017/S0269964805050096]