*banner
 

A Causality Interface for Deadlock Analysis in Dataflow
Ye Zhou, Edward A. Lee

Citation
Ye Zhou, Edward A. Lee. "A Causality Interface for Deadlock Analysis in Dataflow". Proceedings of the Sixth ACM International Conference on Embedded Software (EMSOFT’06), Sang Lyul Min, Wang Yi (eds.), ACM, 44-52, October, 2006.

Abstract
In this paper, we consider a concurrent model of computation called dataflow, where components (actors) communicate via streams of data tokens. Dataflow semantics has been adopted by experimental and production languages used to design embedded systems. The execution of a data-flow actor is enabled by the availability of its input data. One important question is whether a dataflow model will deadlock (i.e., actors cannot execute due to a data dependency loop). Deadlock in many cases can be determined, although it is generally not decidable. We develop a causality interface for dataflow actors based on the general framework we introduced in [1] and show how this causality information can be algebraically composed so that composition of components acquire causality interfaces that are inferred from their components and the interconnections. We illustrate the use of these causality interfaces to statically analyze for deadlock.

Electronic downloads


Internal. This publication has been marked by the author for Chess-only distribution, so electronic downloads are not available without logging in.
Citation formats  
  • HTML
    Ye Zhou, Edward A. Lee. <a
    href="http://chess.eecs.berkeley.edu/pubs/72.html"
    >A Causality Interface for Deadlock Analysis in
    Dataflow</a>, Proceedings of the Sixth ACM
    International Conference on Embedded Software
    (EMSOFT’06), Sang Lyul Min, Wang Yi (eds.), ACM,
    44-52, October, 2006.
  • Plain text
    Ye Zhou, Edward A. Lee. "A Causality Interface for
    Deadlock Analysis in Dataflow". Proceedings of the
    Sixth ACM International Conference on Embedded Software
    (EMSOFT’06), Sang Lyul Min, Wang Yi (eds.), ACM,
    44-52, October, 2006.
  • BibTeX
    @inproceedings{ZhouLee06_CausalityInterfaceForDeadlockAnalysisInDataflow,
        author = {Ye Zhou and Edward A. Lee},
        title = {A Causality Interface for Deadlock Analysis in
                  Dataflow},
        booktitle = {Proceedings of the Sixth ACM International
                  Conference on Embedded Software (EMSOFT’06)},
        editor = {Sang Lyul Min, Wang Yi},
        organization = {ACM},
        pages = {44-52},
        month = {October},
        year = {2006},
        abstract = {In this paper, we consider a concurrent model of
                  computation called dataflow, where components
                  (actors) communicate via streams of data tokens.
                  Dataflow semantics has been adopted by
                  experimental and production languages used to
                  design embedded systems. The execution of a
                  data-flow actor is enabled by the availability of
                  its input data. One important question is whether
                  a dataflow model will deadlock (i.e., actors
                  cannot execute due to a data dependency loop).
                  Deadlock in many cases can be determined, although
                  it is generally not decidable. We develop a
                  causality interface for dataflow actors based on
                  the general framework we introduced in [1] and
                  show how this causality information can be
                  algebraically composed so that composition of
                  components acquire causality interfaces that are
                  inferred from their components and the
                  interconnections. We illustrate the use of these
                  causality interfaces to statically analyze for
                  deadlock.},
        URL = {http://chess.eecs.berkeley.edu/pubs/72.html}
    }
    

Posted by Ye Zhou on 9 May 2006.
Groups: chess chesslocal ptolemy
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess