A colored Petri net based scheduling scheme  for multiprocessor system-on-chip

doi:10.3969/j.issn.0253-2778.2014.01.003

Journal of University of Science and Technology of China ›› 2014, Vol. 44 ›› Issue (1): 19-33.DOI: 10.3969/j.issn.0253-2778.2014.01.003

• Original Paper • Previous Articles

A colored Petri net based scheduling scheme for multiprocessor system-on-chip

FENG Xiaojing, LI Xi, WANG Chao, CHEN Peng, ZHOU Xuehai

School of Computer Science and Technology, USTC, Hefei 230027, China; Suzhou Institution for Advanced Study, USTC, Suzhou 215123, China

Received:2013-03-18 Revised:2013-04-13 Accepted:2013-04-13 Online:2013-04-13 Published:2013-04-13
Contact: ZHOU Xuehai
About author:FENG Xiaojing, Male, born in 1984, PhD candidate. His research interests include reconfigurable computing technology, multiprocessor systems and formal verification. E-mail: bangyan@mail.ustc.edu.cn
Supported by:
National Natural Science Foundation of China (61202053), Natural Science Foundation of Jiangsu Province (BK2012194).

Abstract

Abstract: A novel colored Petri net (CPN) based dynamic scheduling scheme was proposed, which aimed at generating a hardware scheduler for multiprocessor system-on-chip (MPSoC) platforms. CPN was employed to model inter-task dependences in the proposed scheduling scheme, including RAW, WAW and WAR data dependences, as well as structural dependences. All the dependences can be automatically detected during model execution. Tasks can be then scheduled and dispatched to different processors for out-of-order execution according to the dependences, achieving the goal of improving task-level parallelism. The scheduling scheme is implemented both with software simulation tools and on an FPGA-based hardware platform. Through state space analyses and comparing experiments, the correctness and effectiveness of the scheduling scheme are demonstrated.

Key words: colored Petri nets, task scheduling, multiprocessor system-on-chip (MPSoC), model based design

CLC Number:

TP301.

FENG Xiaojing, LI Xi, WANG Chao, CHEN Peng, ZHOU Xuehai. A colored Petri net based scheduling scheme for multiprocessor system-on-chip[J]. Journal of University of Science and Technology of China, 2014, 44(1): 19-33.

References

［1］ Kumar, Hughes C J, Nguyen A. Carbon: Architectural support for fine-grained parallelism on chip multiprocessors［C］// Proceedings of the 34th Annual International Symposium on Computer Architecture. San Diego, USA: ACM Press, 2007: 162-173.
［2］ Sanchez D, Yoo R M, Kozyrakis C. Flexible architectural support for fine-grain scheduling［C］// Proceedings of the 15th Edition of ASPLOS on Architectural Support for Programming Languages and Operating Systems. Pittsburgh, USA: ACM Press, 2010: 311-322.
［3］ Etsion Y, Cabarcas F, Rico A, et al. Task superscalar: An out-of-order task pipeline［C］// Proceedings of the 43rd Annual IEEE/ACM International Symposium on Microarchitecture. Atlanta, USA: IEEE Computer Society, 2010: 89-100.
［4］ Wang C, Zhang J N, Zhou X H, et al. SOMP: Service-oriented multi processors［C］// Proceedings of the IEEE International Conference on Services Computing. Washington, USA: IEEE Computer Society, 2011: 709-716.
［5］ Alur R, Dill D L. A theory of timed automata［J］. Theoretical Computer Science, 1994, 126(2): 183-235.
［6］ Alur R, La Torre S, Pappas G J. Optimal paths in weighted timed automata［J］. Theoretical Computer Science, 2004, 318(3): 297-322.
［7］ Behrmann G, Fehnker A, Hune T, et al. Minimum-cost reachability for priced timed automata［C］// Proceedings of the 4th International Workshop on Hybrid Systems: Computation and Control. Rome, Italy: Springer-Verlag, 2001: 147-161.
［8］ Abdeddam Y, Kerbaa A, Maler O. Task graph scheduling using timed automata［C］// Proceedings of the 17th International Symposium on Parallel and Distributed Processing. Washington, USA: IEEE Computy Society, 2003: 237.2(1-8).
［9］ Behrmann G, Larsen K G, Rasmussen J I. Optimal scheduling using priced timed automata［J］. ACM SIGMETRICS Performance Evaluation Review, 2005, 32(4): 34-40.
［10］ Srba J. Comparing the expressiveness of timed automata and timed extensions of petri nets［C］// Proceedings of the 6th International Conference on Formal Modeling and Analysis of Timed Systemss. Saint Malo, France: Springer-Verlag, 2008: 15-32.
［11］ Murata T. Petri nets: Properties, analysis and applications［J］. Proceedings of the IEEE, 1989, 77(4): 541-580.
［12］ Jensen K. Coloured Petri nets［A］// Petri Nets: Central Models and Their Properties, Lecture Notes in Computer Science. Springer, 1987, 254: 248-299.
［13］ Zuberek W M, Govindarajan R, Suciu F. Timed colored Petri net models of distributed memory multithreaded multiprocessors［C］// Proceedings of the Workshop on Practical Use of Colored Petri Nets and Design. Aarhus,Denmark, 1998: 253-270.
［14］ Azgomi M A, Entezari-Maleki R. Task scheduling modelling and reliability evaluation of grid services using coloured Petri nets［J］. Future Generation Computer Systems, 2010, 26(8): 1 141-1 150.
［15］ Blej M, Azizi M. Modeling and analysis of a real-time system using the networks of extended Petri［J］. Journal of Computers, 2009, 4(7): 641-645.
［16］ Madhukar M, Leuze M, Dowdy L. Petri net model of a dynamically partitioned multiprocessor system［C］// Proceedings of the 6th International Workshop on Petri Nets and Performance Models. Durham, UK: IEEE Computer Society, 1995: 73-82.
［17］ Tavares E, Oliveira Jr M, Maciel B, et al. Pre-runtime scheduling considering timing and energy constraints in embedded systems with multiple processors［C］// IFIP working Conference on Model-Driven Design to Resource Management for Distributed Embedded Systems. Braga, Portugal: Springer, 2006: 255-264.
［18］ Barreto R, Maciel P, Neves M, et al. A novel approach for off-line multiprocessor scheduling in embedded hard real-time systems［C］// FIP working Conference on Design Methods and Applications for Distributed Embedded Systems. Toulouse, France: Springer, 2004: 157-166.
［19］ Neubauer F, Hoheisel A, Geiler J. Workflow-based Grid applications［J］. Future Generation Computer Systems, 2006, 22(1-2): 6-15.
［20］ Hoheisel A, Der U. Dynamic workflows for grid applications［C］// Proceedings of the 3rd Cracow Grid Workshop. Krakau, Polen, 2003(http://www.andreas-hoheisel.de/).
［21］ Eskinazi R, de Lima M E, Maciel P R M, et al. A timed Petri net approach for pre-runtime scheduling in partial and dynamic reconfigurable systems［C］// Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium. Denver, USA: IEEE Computer Society, 2005: 330-337.
［22］ Jensen K. An introduction to the theoretical aspects of coloured Petri nets［A］// A Decade of Concurrency Reflections and Perspectives, Lecture Notes in Computer Science. Springer, 1994, 803: 230-272.
［23］ Wang C, Li X, Chen P, et al. Detecting data hazards in multi-processor system-on-chips on FPGA［C］// Proceedings of the 26th Parallel and Distributed Processing Symposium Workshops & PhD Forum. Shanghai, China: IEEE Press, 2012: 282-287.

[1]	CHEN Feng, ZHANG Zhi, LI Qinjian, CHEN Yuqiang, CHEN Guoliang. Dynamic task scheduling algorithm of parallel computing for FCD big data [J]. Journal of University of Science and Technology of China, 2018, 48(9): 718-722.
[2]	ZHANG Xu, GU Naijie, SU Junjie,. A real-time multi-task scheduling framework in Linux user space [J]. Journal of University of Science and Technology of China, 2017, 47(8): 635-643.
[3]	TANG Jiufei,LI He,YU Junqing. Research on stream program task scheduling and cache optimization for X86 multi-core processor [J]. Journal of University of Science and Technology of China, 2016, 46(3): 200-207.

A colored Petri net based scheduling scheme for multiprocessor system-on-chip

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments