Consistency in dataflow graphs

Abstract

This paper describes an analytical model for the behavior of dataflow graphs with data-dependent control flow. The number of tokens produced or consumed by each actor is given as a symbolic function of the Booleans in the system. Long term averages can be analyzed to determine consistency of token flow rates, which in turn determines whether memory requirements are bounded. Short-term behavior can be analyzed to construct an annotated schedule, or a static schedule that annotates each firing of an actor with the Boolean conditions under which that firing occurs. Annotated schedules can be used to generate efficient implementations of the algorithms given by the dataflow graphs.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>