Task Dependence in Scheduling and Load Balancing在调度和负载平衡任务依赖.pptVIP

Task Dependence in Scheduling and Load Balancing Prof. Adam Meyerson UCLA Relating Energy to Speed Typical relationship E = s2. Derived from physics. Assumed in many papers… Two “meanings” for speed. CPU operations per time unit Rate at which tasks complete Task Completion Rates In a simple experiment, we ran two different programs which fill a large array. Task-Dependent Scheduling Given a set of tasks and completion rates at various CPU speeds… Schedule tasks to optimize QoS (i.e. minimize weighted flow time, observe deadlines, maximize value) while minimizing energy. Energy Effect of Parallel Tasks Some observations based on LEAP… Running two cores costs less than twice the energy of running one core. Energy savings from running parallel tasks varies. Depends on use of shared resources (memory etc) Some pairs take more energy in parallel (basically one core will be idle, waiting for shared resource). Task-Dependent Load Balancing Task-Dependent Load Balancing Given: A set of tasks T, each with a duration A number of cores c. Energy/time E(S) for each S?T with |S|≤c. We must allocate tasks to (core, timestep) such that each task is allocated to a single core and to a number of timesteps equal to its duration. Minimize ∑tE(St) where St are active tasks at t. * 6.5146 sec [1.00] 4.1386 sec [1.58] Random Order 4.7595 sec [1.00] 2.6287 sec [1.81] Linear Order 0.98 GHz [1.00] 1.83 GHz [1.87] Thanos Stathopoulos, Dustin McIntire, William J. Kaiser. The Energy Endoscope: Real-Time Detailed Energy Accounting for Wireless Sensor Nodes. Proceedings of the 7th International Conference on Information Processing in Sensor Networks (IPSN 2008) Core 1 Core 2 Task 1 Task 2 Task 3 In prior work, energy determined by total time of activity, plus activation costs. Perhaps better to consider instantaneous energy consumption which depends on the set of active tasks in a non-trivial way. * * *