2008 • 60 Pages • 502 KB • English

Posted April 14, 2020 • Uploaded
by letitia81

PREVIEW PDF

Page 1

Energy Efﬁcient Deadline Scheduling in Two Processor Systems 1 1 2 Tak-Wah Lam Lap-Kei Lee Isaac K. K. To Prudence W. H. 2 Wong 1Department of Computer Science University of Hong Kong 2Department of Computer Science University of Liverpool CTAG seminar 2008 March Based on ISAAC 2007 presentation Lam, Lee, To, Wong (HKU, UoL) 2-processor energy efﬁcient scheduling CTAGS 2008 1 / 27

Page 2

Problem and contribution Outline 1 Problem and contribution Speed scaling Online real-time scheduling Known bounds and our contribution 2 Main ideas in algorithm and proof Review of previous algorithms New algorithm: Slow-SR 3 Open Problems and Summary Lam, Lee, To, Wong (HKU, UoL) 2-processor energy efﬁcient scheduling CTAGS 2008 2 / 27

Page 3

Problem and contribution Speed scaling Saving energy via Speed scaling Experience using laptops: Running slower saves energy. Processors can dynamically slow down (usually in 0.5ms). Why slow is good? Transistors are capacitor-like. . . When state not changing, no current ⇒ no energy used. To switch state, a current ﬂows to (dis)charge the base of transistors, which expend energy. ✄ Transistors also leaks, making them somewhat resistor-like. Let’s ignore such details. Running slower reduces frequency f of state changes. Nearly useless: you just spend energy later. ✄ Cooling requirement is reduced, though. Lam, Lee, To, Wong (HKU, UoL) 2-processor energy efﬁcient scheduling CTAGS 2008 3 / 27

Page 4

Problem and contribution Speed scaling Saving energy via Speed scaling Experience using laptops: Running slower saves energy. Processors can dynamically slow down (usually in 0.5ms). Why slow is good? Transistors are capacitor-like. . . When state not changing, no current ⇒ no energy used. To switch state, a current ﬂows to (dis)charge the base of transistors, which expend energy. ✄ Transistors also leaks, making them somewhat resistor-like. Let’s ignore such details. Running slower reduces frequency f of state changes. Nearly useless: you just spend energy later. ✄ Cooling requirement is reduced, though. Lam, Lee, To, Wong (HKU, UoL) 2-processor energy efﬁcient scheduling CTAGS 2008 3 / 27

Page 5

Problem and contribution Speed scaling Saving energy via Speed scaling Experience using laptops: Running slower saves energy. Processors can dynamically slow down (usually in 0.5ms). Why slow is good? Transistors are capacitor-like. . . When state not changing, no current ⇒ no energy used. To switch state, a current ﬂows to (dis)charge the base of transistors, which expend energy. ✄ Transistors also leaks, making them somewhat resistor-like. Let’s ignore such details. Running slower reduces frequency f of state changes. Nearly useless: you just spend energy later. ✄ Cooling requirement is reduced, though. Lam, Lee, To, Wong (HKU, UoL) 2-processor energy efﬁcient scheduling CTAGS 2008 3 / 27

Page 6

Problem and contribution Speed scaling But it does help! When frequency is lowered: voltage V required for reliable operation is reduced. 2 Power consumption (should) varies as V f ! E.g., Pentium M spec (1.6GHz) f V P P/f 1.6 GHz 1.484V 24.5W 15.3nW 0.6 GHz 0.956V 6W 10nW Looks like P/f varies as V instead of V 2. Ideally: If we assume f and V required are proportional, power 3 2 varies as f , energy varies as f . ✄ Not quite the case: f varies as (V − Vt )2/V , typical Vt of 0.5V ruins the day. Still, a reasonable approximation, especially if Vt can be lowered. Our model: Processor speed adjustable. When running at α speed s, spend power s (α is around 2 or 3). Lam, Lee, To, Wong (HKU, UoL) 2-processor energy efﬁcient scheduling CTAGS 2008 4 / 27

Page 7

Problem and contribution Speed scaling But it does help! When frequency is lowered: voltage V required for reliable operation is reduced. 2 Power consumption (should) varies as V f ! E.g., Pentium M spec (1.6GHz) f V P P/f 1.6 GHz 1.484V 24.5W 15.3nW 0.6 GHz 0.956V 6W 10nW Looks like P/f varies as V instead of V 2. Ideally: If we assume f and V required are proportional, power 3 2 varies as f , energy varies as f . ✄ Not quite the case: f varies as (V − Vt )2/V , typical Vt of 0.5V ruins the day. Still, a reasonable approximation, especially if Vt can be lowered. Our model: Processor speed adjustable. When running at α speed s, spend power s (α is around 2 or 3). Lam, Lee, To, Wong (HKU, UoL) 2-processor energy efﬁcient scheduling CTAGS 2008 4 / 27

Page 8

Problem and contribution Speed scaling But it does help! When frequency is lowered: voltage V required for reliable operation is reduced. 2 Power consumption (should) varies as V f ! E.g., Pentium M spec (1.6GHz) f V P P/f 1.6 GHz 1.484V 24.5W 15.3nW 0.6 GHz 0.956V 6W 10nW Looks like P/f varies as V instead of V 2. Ideally: If we assume f and V required are proportional, power 3 2 varies as f , energy varies as f . ✄ Not quite the case: f varies as (V − Vt )2/V , typical Vt of 0.5V ruins the day. Still, a reasonable approximation, especially if Vt can be lowered. Our model: Processor speed adjustable. When running at α speed s, spend power s (α is around 2 or 3). Lam, Lee, To, Wong (HKU, UoL) 2-processor energy efﬁcient scheduling CTAGS 2008 4 / 27

Page 9

Problem and contribution Online real-time scheduling Real-time scheduling Who decides to go slow? One possibility: schedulers. Our focus: ﬁrm deadline scheduling Input is a sequence of jobs. Each job has some work to complete by processor(s). Each job has a deadline. Online real-time scheduling: Learn everything about a job when it is released. The algorithm decides the job and speed to run now. We want to reduce energy consumption. . . But we don’t want to give up too much performance—we measure that by throughput of jobs completed by deadline. Lam, Lee, To, Wong (HKU, UoL) 2-processor energy efﬁcient scheduling CTAGS 2008 5 / 27

Page 10

Problem and contribution Online real-time scheduling Real-time scheduling Who decides to go slow? One possibility: schedulers. Our focus: ﬁrm deadline scheduling Input is a sequence of jobs. Each job has some work to complete by processor(s). Each job has a deadline. Online real-time scheduling: Learn everything about a job when it is released. The algorithm decides the job and speed to run now. We want to reduce energy consumption. . . But we don’t want to give up too much performance—we measure that by throughput of jobs completed by deadline. Lam, Lee, To, Wong (HKU, UoL) 2-processor energy efﬁcient scheduling CTAGS 2008 5 / 27

Interactive Video-On-Demand Systems: Resource Management and Scheduling Strategies

1998 • 139 Pages • 9.07 MB

energy-efficient transformers

2017 • 103 Pages • 9.82 MB

energy-efficient lighting

2017 • 95 Pages • 7.17 MB

Planning and Financing Energy Efficient Infrastructure in Appalachia

2012 • 123 Pages • 1.9 MB

Energy Efficient Industrial Lighting

2007 • 127 Pages • 8.72 MB

Energy Efficient Lighting Technology Report

2012 • 116 Pages • 3.6 MB

India: Energy-Efficient Street Lighting

2015 • 177 Pages • 4.57 MB

India: Energy-Efficient Street Lighting

2015 • 176 Pages • 2.89 MB

Energy Efficient Homes Package (ceiling insulation)

2010 • 174 Pages • 6.56 MB

energy efficiency. efficient lighting ciudades inteligentes

2016 • 84 Pages • 19.07 MB

Innovative Energy Efficient LED lighting Solutions

2015 • 95 Pages • 11.39 MB

manual for quality, energy efficient lighting

2006 • 160 Pages • 4.24 MB

Efficient Solutions for Traffic Systems

2016 • 92 Pages • 13.82 MB

Energy consumption in embedded systems

2016 • 45 Pages • 2.46 MB

driving transformation to energy efficient buildings

2011 • 97 Pages • 2.32 MB