Ye Zhou and Edward A. Lee

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-51

May 12, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-51.pdf

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 dataflow 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.

---

BibTeX citation:

@techreport{Zhou:EECS-2006-51,
    Author= {Zhou, Ye and Lee, Edward A.},
    Title= {A Causality Interface for Deadlock Analysis in Dataflow},
    Year= {2006},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-51.html},
    Number= {UCB/EECS-2006-51},
    Note= {The <a href="http://ptolemy.eecs.berkeley.edu/publications/papers/06/causalityInterfaces_EMSOFT06/CausalityInterfaces_EMSOFTpaper_ZHOU.pdf"> published version</a> is also available.},
    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 dataflow 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.},
}

EndNote citation:

%0 Report
%A Zhou, Ye 
%A Lee, Edward A. 
%T A Causality Interface for Deadlock Analysis in Dataflow
%I EECS Department, University of California, Berkeley
%D 2006
%8 May 12
%@ UCB/EECS-2006-51
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-51.html
%F Zhou:EECS-2006-51