skip to main content
10.1145/1006209.1006256acmconferencesArticle/Chapter ViewAbstractPublication PagesicsConference Proceedingsconference-collections
Article

Cluster scheduling for explicitly-speculative tasks

Published: 26 June 2004 Publication History

Abstract

Large-scale computing often consists of many speculative tasks to test hypotheses, search for insights, and review potentially finished products. E.g., speculative tasks are issued by bioinformaticists comparing DNA sequences and computer graphics artists adjusting scene properties. We promote a way of working that exploits the inherent speculation in application-level search made more common by the cost-effectiveness of grid and cluster computing. Researchers and end-users disclose sets of speculative tasks that search an application space, request specific results as needed, and cancel unfinished tasks if early results suggest no need to continue. Doing so matches natural usage patterns, making users more effective, and also enables a new class of schedulers.In simulation, we show how batchactive schedulers reduce user-observed response times relative to conventional models in which tasks are requested one at a time (interactively) or in batches without specifying which tasks are speculative. Over a range of situations, user-observed response time is about 50% better on average and at least two times better for 20% of our simulations. Moreover, we show how user costs can be reduced under an incentive cost model of charging only for tasks whose results are requested.

References

[1]
A. Acharya, G. Edjlali, and J. Saltz. The utility of exploiting idle workstations for parallel computation. Sigmetrics, 1997.
[2]
S. Altschul, W. Gish, W. Miller, E. Myers, and D. Lipman. Basic local alignment search tool. Journal of Molecular Biology, 215:403--10, 1990.
[3]
T. E. Anderson, D. E. Culler, D. A. Patterson, and the NOW team. A case for NOW (Networks of Workstations). IEEE Micro, 15(1):54--64, Feb. 1995.
[4]
R. H. Arpaci, A. C. Dusseau, A. M. Vahdat, L. T. Liu, T. E. Anderson, and D. A. Patterson. The interaction of parallel and sequential workloads on a Network of Workstations. Sigmetrics, 1995.
[5]
F. Berman, G. Fox, and T. Hey. Grid Computing: Making the Global Infrastructure a Reality. John Wiley & Sons, 2003.
[6]
R. Bubenik and W. Zwaenepoel. Performance of optimistic make. Sigmetrics, 1989.
[7]
R. Bubenik and W. Zwaenepoel. Semantics of optimistic computation. ICDCS, 1990.
[8]
F. Chang and G. A. Gibson. Automatic I/O hint generation through speculative execution. OSDI, 1999.
[9]
N. Chrisochoides, A. Fedorov, B. B. Lowekamp, M. Zangrilli, and C. Lee. A case study of optimistic computing on the grid: Parallel mesh generation. NGS Workshop at IPDPS, 2003.
[10]
R. W. Conway, W. L. Maxwell, and L. W. Miller. Theory of Scheduling. Addison-Wesley, 1967.
[11]
C. Cowan and H. Lutfiyya. Formal semantics for expressing optimism: The meaning of HOPE. PODC, 1995.
[12]
D. DeGroot. Throttling and speculating on parallel architectures. Parbase, 1990. Abstract of keynote speech.
[13]
D. Epps. Personal communication, 2004. R&D director at Tippett Studio since 1992.
[14]
M. Giddings and D. Knudson. Xgrid-users email list, Feb. 2004. subjects 'differing resources' and 'What's on your Xgrid' at http://lists.apple.com/mailman/listinfo/xgrid-users.
[15]
M. Harchol-Balter, K. Sigman, and A. Wierman. Asymptotic convergence of scheduling policies with respect to slowdown. Performance, 2002.
[16]
J. Hillner. The wall of fame. Wired Magazine, 11(12), 2003.
[17]
D. Holliman. Personal communication, 2003. Former system administrator for the Berkeley Phylogenomics Group.
[18]
N. H. Kapadia, J. A. B. Fortes, and C. E. Brodley. Predictive application-performance modeling in a computational grid environment. HPDC, 1999.
[19]
C. A. Lee. Optimistic grid computing, 2002. Talk at the Performance Analysis and Distributed Computing Workshop.
[20]
The Lemieux Supercomputer. Pittsburgh Supercomputer Center, http://www.psc.edu/machines/tcs/lemieux.html, 2003.
[21]
T. Lokovic. Personal communication, 2004. Graphics software engineer at Pixar Animation Studios since 1998.
[22]
M. W. Mutka and M. Livny. Profiling workstations' available capacity for remote execution. Performance, 1987.
[23]
V. N. Padmanabhan and J. C. Mogul. Using predictive prefetching to improve World Wide Web latency. Computer Communication Review, 26(3), 1996.
[24]
R. H. Patterson, G. A. Gibson, E. Ginting, D. Stodolsky, and J. Zelenka. Informed prefetching and caching. SOSP, 1995.
[25]
G. F. Pfister. In Search of Clusters. Prentice Hall, 1995.
[26]
N. Polyzotis and Y. Ioannidis. Speculative query processing. Conf. on Innovative Data Systems Research, 2003.
[27]
N. Spring and R. Wolski. Application level scheduling of gene sequence comparison on metacomputers. Supercomputing, 1998.
[28]
D. C. Steere. Exploiting the non-determinism and asynchrony of set iterators to reduce aggregate file I/O latency. SOSP, 1997.

Cited By

View all
  • (2009)Two Auction‐Based Resource Allocation Environments: Design and ExperienceMarket‐Oriented Grid and Utility Computing10.1002/9780470455432.ch23(513-539)Online publication date: 17-Nov-2009
  • (2006)Service contracts and aggregate utility functions2006 15th IEEE International Conference on High Performance Distributed Computing10.1109/HPDC.2006.1652143(119-131)Online publication date: 2006
  • (2005)Scheduling speculative tasks in a compute farmProceedings of the 2005 ACM/IEEE conference on Supercomputing10.1109/SC.2005.62Online publication date: 12-Nov-2005
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ICS '04: Proceedings of the 18th annual international conference on Supercomputing
June 2004
360 pages
ISBN:1581138393
DOI:10.1145/1006209
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2004

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. cluster
  2. grid scheduling
  3. optimistic
  4. speculative

Qualifiers

  • Article

Conference

ICS04
Sponsor:

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2009)Two Auction‐Based Resource Allocation Environments: Design and ExperienceMarket‐Oriented Grid and Utility Computing10.1002/9780470455432.ch23(513-539)Online publication date: 17-Nov-2009
  • (2006)Service contracts and aggregate utility functions2006 15th IEEE International Conference on High Performance Distributed Computing10.1109/HPDC.2006.1652143(119-131)Online publication date: 2006
  • (2005)Scheduling speculative tasks in a compute farmProceedings of the 2005 ACM/IEEE conference on Supercomputing10.1109/SC.2005.62Online publication date: 12-Nov-2005
  • (2005)Profitable services in an uncertain worldProceedings of the 2005 ACM/IEEE conference on Supercomputing10.1109/SC.2005.58Online publication date: 12-Nov-2005

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media