Amirhossein Esmaili
Massoud Pedram
Abstract
Imprecise computations allow scheduling algorithms developed for energy-constrained computing devices to trade off output quality with utilization of system resources. The goal of such scheduling algorithms is to utilize imprecise computations to find a feasible schedule for a given task graph while maximizing the quality of service (QoS) and satisfying a hard deadline and an energy bound. This work presents a heuristic for scheduling tasks with potentially imprecise computations, represented with directed acyclic graphs, on multiprocessor platforms. Furthermore, it presents a mixed integer linear program formulation of the same problem, which provides the optimal reference scheduling solutions, enabling evaluation of the efficacy of the proposed heuristic. Both the heuristic and mathematical program take account of potentially imprecise inputs of tasks on their output quality. Furthermore, the presented heuristic is capable of finding feasible schedules even under tight energy budgets. Through extensive experiments, it is shown that in some cases, the proposed heuristic is capable of finding the same QoS as the ones found by MILP. Furthermore, for those task graphs that MILP outperforms the proposed heuristic, QoS values obtained with the proposed heuristic are, on average, within 1.24% of the optimal solutions while improving the runtime by a factor of 100 or so. This clearly demonstrates the advantage of the proposed heuristic over the exact solution, especially for large task graphs where solving the mathematical problem is hampered by its lengthy runtime.
- Heng Yu, Bharadwaj Veeravalli, and Yajun Ha. 2008. Dynamic scheduling of imprecise-computation tasks in maximizing QoS under energy constraints for embedded systems. In Proceedings of the Asia and South Pacific Design Automation Conference. IEEE.Google Scholar
- Jane W. S. Liu, Kwei-Jay Lin, Riccardo Bettati, David Hull, and Albert Yu. 1994. Use of imprecise computation to enhance dependability of real-time systems. In Foundations of Dependable Computing. Springer.Google Scholar
- Lei Mo, Angeliki Kritikakou, and Olivier Sentieys. 2018. Controllable QoS for imprecise computation tasks on DVFS multicores with time and energy constraints. J. Emerg. Select. Topics Circ. Syst. 8, 4 (2018).Google Scholar
- Junlong Zhou, Jianming Yan, Tongquan Wei, Mingsong Chen, and Xiaobo Sharon Hu. 2017. Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in real-time MPSoC systems. In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition. IEEE.Google ScholarCross Ref
- Georgios L. Stavrinides and Helen D. Karatza. 2010. Scheduling multiple task graphs with end-to-end deadlines in distributed real-time systems utilizing imprecise computations. J. Syst. Softw. 83, 6 (2010).Google ScholarDigital Library
- R. C. Ravindran, C. Mani Krishna, Israel Koren, and Zahava Koren. 2014. Scheduling imprecise task graphs for real-time applications. Int. J. Embedd. Syst. 6, 1 (2014).Google Scholar
- W.-K. Shih and Jane W.-S. Liu. 1992. On-line scheduling of imprecise computations to minimize error. In Proceedings of the Real-Time Systems Symposium. IEEE.Google Scholar
- Jane W.-S. Liu, Kwei-Jay Lin, Wei Kuan Shih, Albert Chuang-shi Yu, Jen-Yao Chung, and Wei Zhao. 1991. Algorithms for scheduling imprecise computations. In Foundations of Real-Time Computing: Scheduling and Resource Management. Springer.Google Scholar
- W.-K. Shih, Jane W.-S. Liu, and J.-Y. Chung. 1989. Fast algorithms for scheduling imprecise computations. In Proceedings of the Real-Time Systems Symposium. IEEE.Google ScholarCross Ref
- Lei Mo, Angeliki Kritikakou, and Olivier Sentieys. 2019. Approximation-aware task deployment on asymmetric multicore processors. In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition. IEEE.Google ScholarCross Ref
- Amirhossein Esmaili, Mahdi Nazemi, and Massoud Pedram. 2019. Modeling processor idle times in MPSoC platforms to enable integrated DPM, DVFS, and task scheduling subject to a hard deadline. In Proceedings of the Asia and South Pacific Design Automation Conference. ACM.Google ScholarDigital Library
- Georgios L. Stavrinides, Francisco Rodrigo Duro, Helen D. Karatza, Javier Garcia Blas, and Jesus Carretero. 2017. Different aspects of workflow scheduling in large-scale distributed systems. Simul. Model. Pract. Theor. 70 (2017).Google Scholar
- Waqaas Munawar, Heba Khdr, Santiago Pagani, Muhammad Shafique, Jian-Jia Chen, and Jörg Henkel. 2014. Peak power management for scheduling real-time tasks on heterogeneous many-core systems. In Proceedings of the International Conference on Parallel and Distributed Systems. IEEE.Google ScholarCross Ref
- Luis Alejandro Cortés, Petru Eles, and Zebo Peng. 2006. Quasi-static assignment of voltages and optional cycles in imprecise-computation systems with energy considerations. Trans. Very Large Scale Integ. Syst. 14, 10 (2006).Google Scholar
- Krishnan Srinivasan and Karam S. Chatha. 2007. Integer linear programming and heuristic techniques for system-level low power scheduling on multiprocessor architectures under throughput constraints. Integ. VLSI J. 40, 3 (2007).Google ScholarDigital Library
- Cosmin Rusu, Rami Melhem, and Daniel Mossé. 2003. Maximizing rewards for real-time applications with energy constraints. ACM Trans. Embedd. Comput. Syst. 2, 4 (2003).Google ScholarDigital Library
- Hakan Aydin, Rami Melhem, Daniel Mosse, and Pedro Mejía-Alvarez. 2001. Optimal reward-based scheduling for periodic real-time tasks. IEEE Trans. Comput. 50, 2 (2001).Google ScholarDigital Library
- Jia-Ming Chen, Wan-Chen Lu, Wei-Kuan Shih, and Ming-Chung Tang. 2009. Imprecise computations with deferred optional tasks. J. Inf. Sci. Eng. 25, 1 (2009).Google Scholar
- J.-Y. Chung, Jane W.-S. Liu, and K.-J. Lin. 1990. Scheduling periodic jobs that allow imprecise results. Trans. Comput. 39, 9 (1990).Google ScholarDigital Library
- Wu-chun Feng and J. W.-S. Liu. 1997. Algorithms for scheduling real-time tasks with input error and end-to-end deadlines. Trans. Softw. Eng. 23, 2 (1997).Google Scholar
- David Hull, Arjun Shankar, Klara Nahrstedt, and Jane W. S. Liu. 1997. An end-to-end QoS model and management architecture. In Proceedings of the Workshop on Middleware for Distributed Real-time Systems and Services. Citeseer.Google Scholar
- Georgios L. Stavrinides and Helen D. Karatza. 2012. Scheduling real-time DAGs in heterogeneous clusters by combining imprecise computations and bin packing techniques for the exploitation of schedule holes. Fut. Gen. Comput. Syst. 28, 7 (2012).Google Scholar
- Yongpan Liu, Huazhong Yang, Robert P. Dick, Hui Wang, and Li Shang. 2007. Thermal vs energy optimization for DVFS-enabled processors in embedded systems. In Proceedings of the International Symposium on Quality Electronic Design. IEEE.Google ScholarDigital Library
- Huang Huang, Vivek Chaturvedi, Gang Quan, Jeffrey Fan, and Meikang Qiu. 2014. Throughput maximization for periodic real-time systems under the maximal temperature constraint. Trans. Embedd. Comput. Syst. 13, 2s (2014).Google Scholar
- Marco E. T. Gerards, Johann L. Hurink, and Jan Kuper. 2015. On the interplay between global DVFS and scheduling tasks with precedence constraints. Trans. Comput. 64, 6 (2015).Google Scholar
- Haluk Topcuoglu, Salim Hariri, and Min-you Wu. 2002. Performance-effective and low-complexity task scheduling for heterogeneous computing. Trans. Parallel Distrib. Syst. 13, 3 (2002).Google Scholar
- IBM ILOG CPLEX Optimization Studio, Version 12.8. Retrieved from https://www.ibm.com/products/ilog-cplex-optimization-studio.Google Scholar
- Gang Chen, Kai Huang, and Alois Knoll. 2014. Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM combination. Trans. Embedd. Comput. Syst. 13, 3s (2014).Google Scholar
- Robert P. Dick, David L. Rhodes, and Wayne Wolf. 1998. TGFF: Task graphs for free. In Proceedings of the International Workshop on Hardware/Software Codesign. IEEE.Google ScholarCross Ref
Index Terms
- Energy-aware Scheduling of Task Graphs with Imprecise Computations and End-to-end Deadlines
Recommendations
Scheduling multiple task graphs with end-to-end deadlines in distributed real-time systems utilizing imprecise computations
In order to meet the inherent need of real-time applications for high quality results within strict timing constraints, the employment of effective scheduling techniques is crucial in distributed real-time systems. In this paper, we evaluate by ...
Multi-heuristic list scheduling genetic algorithm for task scheduling
SAC '03: Proceedings of the 2003 ACM symposium on Applied computingScheduling tasks on a multi-processor system involves making a choice as to the order in which several tasks can be executed and assigned to processors. The problem is to find a schedule that will minimize the execution time of a program. Because task ...
Algorithms for end-to-end scheduling to meet deadlines
SPDP '90: Proceedings of the 1990 IEEE Second Symposium on Parallel and Distributed ProcessingIn a multiprocessor or distributed system, jobs may need to be executed on more than one processor. When all the jobs execute on different processors in turn in the same order, the problem of end-to-end scheduling on the processors is known as the flow-...
Comments