Energy-Efficient Multiprocessor Scheduling for Flow Time and Makespan

Details Energy-Efficient Multiprocessor Scheduling for Flow Time and Makespan Energy-Efficient Multiprocessor Scheduling for Flow Time and Makespan

2010-10-20

arxiv.org/abs/1010.4110v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider energy-efficient scheduling on multiprocessors, where the speed of each processor can be individually scaled, and a processor consumes power $s^{\alpha}$ if it runs at speed $s$, where $\alpha>1$. A scheduling algorithm needs to decide both processor allocations and speeds for a set of parallel jobs whose parallelism can vary with time. The objective is to minimize the sum of overall energy consumption and some performance metric, which in this paper includes flow time and makespan. For both objectives, we present semi-clairvoyant algorithms that are aware of the instantaneous parallelism of the jobs but not their future information. We present U-CEQ algorithm for flow time plus energy, and show that it is O(1)-competitive. This is the first O(1)-competitive result for multiprocessor speed scaling on parallel jobs. We also consider, for the first time in the literature, makespan plus energy. We present P-FIRST algorithm and show that it is $O(\ln^{1-1/\alpha}P)$-competitive for parallel jobs consisting of fully-parallel and sequential phases, where $P$ is the total number of processors. Moreover, we prove that P-FIRST is asymptotically optimal in this setting by providing a matching lower bound. In addition, we revisit non-clairvoyant scheduling for flow time plus energy, and show that N-EQUI algorithm is $O(\ln P)$-competitive. We then prove a lower bound of $\Omega(\ln^{1/\alpha}P)$ for any non-clairvoyant algorithm.

Affiliated with

Also associated with

No associations

Rating

Energy-Efficient Multiprocessor Scheduling for Flow Time and Makespan does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Energy-Efficient Multiprocessor Scheduling for Flow Time and Makespan, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Energy-Efficient Multiprocessor Scheduling for Flow Time and Makespan will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-717036