Academic
Publications
Scalably Scheduling Power-Heterogeneous Processors

Scalably Scheduling Power-Heterogeneous Processors,10.1007/978-3-642-14165-2_27,Anupam Gupta,Ravishankar Krishnaswamy,Kirk Pruhs

Scalably Scheduling Power-Heterogeneous Processors   (Citations: 5)
BibTex | RIS | RefWorks Download
We show that a natural online algorithm for scheduling jobs on a heterogeneous multiprocessor, with arbitrary power functions, is scalable for the objective function of weighted flow plus energy.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...[3] considered the objective of weighted response time plus energy, and assumed that the i th processor had an arbitrary power function Pi(s) specifying the power consumption when the processor is run at a speed s. Perhaps the most interesting special case of this problem is when each processor i can only run at a speed si with power Pi. This special case seems to capture much of the complexity of the general case...
    • ...[3] considered the natural greedy algorithm for assigning jobs to processors: a newly arriving job is assigned to a processor such that the increase in the cost to the online algorithm is minimized, given whatever scheduling algorithm is being used to sequence the jobs on the individual processors...
    • ...[3] then used the algorithm from [1] to schedule the jobs on the individual processors...
    • ...[3] showed using an amortized local competitiveness argument that this online algorithms is provably scalable...
    • ...So intuitively [3] showed that the operating system can manage power heterogeneous processors well, with a load almost equal to the capacity of the server, if it knows the sizes of the jobs...
    • ...In some sense [3] shows that the natural greedy algorithm has the best possible worst-case performance among online algorithms for scheduling heterogeneous processors for the objective of weighted response time plus energy...
    • ...Thus the natural question left open in [3] is to determine whether there is a scalable nonclairvoyant scheduling algorithm for scheduling power heterogeneous multiprocessors (or if not, to find the algorithm with the best possible worst case guarantee)...

    Kirk Pruhs. Managing Power Heterogeneity

    • ...Existing online results on speed scaling for multiple machines do not consider sleep management [12,9,8]...
    • ...The best result in the non-migratory model is by Gupta et al. [8]...
    • ...Our new algorithm has comparable performance with the best speed scaling results on multiple machines that assume all machines are always on [12,9,8]...

    Sze-Hang Chanet al. Sleep Management on Multiple Machines for Energy and Flow Time

Sort by: