This work presents a cyclic dependency analysis for stream-based programs. Specifically, we focus on the cyclo-static dataflow (CSDF) programming model with control messages through teleport messaging as implemented in the StreamIt framework. Unlike existing cyclic dependency analyses, we allow overlapped teleport messages. An overlapped teleport message is one that traverses actors that themselves transmit teleport messages, which can complicate the stream graph topology with teleport messages. Therefore, the challenge in this work is to decide whether such stream graphs are feasible in the presence of such complex teleport messages. Our analysis addresses this challenge by first ensuring that the stream graph with teleport messages is feasible, and then computing an execution schedule for the CSDF graph in the presence of complex overlapped teleport messaging constraints. Consequently, our analysis accepts a larger class of CSDF stream graphs with complex teleport messaging topologies for execution.
Title
Checking for Circular Dependencies in Distributed Stream Programs
Published
2011-08-29
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
EECS-2011-97
Type
Text
Extent
12 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
