ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

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

  • School of Computer Science and Technology, USTC, Hefei 230027, China

  • Suzhou Institution for Advanced Study, USTC, Suzhou 215123, China

Funds:  National Natural Science Foundation of China (61202053), Natural Science Foundation of Jiangsu Province (BK2012194).
Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2014.01.003
More Information
  • Author Bio:

    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

  • Corresponding author: ZHOU Xuehai
  • Received Date: 18 March 2013
  • Accepted Date: 13 April 2013
  • Rev Recd Date: 13 April 2013
  • Publish Date: 30 January 2014
    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.

    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.
    • FullText(HTML)
  • loading
    • References(23)
  • [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.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [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.
    Recommended articles
    TrendMD
    Volume 44 Issue 1 page: 19-33
    Cover

    Article Metrics

    Article views (27) PDF downloads(58)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return