Transcript Slide presentation

Power Issues
Kiran Muthabatulla
Internet Technology Seminar
The 4 Papers are divided into 3 Main Sections
• Real time Dynamic Voltage Scaling for Low-Power
Embedded Operating systems
• SPAN:An Energy efficient Coordination algorithm
for Topology Maintenance in Ad hoc Wireless Networks
Minimum Energy Routing Schemes for a Wireless Ad
Hoc Network
3. Dynamic Power Management for Portable Systems
Section 1: Real time Dynamic Voltage Scaling for LowPower Embedded Operating systems
Computation and Communications moving towards Mobile
and Portable systems.
Powerful Microprocessors running Sophisticated, fast,
Intelligent applications have increasing processing
power requirements.
Limitation:
Conflict in design goals as mobile systems they should be
designed to maximize battery life but as intelligent
devices they need more powerful processors which
consume more energy.
Though Advances in Semiconductor to provide greater
computation per unit of Energy and longer total battery
life, the fundamental tradeoff between performance and
battery life remains critically important.
The Design generally boils down to tradeoff between computational
power of the processor and the systems battery life.
Dynamic Voltage Scaling (DVS):
Exploits hardware characteristics of processors to reduce
energy dissipation by lowering the Supply Voltage and
operating frequency of the devices.
DVS considerations:
Peak computing frequency rate is very high than average
rate.
Processors Based on CMOS logic: E = k (V)exp 2
DVS Hardware:
A Programmable DC-DC switching voltage regulator.
A Programmable clock generator.
A High performance Processor with wide operating ranges
DVS Operation:
Simple Feedback mechanism detects the amount of idle
time on the processor over a period of time and blindly
adjusts the frequency and Voltage to handle the
computational load.
Time Constrained Applications:
Example:
Changing the frequency of the Processor may violate some
of the timeliness guarantees.
Hence we need a DVS algorithm that must consider
Deadlines and hence must be tightly coupled with the
actual real time scheduler of the O.S.
Classic Real time Schedulers:
1. Set of Tasks that are executed Periodically.
2. Each task T has an associated Period P and a worst case computation
time C.
3. The task is released once every P time units.
4. Tasks Needs to complete execution by its deadline.
Schedulablity Tests:
A real time Scheduler guarantees that tasks will meet their Deadlines if
1. The Task Set is Schedulable
2. No task exceeds its specified worst case computation bound.
Types of Real time Schedulers:
Rate Monotonic (RM): Static Priority scheduler and assigns task priority
according to period. Selects the task with the shortest period that is
ready to run.
Earliest Deadline First (EDF): Dynamic Priority Scheduler that sorts
tasks by deadlines and gives highest priority to the released task with
the most imminent deadline.
Both assume that task deadline = Period.
Algorithm No 1: Static Voltage Scaling:
Provides Voltage Scaling while maintaining Real time scheduling.
Lowest Possible Frequency that will allow all the deadlines for a given
task set.
Frequency is set statically and will not be changed unless the task set is
changed.
But how do we find the Lowest Possible Frequency..??
Frequency Selection:
1. Scale the Operating frequency by a factor x, where 0 < x <=1
2. This results in the worst case computation needed by a task to be
scaled by 1/x, while Period and deadline remains unaffected.
3. Now Plug the new worst case computation values in the scalability
tests and see if the tests pass for both RM and EDF at this frequency.
4. The Lowest of all the frequencies that pass the tests is selected and
the frequency is changed which results in voltage and energy saving
Advantages and Disadvantages of Static Voltage Scaling
1. The Frequency and Voltage Scaling are static for a task set and are
changed only when the task set are changed.
2. Need not be tightly coupled with the task management functions of
the real time O.S hence simplifying implementation
3. Does not realize the full potential of energy saving.
4. Does not deal with situations when a task uses less than its worst case
requirement of the processor cycle.
Algorithm No 2: Cycle Conserving RT-DVS.
This algorithm reduces operating frequency and voltage when tasks use
less than their worst case time allotment and increase frequency to
meet the worst case needs.
Initially Task T released with the worst case computation time (C).
If the task finished earlier than C in CC , then this CC is used in place of
of C till the next time this task is supposed to be released.
The Utilization is re-calculated with the new small CC which would
yield lower frequency. So the tasks after this T can run at a lower
voltage until this task is re-released again with the original C.
At each scheduling point, the utilization is re-computed.
DVS algorithm for EDF scheduling
DVS algorithm for RM scheduling
Advantages and Disadvantages of Cycle Conservation RT-DVS
EDF Scheduling : If multiple tasks are simultaneously in reduced –
utilization state, the total saving can be significant.
RM Scheduling : Somewhat complex due to the no of counters
The Main Challenging in designing these algorithms is to ensure that
deadline guarantees are not violated when the operating frequencies
are reduced.
Algorithm No 3: Look – Ahead RT DVS :
The Previous algorithms start with the worst case initially and execute at
high frequencies and gradually reduce as some of the tasks are
completed.
This Approach differs as much work as possible, and sets the operating
frequency to meet the minimum work that must be done now to
ensure all future dead lines are met.
This may mean that we will be forced to run at a high frequencies later in
order to complete all the deferred work in time.
But the advantage is if the tasks tend to complete before their worst case
computing time, we may never need to execute at higher frequencies.
Simulator :
Software driven Simulation of the Hardware, capable of voltage and
frequency scaling with real time scheduling.
Inputs : Task Sets, with period and computational times and system
parameters.
Output: Energy consumption of the system.
Conclusion and Future Directions:
Presented Several algorithms for real time dynamic voltage scaling that,
when coupled with under OS task manager mechanisms and realtime scheduler, can achieve significant energy saving , while
simultaneously preserving timeliness guarantees made by real time
scheduling.
Future Directions
1.Expand work beyond the deterministic/absolute real time paradigm.
2. Investigate DVS with probabilistic or statistical deadline guarantees.
3. Integration with other energy conserving mechanisms, including
application energy adaptation and energy adaptive conservation.
Section 2: SPAN : An Energy-Efficient Coordination
algorithm for topology maintenance in Ad hoc Wireless
Networks.
SPAN is a power saving technique for multi hop ad hoc
wireless networks that reduces energy consumption
without significantly diminishing the capacity or
connectivity of the network.
Span builds on the observation that when a region of a
shared channel wireless network has sufficient density
of Nodes, only a small no of them need to be on at
any time to forward traffic for active connections.
Characteristics for Power saving techniques for wireless networks:
1. Allow Many Nodes to turn themselves off.
2. Packet forwarding with minimal more delay than fully active state.
3. Awake Nodes should form as much total capacity as original
network.
4. Should work with any Link Layer that provides for sleeping and
Periodic polling.
5. Power Saving should inter-operate correctly with what ever routing
system the network uses.
SPAN Design:
Coordinators: Coordinators are elected from all nodes. Some stay awake
continuously and perform multi-hop packet routing within the
network, while other nodes remain in power saving modes and
periodically check if they need to wake up and become a coordinator.
SPAN Goals:
1. Ensures that enough coordinators are elected so that every node in a
radio range has at least one coordinators.
2. It rotates the coordinators so that all nodes share the task of providing
global connectivity roughly equally.
3. Minimize the no of Nodes elected as coordinators.
4. Elects Coordinators only on Local information stored in local routing
tables during the election process.
SPAN Node Broadcasts : Hello Messages periodically.
Hello Messages contains:
Nodes Status ( Coordinator or Not)
Its current coordinators
Current Neighbors.
Information Stored in a Node:
Coordinators
Coordinators of Neighbors
List of Neighbors.
Coordinator announcement:
Eligibility Rule: If 2 neighbors of a non-coordinator node cannot reach
each other either directly or via one or more coordinators, the node
should become a coordinator.
This rule does not yield minimum no of coordinators, but maintains
connectedness.
Announcement contention occurs when multiple nodes discover the lack
of a coordinator at the same time and all decide to become a
coordinator. Solved by back off delay.
As the battery power drops the likelihood of becoming a co-coordinator.
Coordinator Withdrawal:
Each coordinator periodically checks if it should withdraw as a
coordinator.
RULE: A node should withdraw if every pair of its neighbors can reach
each other either directly or through another coordinator.
Also., it withdraws if every other pair of neighbors can reach each other
via some neighbors , even if those neighbors are not coordinators.
This Rule gives a the other neighbors a fair chance to become one.
To prevent temporary loss of connectivity, the withdrawing node still
acts as a coordinators for a “grace period” to continue to use the old
one until the new one is elected.
Conclusion:
This Paper Presents Span, a distributed coordination technique for multi
hop ad hoc wireless networks that reduces energy consumption
without significantly diminishing the capacity or connectivity of the
network.
Span adaptively elects co-ordinates from all nodes in the network and
rotates them in time.
Each Node uses a random back off delay to decide whether to become a
coordinator.
Section 3: Dynamic Power Management for Portable Systems
Dynamic PM algorithms increase the battery life time by selectively
placing idle components into lower power states.
Device Power States and System Power States.
Power Manager observers the overall work load of the system and
decides when and how to force power state transition.
The most common policy for hard disks is a timeout policy. But if
timeout is large, there waste of power.
Power Management implemented at MAC and physical layers.
The Standard Requires that a central access point send out a beacon
every 100 ms followed by a traffic indication map. Each card that
desires to communicate should actively listen to the Beacon for
synchronization to the clock of the AP and for the TMI to see if data
is arriving for it. If the card does not need to transmit or receive, the
card can go to a low power state.
Predictive policies for Hard disks: Predictive policies force the Hard disk
to go to a low power state as soon as the component becomes idle if
the predictor assumes that idle period will last long enough.
System Model
The System Modeled consists of User, deviced with a Queue
User Model
Portable Devices:
Portable Devices have multiple power states.
Hard Disks has 3 Power states:
Active, Idle, Sleep
Smart Bridge has 3 power states:
Active, Idle, Standby
Wireless Card has Active and InActive States
Active States
:
Transmitting and Receiving
InActive States
:
Dose and Off
SMDP Progression
Conclusion:
This Paper Presents Time-Indexed Semi Markov decision Processes for
Optimizing Power Management Policies of Portable Systems.
Simulated and Measured Large Power Saving on 3 different Portable
Devices.
The Measurements of Hard Disk using this approach shows 1.7 times
lower power consumption than compared to Windows timeout policy.
This Policy obtains an average 3 times lower power consumption for the
wireless card relative to the default policy.