Chin-Fu Kuo
Skip Abstract Section
Abstract
Currently, the multiprocessor architecture platform becomes more and more popular to the applications with higher computational capacity for meeting the fast-grown demand of applications and increasing the performance of whole system. Managing the consumption of resources has become an important issue in many different settings. The energyefficient scheduling for multiprocessors becomes one of important research issues. In this paper we study the scheduling problem of a heterogeneous non-DVSmultiprocessor platform with a task set. The processors have different characteristics of power consumption. We propose an off-line taskto- processor assignment algorithm, the Best-Fit Decreasing Physical Power Consumption (BDPC) algorithm to derive a feasible task assignment with the minimal energy consumption and has the time complexity of O(N(logN + M)), where N and M are the numbers of tasks and processor types, respectively. A series of experiments were conducted to evaluate the proposed algorithm. The experimental results demonstrate that the performance of the proposed BDPC algorithm is better than the compared algorithms.
- MPC8536E PowerQUICC III Integrated Processor Hardware Specifications. http://cache.freescale.com/files/32bit/doc/data_sheet/MPC8536EEC.pdf, Sep. 2011.Google Scholar
- M. Awan and S. Petters. Energy-aware partitioning of tasks onto a heterogeneous multi-core platform. In IEEE 19th Real-Time and Embedded Technology and Applications Symposium, pages 205--214, 2013. Google ScholarDigital Library
- H. Aydin, V. Devadas, and D. Zhu. System-level energy management for periodic real-time tasks. In Real-Time Systems Symposium, 2006. RTSS '06. 27th IEEE International, pages 313--322, Dec 2006. Google ScholarDigital Library
- H. Aydin and Q. Yang. Energy-aware partitioning for multiprocessor real-time systems. In International Parallel and Distributed Processing Symposium, 2003. Google ScholarDigital Library
- R. A. Carrasco. Resource Cost Aware Scheduling Problems. PhD thesis, Columbia University, 2013.Google Scholar
- J.-J. Chen, H.-R. Hsu, and T.-W. Kuo. Leakage-aware energy-efficient scheduling of real-time tasks in multiprocessor systems. In IEEE Real-time and Embedded Technology and Applications Symposium, pages 408--417, 2006. Google ScholarDigital Library
- J.-J. Chen and C.-F. Kuo. Energy-efficient scheduling for real-time systems on dynamic voltage scaling (DVS) platforms. In IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pages 28--38, 2007. Google ScholarDigital Library
- H. Cheng and S. Goddard. Online energy-aware I/O device scheduling for hard real-time systems. In Proceedings of the Conference on Design, Automation and Test in Europe: Proceedings, DATE '06, pages 1055--1060, 3001 Leuven, Belgium, Belgium, 2006. European Design and Automation Association. Google ScholarDigital Library
- A. Colin, A. Kandhalu, and R. Rajkumar. Energy-efficient allocation of real-time applications onto heterogeneous processors. In Embedded and Real-Time Computing Systems and Applications (RTCSA), 2014 IEEE 20th International Conference on, pages 1--10, Aug 2014.Google ScholarCross Ref
- R. I. Davis and A. Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35:1--35:44, Oct. 2011. Google ScholarDigital Library
- C. Ellis. The case for higher-level power management. In Workshop on Hot Topics in Operating Systems, pages 162--167, 1999. Google ScholarDigital Library
- K. Funaoka, S. Kato, and N. Yamasaki. Energy-efficient optimal real-time scheduling on multiprocessors. In the 11th IEEE International Symposium on Object Oriented Real-Time Distributed Computing, pages 23--30, 2008. Google ScholarDigital Library
- F. Gruian. System-level design methods for low-energy architectures containing variable voltage processors. In Power-Aware Computing Systems, pages 1--12, 2000. Google ScholarDigital Library
- C.-M. Hung, J.-J. Chen, and T.-W. Kuo. Energy-efficient real-time task scheduling for a DVS system with a non-DVS processing element. In the 27th IEEE Real-Time Systems Symposium, pages 303--312, 2006. Google ScholarDigital Library
- S.-Y. Jing, S. Ali, K. She, and Y. Zhong. State-of-the-art research study for green cloud computing. The Journal of Supercomputing, 65(1):445--468, 2013. Google ScholarDigital Library
- A. Kandhalu, J. Kim, K. Lakshmanan, and R. Rajkumar. Energy-aware partitioned fixed-priority scheduling for chip multi-processors. In 2011 IEEE 17th International Conference on Embedded and Real-Time Computing Systems and Applications, pages 93--102, August 2011. Google ScholarDigital Library
- K. H. Kim, A. Beloglazov, and R. Buyya. Power-aware provisioning of cloud resources for real-time services. In Proceedings of the 7th International Workshop on Middleware for Grids, Clouds and e-Science, MGC '09, pages 1:1--1:6, New York, NY, USA, 2009. ACM. Google ScholarDigital Library
- C.-F. Kuo, L.-C. Chien, and Y.-F. Lu. Scheduling algorithm with energy-response trade-off considerations for mixed task sets. In Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS '13, pages 410--415, New York, NY, USA, 2013. ACM. Google ScholarDigital Library
- T.-W. Kuo, Y.-T. Kao, and C.-F. Kuo. Two-version based concurrency control and recovery in real-time client/server databases. Computers, IEEE Transactions on, 52(4):506--524, 2003. Google ScholarDigital Library
- C.-F. Liao, Y.-F. Lu, A.-C. Pang, and T.-W. Kuo. A secure routing protocol for wireless embedded networks. In Embedded and Real-Time Computing Systems and Applications, 2008. RTCSA '08. 14th IEEE International Conference on, pages 421--426, Aug 2008. Google ScholarDigital Library
- C. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 20(1):46--61, January 1973. Google ScholarDigital Library
- Y.-F. Lu, C.-F. Kuo, and A.-C. Pang. A novel key management scheme for wireless embedded systems. SIGAPP Appl. Comput. Rev., 12(1):50--59, Apr. 2012. Google ScholarDigital Library
- Y.-F. Lu, J. Wu, and C.-F. Kuo. A path generation scheme for real-time green internet of things. SIGAPP Appl. Comput. Rev., 14(2):45--58, June 2014. Google ScholarDigital Library
- J. L. March, J. Sahuquillo, S. Petit, H. Hassan, and J. Duato. Power-aware scheduling with effective task migration for real-time multicore embedded systems. Concurrency and Computation: Practice and Experience, 25(14):1987--2001, 2013.Google ScholarCross Ref
- G. Moreno and D. Niz. An optimal real-time voltage and frequency scaling for uniform multiprocessors. In the 18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pages 21--30, 2012. Google ScholarDigital Library
- G. Qu. What is the limit of energy saving by dynamic voltage scaling? In Computer Aided Design, 2001. ICCAD 2001. IEEE/ACM International Conference on, pages 560--563, Nov 2001. Google ScholarDigital Library
- R. Roycki and J. Wglarz. Solving a power-aware scheduling problem by grouping jobs with the same processing characteristic. Discrete Applied Mathematics, (0):--, 2013.Google Scholar
- Y.-I. Seol, J.-U. Kim, and Y.-K. Kim. A power-aware scheduler exploiting all slacks under edf scheduling. In H. Y. Jeong, M. S. Obaidat, N. Y. Yen, and J. J. J. H. Park, editors, Advances in Computer Science and its Applications, volume 279 of Lecture Notes in Electrical Engineering, pages 51--57. Springer Berlin Heidelberg, 2014.Google Scholar
- H.-W. Tseng, A.-C. Pang, J. Chen, and C.-F. Kuo. An adaptive contention control strategy for IEEE 802.15. 4-based wireless sensor networks. Vehicular Technology, IEEE Transactions on, 58(9):5164--5173, 2009.Google Scholar
- P.-H. Tseng, P.-C. Hsiu, C.-C. Pan, and T.-W. Kuo. User-centric energy-efficient scheduling on multi-core mobile devices. In Proceedings of the The 51st Annual Design Automation Conference on Design Automation Conference, pages 1--6. ACM, 2014. Google ScholarDigital Library
- J. Wu and K.-L. Ke. Energy-efficient real-time scheduling of tasks with abortable critical sections. Journal of Information Science and Engineering, 30:765--786, 2014.Google Scholar
- J. Wu, H.-C. Lin, and Y.-F. Lu. Lightweight distributed topology control algorithms for heterogeneous wireless sensor networks. In Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA '07, pages 347--354, Washington, DC, USA, 2007. IEEE Computer Society. Google ScholarDigital Library
- C. Xian, Y.-H. Lu, and Z. Li. Energy-aware scheduling for real-time multiprocessor systems with uncertain task execution time. In the 44th ACM/IEEE Design Automation Conference, pages 664--669, 2007. Google ScholarDigital Library
- C.-Y. Yang, J.-J. Chen, and T.-W. Kuo. An approximation algorithm for energy-efficient scheduling on a chip multiprocessor. In DATE 2005, pages 468--473, 2005. Google ScholarDigital Library
- X. Zhong and C.-Z. Xu. Energy-aware modeling and scheduling for dynamic voltage scaling with statistical real-time guarantee. Computers, IEEE Transactions on, 56(3):358--372, March 2007. Google ScholarDigital Library
Index Terms
- Task assignment with energy efficiency considerations for non-DVS heterogeneous multiprocessor systems
Recommendations
Energy-efficient assignment for tasks on non-dvs heterogeneous multiprocessor system
RACS '14: Proceedings of the 2014 Conference on Research in Adaptive and Convergent SystemsThis paper aims to study the scheduling problem of a heterogeneous non-DVS multiprocessor platform with a task set. The processors have different characteristics of power consumption. We propose an off-line task-to-processor assignment algorithm, the ...
Energy-efficient dynamic task scheduling algorithms for DVS systems
Dynamic voltage scaling (DVS) is a well-known low-power design technique that reduces the processor energy by slowing down the DVS processor and stretching the task execution time. However, in a DVS system consisting of a DVS processor and multiple ...
An Energy-Efficient Scheduling Algorithm for Sporadic Real-Time Tasks in Multiprocessor Systems
HPCC '11: Proceedings of the 2011 IEEE International Conference on High Performance Computing and CommunicationsAs the energy consumption of embedded multiprocessor systems becomes increasingly prominent, the real-time energy-efficient scheduling in multiprocessor systems becomes an urgent problem to reduce the system energy consumption while meeting real-time ...
Comments