Name
Title | ||
|---|---|---|
Scheduling parallel tasks on multiprocessor computers with efficient power management |
Abstract | ||
|---|---|---|
In this paper, scheduling parallel tasks on multiprocessor computers with dynamically variable voltage and speed is addressed as combinatorial optimization problems. Our scheduling problems are defined such that the energy-delay product is optimized by fixing one factor and minimizing the other. It is noticed that power-aware scheduling of parallel tasks has rarely been discussed before. Our investigation in this paper makes some initial attempt to energy efficient scheduling of parallel tasks on multiprocessor computers with dynamic voltage and speed. Our scheduling problems contain three nontrivial subproblems, namely, system partitioning, task scheduling, and power supplying. The harmonic system partitioning and processor allocation scheme is used, which divides a multiprocessor computer into clusters of equal sizes and schedules tasks of similar sizes together to increase processor utilization. A three-level energy/time/power allocation scheme is adopted for a given schedule, such that the schedule length is minimized by consuming given amount of energy or the energy consumed is minimized without missing a given deadline. The performance of our heuristic algorithms is analyzed and accurate performance bounds are derived. Simulation data which validate our analytical results are also presented. It is found that our analytical results provide very accurate estimation of the expected normalized schedule length and the expected normalized energy consumption, and that our heuristic algorithms are able to produce solutions very close to optimum. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/IPDPSW.2010.5470912 | IPDPS Workshops |
Keywords | Field | DocType |
parallel processing,power management,power aware computing,scheduling,power-aware scheduling,harmonic system partitioning,parallel task,power supplying,multiprocessing systems,system partitioning,simulation,parallel task scheduling,energy consumption,multiprocessor computer,list scheduling,energy-time-power allocation scheme,processor allocation scheme,performance analysis,task scheduling,power aware scheduling,algorithm design and analysis,heuristic algorithm,voltage,dynamic scheduling,energy management,energy efficiency,scheduling algorithm,scheduling problem,schedules,concurrent computing,energy efficient,resource management | Fixed-priority pre-emptive scheduling,Multiprocessor scheduling,Fair-share scheduling,Computer science,Parallel computing,Two-level scheduling,Schedule,Rate-monotonic scheduling,Dynamic priority scheduling,Round-robin scheduling | Conference |
ISBN | Citations | PageRank |
978-1-4244-6533-0 | 1 | 0.37 |
References | Authors | |
0 | 1 | |