Real Time Global Scheduling Analysis for Generalized DAG Task Upon Heterogeneous Machine

Authors

  • Adhe Widianjaya EEPIS Robotics Research Center, Electronic Engineering Polytechnic Institute of Surabaya, Surabaya, Indonesia.
  • Dadet Pramadihanto EEPIS Robotics Research Center, Electronic Engineering Polytechnic Institute of Surabaya, Surabaya, Indonesia.
  • Sritrusta Sukaridhoto EEPIS Robotics Research Center, Electronic Engineering Polytechnic Institute of Surabaya, Surabaya, Indonesia.

Keywords:

Real Time Scheduling, Capacity Augmentation Bound, Heterogeneous Processor, Unrelated Parallel Machine, Parallel Tasks, Directed Acyclic Graph,

Abstract

This paper presents a heterogeneous model of real time task system with novel processing rate work parameter. The model considers the precedence constraint with implicit deadline. Global EDF scheduling algorithm was applied on this model and analyzed in the context of its schedulability and capacity augmentation bound. By combining parallel tasks analysis upon identical multiprocessor and their processing rate upon heterogeneous system, we derived utilization augmentation, which is useful for extending capacity augmentation bound. Our experiments showed that there was a schedulable task system which is characterized by utilization augmentation upon heterogeneous system under Global EDF with capacity augmentation bound of (4-m/2)(1+√(U_Aug)). Our model with processing rate is also useful for practical consideration.

References

Fisher, N., Goossens, J., and Baruah, S. Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible. Real-Time Systems, 45, 1 (2010), pp. 26–71.

Lopez J. M., Diaz J. L., Garcia D. F. Utilization bounds for EDF scheduling on real-time multiprocessor systems. Real-Time Systems, 28, 1 (2004), pp. 39-68.

Liu, C. L., and Layland, J.W. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 20, 1 (1973), pp. 46-61.

Kato, S. Yamasaki, N., Ishikawa, Y. Semi-Partitioned Scheduling of Sporadic Task Systems on Multiprocessors. Proceedings of 21st Euromicro Conference on Real-Time Systems (2009), pp. 249-258.

Bastoni, A., Bjorn, B., Anderson, J. Is Semi-Partitioned Scheduling Practical?. Proceedings of 23rd Euromicro Conference on Real-Time Systems (2011), pp. 125-135.

Baruah, S., Bertogna, M., Butazzo, G. Multiprocessors Scheduling for Real Time Systems. Springer International Publishing. (2015).

Bonifaci V., et. al. Feasibility Analysis in the Sporadic DAG Task Model. Proceedings of 25rd Euromicro Conference on Real-Time Systems (2013), pp. 225-233.

Li J., Agrawal K., Lu C., and Gill C., Analysis of Global EDF for Parallel Task. Proceedings of 23th Euromicro Conference on RealTime Systems (2013), pp. 3-13.

Raravi G., Andersson B., Bletsas K., and Nelis V., Task Assignment Algorithm for Two-Type Heterogeneous Multiprocessors. Real Time Systems, vol. 50, Issue 1 (2014), pp. 87-141.

Lawler E.L., Labeteoulle J., On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming. Journal of the ACM, 25, (1978), page no. 612-619.

Sviridenko M., and Wiese A., Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines. Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO 2013), pp. 387-398.

Cordeiro, D., et. al. Random graph generation for scheduling simulations, Proceedings of he 3rd International ICST Conference on Simulation Tools and Techniques (2010).

“ARM big.LITTLE”. https://en.wikipedia.org/wiki/ARM_ big.LITTLE. Accessed on July 1st, 2016.

“i.MX”. https://en.wikipedia.org/wiki/I.MX. Accessed on July 1st, 2016.

Downloads

Published

2017-06-01

How to Cite

Widianjaya, A., Pramadihanto, D., & Sukaridhoto, S. (2017). Real Time Global Scheduling Analysis for Generalized DAG Task Upon Heterogeneous Machine. Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 9(2-5), 113–117. Retrieved from https://jtec.utem.edu.my/jtec/article/view/2409