research-article

Competitively Scheduling Tasks with Intermediate Parallelizability

Authors:

Benjamin Moseley,

Eric TorngAuthors Info & Claims

ACM Transactions on Parallel Computing (TOPC), Volume 3, Issue 1

Article No.: 4, Pages 1 - 19

https://doi.org/10.1145/2938378

Published: 18 July 2016 Publication History

Abstract

We introduce a scheduling algorithm Intermediate-SRPT, and show that it is O(logP)-competitive with respect to average flow 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. 2011. Speed scaling of processes with arbitrary speedup curves on a multiprocessor. Theory Comput. Syst. 49, 4 (2011), 817--833.

Digital Library

[4]

Jeff Edmonds. 2000. Scheduling in the dark. Theor. Comput. Sci. 235, 1 (2000), 109--141.

Digital Library

[5]

Jeff Edmonds, Jarek Gryz, Dongming Liang, and Renée J. Miller. 2003. Mining for empty spaces in large data sets. Theor. Comput. Sci. 296, 3 (2003), 435--452.

Digital Library

[6]

Jeff Edmonds and Kirk Pruhs. 2012. Scalably scheduling processes with arbitrary speedup curves. ACM Transactions on Algorithms 8, 3 (2012), 28.

Digital Library

[7]

Kyle Fox, Sungjin Im, and Benjamin Moseley. 2013. Energy efficient scheduling of parallelizable jobs. In ACM-SIAM Symposium on Discrete Algorithms, SODA. 948--957.

Digital Library

[8]

Sungjin Im, Benjamin Moseley, and Kirk Pruhs. 2011. A tutorial on amortized local competitiveness in online scheduling. SIGACT News 42, 2 (2011), 83--97.

Digital Library

[9]

Bala Kalyanasundaram and Kirk Pruhs. 2000. Speed is as powerful as clairvoyance. J. ACM 47, 4 (2000), 617--643.

Digital Library

[10]

Stefano Leonardi and Danny Raz. 2007. Approximating total flow time on parallel machines. Journal of Computer and Systems Sciences 73, 6 (2007), 875--891.

Digital Library

[11]

John Markoff. 2004. Intel’s big shift after hitting technical wall. New York Times (17 May 2004).

[12]

Rick Merritt. 2008. CPU designers debate multi-core future. EE Times (6 February 2008).

[13]

Cynthia A. Phillips, Clifford Stein, Eric Torng, and Joel Wein. 2002. Optimal time-critical scheduling via resource augmentation. Algorithmica 32, 2 (2002), 163--200.

Digital Library

[14]

Kirk Pruhs, Julien Robert, and Nicolas Schabanel. 2010. Minimizing maximum flowtime of jobs with arbitrary parallelizability. In Workshop on Approximation and Online Algorithms, WAOA. 237--248.

Digital Library

[15]

Kirk Pruhs, Jiri Sgall, and Eric Torng. 2004. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapter Online Scheduling.

[16]

Julien Robert and Nicolas Schabanel. 2007. Non-clairvoyant batch sets scheduling: Fairness is fair enough. In European Symposium on Algorithms, ESA. 741--753.

Digital Library

[17]

Julien Robert and Nicolas Schabanel. 2008. Non-clairvoyant scheduling with precedence constraints. In ACM-SIAM Symposium on Discrete Algorithms, SODA. 491--500.

Digital Library

Cited By

Vaze RNair J(2022)Speed Scaling with Multiple Servers under a Sum-Power ConstraintACM SIGMETRICS Performance Evaluation Review10.1145/3529113.352912849:3(45-50)Online publication date: 25-Mar-2022
https://dl.acm.org/doi/10.1145/3529113.3529128
Moselely BZhang RZhao S(2022)Online scheduling of parallelizable jobs in the directed acyclic graphs and speed-up curves modelsTheoretical Computer Science10.1016/j.tcs.2022.10.005938(24-38)Online publication date: Nov-2022
https://doi.org/10.1016/j.tcs.2022.10.005
Berg BWhitehouse JMoseley BWang WHarchol-Balter M(2021)The case for phase-aware scheduling of parallelizable jobsPerformance Evaluation10.1016/j.peva.2021.102246(102246)Online publication date: Oct-2021
https://doi.org/10.1016/j.peva.2021.102246
Show More Cited By

Index Terms

Competitively Scheduling Tasks with Intermediate Parallelizability
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Competitively scheduling tasks with intermediate parallelizability
SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures

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 ...
Mixed Pfair/ERfair scheduling of asynchronous periodic tasks
Abstract
Pfair scheduling was proposed by Baruah, Cohen, Plaxton, and Varvel as a non-work-conserving way of optimally and efficiently scheduling periodic tasks on a multiprocessor. In this paper, we introduce a work-conserving variant of Pfair scheduling ...
Scheduling of deteriorating jobs with release dates to minimize the maximum lateness

In this paper, we consider the problem of scheduling n deteriorating jobs with release dates on a single (batching) machine. Each job's processing time is a simple linear function of its starting time. The objective is to minimize the maximum lateness. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Parallel Computing

ACM Transactions on Parallel Computing Volume 3, Issue 1

Special Issue for SPAA 2014

June 2016

192 pages

ISSN:2329-4949

EISSN:2329-4957

DOI:10.1145/2965648

Editor:
Phillip B. Gibbons
Carnegie Mellon University, Pittsburgh, USA

Issue’s Table of Contents

Copyright © 2016 ACM.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 July 2016

Accepted: 01 May 2015

Revised: 01 March 2015

Received: 01 October 2014

Published in TOPC Volume 3, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

NSF
IBM Faculty Award

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
162
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Vaze RNair J(2022)Speed Scaling with Multiple Servers under a Sum-Power ConstraintACM SIGMETRICS Performance Evaluation Review10.1145/3529113.352912849:3(45-50)Online publication date: 25-Mar-2022
https://dl.acm.org/doi/10.1145/3529113.3529128
Moselely BZhang RZhao S(2022)Online scheduling of parallelizable jobs in the directed acyclic graphs and speed-up curves modelsTheoretical Computer Science10.1016/j.tcs.2022.10.005938(24-38)Online publication date: Nov-2022
https://doi.org/10.1016/j.tcs.2022.10.005
Berg BWhitehouse JMoseley BWang WHarchol-Balter M(2021)The case for phase-aware scheduling of parallelizable jobsPerformance Evaluation10.1016/j.peva.2021.102246(102246)Online publication date: Oct-2021
https://doi.org/10.1016/j.peva.2021.102246
Berg BHarchol-Balter MMoseley BWang WWhitehouse JScheideler CSpear M(2020)Optimal Resource Allocation for Elastic and Inelastic JobsProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400265(75-87)Online publication date: 9-Jul-2020
https://doi.org/10.1145/3350755.3400265
Berg BVesilo RHarchol-Balter M(2020)heSRPT: Parallel scheduling to minimize mean slowdownPerformance Evaluation10.1016/j.peva.2020.102147(102147)Online publication date: Oct-2020
https://doi.org/10.1016/j.peva.2020.102147
Berg BVesilo RHarchol-Balter M(2019)heSRPTACM SIGMETRICS Performance Evaluation Review10.1145/3374888.337489647:2(18-20)Online publication date: 4-Dec-2019
https://doi.org/10.1145/3374888.3374896

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents