Exploring the throughput-fairness tradeoff of deadline scheduling in heterogeneous computing environments

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Exploring the throughput-fairness tradeoff of deadline scheduling in heterogeneous computing environments

Full text

Pdf (263 KB)

Source

Joint International Conference on Measurement and Modeling of Computer Systems archive
Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems table of contents

Annapolis, MD, USA

POSTER SESSION: Posters table of contents

Pages 463-464

Year of Publication: 2008

ISBN:978-1-60558-005-0

Also published in ...

Authors

Vasumathi Sundaram	University of Minnesota, Minneapolis, MN, USA
Abhishek Chandra	University of Minnesota, Minneapolis, MN, USA
Jon Weissman	University of Minnesota, Minneapolis, MN, USA

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 60, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1375457.1375522 What is a DOI?

ABSTRACT

The scalability and computing power of large-scale computational platforms has made them attractive for hosting compute-intensive time-critical applications. Many of these applications are composed of computational tasks that require specific deadlines to be met for successful completion. In this paper, we show that combining redundant scheduling with deadline-based scheduling in these systems leads to a fundamental tradeoff between throughput and fairness. We propose a new scheduling algorithm called Limited Resource Earliest Deadline (LRED) that couples redundant scheduling with deadline-driven scheduling in a flexible way by using a simple tunable parameter to exploit this tradeoff. Our evaluation of LRED shows that LRED provides a powerful mechanism to achieve desired throughput or fairness under high loads and low timeliness environments.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	David P. Anderson, BOINC: A System for Public-Resource Computing and Storage, Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing, p.4-10, November 08-08, 2004 [doi>10.1109/GRID.2004.14]
	2	R. Jain, D. Chiu, and W. Hawe. A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems. DEC Research Report TR-301, Sep 1984.
	3	C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
	4	V. Sundaram, A. Chandra, and J. Weissman. Exploring the Throughput-Fairness Tradeoff of Deadline Scheduling in Heterogeneous Computing Environments. Technical Report 08-003, 2008.
	5	D. Zhou , V. Lo, Cluster Computing on the Fly: resource discovery in a cycle sharing peer-to-peer system, Proceedings of the 2004 IEEE International Symposium on Cluster Computing and the Grid, p.66-73, April 19-22, 2004