Energy-efficient multiprocessor scheduling for flow time and makespan

DOI10.1016/J.TCS.2014.07.007MaRDI QIDQ401300zbMATH OpenOpenAlexFDO

Authors Hongyang Sun, Yuxiong He, Wen-Jing Hsu, Rui Fan

Publication date 26 August 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.4110

zbMATH Keywords

competitive analysismakespanonline schedulingdynamic speed scalingmultiprocessorstotal flow timeenergy-performance tradeoff

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: We consider energy-efficient scheduling on multiprocessors, where the speed of each processor can be individually scaled, and a processor consumes power $s^{alpha}$ when running at speed $s$, for $alpha>1$. A scheduling algorithm needs to decide at any time both processor allocations and processor speeds for a set of parallel jobs with time-varying parallelism. The objective is to minimize the sum of the total energy consumption and certain performance metric, which in this paper includes total flow time and makespan. For both objectives, we present instantaneous parallelism clairvoyant (IP-clairvoyant) algorithms that are aware of the instantaneous parallelism of the jobs at any time but not their future characteristics, such as remaining parallelism and work. For total flow time plus energy, we present an $O(1)$-competitive algorithm, which significantly improves upon the best known non-clairvoyant algorithm and is the first constant competitive result on multiprocessor speed scaling for parallel jobs. In the case of makespan plus energy, which is considered for the first time in the literature, we present an $O(l{n}^{1-1/alpha}P)$-competitive algorithm, where $P$ is the total number of processors. We show that this algorithm is asymptotically optimal by providing a matching lower bound. In addition, we also study non-clairvoyant scheduling for total flow time plus energy, and present an algorithm that achieves $O(lnP)$-competitive for jobs with arbitrary release time and $O(l{n}^{1/alpha}P)$-competitive for jobs with identical release time. Finally, we prove an $Omega(l{n}^{1/alpha}P)$ lower bound on the competitive ratio of any non-clairvoyant algorithm, matching the upper bound of our algorithm for jobs with identical release time.

Recommendations

• Improved multi-processor scheduling for flow time and energy
• Optimising makespan and energy consumption in task scheduling for parallel systems
• Power-aware scheduling for makespan and flow
• Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion
• Energy efficient scheduling of parallelizable jobs
• Energy Efficient Scheduling of Parallelizable Jobs
• Scheduling Precedence Constrained Tasks with Reduced Processor Energy on Multiprocessor Computers

Cites work

• scientific article; zbMATH DE number 437570 (Why is no real title available?)
• scientific article; zbMATH DE number 193053 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1306870 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• An Analysis of Preemptive Multiprocessor Job Scheduling
• Energy Efficient Scheduling of Parallelizable Jobs
• Energy-Efficient Due Date Scheduling
• Energy-efficient algorithms for flow time minimization
• How to schedule when you have to buy your energy
• Non-clairvoyant Batch Sets Scheduling: Fairness Is Fair Enough
• Non-clairvoyant Speed Scaling for Weighted Flow Time
• Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics
• Nonclairvoyant speed scaling for flow and energy
• Online scheduling of parallel programs on heterogeneous systems with applications to Cilk
• Online speed scaling based on active job count to minimize flow plus energy
• Preemptive Scheduling of Parallel Jobs on Multiprocessors
• Scalably scheduling processes with arbitrary speedup curves
• Scheduling in the dark
• Scheduling multithreaded computations by work stealing
• Semi-clairvoyant scheduling
• Simultaneous job scheduling and resource allocation on parallel machines
• Speed is as powerful as clairvoyance
• Speed scaling for energy and performance with instantaneous parallelism
• Speed scaling for weighted flow time
• Speed scaling of processes with arbitrary speedup curves on a multiprocessor
• Speed scaling with an arbitrary power function
• Using parallel program characteristics in dynamic processor allocation policies

Cited in

(12)

• Power-aware scheduling for makespan and flow
• Speedup-aware co-schedules for efficient workload management
• Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines
• Minimizing total completion time in multiprocessor job systems with energy constraint
• Discrete-continuous scheduling to minimize the makespan for power processing rates of jobs
• Speed scaling for energy and performance with instantaneous parallelism
• Sleep management on multiple machines for energy and flow time
• Scheduling heterogeneous processors isn't as easy as you think
• Speed scaling of processes with arbitrary speedup curves on a multiprocessor
• Energy-Efficient Algorithms for Flow Time Minimization
• Energy-efficient algorithms for flow time minimization
• Improved multi-processor scheduling for flow time and energy

This page was built for publication: Energy-efficient multiprocessor scheduling for flow time and makespan

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q401300)