Checking for Circular Dependencies in Distributed Stream Programs

Abstract

This work presents a cyclic dependency analysis for streambased 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 29, 2011
Accession Number
ADA548741

Entities

People

  • Dai Bui
  • Edward A. Lee
  • Hiren Patel

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Compilers
  • Computational Science
  • Computations
  • Computer Programming
  • Computer Science
  • Debugging
  • Digital Signal Processing
  • Electrical Engineering
  • Engineering
  • Image Processing
  • Language
  • Linear Programming
  • Military Research
  • Scheduling (Production)
  • Signal Processing

Fields of Study

  • Computer science

Readers

  • Distributed Systems and Data Platform Development
  • Materials Science.