Username   Password       Forgot your password?  Forgot your username? 

Schedulability Analysis and Symbolic Verification Method for Heterogeneous Multicore Real-Time Systems

Volume 13, Number 6, October 2017 - Paper 1  - pp. 785-795
DOI: 10.23940/ijpe.17.06.p1.785795

Wei Wang*, Zhengyu Liao, Dong Guo, Hui Zhang, Chunqi Tian, Jianing Tong

Department of computer science and technology, Tongji University, Shanghai 200092, China

(Submitted on July 25, 2017; Revised on August 30, 2017; Accepted on September 15, 2017)

(This paper was presented at the Third International Symposium on System and Software Reliability.)


As heterogeneous multicore real-time systems are increasingly applied in safety critical systems, it is important to ensure the correctness of these systems. One key attribute of real-time systems is the schedulability that guarantees to satisfy the timing requirements. This paper presents a method for modeling and verifying schedulability of heterogeneous multi-core systems and the method we present uses timed-automata (TA) to model tasks and resources of heterogeneous systems considering their special features. Also this method allows us to establish complex dependences between tasks and use different scheduling policies. After that we choose CPU-GPU heterogeneous multi-core systems as an example and we model three TA networks according to three levels of this system, which are real-time tasks, resources and scheduling management modules. Finally, we use UPPAAL to verify if the model we established satisfies habitudes. According to our method, we present a link between model checking methods and schedulability analysis method for heterogeneous multicore real-time systems and we can automatically and accurately verify the schedulability of selected systems.


References: 13

    1. H. Alan, Q. Y. Meng, B. Martin, “Radiation Modeling Using the Uintah Heterogeneous CPU-GPU Runtime System”, in Proceedings of the 1st Conference of the Extreme Science and Engineering Discovery Environment (XSEDE’12), ACM, 2012.

    2. G. Behrmann, A. David, K. G. Larsen. “A Tutorial on Uppaal[M]//Formal Methods for the Design of Real-Time Systems”, Springer Berlin Heidelberg, 2004.

    3. Sheng-Xin Dai, Mei Hong, Bing Guo, Qiu-Hui Yang, Wei Huang, Bao-Ping Xu, “Schedulability Analysis Model for Multiprocessor Real-Time Systems Using UPPAAL”. Ruan Jian Xue Bao/ Journal of Software, vol. 26, no. 2, pp. 279-296, 2015.

    4. A David, J Illum, KG Larsen, A Skou. “Model-Based Framework for Schedulability Analysis Using UPPAAL 4.1.” in Mosterman PJ, ed. Proc. of the Model-Based Design for Embedded Systems. Boca Raton: CRC Press, 2010.

    5. R. I Davis and A. Burns, “A Survey of Hard Real-Time Scheduling for Multiprocessor Systems”, ACM Computing Surveys, vol. 43, no. 4, pp. 1-44, 2011.

    6. G. Elliott, B Ward, and J Anderson, “GPUSync: A Framework for Real-Time GPU Management”, in Proceedings of the 34th IEEE Real-Time Systems Symposium, December 2013.

    7. E. Fersman, L. Mokrushin, P. Pettersson, Y. Wang. “Schedulability Analysis of Fixed-Priority Systems Using Timed Automata”, Theoretical Computer Science, vol. 354, no. 2, 2006.

    8. R. Gurulingesh, “Real-Time Scheduling on Heterogeneous Multiprocessors”, PhD dissertation, 2014.

    9. W. Jane,S. Liu, “Real-Time Systems”, United States: Pearson Education, 2002.

    10. P. Krcal, M. Stigge, W. Yi. “Multi-Processor Schedulability Analysis of Preemptive Real-Time Tasks with Variable Execution Times,” in Proceedings of the Formal Modeling and Analysis of Timed Systems, Springer-Verlag, 2007.

    11. S. Lui, A. Tarek, et al, “Real Time Scheduling Theory: A Historical Perspective,” Journal of Real Time Systems, vol. 28, no. 2-3, pp. 101-155, 2004.

    12. K. Shinpei, L. Karthik, et al, “TimeGraph: GPU Scheduling for Real-Time Multi-Tasking Environments,” in Proceedings of the 2011 USENIX conference on USENIX annual technical conference, 2011.

    13. W. Wang, G. Dong, G. S. Zeng, et al, “Reachability Analysis of Cost-Reward Timed Automata for Energy Efficiency Scheduling,” in Proceedings of Programming Models and Applications on Multicores and Manycores (PMAM'14), ACM, 2014.


      Click here to download the paper.

      Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

      This site uses encryption for transmitting your passwords.