Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Objective Function
Online Algorithm
Power Function
Subscribe
Academic
Publications
Scalably Scheduling PowerHeterogeneous Processors
Scalably Scheduling PowerHeterogeneous Processors,10.1007/9783642141652_27,Anupam Gupta,Ravishankar Krishnaswamy,Kirk Pruhs
Edit
Scalably Scheduling PowerHeterogeneous Processors
(
Citations: 5
)
BibTex

RIS

RefWorks
Download
Anupam Gupta
,
Ravishankar Krishnaswamy
,
Kirk Pruhs
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.
Conference:
International Colloquium on Automata, Languages and Programming  ICALP
, pp. 312323, 2010
DOI:
10.1007/9783642141652_27
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
Citation Context
(2)
...[
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 worstcase 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 nonmigratory 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
]...
SzeHang Chan
,
et al.
Sleep Management on Multiple Machines for Energy and Flow Time
References
(25)
EnergyEfficient Algorithms for Flow Time Minimization
(
Citations: 53
)
Susanne Albers
,
Hiroshi Fujiwara
Conference:
Symposium on Theoretical Aspects of Computer Science  STACS
, pp. 621633, 2006
Optimal speed scaling under arbitrary power functions
(
Citations: 8
)
Lachlan L. H. Andrew
,
Adam Wierman
,
Ao Tang
Journal:
Sigmetrics Performance Evaluation Review  SIGMETRICS
, vol. 37, no. 2, pp. 3941, 2009
Weighted flow time does not admit O(1)competitive algorithms
(
Citations: 3
)
Nikhil Bansal
,
Holeung Chan
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 12381244, 2009
Scheduling for Speed Bounded Processors
(
Citations: 17
)
Nikhil Bansal
,
Holeung Chan
,
TakWah Lam
,
Lapkei Lee
Conference:
International Colloquium on Automata, Languages and Programming  ICALP
, pp. 409420, 2008
Speed scaling with an arbitrary power function
(
Citations: 26
)
Nikhil Bansal
,
Holeung Chan
,
Kirk Pruhs
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 693701, 2009
Sort by:
Citations
(5)
EnergyEfficient Due Date Scheduling
HoLeung Chan
,
TakWah Lam
,
Rongbin Li
Published in 2011.
Managing Power Heterogeneity
Kirk Pruhs
Published in 2011.
Nonclairvoyantly scheduling powerheterogeneous processors
(
Citations: 1
)
Anupam Gupta
,
Ravishankar Krishnaswamy
,
Kirk Pruhs
Conference:
International Green Computing Conference  IGCC
, 2010
Scheduling to Minimize Energy and Flow Time in Broadcast Scheduling
Benjamin Moseley
Journal:
Computing Research Repository  CORR
, vol. abs/1007.3, 2010
Sleep Management on Multiple Machines for Energy and Flow Time
SzeHang Chan
,
TakWah Lam
,
LapKei Lee
,
ChiMan Liu
,
HingFung Ting