基于有色Petri网的多处理器片上系统调度方法

doi:10.3969/j.issn.0253-2778.2014.01.003

中国科学技术大学学报 ›› 2014, Vol. 44 ›› Issue (1): 19-33.DOI: 10.3969/j.issn.0253-2778.2014.01.003

• 论著 • 上一篇

基于有色Petri网的多处理器片上系统调度方法

冯晓静，李曦，王超，陈鹏，周学海

中国科学技术大学计算机科学与技术学院，安徽合肥 230027; 中国科学技术大学苏州研究院，苏州 215123

收稿日期:2013-03-18 修回日期:2013-04-13 接受日期:2013-04-13 出版日期:2013-04-13 发布日期:2013-04-13

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

摘要： 为了生成一个适用于多处理器片上系统的硬件调度器，提出一种新型的基于有色Petri网（CPN）的动态调度方法.该调度方法使用CPN对包括写后读、写后写、读后写数据相关以及结构相关在内的任务间相关性进行了建模，这些相关会在模型运行的过程中被自动检测出来.根据相关性，任务会被动态地调度并分配到不同的计算单元上乱序执行，从而达到提高任务级并行度的目的.该调度方法分别在软件仿真平台和基于FPGA的硬件平台上得以实现.状态空间分析和对比实验的结果证明了调度方法的正确性和有效性.

关键词: 有色Petri网, 任务调度, 多处理器片上系统, 基于模型的设计方法

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

中图分类号:

TP301.

冯晓静，李曦，王超，陈鹏，周学海. 基于有色Petri网的多处理器片上系统调度方法[J]. 中国科学技术大学学报, 2014, 44(1): 19-33.

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.

参考文献

［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]	陈锋，张智，李琴剑，陈宇强，陈国良. FCD大数据并行处理的动态任务调度算法[J]. 中国科学技术大学学报, 2018, 48(9): 718-722.
[2]	张旭，顾乃杰，苏俊杰，. 一种Linux用户态实时多任务调度框架[J]. 中国科学技术大学学报, 2017, 47(8): 635-643.
[3]	唐九飞，李鹤，于俊清. 面向X86多核处理器的数据流程序任务调度与缓存优化[J]. 中国科学技术大学学报, 2016, 46(3): 200-207.

基于有色Petri网的多处理器片上系统调度方法

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价