[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2612669.2612682acmconferencesArticle/Chapter ViewAbstractPublication PagesspaaConference Proceedingsconference-collections
research-article

Competitively scheduling tasks with intermediate parallelizability

Published: 21 June 2014 Publication History

Abstract

We introduce a scheduling algorithm Intermediate-SRPT, and show that it is O(log P)-competitive with respect to average waiting time when scheduling jobs whose parallelizability is intermediate between being fully parallelizable and sequential. Here the parameter P denotes the ratio between the maximum job size to the minimum. We also show a general matching lower bound on the competitive ratio. Our analysis builds on an interesting combination of potential function and local competitiveness arguments.

References

[1]
http://www.tilera.com/.
[2]
http://projects.csail.mit.edu/angstrom/.
[3]
Ho-Leung Chan, Jeff Edmonds, and Kirk Pruhs. Speed scaling of processes with arbitrary speedup curves on a multiprocessor. Theory Comput. Syst., 49(4):817--833, 2011.
[4]
Jeff Edmonds. Scheduling in the dark. Theor. Comput. Sci., 235(1):109--141, 2000.
[5]
Jeff Edmonds, Jarek Gryz, Dongming Liang, and Renée J. Miller. Mining for empty spaces in large data sets. Theor. Comput. Sci., 296(3):435--452, 2003.
[6]
Jeff Edmonds and Kirk Pruhs. Scalably scheduling processes with arbitrary speedup curves. ACM Transactions on Algorithms, 8(3):28, 2012.
[7]
Kyle Fox, Sungjin Im, and Benjamin Moseley. Energy efficient scheduling of parallelizable jobs. In SODA, pages 948--957, 2013.
[8]
Sungjin Im, Benjamin Moseley, and Kirk Pruhs. A tutorial on amortized local competitiveness in online scheduling. SIGACT News, 42(2):83--97, 2011.
[9]
Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. J. ACM, 47(4):617--643, 2000.
[10]
Stefano Leonardi and Danny Raz. Approximating total flow time on parallel machines. Journal of Computer and Systems Sciences, 73(6):875--891, 2007.
[11]
John Markoff. Intel's big shift after hitting technical wall. New York Times, May 2004.
[12]
Rick Merritt. CPU designers debate multi-core future. EE Times, February 2008.
[13]
Cynthia A. Phillips, Clifford Stein, Eric Torng, and Joel Wein. Optimal time-critical scheduling via resource augmentation. Algorithmica, 32(2):163--200, 2002.
[14]
Kirk Pruhs, Julien Robert, and Nicolas Schabanel. Minimizing maximum flowtime of jobs with arbitrary parallelizability. In WAOA, pages 237--248, 2010.
[15]
Kirk Pruhs, Jiri Sgall, and Eric Torng. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter Online Scheduling. 2004.
[16]
Julien Robert and Nicolas Schabanel. Non-clairvoyant batch sets scheduling: Fairness is fair enough. In ESA, pages 741--753, 2007.
[17]
Julien Robert and Nicolas Schabanel. Non-clairvoyant scheduling with precedence constraints. In SODA, pages 491--500, 2008.

Cited By

View all
  • (2021)Optimal Job Scheduling With Resource Packing for Heterogeneous ServersIEEE/ACM Transactions on Networking10.1109/TNET.2021.306820129:4(1553-1566)Online publication date: Aug-2021
  • (2019)Online Job Scheduling with Redundancy and Opportunistic CheckpointingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.287113530:4(897-909)Online publication date: 18-Jul-2019
  • (2019)Online Job Scheduling with Resource Packing on a Cluster of Heterogeneous ServersIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737465(1441-1449)Online publication date: Apr-2019
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures
June 2014
356 pages
ISBN:9781450328210
DOI:10.1145/2612669
  • General Chair:
  • Guy Blelloch,
  • Program Chair:
  • Peter Sanders
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: 21 June 2014

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. parallelization
  2. scheduling
  3. speedup curves

Qualifiers

  • Research-article

Funding Sources

Conference

SPAA '14

Acceptance Rates

SPAA '14 Paper Acceptance Rate 30 of 122 submissions, 25%;
Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2021)Optimal Job Scheduling With Resource Packing for Heterogeneous ServersIEEE/ACM Transactions on Networking10.1109/TNET.2021.306820129:4(1553-1566)Online publication date: Aug-2021
  • (2019)Online Job Scheduling with Redundancy and Opportunistic CheckpointingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.287113530:4(897-909)Online publication date: 18-Jul-2019
  • (2019)Online Job Scheduling with Resource Packing on a Cluster of Heterogeneous ServersIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737465(1441-1449)Online publication date: Apr-2019
  • (2019)Revisiting SRPT for Job Scheduling in Computing ClustersQueueing Theory and Network Applications10.1007/978-3-030-27181-7_17(276-291)Online publication date: 23-Jul-2019
  • (2018)Scheduling Parallel Jobs Online with Convex and Concave ParallelizabilityTheory of Computing Systems10.1007/s00224-016-9722-062:2(304-318)Online publication date: 1-Feb-2018
  • (2017)Mitigating Service Variability in MapReduce Clusters via Task Cloning: A Competitive AnalysisIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.268976728:10(2866-2880)Online publication date: 1-Oct-2017
  • (2017)When data acquisition meets data analytics: A distributed active learning framework for optimal budgeted mobile crowdsensingIEEE INFOCOM 2017 - IEEE Conference on Computer Communications10.1109/INFOCOM.2017.8057034(1-9)Online publication date: May-2017
  • (2017)Scalable software-defined networking through hybrid switchingIEEE INFOCOM 2017 - IEEE Conference on Computer Communications10.1109/INFOCOM.2017.8057001(1-9)Online publication date: May-2017
  • (2017)Addressing job processing variability through redundant execution and opportunistic checkpointing: A competitive analysisIEEE INFOCOM 2017 - IEEE Conference on Computer Communications10.1109/INFOCOM.2017.8056972(1-9)Online publication date: May-2017
  • (2016)Scheduling Parallelizable Jobs Online to Minimize the Maximum Flow TimeProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935782(195-205)Online publication date: 11-Jul-2016
  • Show More Cited By

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